HashMap – это структура данных, основанная на массиве бакетов, где каждый бакет может содержать связный список или дерево объектов. Эффективность HashMap напрямую зависит от качества хеш-функции ключей.
Внутренне HashMap хранит массив бакетов (
Добавление элемента начинается с расчета индекса бакета на основе хеша ключа. Если бакет пуст, создается новый узел. При коллизии, новый элемент добавляется в связный список или дерево. Если элемент с таким ключом существует, его значение обновляется. При достижении порога заполнения массив бакетов расширяется.
Поиск элемента начинается с вычисления индекса бакета. Затем происходит поиск по связному списку или дереву. Сложность поиска в среднем O(1), при плохой хэш-функции O(n) (до 8 элементов), а при использовании дерева O(logN). Предварительная проверка наличия ключа с помощью
Изображение носит иллюстративный характер
Внутренне HashMap хранит массив бакетов (
table), количество элементов (size), порог заполнения (threshold) и коэффициент загрузки (loadFactor). Бакет представляет собой узел (Node), содержащий ключ, значение, хеш и ссылку на следующий узел. При переполнении бакета, связный список преобразуется в дерево. Добавление элемента начинается с расчета индекса бакета на основе хеша ключа. Если бакет пуст, создается новый узел. При коллизии, новый элемент добавляется в связный список или дерево. Если элемент с таким ключом существует, его значение обновляется. При достижении порога заполнения массив бакетов расширяется.
Поиск элемента начинается с вычисления индекса бакета. Затем происходит поиск по связному списку или дереву. Сложность поиска в среднем O(1), при плохой хэш-функции O(n) (до 8 элементов), а при использовании дерева O(logN). Предварительная проверка наличия ключа с помощью
containsKey() избыточна, достаточно проверять результат get() на null.
