По какому принципу выбирается бакет в HashMap для хранения ключа и как вычисляется индекс бакета

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

Знаете ли вы устройство HashMap глубже уровня «хеш по модулю размера», и понимаете ли, что в Android коллекции из java.util это не единственный вариант. Вопрос быстро уходит в память и в выбор структуры под задачу.

Как отвечать

HashMap не берёт hashCode() ключа напрямую: он перемешивает его, складывая через xor со сдвигом на шестнадцать бит вправо. Индекс считается как (n - 1) & hash, где n это длина массива бакетов и всегда степень двойки, поэтому побитовое И заменяет остаток от деления. Из младших битов и берётся индекс, отсюда и нужда в перемешивании: иначе ключи, отличающиеся только старшей половиной хеша, встали бы в один бакет.

Коллизии складываются в список внутри бакета, длинный список превращается в дерево. Когда заполнение превышает коэффициент загрузки, массив удваивается и элементы раскладываются заново.

Для Android стоит добавить, что hashMapOf в Kotlin это тот же java.util.HashMap, а hashCode у data class собирается из свойств основного конструктора. И что на небольших словарях платформа предлагает ArrayMap (два массива и бинарный поиск по хешам, меньше накладных объектов) и SparseArray для ключей типа Int без упаковки в Integer.

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

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

Кладут в ключи data class с изменяемым свойством. После правки поля объект теряется в мапе, а на экране это выглядит как случайно пропавший элемент списка.

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