Что такое bucket (корзина) в HashMap

Сам массив table представляет собой хеш-таблицу, а его длина (table.length) называется емкостью (capacity). Каждый бакет хранит либо null (если корзина пуста), либо ссылку на пе...

🟢 Junior Level

Краткий ответ для собеседования (30 секунд)

Bucket (корзина / бакет) в HashMap — это отдельная ячейка внутреннего массива Node<K,V>[] table.

Сам массив table представляет собой хеш-таблицу, а его длина (table.length) называется емкостью (capacity). Каждый бакет хранит либо null (если корзина пуста), либо ссылку на первый элемент коллекции, попавший по этому индексу. Если в одну и ту же корзину попадают несколько элементов с одинаковым вычисленным индексом (коллизия), они объединяются в односвязный список через ссылку next. Если число элементов в одной корзине достигает 8 (при размере таблицы не менее 64), бакет перестраивается в сбалансированное красно-черное дерево (TreeNode).

Сравнительная таблица состояний корзины (Bucket States)

Состояние корзины	Внутреннее представление	Потребление памяти (RAM)	Временная сложность поиска
1. Пустая (Empty)	`table[i] == null`	4 или 8 байт (ссылка в массиве)	$O(1)$ — мгновенная проверка на `null`
2. Единственный узел (Single Node)	`Node<K,V>` без продолжения (`next == null`)	32 байта (узел) + ссылки на ключ/значение	$O(1)$ — проверка одного ключа
3. Связный список (Collision List)	Цепочка узлов `Node<K,V>` (от 2 до 7 элементов)	По 32 байта на каждый узел списка	$O(k)$, где $k$ — глубина коллизии ($k \le 7$)
4. Красно-черное дерево (Treeified)	Дерево `TreeNode<K,V>` ($\ge 8$ элементов)	~56–64 байта на каждый узел дерева	$O(\log k)$ — логарифмический поиск

Демонстрация на Java 21

import java.util.HashMap;

public class BucketInspectionDemo {
    public static void main(String[] args) {
        // Создаем мапу (массив table пока равен null!)
        HashMap<String, String> map = new HashMap<>();

        // При первом put() создается массив table[] длиной 16 бакетов (индексы 0..15)
        map.put("Java", "Language");
        map.put("Kotlin", "Language");

        // Индекс корзины рассчитывается по формуле: index = (table.length - 1) & hash
        // null-ключ всегда попадает в корзину с индексом 0:
        map.put(null, "DefaultValue");

        System.out.println("Количество элементов в мапе: " + map.size());
    }
}

🟡 Middle Level

Математика адресации корзины: почему емкость всегда $2^n$

Индекс корзины, в которую помещается элемент, вычисляется формулой:

int index = (table.length - 1) & hash;

Зачем нужна степень двойки:

Аппаратное ускорение: деление процессора (idiv) занимает десятки тактов, тогда как битовое AND выполняется за 1 такт.
Полнота покрытия: число $(2^n - 1)$ в двоичной системе счисления представляет собой сплошную последовательность единиц:
- $16 - 1 = 15 = 0000\,1111_b$
- $32 - 1 = 31 = 0001\,1111_b$
- $64 - 1 = 63 = 0011\,1111_b$
  Это гарантирует, что каждый младший бит хеша будет равноправно участвовать в выборе индекса корзины.

Функция `tableSizeFor(int cap)`: Округление емкости вверх

Если разработчик создает мапу с произвольным initialCapacity (например, new HashMap<>(10)), JVM не создает массив из 10 ячеек. Внутренний алгоритм округляет переданное число до ближайшей степени двойки вверх:

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

(В Java 8 использовалась последовательность битовых сдвигов n |= n >>> 1; n |= n >>> 2; ... n |= n >>> 16;, в современных версиях оптимизированная через intrinsic numberOfLeadingZeros).

Входное значение: 10  ──► tableSizeFor(10)  ──► capacity = 16
Входное значение: 17  ──► tableSizeFor(17)  ──► capacity = 32
Входное значение: 500 ──► tableSizeFor(500) ──► capacity = 512

Правильный расчет `initialCapacity`

Если вы ожидаете сохранить в мапе 1000 элементов, наивная инициализация new HashMap<>(1000) приведет к лишнему ресайзу:

tableSizeFor(1000) округлит емкость до 1024;
Порог расширения: threshold = 1024 * 0.75 = 768;
При вставке 769-го элемента произойдет дорогостоящий ресайз таблицы с удвоением до 2048!

Формула бесконфликтной емкости:

$\text{initialCapacity} = \left\lceil \frac{\text{expectedSize}}{\text{loadFactor}} \right\rceil + 1 = \left\lceil \frac{1000}{0.75} \right\rceil + 1 = 1335 \longrightarrow 2048$ В Java 19+ для этого добавлен официальный фабричный метод:

Map<String, User> userCache = HashMap.newHashMap(1000); // Сам рассчитает емкость 2048!

🔴 Senior Level

Анализ накладных расходов памяти: Heap vs Cache Locality

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

Массив корзин Node<K,V>[] table:
- Длина массива: N ячеек
- Каждая ячейка: ссылка (4 байта при Compressed OOPs, 8 байт без)
- Заголовок массива в куче: 16 байт

При capacity = 16: $16 \times 4 + 16 = 80$ байт.
При избыточном initialCapacity = 1_000_000: пустой массив займет ~4 МБ оперативной памяти, даже если в него добавят всего 5 элементов!

Проблема Cache Locality в Separate Chaining:

HashMap использует метод цепочек (Separate Chaining). В отличие от открытой адресации (Open Addressing / Linear Probing), где все данные хранятся подряд в непрерывном массиве (как в Python dict или специализированных высокопроизводительных коллекциях Eclipse Collections / Agrona):

В Java HashMap узлы Node аллоцируются в произвольных участках кучи через new Node<>();
Обход связного списка в корзине при коллизии приводит к последовательным промахам кэша процессора (CPU Cache Misses);
Однако метод цепочек был выбран архитекторами Java из-за устойчивости: он не деградирует при коэффициентах загрузки $>0.7$ и не страдает от эффекта кластеризации (Primary Clustering), свойственного открытой адресации.

Анализ аномалий распределения: Skewed Buckets в Production

В продакшен-мониторинге перекос распределения по корзинам (когда 95% элементов собираются в 2–3 бакетах) свидетельствует о нарушении контракта hashCode():

// Худший сценарий распределения корзин:
public class DefectiveKey {
    private final String id;
    public DefectiveKey(String id) { this.id = id; }
    
    // ❌ КАТАСТРОФА: все элементы всегда попадают в один бакет (индекс = 0)!
    @Override
    public int hashCode() {
        return 42;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof DefectiveKey other && this.id.equals(other.id);
    }
}

В такой ситуации HashMap превращается в одно красно-черное дерево, деградируя производительность до $O(\log n)$ с постоянным перебалансированием дерева при вставке.

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

1. 30-секундный эссенс (Elevator Pitch)

Бакет (корзина) в HashMap — это ячейка внутреннего массива Node<K,V>[] table, адресуемая битовой маской (table.length - 1) & hash. Корзина может находиться в 4 состояниях: пустая (null), единичный узел, связный список (при коллизиях до 7 элементов) и красно-черное дерево (TreeNode при $\ge 8$ элементах и емкости $\ge 64$). Емкость таблицы всегда кратна степени двойки, а при создании мапы через new HashMap<>(cap) значение округляется вверх методом tableSizeFor(). Для избежания ресайза в Java 19+ рекомендуется использовать HashMap.newHashMap(n).

2. 4 каверзных вопроса с глубокими ответами

Вопрос 1: Что физически хранится в ячейке `table[index]`, если в данный бакет попало несколько элементов с одинаковым индексом?

Ответ: В самой ячейке массива table[index] физически хранится обычная ссылка (указатель) на первый узел (голову) односвязного списка Node<K,V> (или корень красно-черного дерева TreeNode<K,V>). Все последующие элементы цепочки коллизий привязаны друг к другу ссылками node.next и физически распределены по куче JVM. Массив table не расширяется «вглубь», он содержит строго плоский список указателей.

Вопрос 2: Как метод `tableSizeFor(int cap)` преобразует произвольное число в ближайшую степень двойки без циклов?

Ответ: Метод берет переданное число $cap - 1$ и вычисляет количество ведущих нулевых битов с помощью процессорной инструкции LZCNT / метода Integer.numberOfLeadingZeros(). Затем беззнаковый сдвиг -1 >>> leadingZeros заполняет все разряды после старшего бита единицами, превращая число в маску вида 000...01111111. Прибавление единицы (+ 1) дает степень двойки ($2^k$). Вся операция занимает несколько тактов CPU без циклов и условий.

Вопрос 3: Почему в Java `HashMap` используется метод цепочек (Separate Chaining), а не метод открытой адресации (Open Addressing)?

Ответ: В открытой адресации при коллизии элемент помещается в следующую свободную ячейку того же массива. Это дает идеальную локальность данных в кэше CPU, но имеет фатальные недостатки:

Требует низкого коэффициента загрузки (не более $0.5$), иначе производительность падает экспоненциально из-за кластеризации;
Удаление элементов крайне дорогое (требует маркерных надгробий TOMBSTONE и периодической дефрагментации);
Метод цепочек с древофикацией (Java 8+) гарантирует предсказуемую верхнюю границу $O(\log n)$ даже при злонамеренном подборе коллизий.

Вопрос 4: Как распределение Пуассона объясняет выбор порога превращения списка бакета в дерево (`TREEIFY_THRESHOLD = 8`)?

Ответ: При честной реализации hashCode() распределение ключей по корзинам подчиняется закону Пуассона со средним значением $\lambda = 0.5$ (при load factor 0.75). Вероятность того, что в одну корзину случайно попадет 8 элементов, составляет $P(8) \approx 6 \times 10^{-8}$ (шесть стомиллионных). Это означает, что при нормальной работе превращение в дерево практически никогда не произойдет. Порог 8 выбран так, чтобы не тратить память на тяжелые узлы TreeNode в штатном режиме, но защитить систему от деградации при атаках Hash Flooding DoS.

3. Типичные ошибки и Red Flags

❌ “Емкость массива бакетов может быть произвольным четным числом.”
Правильно: Емкость HashMap строго равна степени двойки ($2^n$). Если указать 10, JVM округлит емкость до 16.

❌ “При вызове new HashMap(100) мапа вмещает 100 элементов без ресайза.”
Правильно: 100 будет округлено до 128. Порог ресайза составит $128 \times 0.75 = 96$. При добавлении 97-го элемента произойдет ресайз.

❌ “Пустые бакеты не расходуют оперативную память.”
Правильно: Сам массив table аллоцирует непрерывный кусок памяти под ссылки. Массив на 1 000 000 ячеек займет ~4 МБ, даже будучи абсолютно пустым.