Всегда ли в бакете HashMap в Java используется связанный список

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

Знаете ли вы устройство HashMap глубже, чем «массив списков». Правильный ответ: нет, не всегда, с Java 8 бакет может стать красно-чёрным деревом. Следом спрашивают, при каком условии это происходит и зачем вообще понадобилось.

Как отвечать

Индекс бакета считается по хэшу ключа, который HashMap дополнительно перемешивает: h ^ (h >>> 16), чтобы старшие биты участвовали в выборе ячейки. Пока коллизий мало, в бакете лежит односвязный список узлов Node.

Дальше три константы из исходников:

• TREEIFY_THRESHOLD = 8: когда длина списка в бакете превышает восемь, список превращается в дерево из узлов TreeNode;
• MIN_TREEIFY_CAPACITY = 64: если сама таблица меньше 64 бакетов, вместо дерева HashMap увеличивает таблицу, это дешевле;
• UNTREEIFY_THRESHOLD = 6: при расщеплении бакета во время resize() дерево из шести и меньше элементов снова становится списком.

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

Зачем это нужно: при нормальном hashCode восемь элементов в одном бакете почти невероятны, в комментарии к исходникам вероятность оценена порядка шести на сто миллионов. Деревья страхуют от плохих хэш-функций и от атак, когда ключи с одинаковым хэшем подбирают специально, чтобы положить сервис. Тот же приём применяется в ConcurrentHashMap.

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

Называют только порог восемь и забывают про минимальную ёмкость 64. На маленькой таблице длинный бакет вызовет resize(), а не превращение в дерево.

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

Путают бакет HashMap с LinkedHashMap. Двусвязный список в LinkedHashMap хранит порядок вставки по всей карте и к коллизиям отношения не имеет.