Хеширование в HashMap работает следующим образом: когда в HashMap добавляют ключ и значение, для ключа сразу высчитывается хэш. 1 Это числовой идентификатор, который указывает элементу, в какую ячейку памяти записаться. 3

Связь между значением элемента и его позицией в хеш-таблице задаёт хеш-функция. 2 Она получает входную часть данных (ключ), а на выходе выдаёт целое число — хеш-значение (или хеш-код). 2 Затем хеш-значение привязывает ключ к определённому индексу хеш-таблицы. 2

Для основных операций: вставки, поиска и удаления, используется одна и та же хеш-функция, поэтому эти операции осуществляются довольно быстро. 2

В идеальной ситуации хэш полностью индивидуален для каждого уникального объекта. 1 Но в реальности хэши могут совпадать у совершенно разных объектов. 1 Это происходит из-за несовершенства существующих алгоритмов. 1 Тогда значения обоих ключей окажутся записаны в одну «корзинку» — это и есть коллизия. 1

Чтобы избежать коллизий, для хранения значений используется связанный список: даже если случится коллизия, новое значение просто запишется в начало той же «корзинки», не изменив старое. 1