🟢 Junior Level

Bucket (корзина) — это элемент массива table[] внутри HashMap.

Аналогия: Представьте почтовый шкаф с ячейками: массив — это весь шкаф, бакет — конкретная ячейка. Но в отличие от реальной ячейки, в бакет можно положить сколько угодно элементов — они выстраиваются в цепочку (linked list).

Когда HashMap хочет положить элемент, она вычисляет номер корзины по формуле:

index = (размер_таблицы - 1) & hash(ключа)

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 100); // Попал в корзину X (зависит от hashCode("key1"))
map.put("key2", 200); // Попал в корзину Y (зависит от hashCode("key2"))

Простая аналогия: Почтовый индекс определяет, на какое почтовое отделение (бакет) отправить письмо. А уже внутри отделения ищут конкретного получателя.

🟡 Middle Level

Три состояния бакета

1. Пустой (Empty) — ячейка содержит null. Занимает только память под указатель (4-8 байт).
2. Связный список (Linked List) — при коллизиях ноды связываются через поле next. Поиск: O(k), где k — количество элементов в бакете.
3. Дерево (Tree) — при 8+ элементах и capacity >= 64 список превращается в красно-чёрное дерево (TreeNode, Java 8+). Поиск: O(log k).

Почему бакетов всегда 2^n?

Это фундаментальное архитектурное решение:

• Формула index = (n-1) & hash корректно распределяет элементы только при степени двойки
• При resize (удвоении) элементы либо остаются на месте, либо перемещаются на index + oldCap — без полного пересчёта хеша

Параметры, влияющие на бакеты

Параметр	Значение по умолчанию	Влияние
Initial Capacity	16	Начальное количество бакетов
Load Factor	0.75	При каком заполнении бакеты удваиваются

Типичная ошибка: Не учитывать, что new HashMap(10) создаст 16 бакетов (ближайшая степень двойки вверх).

Когда НЕ использовать большой initialCapacity

Не задавайте избыточный initialCapacity: HashMap на 1 000 000 бакетов с 10 элементами тратит ~8 МБ памяти впустую (массив ссылок на null).

🔴 Senior Level

Internal Implementation

Бакет — это элемент массива Node<K,V>[] table. Каждый Node содержит:

class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Следующий элемент в цепочке коллизий
}

При treeification бакет хранит TreeNode:

class TreeNode<K,V> {
    TreeNode<K,V> parent, left, right, prev;
    boolean red;
    // + наследует hash, key, value, next от Node
}

TreeNode занимает ~2x больше памяти из-за дополнительных ссылок и флага цвета.

Распределение Пуассона

Распределение Пуассона — статистическая модель, описывающая вероятность редких событий. Вероятность попадания 8+ элементов в один бакет при хорошем hashCode ≈ 0.00000006 — практически нулевая.

При loadFactor 0.75 вероятность количества элементов в бакете подчиняется распределению Пуассона:

• 0 элементов: ~22%
• 1 элемент: ~33%
• 2 элемента: ~25%
• 8 элементов: ~0.00000006 (почти невозможно при хорошем hashCode)

Порог 8 для treeification выбран именно на основе этой статистики.

Hash Flooding Attack

Если злоумышленник подберёт ключи с одинаковым хешем, все элементы попадут в один бакет. До Java 8 это приводило к O(n) и DoS-атаке. Treeification (O(log n)) нивелирует эту угрозу.

Cache Locality

Бакеты разбросаны по разным адресам в Heap. Длинные цепочки ведут к частым Cache Miss, так как каждая Node — отдельный объект. Это влияет на реальную производительность больше, чем асимптотическая сложность.

Memory Implications

• Пустой бакет: 4-8 байт (зависит от UseCompressedOops)
• Node в списке: ~32-48 байт
• TreeNode: ~64-80 байт
• При capacity=16: ~128 байт на сам массив (16 ссылок)

Production Monitoring

Для диагностики проблем с бакетами можно использовать reflection или instrumentation для анализа распределения элементов по бакетам. В production аномальное количество элементов в одном бакете указывает на плохой hashCode() ключа.

---

🎯 Шпаргалка для интервью

Обязательно знать:

• Bucket = элемент массива table[], хранит список или дерево элементов
• Три состояния: пустой, связный список, дерево (TreeNode при 8+ элементах и capacity >= 64)
• Capacity всегда степень двойки — для формулы index = (n-1) & hash
• При resize элементы либо остаются на месте, либо смещаются на index + oldCap
• Не задавайте избыточный initialCapacity — пустые бакеты тратят память
• Распределение Пуассона: вероятность 8+ элементов в бакете ≈ 0.00000006

Частые уточняющие вопросы:

• Что будет при new HashMap(10)? — capacity станет 16 (ближайшая степень двойки)
• Почему treeification при 8, а не 4? — для k ≤ 7 список быстрее дерева (меньше overhead)
• Сколько памяти занимает пустой бакет? — 4-8 байт (ссылка на null)
• Что такое treeification? — конвертация списка в красно-чёрное дерево при 8+ коллизиях

Красные флаги (НЕ говорить):

• «Бакет хранит только один элемент» — нет, при коллизиях — список/дерево
• «HashMap создаёт массив при конструкторе» — нет, ленивая инициализация (Java 8+)
• «При 8 элементах всегда дерево» — только если capacity >= 64

Связанные темы:

• [[1. Как устроена HashMap внутри]]
• [[3. Как HashMap определяет, в какой bucket положить элемент]]
• [[6. Что происходит при достижении 8 элементов в одном bucket]]
• [[17. Что такое capacity в HashMap]]