Что такое хэшмап
Что проверяют
Знаете ли вы, как HashMap устроен внутри, а не только что он «быстро ищет по ключу». Следом почти всегда спрашивают про контракт equals/hashCode и про то, что на Android иногда берут вместо HashMap.
Как отвечать
HashMap хранит пары ключ-значение в массиве корзин (бакетов). Номер корзины считается из hashCode() ключа: хэш перемешивается (h ^ (h >>> 16)) и берётся по маске (n - 1) & hash, поэтому размер таблицы всегда степень двойки.
- коллизии: разные ключи могут попасть в одну корзину, тогда элементы лежат цепочкой. С Java 8 цепочка длиннее восьми элементов при таблице от 64 корзин превращается в красно-чёрное дерево, и худший случай становится O(log n) вместо O(n);
- ёмкость и load factor: по умолчанию 16 корзин и коэффициент 0.75. При превышении порога таблица удваивается и элементы перераспределяются, это дорогая операция. Если размер известен заранее, задайте начальную ёмкость;
- сложность: вставка, поиск и удаление в среднем O(1), при плохом
hashCodeдеградируют; - потокобезопасность: её нет. Для общего доступа из нескольких потоков берут
ConcurrentHashMap; - порядок: не гарантирован. Нужен порядок вставки:
LinkedHashMap, сортировка:TreeMap.
Для Android добавьте две вещи. В Kotlin mutableMapOf() возвращает LinkedHashMap, а hashMapOf() обычный HashMap. На небольших коллекциях, до сотен элементов, экономнее по памяти ArrayMap и SparseArray из android.util (или их аналоги из androidx.collection): они хранят данные в плотных массивах и ищут бинарным поиском, а SparseArray с ключом Int ещё и избавляет от автоупаковки.
Где спотыкаются
Говорят, что хэш-функция даёт уникальный индекс. Не даёт: корзин меньше, чем возможных ключей, коллизии неизбежны, и весь механизм построен вокруг их обработки.
Переопределяют equals, но забывают hashCode. Тогда два равных объекта попадают в разные корзины, и get возвращает null для ключа, который вроде бы лежит в мапе.
Кладут в ключ изменяемый объект и меняют его поля после вставки. Хэш меняется, элемент остаётся в старой корзине и становится недоступен.