Какая структура данных в Bucket в HashMap?

Какая структура данных в Bucket в HashMap

Этот вопрос был кардинально изменён в Java 8. Давай разберёмся, как эволюционировала структура HashMap и почему.

В Java 7 и ранее: Linked List

В старых версиях Java каждый bucket (корзина) был просто связным списком (linked list) с цепочкой элементов:

// До Java 8: простая структура
Node -> Node -> Node -> null

// Где Node выглядел так:
public class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next; // ссылка на следующий элемент в цепочке
}

Проблема: при большом количестве коллизий (много элементов в одном bucket) поиск деградировал до O(n) (линейный поиск по цепочке).

В Java 8+: Red-Black Tree (Красно-чёрное дерево)

Начиная с Java 8, HashMap оптимизирована: каждый bucket может содержать либо связный список, либо красно-чёрное дерево (binary search tree).

public class HashMap<K, V> {
    static final int TREEIFY_THRESHOLD = 8;  // порог преобразования в дерево
    static final int UNTREEIFY_THRESHOLD = 6; // порог преобразования обратно
    static final int MIN_TREEIFY_CAPACITY = 64; // минимум элементов для tree
    
    // Когда элементов в bucket > TREEIFY_THRESHOLD = 8,
    // структура автоматически преобразуется из List в Tree
}

Как это работает:

Нормальный случай (мало коллизий):
Bucket[0]: Node -> Node -> Node

Много коллизий (>8):
Bucket[5]: TreeNode (красно-чёрное дерево)
           /     \
        Node     Node
       /  \     /  \
    Node Node Node Node

Структура TreeNode в красно-чёрном дереве

// В HashMap есть внутренний класс TreeNode
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;    // предыдущий в порядке insertion
    boolean red;            // цвет для balanced tree (красно-чёрное дерево)
    
    // методы балансировки дерева
    // ...
}

Как работает преобразование (treeify)

public class HashMapBucketEvolution {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        
        // Добавляем элементы
        // Пока < 8 элементов в bucket - используется linked list
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");
        // ...
        
        // После 8-го элемента в одном bucket - преобразуется в дерево
        // Это происходит автоматически, если capacity >= MIN_TREEIFY_CAPACITY
    }
}

Условия treeify:

1. Количество элементов в bucket >= 8 (TREEIFY_THRESHOLD)
2. Размер всей HashMap >= 64 (MIN_TREEIFY_CAPACITY)

Если условие (2) не выполнено, вместо treeify происходит resize.

Преимущества Tree vs List

Пример: почему это важно

public class HashMapBucketComparison {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>(16);
        
        // Добавляем элементы с одинаковым хешем (worst case)
        // В Java 7: O(n) поиск по цепочке
        // В Java 8+: O(log n) поиск по дереву
        
        for (int i = 0; i < 1000; i++) {
            // Если хеши коллизируют, в Java 8 дерево даст ускорение
            map.put(i, "value_" + i);
        }
        
        // Поиск 500
        // Java 7: до 1000 сравнений в худшем случае
        // Java 8+: максимум ~10 сравнений (log2 1000)
        String value = map.get(500); // O(log n)
    }
}

Внутренняя структура элемента в HashMap

// Для обычного bucket (List):
static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
    
    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

// Для bucket с Tree:
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
    // Все поля Node плюс:
    TreeNode<K, V> parent;
    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode<K, V> prev;
    boolean red; // для балансировки
}

Процесс resize и treeify

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ...
    if (binCount >= TREEIFY_THRESHOLD - 1) // binCount = количество элементов в bucket
        treeifyBin(tab, hash); // преобразовать в дерево
}

final void treeifyBin(Node<K, V>[] tab, int hash) {
    if (tab.length < MIN_TREEIFY_CAPACITY) { // если мало всего
        resize(); // resize вместо treeify
        return;
    }
    // Иначе преобразуем связный список в красно-чёрное дерево
    // Все Node преобразуются в TreeNode
    TreeNode<K, V> hd = null, tl = null;
    for (Node<K, V> e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
        TreeNode<K, V> p = new TreeNode<>(e.hash, e.key, e.value, null);
        // построение дерева...
    }
}

Обратное преобразование (untreeify)

Когда элементы удаляются и размер bucket уменьшается до <= 6, дерево преобразуется обратно в список (для экономии памяти):

final void untreeify(HashMap<K, V> map) {
    // Преобразовать TreeNode обратно в Node
    // Это снижает память и улучшает cache locality для малых buckets
}

Сложность операций в HashMap

// До Java 8 в худшем случае (много коллизий):
get(key)    // O(n) - линейный поиск по цепочке
put(key)    // O(n)
remove(key) // O(n)

// Java 8+ в худшем случае:
get(key)    // O(log n) - поиск по дереву
put(key)    // O(log n) + балансировка
remove(key) // O(log n)

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

public class PerformanceTest {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // В Java 7: возможен ДДос через HashDoS
        // Если пришлют 1000000 элементов с одинаковым хешем,
        // HashMap будет работать O(n) = медленно
        
        // В Java 8: даже при hashDoS атаке производительность O(log n)
        // Это делает HashMap намного более устойчивой
    }
}

Вывод

• До Java 8: bucket = связный список (linked list)
• Java 8+: bucket = linked list при малом числе коллизий, красно-чёрное дерево при >8 элементах
• Преимущество: O(log n) вместо O(n) в случае коллизий
• Порог: TREEIFY_THRESHOLD = 8, UNTREEIFY_THRESHOLD = 6
• Минимум: MIN_TREEIFY_CAPACITY = 64 (размер всей HashMap)