Какая сложность поиска в хэшмапе при использовании сбалансированного дерева вместо связного списка

Что проверяют

Знаете ли вы, как устроен HashMap начиная с Java 8, и от чего именно защищает дерево в корзине. Следом спрашивают про пороги превращения и про ключи, которые не реализуют Comparable.

Как отвечать

Сначала главное: средняя сложность поиска остаётся O(1). Дерево меняет только худший случай, когда много ключей попали в одну корзину.

• до Java 8: корзина это связный список, при массовых коллизиях поиск деградирует до O(n);
• с Java 8: когда цепочка в корзине превышает TREEIFY_THRESHOLD = 8, список превращается в красно-чёрное дерево из TreeNode. Поиск в корзине стоит O(log k), где k это число элементов в ней, в худшем случае для всей карты O(log n);
• условие по ёмкости: если таблица меньше MIN_TREEIFY_CAPACITY = 64, вместо дерева делается resize, потому что коллизии, скорее всего, от маленькой таблицы;
• обратное превращение: при разделении корзины во время resize дерево из UNTREEIFY_THRESHOLD = 6 узлов и меньше снова становится списком.

Как дерево упорядочивает ключи: сначала по хэшу, затем, если ключи одного класса и реализуют Comparable, через compareTo. Для несравнимых ключей с одинаковым хэшем порядка нет, поиску приходится обходить оба поддерева, и гарантия O(log n) пропадает.

Зачем это нужно: защита от атак подбором коллизий, когда злоумышленник шлёт ключи с одинаковым хэшем и превращает каждый запрос в линейный проход. Цена: TreeNode примерно вдвое больше обычного узла, поэтому деревья включаются только при реальном скоплении.

Где спотыкаются

Говорят, что весь HashMap становится деревом и поиск теперь всегда O(log n). Дерево появляется только в перегруженной корзине, остальные остаются списками.

Забывают про порог ёмкости 64 и отвечают, что длинная цепочка всегда превращается в дерево.

Не упоминают hashCode и equals. hashCode, возвращающий константу, дерево частично спасает только для Comparable ключей, а правильное решение всё равно в исправлении хэша.