HashMap в Java реализован на основе массива бакетов, каждый из которых содержит связный список или дерево (TreeNode) элементов с одинаковым хеш-кодом. При добавлении элемента вычисляется хеш-код ключа, который используется для определения индекса бакета. Если бакет пуст, элемент помещается туда напрямую. Если нет — происходит поиск по списку или дереву для обновления значения или добавления нового узла.

Основные моменты работы:

При коллизиях используется цепочка (связный список) или дерево (если элементов много) для ускорения поиска.
При достижении определённого порога размера массива происходит расширение (rehash) с перераспределением элементов.
В Java 8 и выше для длинных цепочек используется преобразование в красно-чёрное дерево для улучшения производительности поиска.

Пример упрощённой логики вставки:

int hash = key.hashCode();
int index = (hash & 0x7fffffff) % table.length;
Node<K,V> node = table[index];
// если node == null, вставляем новый
// иначе ищем в цепочке или дереве, обновляем или добавляем

Таким образом, HashMap обеспечивает амортизированное время доступа O(1) при хорошем распределении хешей.

Как устроена HashMap внутри и как работает?