🔑 Раздел 10 · Вопрос #21

Когда временная сложность может стать O(n)

Хотя в штатном режиме HashMap выполняет базовые операции (get, put, remove) за константное время $O(1)$, в неблагоприятных условиях временная сложность может деградировать до ли...

🔑 HashMap equals hashCode 📄 Исходный Markdown

🟢 Junior Level

Хотя в штатном режиме HashMap выполняет базовые операции (get, put, remove) за константное время $O(1)$, в неблагоприятных условиях временная сложность может деградировать до линейной — $O(N)$. Это означает, что время выполнения операции будет расти прямо пропорционально количеству сохраненных элементов.

Основные сценарии деградации до $O(N)$:

  1. Некачественная хеш-функция: Если метод hashCode() у ключей реализован некорректно (например, возвращает одно и то же число для всех объектов), все элементы попадают в одну корзину.
  2. Малый размер таблицы (capacity < 64): Даже если в одном бакете накопилось 8 коллизий, красно-чёрное дерево не создается, пока общая ёмкость таблицы меньше 64. Элементы остаются в связном списке, поиск по которому занимает $O(N)$.
  3. Ключи без интерфейса Comparable (в дереве коллизий): Если при совпадении хешей ключи не реализуют Comparable, поиск по красно-чёрному дереву вынужден рекурсивно обходить обе ветви, что вырождается в $O(N)$.
  4. Итерация по разреженной таблице: Полный обход элементов (forEach, entrySet) всегда требует времени $O(\text{capacity} + N)$, что при избыточной ёмкости может привести к миллионам пустых проверок.
// Катастрофический пример: хеш-код всегда возвращает константу
class BrokenKey {
    private final String id;

    public BrokenKey(String id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return 42; // Все ключи попадут в один и тот же бакет!
    }

    @Override
    public boolean equals(Object obj) {
        return (obj instanceof BrokenKey other) && this.id.equals(other.id);
    }
}

Аналогия: Представьте картотеку на 100 ящиков. Если архивариус ошибается и складывает все документы в одну единственную папку, то для поиска нужной бумаги придется перебрать всю кипу документов лист за листом ($O(N)$), а остальные 99 ящиков будут бессмысленно пустовать.

🟡 Middle Level

Сравнительный анализ сценариев деградации

Сценарий Причина деградации Временная сложность get/put Способ устранения
Java 7 (наследие) Отсутствие деревьев; коллизии разрешаются только списками $O(N)$ Переход на Java 8+
capacity < 64 при коллизиях Таблица предпочитает resize() вместо трификации $O(N)$ (на этапе роста) Качественный hashCode(), начальный capacity >= 64
Коллизии ключей без Comparable Поиск в TreeNode не знает направления обхода (left/right) $O(N)$ при одинаковых хешах Реализация Comparable<T> у класса ключа
Hash Flooding DoS Злоумышленник целенаправленно генерирует ключи с одинаковым хешем $O(N)$ (Java 7) / $O(\log N)$ (Java 8+) Использование String (реализует Comparable)
Итерация по entrySet() Сканирование всех незаполненных слотов массива $O(\text{capacity} + N)$ Задавать capacity строго под ожидаемый размер

Детальный разбор: барьер MIN_TREEIFY_CAPACITY = 64

В Java 8+ для защиты от деградации до $O(N)$ связный список бакета превращается в красно-чёрное дерево (TreeNode) при достижении 8 элементов (TREEIFY_THRESHOLD = 8).

Однако трификация происходит только при выполнении дополнительного условия: \(\text{table.length} \ge 64\)

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // Вместо создания дерева удваиваем таблицу!
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // Создание красно-чёрного дерева (TreeNode)
    }
}

Если у вас создана стандартная new HashMap<>() (начальная ёмкость 16) с плохими ключами:

  • 8-й элемент в одном бакете $\to$ ресайз до 32 (список сохраняется, $O(N)$).
  • 9-й элемент в том же бакете $\to$ ресайз до 64 (список сохраняется, $O(N)$).
  • Лишь после достижения ёмкости 64 следующий вызов treeifyBin конвертирует бакет в дерево со сложностью поиска $O(\log N)$.

🔴 Senior Level

Главный миф Java 8+: почему TreeNode может деградировать до $O(N)$

Многие разработчики уверены, что начиная с Java 8 худший случай в HashMap гарантированно составляет $O(\log N)$. Это опасное заблуждение.

Изучим метод поиска find в классе HashMap.TreeNode:

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> q, pl = p.left, pr = p.right;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr; // Направленный спуск O(log N)
        else if ((q = pr.find(h, k, kc)) != null) // Внимание сюда!
            return q;
        else
            p = pl; // Рекурсивный поиск по обеим ветвям!
    } while (p != null);
    return null;
}

Механизм деградации:

  1. Если у всех ключей хеш-код совпадает (ph == h), бинарное дерево не может разветвляться по хешу.
  2. HashMap пытается получить класс сравнения: comparableClassFor(k).
  3. Если ключ НЕ реализует Comparable<K>:
    • Метод не может определить, в какую ветвь идти (dir неизвестен).
    • Алгоритм запускает рекурсивный вызов по правому поддереву: pr.find(h, k, kc).
    • Если элемент там не найден, он спускается по левому поддереву: p = pl.
    • Результат: Происходит полный обход всех вершин бинарного дерева поиска (Full Tree Traversal). Поиск несуществующего ключа обходит абсолютно каждый узел, деградируя ровно до $O(N)$!

Атака Hash Flooding (DoS) и CVE-2011-4858

В конце 2011 года исследователи продемонстрировали практическую DoS-атаку на веб-серверы (Tomcat, Jetty, PHP, Node.js). Злоумышленник отправлял один специально сформированный HTTP POST-запрос с десятками тысяч параметров формы, чьи строковые имена генерировали одинаковый hashCode() (например, "AaAa", "BBBB", "AaBB").

В Java 7:

  • Сервер помещал параметры в HashMap<String, String>.
  • Все $N$ параметров попадали в один бакет в виде связного списка.
  • Для вставки каждого нового параметра put просматривал всю цепочку существующих элементов для проверки equals().
  • Суммарная сложность вставки $N$ элементов: \(\sum_{i=1}^{N} i = \frac{N(N-1)}{2} = O(N^2)\)
  • Запрос из 50 000 параметров замораживал ядро CPU на 5–10 минут.

В Java 8+ класс String реализует Comparable<String>. При коллизиях бакет становится деревом, а поиск и вставка выполняются за $O(N \log N)$ вместо $O(N^2)$, что полностью нейтрализует фатальный эффект атаки.

4 Tricky Questions

1. Если разработчик написал класс ключа с фиксированным hashCode() { return 1; }, но забыл реализовать Comparable, какая временная сложность будет у map.get() при 1 000 000 элементов в Java 21?

Ответ: Сложность будет строго $O(N)$. Так как хеш-коды одинаковы, все элементы окажутся в одном бакете. Таблица превысит порог 64 и превратится в TreeNode. Однако при вызове get() метод TreeNode.find не сможет вызвать compareTo(). Ему придется рекурсивно обходить и левое, и правое поддеревья каждого узла. В худшем сценарии (поиск отсутствующего ключа) JVM обойдет все 1 000 000 узлов, что займет линейное время $O(N)$.

2. Почему операция put() в HashMap без коллизий может внезапно занять $O(N)$ времени?

Ответ: Это происходит в момент срабатывания процедуры resize(). Если текущее количество элементов size превышает threshold (например, при вставке 13-го элемента в таблицу емкостью 16), HashMap выделяет новый массив удвоенного размера и переносит туда все $N$ существующих элементов. Хотя амортизированная сложность последовательности вставок составляет $O(1)$, единичный конкретный вызов put() в момент ресайза занимает строго линейное время $O(N)$.

3. Является ли сложность итерации map.keySet() равной $O(N)$ деградацией?

Ответ: Нет, это штатное поведение структуры данных. Сложность итератора HashMap описывается как $O(\text{capacity} + N)$. Итератор вынужден последовательно перебирать весь внутренний массив ссылок table. Если в таблице емкостью 1 000 000 хранится всего 5 элементов, итератор совершит 1 000 000 проверок на null, что формально пропорционально размеру массива ($O(C)$), а не числу элементов. Для сценариев с частой итерацией по разреженным данным следует использовать LinkedHashMap, где поддерживается непрерывный двусвязный список элементов со сложностью обхода строго $O(N)$.

4. Зачем в методе treeifyBin при коллизии из 8 элементов проверяется условие tab.length < 64, вместо немедленного создания дерева?

Ответ: Превращение бакета в красно-чёрное дерево — дорогая операция:

  1. TreeNode весит 56–64 байта (вместо 32 байт у стандартного Node).
  2. Построение дерева требует аллокации новых объектов и балансировки (повороты, перекрашивания).

Если общий размер таблицы еще мал ($< 64$), появление 8 элементов в одном бакете чаще всего обусловлено случайной скученностью при малом числе ячеек. Вызов resize() удваивает емкость и добавляет 1 бит к маске индексации (n - 1) & hash, что с вероятностью $\approx 50\%$ разделяет скопившиеся элементы по двум разным бакетам без лишних затрат памяти на TreeNode.

🎯 Шпаргалка для интервью

  • Когда сложность $O(N)$:
    • Неправильный hashCode() (все ключи в одном бакете) + отсутствие Comparable у ключей.
    • Таблица размером $< 64$ при наличии $\ge 8$ коллизий в одном бакете.
    • Старая версия платформы (Java 7 и ниже, где нет TreeNode).
    • Разовый вызов put() в момент срабатывания resize().
    • Поиск в красно-чёрном дереве ключей с одинаковым хешем без реализации Comparable.
  • Миф о гарантированном $O(\log N)$: Дерево TreeNode гарантирует $O(\log N)$ только для ключей, реализующих Comparable<K>. Без него TreeNode.find рекурсивно обходит обе ветви ($O(N)$).
  • Hash Flooding DoS: Атака на Java 7 через подбор коллизий ($O(N^2)$ при наполнении). В Java 8+ нейтрализована деревьями для строк.
  • Итерация: Штатная сложность обхода keySet()/entrySet() составляет $O(C + N)$.

Связанные темы