Как распределяются элементы между бакетами в Map в Java
Что проверяют
Знает ли кандидат реальную формулу индекса бакета в HashMap, зачем хеш перемешивается перед использованием и при каких условиях цепочка превращается в дерево.
Как отвечать
HashMap хранит массив Node[] table, длина которого всегда степень двойки. Индекс бакета считается маской, а не остатком: index = (n - 1) & hash, где n длина таблицы. Формула hashCode % length звучит в ответах постоянно и она неверна.
Перед этим хеш ключа перемешивается: hash = h ^ (h >>> 16). Маска берёт только младшие биты, и без подмешивания старших ключи, различающиеся лишь в верхней половине хеша, легли бы в один бакет.
Коллизии и деревья:
- записи с одинаковым индексом складываются в односвязный список внутри бакета;
- при длине цепочки от 8 и размере таблицы не меньше 64 список превращается в красно-чёрное дерево, поиск в бакете становится O(log n). Про второе условие забывают: если таблица меньше 64, вместо построения дерева делается расширение;
- при уменьшении узлов до 6 дерево разворачивается обратно в список.
Рост таблицы: ёмкость по умолчанию 16, коэффициент загрузки 0.75, при превышении порога размер удваивается. Хеши при этом не пересчитываются: благодаря степени двойки цепочка делится ровно надвое, и элемент либо остаётся на месте, либо уезжает на oldCap позиций вперёд, что определяется одним битом hash & oldCap.
Контракт ключа: равные по equals объекты обязаны давать одинаковый hashCode, иначе элемент не найдётся. Ключ должен быть неизменяемым по полям, участвующим в хеше: мутация после вставки теряет запись. Внутри бакета сравнение идёт сначала по сохранённому хешу, затем по equals, поэтому дорогой equals при хорошей хеш-функции почти не вызывается.
Сложность: O(1) в среднем, O(log n) в худшем случае после превращения в дерево (до Java 8 худший случай был O(n)).
Соседние реализации для сравнения: LinkedHashMap использует те же бакеты, но добавляет двусвязный список и хранит порядок вставки или обращения (accessOrder, основа LRU-кеша). TreeMap бакетов не имеет вовсе, это красно-чёрное дерево с сортировкой по компаратору. HashMap не потокобезопасен, для конкурентного доступа берут ConcurrentHashMap с блокировкой на уровне отдельного бакета.
Где спотыкаются
Называют hashCode % length и не помнят про подмешивание старших битов. При разговоре о превращении цепочки в дерево упоминают порог 8 и забывают второе обязательное условие про размер таблицы 64.