Всегда ли в Bucket связный список в HashMap?

# Связный список в Bucket HashMap

Короткий ответ: НЕТ. В Java 8+ HashMap использует динамическое переключение между связным списком и красно-чёрным деревом.

История эволюции HashMap

Java 7 и ранее: ТОЛЬКО связный список

// Старый подход
Entry[] table = new Entry[capacity];

// Каждый bucket — это связный список
class Entry {
    int hash;
    Object key;
    Object value;
    Entry next; // Связный список!
}

Проблема: при плохом распределении hash-кодов (много collisions) один bucket может содержать все элементы, и поиск становится O(n).

Java 8+: Гибридный подход

Решение: динамическое переключение между связным списком и красно-чёрным деревом.

// Java 8+ подход
Node[] table = new Node[capacity];

// Bucket может быть либо:
// 1. LinkedList (Node с next)
class Node {
    int hash;
    K key;
    V value;
    Node next; // Связный список
}

// 2. TreeNode (красно-чёрное дерево)
class TreeNode extends Node {
    TreeNode parent;
    TreeNode left;
    TreeNode right;
    boolean red; // Для красно-чёрного дерева
}

Когда происходит переключение

Переход: Список → Дерево

// При добавлении элемента в bucket
private void putVal(int hash, K key, V value, ...) {
    Node[] tab; Node p; int n, i;
    
    // Найти bucket
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    if ((p = tab[i = (n - 1) & hash]) == null) {
        // Пустой bucket — добавляем элемент
        tab[i] = newNode(hash, key, value, null);
    } else {
        // Bucket не пустой
        Node e; K k;
        
        // Ищем элемент в списке/дереве
        do {
            if (p.hash == hash && ((k = p.key) == key || key.equals(k))) {
                e = p; // Нашли — обновим значение
                break;
            }
            // Проверяем, можно ли преобразовать в дерево
            if (p instanceof TreeNode) {
                // Уже дерево — добавим в дерево
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            } else {
                // Ещё список
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        
                        // КРИТИЧЕСКОЕ УСЛОВИЕ!
                        // Если список слишком длинный — преобразуем в дерево
                        if (binCount >= TREEIFY_THRESHOLD - 1) {
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                        break;
                    }
                    p = e;
                }
            }
        } while (e != null);
    }
}

private void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index;
    Node<K,V> e;
    
    // Если таблица слишком маленькая — просто расширим её
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize(); // Увеличиваем таблицу вместо преобразования в дерево
        return;
    }
    
    // Преобразуем связный список в красно-чёрное дерево
    TreeNode<K,V> hd = null, tl = null;
    for (e = tab[index]; e != null; e = e.next) {
        TreeNode<K,V> p = new TreeNode<>(e.hash, e.key, e.value, null);
        if (tl == null)
            hd = p;
        else {
            p.prev = tl;
            tl.next = p;
        }
        tl = p;
    }
    if (hd != null) {
        hd.root().treeify(tab); // Строим дерево
        tab[index] = hd;
    }
}

Пороги переключения

public class HashMap<K,V> {
    // ЭТИ КОНСТАНТЫ ОПРЕДЕЛЯЮТ ПЕРЕКЛЮЧЕНИЕ
    
    /**
     * Порог для преобразования списка в дерево
     * Когда в одном bucket'е 8 элементов — преобразуем в дерево
     */
    static final int TREEIFY_THRESHOLD = 8;
    
    /**
     * Порог для преобразования дерева в список
     * Когда в дереве меньше 6 элементов — преобразуем обратно в список
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /**
     * Минимальная длина таблицы для преобразования в дерево
     * Если таблица меньше 64, расширим её вместо преобразования
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
}

Практический пример

public class HashMapBucketDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // Сценарий: вставляем элементы с одинаковым hash (collision)
        // В реальности это случается редко, но давайте симулируем
        
        // Вставляем первые 8 элементов — остаёмся в списке
        for (int i = 0; i < 8; i++) {
            map.put("key" + i, i);
            System.out.println("Added " + i + " elements");
        }
        // Всё ещё связный список внутри bucket'а
        
        // 9-й элемент — ПРЕОБРАЗОВАНИЕ В ДЕРЕВО!
        map.put("key8", 8);
        System.out.println("Added 8 elements - TREEIFIED!");
        // Теперь bucket — красно-чёрное дерево
        
        // Удаляем элементы
        for (int i = 0; i < 3; i++) {
            map.remove("key" + i);
        }
        // В дереве остаётся 6 элементов, но дерево остаётся деревом
        
        // Удаляем ещё один
        map.remove("key3");
        // 5 элементов — ПРЕОБРАЗОВАНИЕ ОБРАТНО В СПИСОК!
        System.out.println("Removed to 5 elements - UNTREEIFIED!");
    }
}

Производительность: Список vs Дерево

Связный список

// O(n) поиск
for (Node e = first; e != null; e = e.next) {
    if (e.hash == hash && e.key.equals(key)) {
        return e.value; // Может понадобиться проверить все n элементов
    }
}

Временная сложность:

• Лучший случай: O(1) — элемент в начале
• Средний случай: O(n) — нужно проверить примерно n/2 элементов
• Худший случай: O(n) — элемента нет или в конце

Красно-чёрное дерево

// O(log n) поиск
private final V getTreeNode(int h, Object k) {
    return ((TreeNode<K,V>)root()).getTreeNode(h, k);
}

// В TreeNode:
final TreeNode<K,V> getTreeNode(int h, Object k) {
    return findTreeNode(h, k, null);
}

// Бинарный поиск через дерево
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl; // Идём влево
        else if (ph < h)
            p = pr; // Идём вправо
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p; // Нашли!
        else if (pl == null)
            p = pr; // Нет левого поддерева
        else if (pr == null)
            p = pl; // Нет правого поддерева
        else if ((cmp = c.compare(k, pk)) < 0)
            p = pl; // Идём влево
        else
            p = pr; // Идём вправо
    } while (p != null);
    return null;
}

Временная сложность:

• Лучший случай: O(1) — элемент в корне
• Средний случай: O(log n) — высота дерева логарифмична
• Худший случай: O(log n) — красно-чёрное дерево сбалансировано

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

Элементов в bucket | Список | Дерево
     1             | O(1)   | O(1)
     8             | O(8)   | O(3)
    16             | O(16)  | O(4)
    32             | O(32)  | O(5)
    64             | O(64)  | O(6)
  1000             | O(1000)| O(10)

Вывод

✅ Java 7 и ранее: только связный список в bucket'е
✅ Java 8+: динамическое переключение

Порядок переключения:

1. Добавляем элементы → остаёмся в списке
2. 8 элементов → преобразуем в дерево (если таблица ≥ 64)
3. Удаляем элементы → при 6 или меньше преобразуем обратно в список

Причина: защита от плохих hash-функций, которые вызывают много collisions. Дерево гарантирует O(log n) вместо O(n).