Как работает HashMap при вставке ключа?

Question

HashMap вычисляет hashCode() ключа и определяет номер бакета.Если бакет пуст — элемент просто добавляется.Если бакет занят — происходит проверка на равенство ключей.При коллизии элементы хранятся в списке или дереве.При необходимости карта расширяется.

YeaHub · Accepted Answer

Процесс вставки состоит из нескольких логических шагов.Основная идеяHashMap хранит данные в массиве бакетов, индекс которых вычисляется по хешу ключа.Этапы вставкиПри выполнении:map.put(key, value);
происходит следующее:Вызывается key.hashCode()Хеш нормализуется (битовые операции)Вычисляется индекс бакетаПроверяется содержимое бакетаРабота с коллизиямиЕсли бакет уже содержит элементы:Сравниваются ключи через equals()Если ключ найден — значение заменяетсяЕсли ключ новый — он добавляется в структуру бакетаВозможные структуры:связанный списоккрасно-чёрное дерево (при большом числе элементов)Когда происходит расширениеРасширение (resize) происходит, если:количество элементов превышает capacity * loadFactorПри этом:создаётся новый массив бакетоввсе элементы перераспределяютсяВыводHashMap обеспечивает быстрый доступ за счёт хеширования, но корректная работа зависит от hashCode() и equals().