Что хранит красно-черное дерево в HashMap?

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

Роль красно-чёрного дерева

С Java 8 в HashMap используется красно-чёрное дерево (Red-Black Tree) для оптимизации производительности при большом количестве коллизий хеша. Каждая ячейка бакета может содержать цепь элементов, организованную как красно-чёрное дерево вместо простого связного списка.

Что именно хранит красно-чёрное дерево

Красно-чёрное дерево в HashMap хранит пары ключ-значение (Entry объекты) того же содержимого, которое могло бы быть просто в связном списке:

private static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
    Node<K, V> left;
    Node<K, V> right;
    Node<K, V> parent;
    boolean red;  // Цвет узла (красный или чёрный)
    
    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

Каждый узел красно-чёрного дерева хранит:

• hash — хеш код ключа
• key — ключ
• value — значение
• left, right, parent — ссылки для структуры дерева
• red — флаг цвета узла

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

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

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

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

Структура TreeNode

TreeNode — это расширенная версия Node, которая добавляет древовидную структуру:

private 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;
    
    TreeNode(int hash, K key, V value, Node<K, V> next) {
        super(hash, key, value, next);
    }
    
    final TreeNode<K, V> find(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 ((kc != null ||
                    (kc = comparableClassFor(k)) != null) &&
                    (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else
                p = pl;
        } while (p != null);
        return null;
    }
}

Преимущества красно-чёрного дерева

1. Улучшенная производительность при коллизиях

• Поиск в связном списке: O(n)
• Поиск в красно-чёрном дереве: O(log n)

2. Автоматическая балансировка Красно-чёрное дерево поддерживает себя в сбалансированном состоянии благодаря правилам:

• Каждый узел либо красный, либо чёрный
• Корень всегда чёрный
• Листья (null) считаются чёрными
• Красный узел не может иметь красного потомка
• Все пути от узла до листьев содержат одинаковое количество чёрных узлов

Пример коллизии с преобразованием

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

// Если много элементов с одинаковым хешем
for (int i = 0; i < 10; i++) {
    String key = "key" + i;  // Предположим, все имеют одинаковый хеш
    map.put(key, "value" + i);
}
// При 8 элементах в одной ячейке произойдёт преобразование в дерево

// Поиск теперь будет за O(log n) вместо O(n)
String value = map.get("key5");

Заключение

Красно-чёрное дерево в HashMap хранит те же пары ключ-значение, что и связный список, но организует их в сбалансированную древовидную структуру для повышения производительности поиска с O(n) до O(log n) при частых коллизиях. Это автоматическое преобразование происходит при достижении порога в 8 элементов в одной ячейке.