После какого количества элементов происходит переход в дерево

После какого количества элементов происходит переход в дерево

Этот вопрос про HashMap в Java, который трансформируется из простого массива в красно-чёрное дерево (Red-Black Tree) для оптимизации производительности.

Переход HashMap: Array → Tree

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

1. Array of Buckets — обычно быстро
2. Red-Black Tree — для конфликтующих элементов

Пороги преобразования

Пороги по умолчанию в Java 8+:

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

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

1. В одном bucket 8+ элементов (коллизии)
2. HashMap имеет минимум 64 элемента (MIN_TREEIFY_CAPACITY)

Если оба условия выполнены → дерево. Если нет → ещё увеличится размер HashMap.

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

1. В дереве осталось < 6 элементов (удаления)

Реальный пример

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

// Добавляем элементы с одинаковым hashCode()
// (в реальности это коллизии)

for (int i = 0; i < 7; i++) {
    map.put("key" + i, i);
}
// Bucket с коллизиями всё ещё список (7 < 8)

map.put("key8", 8);
// Теперь 8 элементов, но если HashMap < 64 элементов:
// → HashMap расширится до 64, коллизии распределятся
// → дерево НЕ создастся

// Добавляем 60+ элементов с коллизиями на один bucket
for (int i = 10; i < 70; i++) {
    map.put("collision" + i, i); // Все с одинаковым hash
}
// Теперь: 8+ элементов В ОДНОМ bucket + 64+ в HashMap
// → Дерево СОЗДАСТСЯ

Визуализация преобразования

До Java 8 (только список):

HashMap (size < 64, коллизии)
┌──────┬──────┬──────┬──────┐
│ null │ null │ node │ null │
│      │      │  │   │      │
│      │      │  v   │      │
│      │      │ node │      │
│      │      │  │   │      │
│      │      │  v   │      │
│      │      │ node │      │
└──────┴──────┴──────┴──────┘
      Linked List

Java 8+ с дерево (при условиях выполнены):

HashMap (size >= 64, коллизии >= 8)
┌──────┬──────┬───────┬──────┐
│ null │ null │ tree  │ null │
│      │      │  /\   │      │
│      │      │ /  \  │      │
│      │      │node  node   │
│      │      │/\     /\    │
└──────┴──────┴───────┴──────┘
    Red-Black Tree

Пример с реальными коллизиями

public class HashCollisionExample {
    
    // Класс с одинаковым hashCode
    static class BadKey {
        String value;
        
        BadKey(String value) {
            this.value = value;
        }
        
        @Override
        public int hashCode() {
            return 1; // ОДИН И ТОТ ЖЕ ХЕШ для всех!
        }
        
        @Override
        public boolean equals(Object o) {
            return value.equals(((BadKey) o).value);
        }
    }
    
    public static void main(String[] args) {
        HashMap<BadKey, String> map = new HashMap<>();
        
        // Добавляем 7 элементов
        for (int i = 0; i < 7; i++) {
            map.put(new BadKey("key" + i), "value" + i);
        }
        // Все в ОДНОМ bucket (linked list)
        
        // Добавляем 8-й
        map.put(new BadKey("key7"), "value7");
        // Теперь 8 элементов в одном bucket...
        // Но HashMap может быть < 64 → она расширится
        
        // Добавляем много больше
        for (int i = 8; i < 70; i++) {
            map.put(new BadKey("key" + i), "value" + i);
        }
        // Теперь: 8+ в bucket + 64+ в HashMap
        // → Дерево создано!
    }
}

Производительность

Linked List поиск в bucket: O(n)

Bucket: node1 → node2 → node3 → ... → node8
Поиск element7: 7 сравнений

Red-Black Tree поиск в bucket: O(log n)

Bucket:      node4
            /      \
         node2    node6
        /    \    /    \
      n1    n3  n5    n7
      
Поиск element7: 3 сравнения (log8 ≈ 3)

Реальное ускорение:

Сизе bucket = 1000 элементов (очень плохая hash функция)

Linked List: 1000 сравнений в среднем = 500
Red-Black Tree: log2(1000) ≈ 10 сравнений

Ускорение: 50x!

Кода Java HashMapа (упрощённо)

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

void putVal(int hash, K key, V value, ...) {
    // ... логика найти bucket ...
    
    if (binCount >= TREEIFY_THRESHOLD - 1) { // >= 7
        treeifyBin(tab, hash); // Попытка преобразовать
    }
}

void treeifyBin(Node<K,V>[] tab, int hash) {
    int n;
    
    // Если таблица слишком маленькая — расширить
    if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize(); // Увеличить HashMap
        return;
    }
    
    // Иначе преобразовать в дерево
    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<>(e.hash, e.key, e.value, null);
        // ... создать Red-Black tree
    }
}

Практические последствия

Хорошо написанный код:

HashMap<String, User> userMap = new HashMap<>();
// Hash функция распределяет элементы равномерно
// Коллизий почти нет → деревья НЕ создаются
// Производительность стабильная

Плохо написанный код:

HashMap<BadHashObject, String> map = new HashMap<>();
// BadHashObject.hashCode() возвращает одно число
// Все элементы в одном bucket
// При 64+ элементах → дерево
// Но уже потеряно времени на поиск!

Вывод

Переход из массива в дерево происходит при:

1. 8+ элементов в одном bucket (TREEIFY_THRESHOLD)
2. И одновременно 64+ элементов в HashMap (MIN_TREEIFY_CAPACITY)

Обратный переход при:

• < 6 элементов в дереве (UNTREEIFY_THRESHOLD) — обратно в список

Эта оптимизация скрытая от программиста — HashMap автоматически выбирает оптимальную структуру данных. Главное — правильно реализовать hashCode() и equals() в своих классах!