PrepBro
← Назад к вопросам

После достижения какой длины список превращается в дерево в HashMap

2.0 Middle🔥 201 комментариев
#Docker, Kubernetes и DevOps#JVM и управление памятью#ORM и Hibernate

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

После достижения какой длины список превращается в дерево в HashMap

Краткий ответ

В Java 8 и позже, когда в корзине (bucket) HashMap накапливается 8 элементов и размер таблицы >= 64, список преобразуется в красно-черное дерево (Red-Black Tree). Обратное преобразование происходит при 6 элементах.

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

Java 7 и ранее

// До Java 8
// HashMap использовал связные списки (linked lists) для разрешения коллизий
// Структура корзины:
// Bucket[0] → Node → Node → Node → Node → ... (O(n) в худшем случае)

// Проблема: При плохом hash code все элементы могут попасть в одну корзину
HashMap<String, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    // Если все ключи имеют одинаковый hash код
    // то все 1000 элементов окажутся в одной цепочке
    // Поиск будет O(n) вместо O(1)
}

Java 8+

Джава 8 предоставила решение: гибридная структура

Java 8+ HashMap Bucket Structure:

Если elements < TREEIFY_THRESHOLD (8):
    Bucket → Linked List (Node → Node → Node)
    Complexity: O(n) для поиска

Если elements >= TREEIFY_THRESHOLD (8) И table.length >= MIN_TREEIFY_CAPACITY (64):
    Bucket → Red-Black Tree (TreeNode)
    Complexity: O(log n) для поиска

Обратное преобразование при UNTREEIFY_THRESHOLD (6):
    Bucket → Linked List снова
    (Удаление элементов → размер < 6 → back to linked list)

Константы в HashMap коде

public class HashMap<K, V> {
    // Максимальная длина списка перед преобразованием в дерево
    static final int TREEIFY_THRESHOLD = 8;
    
    // Минимальный размер таблицы для преобразования в дерево
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // При удалении элементов дерево превращается в список
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // Красно-черное дерево
    static final 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;             // цвет узла (красный/черный)
        // методы для балансировки дерева...
    }
}

Когда происходит преобразование

Сценарий 1: При добавлении 8-го элемента в одну корзину

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

// Предположим, все элементы имеют одинаковый hash код
// (упрощено для примера)

map.put("key1", 1);   // Bucket[0]: Node1
map.put("key2", 2);   // Bucket[0]: Node1 → Node2
map.put("key3", 3);   // Bucket[0]: Node1 → Node2 → Node3
map.put("key4", 4);   // Bucket[0]: Node1 → Node2 → Node3 → Node4
map.put("key5", 5);   // Bucket[0]: Node1 → ... → Node5 (size=5, linked list)
map.put("key6", 6);   // Bucket[0]: Node1 → ... → Node6 (size=6, still linked list)
map.put("key7", 7);   // Bucket[0]: Node1 → ... → Node7 (size=7, still linked list)
map.put("key8", 8);   // Bucket[0]: Node1 → ... → Node8 (size=8)
                      // TREEIFY_THRESHOLD достигнут!
                      // Проверка: table.length >= 64?
                      // Если ДА → преобразуй в Red-Black Tree
                      // Если НЕТ → осталось linked list, но подумай о resize

Сценарий 2: При resize() таблицы

// Когда HashMap растет (resize), она перехешует все элементы
// Это может привести к возникновению длинных цепочек в новой таблице

HashMap<String, Integer> map = new HashMap<>();
// Добавим элементы...
for (int i = 0; i < 100; i++) {
    map.put("key" + i, i);
}

// HashMap будет resize несколько раз:
// capacity: 16 → 32 → 64 → 128 → ...

// Когда capacity становится >= 64, AND
// какой-то bucket имеет >= 8 элементов,
// то этот bucket преобразуется в дерево

Полный процесс treeify

// Упрощенный код из HashMap
public V put(K key, V value) {
    // ... find bucket ...
    
    if (binCount >= TREEIFY_THRESHOLD - 1) { // -1 потому что еще не добавлен
        treeifyBin(tab, hash);
    }
    return putVal(hash, key, value, false, true);
}

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

Пример в коде: Когда случается преобразование

public class HashMapTreeifyExample {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        
        // Сценарий: Добавляем элементы, которые хешируются в одну позицию
        // Это сложно сделать с обычными Integer ключами, но вот пример
        // с кастомным hash code:
        
        class BadKey {
            int value;
            BadKey(int v) { this.value = v; }
            @Override
            public int hashCode() {
                return 0;  // ВСЕ элементы имеют одинаковый хеш!
            }
            @Override
            public boolean equals(Object o) {
                return o instanceof BadKey && 
                    ((BadKey)o).value == this.value;
            }
        }
        
        HashMap<BadKey, String> badMap = new HashMap<>();
        
        // Добавим 8 элементов (все с hash code = 0)
        for (int i = 0; i < 8; i++) {
            badMap.put(new BadKey(i), "value" + i);
        }
        
        // После 8-го элемента (если capacity >= 64) 
        // корзина преобразуется из linked list в red-black tree
        // Вместо O(n) поиск становится O(log n)
    }
}

Почему красно-черное дерево?

Red-Black Tree выбрано потому что:

  1. Самобалансирующееся — высота O(log n)
  2. Гарантированная производительность — O(log n) поиск в худшем случае
  3. Хорошее соотношение между скоростью вставки/удаления и поиском
  4. Не требует полной перебалансировки как AVL дерево
Сравнение Bucket структур:

1. Linked List (Java 7):
   - Insert: O(1)
   - Search: O(n)  ← ПЛОХО при коллизиях
   - Delete: O(n)

2. Red-Black Tree (Java 8+):
   - Insert: O(log n)
   - Search: O(log n)  ← ХОРОШО при коллизиях
   - Delete: O(log n)

3. Гибрид (Java 8+):
   - Малые bucket'ы: linked list (O(1) для поиска среди 5-6 элементов)
   - Большие bucket'ы: tree (O(log n) для поиска среди 1000+ элементов)

Практический пример воздействия

public class HashMapPerformance {
    
    // Симуляция плохого хеширования
    static class Integer8 {
        final int value;
        Integer8(int v) { this.value = v; }
        
        @Override public int hashCode() {
            return value & 7;  // только 8 возможных хешей (0-7)
        }
        @Override public boolean equals(Object o) {
            return o instanceof Integer8 && ((Integer8)o).value == this.value;
        }
    }
    
    public static void main(String[] args) {
        HashMap<Integer8, String> map = new HashMap<>();
        
        // Добавим 10_000 элементов
        // Они распределятся по 8 bucket'ам (из-за плохого хеша)
        // Каждый bucket получит ~1250 элементов
        
        long start = System.nanoTime();
        
        for (int i = 0; i < 10_000; i++) {
            map.put(new Integer8(i), "value" + i);
        }
        
        // Каждый bucket с 1250 элементами:
        // - С linked list: O(1250) в среднем при поиске
        // - С red-black tree: O(log 1250) ≈ O(10) при поиске
        // 
        // Улучшение: 1250 / 10 = 125x быстрее!
        
        long end = System.nanoTime();
        System.out.println("Time: " + (end - start) / 1_000_000 + "ms");
        
        // Теперь поиск:
        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            map.get(new Integer8(i));
        }
        end = System.nanoTime();
        System.out.println("Get time: " + (end - start) / 1_000_000 + "ms");
    }
}

Вывод

При достижении 8 элементов в корзине HashMap преобразуется в красно-черное дерево (при условии, что размер таблицы >= 64). Это улучшение из Java 8 защищает от degenerate cases плохого хеширования, гарантируя O(log n) операции вместо O(n). Обратное преобразование происходит при 6 элементах для избежания постоянного преобразования на границе.

Это классический пример практической оптимизации: гибридный подход (linked list для малых bucket'ов, tree для больших) дает лучшую производительность в большинстве случаев.