Как происходит поиск элемента внутри бакета Map в Java: по хэшу или equals

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

Знаете ли вы, как устроен HashMap изнутри, и понимаете ли, что правильный ответ «и то и другое, в определённом порядке». Следом обычно спрашивают про контракт equals и hashCode и про то, что происходит с корзиной, в которой скопилось много элементов.

Как отвечать

Путь get(key) в HashMap начиная с Java 8:

• хэш: берётся key.hashCode(), и его старшие биты подмешиваются к младшим: h ^ (h >>> 16). Это нужно, потому что индекс считается только по младшим битам;
• индекс корзины: (n - 1) & hash, где n это размер таблицы, всегда степень двойки. По умолчанию корзин 16, а когда элементов становится больше, чем 0.75 от ёмкости, таблица удваивается;
• поиск в корзине: у каждого узла сначала сравнивается сохранённый хэш (дешёвое сравнение int), затем ссылки через ==, и только потом вызывается equals. Так дорогой equals для чужих ключей почти не вызывается;
• дерево вместо списка: если в корзине набирается 8 узлов и таблица не меньше 64 корзин, список превращается в красно-чёрное дерево, и поиск в худшем случае идёт за O(log n) вместо O(n). Если таблица меньше, вместо этого делается resize. Когда узлов становится 6 и меньше, дерево снова превращается в список. Внутри дерева узлы упорядочены по хэшу, а при совпадении по compareTo, если ключ реализует Comparable.

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

Для полноты упомяните TreeMap: там ни hashCode, ни equals не участвуют, всё решает compareTo или переданный Comparator.

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

Нарушают контракт: переопределяют equals, но не hashCode. Равные объекты попадают в разные корзины, и get возвращает null для ключа, который лежит в карте.

Используют изменяемый объект как ключ и после put меняют поле, участвующее в хэше. Запись остаётся в старой корзине, и найти её уже нельзя.

Говорят, что при коллизиях сложность всегда O(n). С Java 8 переполненная корзина становится деревом, хотя полный выигрыш получают только ключи, реализующие Comparable.