В реализации HashMap структура бакета представляет собой контейнер для хранения элементов, которые имеют одинаковый хэш-код (или хэш-коды, попадающие в один и тот же индекс массива после вычисления хэша и применения операции по модулю).

Ранее в Java HashMap бакет реализовывался как связанный список (Linked List) элементов, где каждый элемент содержит ключ, значение и ссылку на следующий элемент. При коллизии (когда несколько ключей попадают в один бакет) новые элементы добавлялись в этот список.

Начиная с Java 8, если количество элементов в бакете превышает определённый порог (обычно 8), связанный список преобразуется в сбалансированное дерево (TreeNode, основанное на красно-чёрном дереве). Это улучшает производительность поиска с O(n) до O(log n) в случае большого количества коллизий.

Таким образом, структура бакета в HashMap — это:

Массив бакетов (bucket array), где каждый бакет — это либо
- связанный список элементов (Entry), либо
- сбалансированное дерево (TreeNode), если элементов много.

Пример упрощённой структуры бакета:

class Node<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

При коллизии элементы с одинаковым индексом хранятся в цепочке через поле next или в дереве.

Как устроена структура бакета внутри реализации HashMap?