Для чего нужна HashMap и в каких кейсах используется

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

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

Как отвечать

HashMap это хеш-таблица: массив корзин, индекс корзины вычисляется из hashCode() ключа. Отсюда поиск, вставка и удаление в среднем за O(1). Детали, которые стоит назвать:

• ёмкость и load factor: по умолчанию 16 корзин и коэффициент 0.75. Когда элементов становится больше, чем ёмкость на коэффициент, массив удваивается, и записи раскладываются заново;
• коллизии: записи с одинаковым индексом лежат цепочкой. С Java 8 длинная цепочка (от 8 элементов при таблице от 64 корзин) превращается в красно-чёрное дерево, и худший случай становится O(log n);
• равенство ключей: сначала сравнивается хеш, потом equals(). Ключу нужны согласованные equals и hashCode, в Kotlin их генерирует data class;
• ограничения: один null-ключ допустим, порядок обхода не гарантирован, потокобезопасности нет.

Кейсы: кеш объектов по id, группировка и частотный подсчёт, поиск вместо перебора списка, дедупликация. Нужен порядок вставки, берут LinkedHashMap (с accessOrder из неё получается LRU), нужна сортировка, TreeMap. В Kotlin mutableMapOf() возвращает LinkedHashMap, а HashMap даёт hashMapOf().

Android-специфика: SparseArray для ключей int без автоупаковки, ArrayMap экономнее по памяти на коллекциях до сотен элементов, но медленнее на больших, LruCache для кеша с ограничением размера. Для доступа из нескольких потоков или корутин на Dispatchers.Default берут ConcurrentHashMap.

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

Используют изменяемый объект как ключ и меняют его после вставки. Хеш уже другой, запись лежит в старой корзине, и get её не находит.

Утверждают, что доступ всегда O(1). Это среднее при хорошей хеш-функции, а hashCode, возвращающий константу, сваливает всё в одну корзину.

Пишут в обычную HashMap из нескольких потоков. Итог: потерянные записи и неконсистентное состояние, которое не воспроизводится в отладке.