Как хранятся элементы в Bucket в HashMap

Хранение элементов в бакете HashMap

В HashMap из Java (и аналогичных структур в Kotlin/Android) элементы хранятся в бакетах (buckets) — это фундаментальная часть реализации, обеспечивающая эффективность операций вставки, поиска и удаления.

Структура бакета

Каждый бакет представляет собой связный список узлов (в Java 7 и ранее) или дерево (в Java 8+ при выполнении условий). Вот как это работает:

1. Индекс бакета вычисляется на основе хэш-кода ключа:

   int index = (n - 1) & hash(key);
   

   Где n — текущий размер массива бакетов (всегда степень двойки), hash(key) — обработанный хэш-код ключа.

2. При коллизии (когда разные ключи попадают в один индекс) элементы добавляются в одну цепочку:

   • В Java 7: используется односвязный список (Entry).
   • В Java 8+: при малом количестве элементов — односвязный список (Node), при превышении порога (TREEIFY_THRESHOLD = 8) и достаточном размере таблицы — преобразуется в красно-черное дерево (TreeNode).

Пример узла (Java 8+)

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Ссылка на следующий узел в цепочке
    
    // Конструктор, методы getKey(), getValue(), hashCode() и т.д.
}

Преобразование в дерево

Когда цепочка становится слишком длинной, производительность поиска деградирует до O(n). Для оптимизации:

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 для первого элемента
    treeifyBin(tab, hash); // Преобразует цепочку в дерево

Условия преобразования:

• Длина цепочки ≥ TREEIFY_THRESHOLD (8)
• Размер таблицы ≥ MIN_TREEIFY_CAPACITY (64)

Организация памяти

• Массив бакетов: Node<K,V>[] table — основной массив, где индекс соответствует бакету.
• Загрузка: каждый бакет может быть:
  • null (нет элементов)
  • Node (голова цепочки или единственный элемент)
  • TreeNode (корень дерева)

Пример визуализации бакета

Индекс 0: null
Индекс 1: Node1("keyA", 1) → Node2("keyB", 2) → Node3("keyC", 3) [список]
Индекс 2: TreeNode... [красно-черное дерево из 8+ элементов]
Индекс 3: null

Ключевые аспекты

1. Равномерность хэширования — критична для распределения по бакетам.
2. capacity — размер массива бакетов, увеличивается при превышении loadFactor.
3. loadFactor (по умолчанию 0.75) — определяет, когда таблица будет ресайзнута.
4. Ресайзинг — при превышении threshold = capacity * loadFactor массив бакетов удваивается, элементы перераспределяются.

Влияние на производительность

• Идеальный случай (отсутствие коллизий): O(1) для get/put.
• Худший случай (все ключи в одном бакете до Java 8): O(n).
• С деревьями (Java 8+): O(log n) даже при плохом хэшировании.

Таким образом, бакеты в HashMap — это гибкая структура, сочетающая массивы, связные списки и деревья для баланса между памятью и производительностью.