Как организована HashMap

HashMap — это структура данных на основе хеш-таблицы, которая хранит пары «ключ-значение» и обеспечивает почти постоянное время выполнения операций вставки, поиска и удаления. Внутри она организована как массив «корзин» (buckets), где каждая корзина может содержать связанный список или красно-чёрное дерево для разрешения коллизий.

Внутреннее устройство

HashMap использует хеш-функцию для преобразования ключа в индекс массива. Этот индекс определяет, в какую корзину будет помещена пара. Хеш-функция должна равномерно распределять ключи, чтобы минимизировать коллизии. В Java хеш-код ключа дополнительно обрабатывается методом hash(), который смешивает старшие и младшие биты для улучшения распределения.

Массив корзин — это обычный массив Node<K,V>[], где каждый элемент — либо null, либо ссылка на узел. Узел содержит ключ, значение, хеш и ссылку на следующий узел (для связанного списка).

При коллизии, когда два разных ключа попадают в одну корзину, элементы хранятся в виде связанного списка. Начиная с Java 8, если размер списка превышает порог TREEIFY_THRESHOLD (8), список преобразуется в красно-чёрное дерево. Это улучшает производительность поиска в корзине с O(n) до O(log n). Обратное преобразование в список происходит при уменьшении размера до UNTREEIFY_THRESHOLD (6).

Основные операции

• Вставка: вычисляется хеш ключа, определяется индекс корзины. Если корзина пуста, создаётся новый узел. Если в корзине уже есть элементы, происходит поиск по ключу: если ключ найден, значение обновляется; если нет — новый узел добавляется в конец списка (или в дерево).
• Поиск: аналогично вычисляется индекс, затем выполняется поиск в списке или дереве по ключу. Сравнение ключей происходит через equals().
• Удаление: сначала находится корзина, затем удаляется узел с соответствующим ключом. При удалении из дерева может потребоваться перебалансировка.

Расширение и перехеширование

HashMap имеет два важных параметра: начальная ёмкость (capacity) и коэффициент загрузки (load factor, по умолчанию 0.75). Когда количество элементов превышает capacity * load factor, происходит resize(): массив увеличивается в два раза, и все элементы перехешируются для распределения по новым корзинам. Это дорогая операция, поэтому важно выбирать начальную ёмкость с учётом ожидаемого количества элементов.

Подводные камни

• Не потокобезопасен: HashMap не синхронизирован. Для многопоточного доступа используйте ConcurrentHashMap или обёртку Collections.synchronizedMap().
• Порядок не гарантирован: порядок обхода элементов может меняться при изменении размера.
• Ключи должны быть неизменяемыми: если хеш-код ключа изменится после вставки, элемент станет недоступным.
• Коллизии могут деградировать производительность: при плохой хеш-функции или множестве коллизий производительность может упасть до O(n).

Коротко

• HashMap — хеш-таблица с массивом корзин, списками и деревьями для разрешения коллизий.
• Операции вставки, поиска и удаления в среднем выполняются за O(1).
• При превышении порога загрузки происходит расширение и перехеширование.
• Не потокобезопасен; для конкурентного доступа используйте ConcurrentHashMap.