Как выбирается место для хранения объекта в хэш-таблице

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

Понимаете ли вы, как HashMap превращает ключ в номер ячейки и что происходит при коллизиях и росте таблицы. На Android следом часто спрашивают, чем HashMap отличается от ArrayMap и SparseArray и когда их брать.

Как отвечать

Разберите путь ключа на примере java.util.HashMap, который используется и в Kotlin на JVM, и на Android:

• хэш-код: вызывается key.hashCode(), затем старшие биты подмешиваются к младшим: h ^ (h >>> 16). Без этого при маленькой таблице работали бы только младшие биты;
• индекс: (n - 1) & hash, где n это длина массива, всегда степень двойки. Это аналог остатка от деления, но дешевле и без отрицательных индексов;
• размер: по умолчанию 16 ячеек и коэффициент загрузки 0.75. Когда элементов становится больше 12, массив удваивается, и каждый элемент остаётся в своей ячейке i или переезжает в i + n;
• коллизии: цепочки. В ячейке лежит связный список, поиск идёт сравнением хэша и equals(). Если в одной ячейке набирается 8 элементов, а таблица не меньше 64, список превращается в красно-чёрное дерево, и худший случай становится O(log n) вместо O(n);
• другие стратегии: открытая адресация с пробированием есть в IdentityHashMap, во внутренней ThreadLocalMap, в словарях Python. В обычном HashMap её нет.

Для Android добавьте платформенную часть. ArrayMap хранит хэши в отсортированном массиве и ищет двоичным поиском, это O(log n), зато без объекта-обёртки на каждую запись, и на коллекциях до нескольких сотен элементов он экономнее по памяти. SparseArray работает с ключами int без упаковки в Integer. Для больших коллекций с частыми вставками HashMap остаётся быстрее.

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

Называют формулу hashCode % length. В Java остаток от отрицательного хэш-кода отрицательный, поэтому реализация использует маску и размер степенью двойки.

Меняют поле ключа после put(): хэш-код меняется, и запись становится недостижимой. Ключи должны быть неизменяемыми.

Переопределяют equals() без hashCode(). Равные объекты попадают в разные ячейки, и containsKey() возвращает false для ключа, который лежит в карте.