Спросят с вероятностью 56%
HashMap — это структура данных, которая использует хеш-таблицу для хранения пар "ключ-значение". Gозволяет выполнять операции вставки, удаления и поиска элементов с почти постоянным временем выполнения, что делает её очень эффективной для определённых задач. Вот как она организована:
Внутреннее устройство
1️⃣ Хеш-функция: Ключи хранятся с использованием хеш-функции, которая преобразует ключ в индекс массива. Этот индекс используется для хранения значения в массиве. Она должна равномерно распределять ключи по индексам массива, чтобы минимизировать коллизии.
2️⃣ Массив бакетов (корзин): Внутри, она состоит из массива бакетов, где каждый бакет представляет собой "корзину", которая может хранить одну или более пар "ключ-значение". При добавлении новой пары "ключ-значение", хеш-функция вычисляет индекс бакета для хранения значения на основе хеш-кода ключа.
3️⃣ Связный список или дерево: В случае коллизии, когда два разных ключа имеют одинаковый хеш-код и попадают в один и тот же бакет,
HashMap использует структуру данных в виде связного списка или дерева для хранения и разрешения коллизий. После определённого порога коллизий, список преобразуется в дерево для улучшения производительности поиска в этом бакете.Работа
- Вставка: Для вставки новой пары "ключ-значение", сначала вычисляется хеш-код ключа, затем используется хеш-функция для определения индекса бакета. Если в бакете уже есть элементы, происходит проверка на наличие ключа с таким же хеш-кодом. Если такой ключ найден, его значение обновляется. Если ключ уникален, пара добавляется в бакет.
- Поиск: Поиск значения по ключу также начинается с вычисления хеш-кода ключа, определения индекса бакета и последующего поиска в связном списке или дереве этого бакета.
- Удаление: Удаление пары "ключ-значение" происходит аналогично поиску: сначала находится бакет, затем в нём ищется и удаляется элемент.
Расширение
Когда фактор заполнения
HashMap превышает определённый порог, происходит автоматическое расширение массива бакетов и перехеширование всех элементов для равномерного распределения по новому массиву бакетов. Это обеспечивает высокую производительность HashMap даже при большом количестве элементов.HashMap — это мощная и эффективная структура данных для хранения и быстрого доступа к данным через ключи. Благодаря использованию хеш-таблиц,
HashMap обеспечивает быстрые операции вставки, поиска и удаления. Разрешение коллизий с помощью связных списков или деревьев и автоматическое расширение помогают поддерживать производительность на высоком уровне.➡️ Примеры ответов
➡️ Список всех вопросов на Java Developer
🧩 Идущий | 🔐 Собесы | 🔐 Тестовые