Как работает HashMap при добавлении элемента?

HashMap хранит данные в виде массива корзин, где каждая корзина соответствует диапазону хешей.

Общая идея работы

HashMap использует hashCode ключа для быстрого определения места хранения значения.

Шаги добавления элемента

При вызове put(key, value) происходит следующее:

1. Вычисляется hashCode() у ключа

2. Хеш преобразуется в индекс массива

3. Определяется корзина (bucket)

4. Проверяется, есть ли элементы в корзине

Обработка коллизий

Если корзина не пуста:

1. Происходит сравнение ключей через equals()

2. Если ключ найден

   • Значение перезаписывается

3. Если ключ не найден

   • Создается новый элемент в корзине

Структура корзины

В зависимости от количества элементов:

1. Сначала используется связанный список

2. При большом количестве элементов — дерево (начиная с Java 8)

Пример

Map<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);

Если у ключей разные хеши, они попадут в разные корзины.

Краткий вывод

Добавление в HashMap основано на hashCode и equals.
Правильная реализация этих методов критична для производительности.