Какой худший случай поиска элемента в HashMap?

Худший случай поиска в HashMap

Временная сложность

Худший случай поиска элемента в HashMap составляет O(n), хотя в среднем это O(1). Давайте разберёмся, почему так происходит.

Нормальный сценарий (O(1))

В идеальном случае HashMap распределяет элементы равномерно по своим бакетам (массиву):

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 10);
map.put("key2", 20);
int value = map.get("key1"); // O(1) — прямой доступ по хешу

Худший случай (O(n)): hash collision

Худший случай наступает, когда множество элементов имеют одинаковый hash code. В этом случае все они попадают в один бакет, и HashMap вынужден переходить по цепочке для поиска нужного элемента:

class BadHashKey {
    private String value;
    
    @Override
    public int hashCode() {
        return 0; // Все объекты возвращают одинаковый хеш
    }
    
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof BadHashKey)) return false;
        return value.equals(((BadHashKey) obj).value);
    }
}

HashMap<BadHashKey, String> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    map.put(new BadHashKey("key" + i), "value" + i);
}
BadHashKey search = new BadHashKey("key500");
String result = map.get(search); // O(n) — перебор по цепочке

Почему Java 8 улучшил это

До Java 8 при массовых коллизиях использовались linked lists. С Java 8 бакет автоматически преобразуется в красно-чёрное дерево (TreeMap), снижая сложность до O(log n):

if (binCount >= TREEIFY_THRESHOLD) { // порог = 8
    treeifyBin(tab, hash); // преобразование в дерево
}

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

1. Плохая реализация hashCode() — возвращает одно значение для разных объектов
2. Малое количество бакетов — при высокой загрузке
3. Целенаправленная атака — DDoS через предсказуемые хеши

Лучшие практики

public class GoodKey {
    private String id;
    private int version;
    
    @Override
    public int hashCode() {
        return Objects.hash(id, version); // Использует все поля
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof GoodKey)) return false;
        GoodKey other = (GoodKey) obj;
        return Objects.equals(id, other.id) && version == other.version;
    }
}

Итоги

• Средний случай: O(1) — нормальное распределение хешей
• Худший случай: O(n) в Java 7, O(log n) в Java 8+ благодаря деревьям
• Причина: коллизии хешей
• Решение: правильная реализация hashCode() и equals()