Какие проблемы решает HashMap и где проявляется её преимущество

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

Понимаете ли вы, откуда берётся «поиск за O(1)» и при каких условиях он перестаёт быть правдой. На Android следом часто спрашивают про SparseArray и ArrayMap: зачем они в SDK, если есть HashMap.

Как отвечать

Главная задача HashMap: найти значение по ключу, не перебирая всё подряд. Как это устроено:

• хэш и корзины: по hashCode() ключа вычисляется индекс в массиве, внутри корзины элементы сравниваются через equals(). Отсюда контракт: равные объекты обязаны давать равный хэш;
• рост: начальная ёмкость 16, коэффициент загрузки 0.75. Когда элементов становится больше, чем ёмкость, умноженная на коэффициент, массив удваивается и всё перераскладывается. Если размер известен заранее, задайте ёмкость в конструкторе;
• коллизии: элементы с одинаковым индексом лежат списком, а начиная с Java 8 длинная корзина (от 8 элементов при таблице от 64) превращается в красно-чёрное дерево, и худший случай становится O(log n), а не O(n);
• порядок: не гарантирован. В Kotlin mutableMapOf() возвращает LinkedHashMap, который хранит порядок вставки, а hashMapOf() даёт обычный HashMap.

Преимущество видно на частых поисках по ключу в большом наборе: кэш объектов по id, индекс для сопоставления двух списков вместо вложенного цикла.

Цену назовите сами: каждая запись это отдельный объект-узел, а ключи Int упаковываются в Integer. Поэтому на Android для числовых ключей есть SparseArray и LongSparseArray без упаковки, а для небольших карт ArrayMap с бинарным поиском: он экономнее по памяти, но медленнее на тысячах элементов. Для нескольких потоков нужен ConcurrentHashMap, обычный HashMap не синхронизирован.

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

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

Переопределяют equals() без hashCode(). В Kotlin это решает data class, но только для полей из основного конструктора.

Отвечают «всегда O(1)», не упоминая средний случай, перераспределение и цену памяти, которая на мобильном устройстве важнее, чем на сервере.