Какая скорость поиска в HashMap в лучшем и худшем случае и при использовании красно-черного дерева

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

Знаете ли вы, что происходит внутри HashMap при коллизиях начиная с Java 8, и можете ли назвать точные пороги. Формула «O(1) в среднем, O(n) в худшем» устарела наполовину. Следом часто спрашивают, почему дерево включается не сразу и когда гарантия O(log n) не работает.

Как отвечать

• лучший и средний случай: O(1). Индекс корзины считается как (n - 1) & hash, где hash это hashCode() ключа с подмешанными старшими битами (h ^ (h >>> 16)). Ёмкость всегда степень двойки, по умолчанию 16, коэффициент загрузки 0.75: при превышении таблица удваивается, и цепочки остаются короткими;
• худший случай без дерева: O(n). Так было до Java 8: если много ключей попадало в одну корзину, поиск шёл по связному списку и вызывал equals у каждого. Сейчас корзина остаётся списком, пока она короткая;
• корзина-дерево: когда в корзину, где уже 8 элементов (TREEIFY_THRESHOLD), добавляется ещё один, а ёмкость таблицы не меньше 64 (MIN_TREEIFY_CAPACITY), список превращается в красно-чёрное дерево из TreeNode. Поиск в такой корзине O(log n). При ёмкости меньше 64 таблица вместо этого расширяется. Если при ресайзе в корзине остаётся 6 элементов или меньше (UNTREEIFY_THRESHOLD), дерево снова становится списком.

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

Для сравнения: TreeMap целиком построен на красно-чёрном дереве и даёт O(log n) на любую операцию, зато держит ключи отсортированными.

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

Говорят, что дерево включается при 8 элементах всегда. Пока ёмкость меньше 64, сработает ресайз, а не превращение в дерево.

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

Ломают ключи сами: меняют поле, от которого зависит hashCode(), уже после put. Элемент остаётся в старой корзине, и get его не находит, неважно, список там или дерево.