Как изменилась работа с коллизиями в HashMap в Java 8

Изменения обработки коллизий в HashMap в Java 8

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

Как работало ДО Java 8

В Java 7 и ранее HashMap полностью полагался на связные списки (linked list) для хранения элементов с одинаковым хешем.

Проблема: если множество элементов хешируются в одну ячейку, то поиск становится O(n) вместо O(1):

// Плохой сценарий в Java 7
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < 1000000; i++) {
    // Если все ключи имеют одинаковый хеш -> одна большая linked list
    map.put("key" + i, i);
}
// get операция в худшем случае: O(n)
Integer val = map.get("key500000");  // нужно пройти через 500000 элементов!

Java 8: Революционное изменение — Red-Black Tree

В Java 8 введена иерархическая структура:

• До 8 элементов в bucket'е: связный список
• 8+ элементов -> преобразование в Red-Black Tree
• Tree остается пока элементов не станет < 6

Ключевые параметры:

• TREEIFY_THRESHOLD = 8 — если уже 8 элементов, то 9-й будет в дереве
• UNTREEIFY_THRESHOLD = 6 — если осталось < 6, обратно в список
• MIN_TREEIFY_CAPACITY = 64 — деревья только при размере таблицы >= 64

Порядок трансформации

public class HashMapVisualization {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        
        // Шаг 1: элементы 1-7 -> связный список в одном bucket'е
        for (int i = 0; i < 7; i++) {
            map.put(i, "value" + i);  // Все имеют одинаковый хеш
        }
        // Состояние: bucket = Node -> Node -> ... (список)
        
        // Шаг 2: 8-й элемент
        map.put(7, "value7");
        // Состояние: список, 8 элементов
        
        // Шаг 3: 9-й элемент
        map.put(8, "value8");
        // ТРАНСФОРМАЦИЯ! bucket = TreeNode (красно-чёрное дерево)
        // Теперь поиск: O(log n) вместо O(n)
        
        // Поиск: O(log 9) примерно 3 операции вместо 9 в списке
        String val = map.get(8);  // Очень быстро!
    }
}

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

При 1000 элементов, все в одном bucket'е:

Java 7: O(n)

• Время поиска 1000-го элемента: около 500 операций в среднем
• Для 1M элементов: около 500000 операций

Java 8: O(log n)

• Время поиска 1000-го элемента: около 10 операций (log2(1000))
• Для 1M элементов: около 20 операций
• УСКОРЕНИЕ: в 25000 раз!

Почему Red-Black Tree?

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

• O(log n) для поиска, вставки, удаления
• Хорошо сбалансирован
• Детерминированные операции
• Меньше памяти, чем другие сбалансированные деревья
• Хорошо изучен и надежен

Внутренний механизм (упрощено)

// Момент, когда происходит преобразование
private void putVal(int hash, K key, V value, ...) {
    Node<K,V>[] tab;
    
    if (binCount >= TREEIFY_THRESHOLD - 1) {
        // binCount = количество элементов в bucket'е
        treeifyBin(tab, hash);
    }
}

private final void treeifyBin(Node<K,V>[] tab, int hash) {
    // Не создавать дерево, если таблица еще маленькая
    if (tab == null || tab.length < MIN_TREEIFY_CAPACITY) {
        resize();  // сначала расширить таблицу
        return;
    }
    
    // Преобразование связного списка в красно-чёрное дерево
    TreeNode<K,V> hd = null, tl = null;
    for (Node<K,V> e = tab[index]; e != null; e = e.next) {
        TreeNode<K,V> p = new TreeNode<>(e.hash, e.key, e.value, null);
        if (tl == null)
            hd = p;
        else {
            p.prev = tl;
            tl.next = p;
        }
        tl = p;
    }
    tab[index] = hd.treeify(null);  // балансировка дерева
}

Защита от DoS атак

Это изменение критично для защиты от Hash Collision DoS:

Раньше (Java 7): злоумышленник мог отправить ключи, которые все хешируются в одно значение. HashMap.get() становится O(n) для каждого ключа -> отказ в обслуживании.

Теперь (Java 8): даже с коллизиями get() остается O(log n) благодаря дереву -> невозможна DoS атака через hash collision.

Практический пример

public class HashMapTreeExample {
    public static void main(String[] args) {
        HashMap<CustomKey, String> map = new HashMap<>();
        
        // Создаем 100 ключей с одинаковым хешем
        for (int i = 0; i < 100; i++) {
            map.put(new CustomKey(i), "value" + i);
        }
        
        // Java 8: быстро (O(log 100) примерно 7 операций)
        // Java 7: медленно (O(100) операций)
        long start = System.nanoTime();
        String val = map.get(new CustomKey(50));
        long end = System.nanoTime();
        
        System.out.println("Time: " + (end - start) + " ns");
    }
    
    static class CustomKey {
        int id;
        CustomKey(int id) { this.id = id; }
        
        @Override
        public int hashCode() {
            return 42;  // Все ключи имеют одинаковый хеш!
        }
        
        @Override
        public boolean equals(Object o) {
            return o instanceof CustomKey && 
                   ((CustomKey)o).id == this.id;
        }
    }
}

Итоговые улучшения Java 8

Параметр | Java 7 | Java 8 | Улучшение

• Худший случай (много коллизий): O(n) | O(log n) | примерно 100000х для 1M элементов
• Устойчивость к DoS: Нет | Да | Защита от атак
• Память: n связей | n связей + дерево структура | плюс 10-20 процентов
• Скорость в норме: O(1) | O(1) | Без изменений

Заключение

Изменение в Java 8 — это фундаментальное улучшение HashMap:

• Безопасность: защита от Hash Collision DoS атак
• Производительность: O(log n) вместо O(n) в худшем случае
• Надежность: предсказуемая производительность

Это отличный пример того, как язык эволюционирует, чтобы защитить разработчиков от ошибок и атак.