Смотрю картинку про хэш‑таблицу и вижу такое слово: buckets. Посоветуйте что это такое и для чего?
-
1стоит добавить в вопрос картинку, которую ты смотришь – Grundy♦ 3 июн '19 в 10:35
-
@Grundy сейчас добавлю – Mike Mclaren 3 июн '19 в 10:38
-
1это переводится как "корзины" =), по вопросу - по сути это отдельная ячейка хеш таблицы, внутри которой элементы уже лежат как упорядоченный список – Stranger in the Q 3 июн '19 в 10:41
-
@StrangerintheQ То есть там в лежат имена и фамилии в алфавитном порядке? Ну раз упорядоченный? – Mike Mclaren 3 июн '19 в 10:48
-
в hashmap - в порядке добавления, насколько я помню – Stranger in the Q 3 июн '19 в 10:49
1 ответ
Бакетом (англ. bucket — ведро) называют набор элементов хеш‑таблицы с совпадающими/близкими значением хеш‑функции.
Хеш‑функция может принимать большой диапазон значений. Из-за технических ограничений (например, при необходимости экономии памяти) внутренний массив хеш‑таблицы может содержать меньшее количество элементов. Тогда элементы с близкими значениями хеша попадут в одну ячейку.
Ситуацию когда у двух элементов, добавленных в хеш‑таблицу совпадают значение хеша называют коллизией. При этом оба элемента попадают в одну ячейку (корзину/ведро) хеш‑таблицы. Большое число коллизий приводит к замедлению работы хеш‑таблицы.
См. Хеш‑таблица/Разрешение коллизий в Википедии
Картинка
Картинка иллюстрирует конкретный алгоритм разрешения коллизий — открытую адресацию.
Все элементы хеш-таблицы распределяются по 255 ячейкам (число дано для примера, количество ячеек может быть произвольным). У «John Smith» и «Sandra Dee» хеш совпадает. Оба значения размещаются рядом в хеш‑таблице. При использовании этого алгоритма разрешения коллизий это влияет на следующий элемент «Ted Baker», который перемещается в следующую по порядку корзину несмотря на то что имеет уникальный хеш.
Надо сказать, что класс HashMap
в Java на данный момент использует другой тип разрешения коллизий, в котором каждый бакет представляет из себя дерево поиска, хотя это деталь реализации, не указанная в JavaDoc. Количество бакетов в HashMap
можно задать с помощью capacity и растет по мере необходимости.
-
-
-
-
@Dred то есть вы полагаете что в hashmap не влезет 257 элементов? =) – Stranger in the Q 3 июн '19 в 10:52
-
@StrangerintheQ,не, конечно влезет, может быть только, что в последней ячейке будет указан адрес на новый адрес в памяти, где будет храниться новая информация, что-то типо Linked – Dred 3 июн '19 в 10:54