Что такое коллизия в хэшмапе

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

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

Как отвечать

Коллизия это ситуация, когда два разных ключа попадают в одну корзину (bucket) внутреннего массива. Причин две: одинаковый hashCode() у разных объектов, как у строк "Aa" и "BB" (у обеих 2112), или разные хэши, которые после приведения к размеру массива дали один индекс. Второй случай неизбежен: значений int около четырёх миллиардов, а корзин по умолчанию 16.

Как с этим живёт java.util.HashMap (на Android он взят из OpenJDK, поведение то же):

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

Открытая адресация, когда при коллизии ищется следующая свободная ячейка, это другой способ, в HashMap он не используется.

Для Android уместно добавить ArrayMap и SparseArray: они хранят отсортированный массив хэшей и ищут бинарным поиском, экономят память на маленьких коллекциях, но проигрывают на сотнях и тысячах элементов. SparseArray к тому же обходится без упаковки ключей Int.

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

Приводят в пример анаграммы вроде «cat» и «act». Строковый хэш в Java зависит от порядка символов, у этих строк он разный.

Переопределяют equals без hashCode. Два равных объекта окажутся в разных корзинах, и get вернёт null. В Kotlin это решает data class, но только для полей из основного конструктора.

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