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

Bucket (корзина) — это элемент внутреннего массива в HashMap, который хранит узлы (entries) с ключами, имеющими одинаковый индекс после вычисления хэш-кода.

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

1. При добавлении пары ключ-значение вычисляется hashCode() ключа.
2. На основе этого хэша определяется индекс в массиве Node<K,V>[] table. Ячейка массива по этому индексу и есть bucket.
3. Если в bucket уже есть элементы (произошла коллизия), новые элементы добавляются в цепочку.

Структура bucket в Java 8+:

• При малом количестве элементов (<= 8) bucket представляет собой связный список (Node).
• При большом количестве элементов (> 8) и при условии, что общий размер таблицы превышает 64, список преобразуется в сбалансированное дерево (TreeNode). Это предотвращает деградацию производительности до O(n) при атаках с использованием коллизий.

// Упрощенная структура узла для списка в bucket (Java 8+)
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // Хэш-код ключа
    final K key;
    V value;
    Node<K,V> next; // Ссылка на следующий узел в цепочке коллизий
}

Производительность: При хорошем хэшировании и равномерном распределении элементов доступ к bucket происходит за O(1). Плохой хэш-код ведет к переполнению одного bucket и снижению производительности.