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

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

Временная сложность поиска в HashMap в худшем случае зависит от версии Java и способа разрешения коллизий.

До Java 8: O(n)

В ранних версиях Java коллизии в HashMap разрешались исключительно через цепочки (chaining) — связные списки. В худшем случае, когда все ключи попадают в один bucket, поиск деградирует до O(n), где n — количество элементов.

// Пример: все ключи имеют одинаковый hashCode
class BadKey {
    @Override
    public int hashCode() { return 42; } // Всегда один bucket
}

Начиная с Java 8: O(log n)

В Java 8 был введён механизм treeification: когда количество элементов в одном bucket превышает порог TREEIFY_THRESHOLD = 8, связный список преобразуется в красно-чёрное дерево (Red-Black Tree). Это улучшает worst-case сложность до O(log n).

Обратное преобразование (untreeify) происходит при уменьшении до UNTREEIFY_THRESHOLD = 6.

Условия для treeification

Для преобразования в дерево необходимо выполнение двух условий:

• Количество элементов в bucket >= 8
• Общая ёмкость HashMap >= MIN_TREEIFY_CAPACITY = 64

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

Практические рекомендации

• Правильная реализация hashCode() — распределяйте хеши равномерно
• Используйте immutable ключи — String, Integer, enum
• Контролируйте load factor — по умолчанию 0.75, баланс памяти и скорости
• Профилируйте — используйте JMH для бенчмарков

Итог

Ключевой вывод: в современной Java (8+) worst-case сложность HashMap — O(log n) благодаря Red-Black Tree, но только при правильно работающем hashCode() и equals().