`HashMap` — это структура данных, которая использует хеш-таблицу для хранения пар "ключ-значение". Gозволяет выполнять операции вставки, удаления и поиска элементов с почти постоянным временем выполнения, что делает её очень эффективной для определённых задач. Вот как она организована:

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

1. Хеш-функция: Ключи хранятся с использованием хеш-функции, которая преобразует ключ в индекс массива. Этот индекс используется для хранения значения в массиве. Она должна равномерно распределять ключи по индексам массива, чтобы минимизировать коллизии.

2. Массив бакетов (корзин): Внутри, она состоит из массива бакетов, где каждый бакет представляет собой "корзину", которая может хранить одну или более пар "ключ-значение". При добавлении новой пары "ключ-значение", хеш-функция вычисляет индекс бакета для хранения значения на основе хеш-кода ключа.

3. Связный список или дерево: В случае коллизии, когда два разных ключа имеют одинаковый хеш-код и попадают в один и тот же бакет, `HashMap` использует структуру данных в виде связного списка или дерева для хранения и разрешения коллизий. После определённого порога коллизий, список преобразуется в дерево для улучшения производительности поиска в этом бакете.

Работа

• Вставка: Для вставки новой пары "ключ-значение", сначала вычисляется хеш-код ключа, затем используется хеш-функция для определения индекса бакета. Если в бакете уже есть элементы, происходит проверка на наличие ключа с таким же хеш-кодом. Если такой ключ найден, его значение обновляется. Если ключ уникален, пара добавляется в бакет.
• Поиск: Поиск значения по ключу также начинается с вычисления хеш-кода ключа, определения индекса бакета и последующего поиска в связном списке или дереве этого бакета.
• Удаление: Удаление пары "ключ-значение" происходит аналогично поиску: сначала находится бакет, затем в нём ищется и удаляется элемент.

Расширение

Когда фактор заполнения `HashMap` превышает определённый порог, происходит автоматическое расширение массива бакетов и перехеширование всех элементов для равномерного распределения по новому массиву бакетов. Это обеспечивает высокую производительность `HashMap` даже при большом количестве элементов.

`HashMap` — это мощная и эффективная структура данных для хранения и быстрого доступа к данным через ключи. Благодаря использованию хеш-таблиц, `HashMap` обеспечивает быстрые операции вставки, поиска и удаления. Разрешение коллизий с помощью связных списков или деревьев и автоматическое расширение помогают поддерживать производительность на высоком уровне.

Feb. 22, 2024, easyoffer

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

Oct. 21, 2023, Источник