Какая сложность у HashMap если столкнулись с коллизией?

# Какая сложность у HashMap если столкнулись с коллизией?

Отличный вопрос, который проверяет глубокое понимание того, как HashMap работает под капотом. Ответ: O(n) в худшем случае, но на практике O(log n) благодаря красно-черным деревьям.

HashMap до Java 8 — O(n) при коллизиях

В старых версиях Java HashMap использовал цепочки (chains) для разрешения коллизий:

Пример коллизии:
hash("john") % 16 = 5
hash("john") % 16 = 5   // Коллизия! Обе строки хешируются в один bucket

Bucket 5: [("john", 30) -> ("jane", 25) -> ("jack", 35)]
           (связный список)

При коллизии нужно пройти по всей цепочке:

public V get(Object key) {
    int hash = hash(key);
    int index = hash % table.length;
    
    Entry e = table[index];
    while (e != null) {
        if (e.key.equals(key)) {
            return e.value;
        }
        e = e.next;  // O(n) если много коллизий!
    }
    return null;
}

В худшем случае все ключи хешируются в один bucket — O(n) временная сложность.

HashMap после Java 8 — O(log n)

Java 8 внесла решающее улучшение: если цепочка достигает 8 элементов, она преобразуется в красно-черное дерево!

// В HashMap.java (упрощенно)
static final int TREEIFY_THRESHOLD = 8;  // Порог преобразования в дерево

// Когда коллизия
private void putVal(int hash, K key, V value, ...) {
    // ...
    if (binCount >= TREEIFY_THRESHOLD - 1) {
        treeifyBin(tab, hash);  // Преобразовать в дерево!
    }
}

Цепочка с 8+ элементами преобразуется:

ДО (Linked List):         ПОСЛЕ (Red-Black Tree):
[1] -> [2] -> [3] ->          [5]
[4] -> [5] -> [6] ->         /   \
[7] -> [8]                  [3]   [7]
                           /  \   /  \
                        [1] [4][6] [8]

С красно-черным деревом поиск становится O(log n) вместо O(n).

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

public class HashMapCollisionDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        // Добавляем элементы, которые коллизируют
        map.put("John", 30);
        map.put("Jane", 25);
        map.put("Jack", 35);
        map.put("Jerry", 28);
        map.put("Jenny", 26);
        map.put("Joseph", 40);
        map.put("Joshua", 32);
        map.put("Jason", 29);  // 8-й элемент — преобразуется в дерево
        
        // После этого операции будут O(log n) вместо O(n)
        Integer age = map.get("John");  // O(log n) в дереве
    }
}

Сравнение сложности

Почему это важно

Кэш-атака (Denial of Service) была возможна в старых версиях:

// ДО Java 8: Атака через коллизии
// Если злоумышленник знает hash function, может создать
// ключи, которые все коллизируют, и HashMap станет O(n)

Map<String, Integer> map = new HashMap<>();
// Добавить 10000 ключей, все с одинаковым hash
for (int i = 0; i < 10000; i++) {
    map.put(createKeyWithSameHash(i), i);
}
// get() будет O(10000) вместо O(1) !

После Java 8 такая атака уже не работает, потому что дерево гарантирует O(log n).

Детали реализации в Java 8+

// Узел красно-черного дерева в HashMap
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
    TreeNode<K,V> parent;   // Родитель
    TreeNode<K,V> left;     // Левый потомок
    TreeNode<K,V> right;    // Правый потомок
    TreeNode<K,V> prev;     // Предыдущий
    boolean red;            // Цвет для балансировки
    
    // Операции поиска — O(log n)
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        // Бинарный поиск в дереве
    }
}

Когда цепочка снова становится меньше (например, при удалениях), дерево преобразуется обратно в список.

Правильный ответ на интервью

"В HashMap без коллизий операция O(1). Если возникают коллизии:

• До Java 8: O(n) — приходится искать в цепочке
• Java 8 и позже: O(log n) — цепочка из 8+ элементов преобразуется в красно-черное дерево

В практике с хорошей hash function и нормальным load factor (~0.75), коллизии редки, и средняя сложность остается близка к O(1)."

Совет для interview

Знание этой эволюции показывает, что ты:

• Понимаешь внутреннее устройство коллекций
• Осведомлен об истории Java и улучшениях
• Думаешь о security implications (DOS атаки)
• Аналитически подходишь к performance problems