Когда структура данных внутри бакета HashMap меняется на дерево?

HashMap: переход от связного списка к красно-чёрному дереву

Это одна из важнейших оптимизаций в Java 8+. Давайте разберемся, когда и почему это происходит.

До Java 8: только связные списки

// До Java 8 - каждый бакет это всегда связный список
public class HashMapOld {
    static class Node {
        int hash;
        Object key;
        Object value;
        Node next;  // Связный список
    }
    
    private Node[] buckets;
    
    public Object get(Object key) {
        int bucketIndex = hash(key) % buckets.length;
        Node node = buckets[bucketIndex];
        
        // О(n) в худшем случае
        while (node != null) {
            if (node.key.equals(key)) {
                return node.value;
            }
            node = node.next;  // Проходимся по списку
        }
        return null;
    }
}

Проблема: Если много hash'ей коллизий → O(n) для поиска вместо O(1)

Java 8+: гибридная структура

public class HashMapNew {
    static class Node {
        int hash;
        Object key;
        Object value;
        Node next;  // Для совместимости
    }
    
    // TreeNode наследует Node, но расширяет функционал
    static class TreeNode extends Node {
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        TreeNode prev;
        boolean red;  // Для красно-чёрного дерева
    }
    
    private Node[] buckets;
    
    static final int TREEIFY_THRESHOLD = 8;  // КЛЮЧЕВОЙ ПАРАМЕТР
    static final int UNTREEIFY_THRESHOLD = 6;
}

ГЛАВНЫЙ МОМЕНТ: когда происходит преобразование

Преобразование в дерево (TREEIFY) происходит когда:

// 1. В одном бакете уже 8 элементов (индекс 7)
// 2. И добавляем 9-й элемент (индекс 8)
// → преобразуем связный список в красно-чёрное дерево

Обратное преобразование (UNTREEIFY) происходит когда:

// 1. После удаления элементов в дереве
// 2. Остается 6 элементов или меньше
// 3. Преобразуем обратно в связный список

Примеры

Сценарий 1: Переход в дерево из-за коллизии

HashMap<String, String> map = new HashMap<>();

// Предположим, у нас плохая хеш-функция и все эти ключи
// коллизируют в один бакет (нереально, но для примера)
map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");
map.put("key4", "value4");
map.put("key5", "value5");
map.put("key6", "value6");
map.put("key7", "value7");
map.put("key8", "value8");  // 8-й элемент - еще связный список

map.put("key9", "value9");  // 9-й элемент
// ЗДЕСЬ ПРОИСХОДИТ TREEIFY - преобразуем в красно-чёрное дерево

Сценарий 2: Специально вызванная коллизия

public class CollisionDemo {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        
        // Целенаправленно создаем коллизии
        // используя свойства Integer.hashCode()
        for (int i = 0; i < 1000; i++) {
            // Эти числа специально подобраны, чтобы коллизировать
            if (i % 3 == 0) {  // Упрощенный пример
                map.put(i, "value" + i);
            }
        }
        
        // После добавления 9 коллизирующих элементов
        // этот бакет станет деревом
    }
}

Внутренний код Java 8+ HashMap

private static final int TREEIFY_THRESHOLD = 8;
private static final int UNTREEIFY_THRESHOLD = 6;

// Когда добавляем элемент в бакет
private void putVal(int hash, K key, V value, boolean onlyIfAbsent, 
                    boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // ... код ...
    
    // Если в бакете уже есть элементы
    if ((p = tab[i = (n - 1) & hash]) != null) {
        Node<K,V> e; K k;
        
        // Проходим по цепочке
        int binCount = 0;
        for (;;++binCount) {  // binCount считает элементы
            // ... код сравнения ...
            
            // Если это 8-й элемент в цепочке
            if (binCount >= TREEIFY_THRESHOLD - 1) {
                treeifyBin(tab, hash);  // Преобразуем в дерево
                break;
            }
        }
    }
}

// Преобразование в дерево
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    
    // Минимальный размер таблицы для treeify
    if ((n = tab.length) < MIN_TREEIFY_CAPACITY)  // MIN = 64
        resize();  // Если таблица слишком маленькая, расширяем
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        
        // Строим красно-чёрное дерево из узлов
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

// Обратное преобразование
final Node<K,V> untreeify(Node<K,V> head) {
    Node<K,V> q, p = head;
    for (;;p = q) {
        if ((q = p.next) == null)
            break;
        p.next = q.next;  // Удаляем дерево
        q.next = p;       // Создаем список
    }
    return p;
}

Почему TREEIFY_THRESHOLD = 8?

- 8 это оптимальный порог, выбранный через анализ производительности
- При 8+ элементах красно-чёрное дерево эффективнее связного списка
- Поиск в дереве O(log n) ≈ 3 сравнения
- Поиск в списке из 8 элементов = 4 сравнения в среднем

Важное дополнение: MIN_TREEIFY_CAPACITY

static final int MIN_TREEIFY_CAPACITY = 64;

// Это ОЧЕНЬ важно!
// Если таблица меньше 64 элементов, вместо treeify()
// просто расширяем таблицу - это проще чем строить дерево

HashMap<String, String> small = new HashMap<>(8);
// Даже если будет 9+ коллизий, сначала расширим таблицу

Практический пример с реальным кодом

public class HashMapBehaviorDemo {
    public static void main(String[] args) throws Exception {
        HashMap<String, String> map = new HashMap<>();
        
        // Узнаем текущую емкость
        java.lang.reflect.Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        
        // Добавляем элементы
        for (int i = 0; i < 20; i++) {
            map.put("key" + i, "value" + i);
            
            // После каждого добавления проверяем размер таблицы
            Object[] table = (Object[]) tableField.get(map);
            System.out.println("i=" + i + ", size=" + table.length);
        }
    }
}

Резюме: Когда меняется структура

Практическое значение

Это оптимизация защищает от DoS атак с плохой хеш-функцией:

// Без дерева: O(n) для каждого поиска при коллизиях
// С деревом: O(log n) даже при большом количестве коллизий

Главное: HashMap в Java 8+ самооптимизируется под условия использования!