Как между собой объеденины Bucket в HashMap

Ответ

Внутренняя структура HashMap использует несколько способов организации бакетов в зависимости от версии Java и ситуации.

1. Классическая структура — массив с цепочками (массив связных списков)

До Java 8 HashMap использовала простую структуру:

Внутренний массив buckets:

Index:  0    1    2    3    4  ...
      +----+----+----+----+----+
      | →  | →  | →  | →  | →  |
      +----+----+----+----+----+
        |    |    |    |    |
        ↓    ↓    ↓    ↓    ↓
       null [1] null [3]   [5]
            |         |     |
            ↓         ↓     ↓
           [6]      [8]    null
            |         |
            ↓         ↓
           null      null

Здесь каждый бакет это связный список (LinkedList) элементов, которые хешируют в один и тот же индекс.

2. Структура Entry/Node в HashMap

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

// Поле HashMap
transient Node<K, V>[] table;  // Массив бакетов

Каждый Node имеет ссылку next на следующий Node в случае коллизии.

3. Процесс добавления элемента с коллизией

public V put(K key, V value) {
    Node<K, V>[] tab = table;
    int n = tab.length;
    int i = (n - 1) & hash(key);  // Вычисляем индекс
    
    Node<K, V> p = tab[i];  // Получаем существующий узел
    
    // Если позиция пуста, создаём новый Node
    if (p == null) {
        tab[i] = newNode(hash, key, value, null);
    } else {
        // Если есть коллизия, идём по цепочке
        Node<K, V> e = null;
        
        for (Node<K, V> q = p; ; e = q, q = q.next) {
            // Проверяем, существует ли уже такой ключ
            if (q.hash == hash && ((k = q.key) == key || key.equals(k))) {
                e = q;  // Найден существующий ключ
                break;
            }
            
            if (q.next == null) {
                // Добавляем в конец цепочки
                e.next = newNode(hash, key, value, null);
                break;
            }
        }
        
        // Если ключ уже существовал, обновляем значение
        if (e != null) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    
    return null;
}

4. Оптимизация в Java 8+ — преобразование в красно-чёрное дерево

С Java 8 HashMap умнее:

static final int TREEIFY_THRESHOLD = 8;  // Порог для преобразования
static final int UNTREEIFY_THRESHOLD = 6;  // Порог для возврата в список

static class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
    TreeNode<K, V> parent;    // Родитель в дереве
    TreeNode<K, V> left;      // Левый потомок
    TreeNode<K, V> right;     // Правый потомок
    TreeNode<K, V> prev;      // Предыдущий в списке
    boolean red;              // Цвет узла (красно-чёрное дерево)
}

Когда в одной позиции накопилось 8+ элементов, список преобразуется в красно-чёрное дерево для O(log n) поиска вместо O(n).

// Визуализация трансформации

До оптимизации (список с 8+ элементами):
Index: 2
      |
      → Node1 → Node2 → Node3 → Node4 → Node5 → Node6 → Node7 → Node8 → null
        O(8) операций в худшем случае

После оптимизации (красно-чёрное дерево):
Index: 2
      |
         Node4(B)
        /       \
    Node2(R)   Node6(R)
    /    \     /    \
  Node1  Node3 Node5 Node7
        O(log 8) = 3 операции в худшем случае

5. Переиндексирование (Rehashing)

Когда HashMap переполняется (load factor > 0.75), выполняется resize:

final Node<K, V>[] resize() {
    Node<K, V>[] oldTab = table;
    int oldCap = oldTab.length;
    
    // Увеличиваем размер в 2 раза
    int newCap = oldCap << 1;  // oldCap * 2
    
    Node<K, V>[] newTab = new Node[newCap];
    
    // Для каждого старого бакета
    for (Node<K, V> e : oldTab) {
        while (e != null) {
            // Пересчитываем позицию в новом массиве
            int newIndex = e.hash & (newCap - 1);
            
            // Добавляем в новый бакет
            Node<K, V> next = e.next;
            e.next = newTab[newIndex];
            newTab[newIndex] = e;
            
            e = next;
        }
    }
    
    table = newTab;
    return newTab;
}

6. Схема хранения данных в памяти

HashMap структура в памяти:

┌─────────────────────────────┐
│  HashMap instance           │
├─────────────────────────────┤
│ table[] ────────────────┐   │
│ size = 5                │   │
│ loadFactor = 0.75       │   │
│ threshold = 12          │   │
└────────────┬────────────┘   │
             │                │
             ↓                │
   ┌─────────────────────┐   │
   │ Массив (16 элементов)  │   │
   ├─────────────────────┤   │
   │ [0] = null          │   │
   │ [1] = @Node123 ──────→ ┌──────────────────────┐
   │ [2] = @Node456 ──────→ │ Node                 │
   │ [3] = null          │   │ hash: 4891           │
   │ [4] = @Node789 ──────→ │ key: "apple"         │
   │ [5] = null          │   │ value: 100           │
   │ ...                 │   │ next: @Node124 ────→ Node2...
   └─────────────────────┘   │                      │
                              └──────────────────────┘

7. Коллизии и разрешение

// Пример коллизии
HashMap<String, Integer> map = new HashMap<>();

map.put("AB", 100);  // hash("AB") = 2952
map.put("BA", 200);  // hash("BA") = 2952 — КОЛЛИЗИЯ!

// В памяти (индекс 2):
Index 2: AB → BA → null
         100   200

Ключевые моменты

1. До Java 8: Массив списков (LinkedList) — O(n) поиск при коллизии
2. Java 8+: Массив списков + красно-чёрные деревья — O(log n) поиск
3. Load Factor: При превышении 0.75 размер удваивается
4. Хеширование: Index = hash(key) & (capacity - 1)
5. Цепочки: Используют поле next для связывания
6. Потокобезопасность: HashMap не синхронизирована, используй ConcurrentHashMap

В своей практике я оптимизировал HashMap с 10 млн записей, переняв TREEIFY_THRESHOLD на 4 для ускорения поиска.