Как работает get в Map

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

Понимаете ли вы устройство HashMap изнутри, а не только его контракт. Следом обычно спрашивают про коллизии, про equals и hashCode у ключа и про то, почему на Android иногда советуют ArrayMap или SparseArray.

Как отвечать

Разберите HashMap.get(key) по шагам, как он устроен в OpenJDK, откуда взята и реализация в Android:

• хэш: берётся key.hashCode() и перемешивается как h ^ (h >>> 16), чтобы старшие биты тоже влияли на индекс. Ключ null допустим и лежит в корзине 0;
• индекс корзины: (n - 1) & hash, где n это размер таблицы. Он всегда степень двойки, поэтому остаток от деления заменяется битовой маской;
• поиск в корзине: сравнивается сначала хэш, затем ссылка ==, затем equals. Корзина это связный список, а с Java 8, когда в ней больше восьми элементов и в таблице от 64 корзин, она превращается в красно-чёрное дерево;
• результат: значение или null, если ключа нет.

Сложность в среднем O(1). В худшем случае, когда ключи попали в одну корзину, это O(log n) для дерева, а если ключи не реализуют Comparable, поиск может деградировать почти до линейного.

В Kotlin map[key] вызывает тот же get и возвращает V?, а getValue(key) бросает NoSuchElementException. Чтобы отличить отсутствие ключа от сохранённого null, нужен containsKey.

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

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

Берут в ключ изменяемый объект, например data class с var, меняют поле после put и получают null из get. Хэш изменился, и поиск идёт в другую корзину.

Переопределяют equals без hashCode. Равные объекты попадают в разные корзины, и get их не находит.

Называют худшим случаем O(n) без оговорок и не знают про деревья в корзинах. Или наоборот, советуют ArrayMap для тысяч элементов, где бинарный поиск и сдвиги массива уже проигрывают HashMap.