Что такое bucket в структуре HashMap (Java)?

«Что такое bucket в структуре HashMap (Java)?» — вопрос из категории Java Core, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Bucket (корзина) — это элемент внутреннего массива Node<K,V>[] table в HashMap, который хранит узлы (ноды) с данными. Каждая корзина соответствует определенному индексу, вычисляемому на основе хэш-кода ключа.

Как это работает:

  1. При добавлении пары ключ-значение вычисляется хэш ключа.
  2. На основе хэша определяется индекс корзины: index = (n - 1) & hash, где n — размер массива.
  3. Элемент помещается в соответствующую корзину.

Важные особенности:

  • Коллизии: Если разные ключи попадают в одну корзину (по индексу), элементы хранятся как связный список или, при достижении порога, как сбалансированное дерево (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)).