Ответ
Bucket (корзина) — это элемент внутреннего массива Node<K,V>[] table в HashMap, который хранит узлы (ноды) с данными. Каждая корзина соответствует определенному индексу, вычисляемому на основе хэш-кода ключа.
Как это работает:
- При добавлении пары ключ-значение вычисляется хэш ключа.
- На основе хэша определяется индекс корзины:
index = (n - 1) & hash, гдеn— размер массива. - Элемент помещается в соответствующую корзину.
Важные особенности:
- Коллизии: Если разные ключи попадают в одну корзину (по индексу), элементы хранятся как связный список или, при достижении порога, как сбалансированное дерево (TreeBin).
- Вместимость: Начальная емкость (количество корзин) по умолчанию — 16.
- Рехеширование: При превышении
load factor(коэффициент загрузки, по умолчанию 0.75) количество корзин удваивается, и все элементы перераспределяются.
Пример структуры:
// Упрощенное представление внутреннего массива HashMap
Node<K,V>[] table = new Node[16]; // 16 корзин (bucket'ов)
// table[0] -> null
// table[1] -> Node<K1,V1> -> Node<K2,V2> // Коллизия, список из двух узлов
// table[2] -> null
// ...
Корзины — фундаментальная структура для эффективного доступа к данным в HashMap (в среднем O(1)).