Как устроена HashMap

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

1. Вычисляется хэш-код ключа (через hashCode()).
2. На основе хэша определяется индекс бакета (обычно hash % capacity).
3. Если бакет пуст — элемент добавляется. Если нет — происходит проверка на совпадение ключей (через equals()). При совпадении значение перезаписывается, иначе элемент добавляется в список/дерево.

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);  // Хэш "apple" -> индекс бакета -> сохранение
map.put("banana", 2);

При достижении определенного порога заполнения (по умолчанию 75%) HashMap увеличивает capacity и перехеширует все элементы. В Java 8+ при большом количестве коллизий списки преобразуются в сбалансированные деревья для улучшения производительности.