ℹ️ Как устроен под капотом HashMap?

HashMap — это коллекция, обеспечивающая хранение пар "ключ-значение" и быструю работу с элементами за амортизированное O(1) время для операций вставки и поиска.

🔹 Структура HashMap

В основе HashMap лежит массив, где каждый элемент представляет собой "корзину" (bucket), и эти корзины хранят связные списки или сбалансированные деревья. Как работает эта структура:

▪️ Ключи: Ключ должен быть иммутабельным, а также допускается null в качестве ключа.
▪️ Хэширование: Для вычисления индекса бакета HashMap находит хэш для ключа. Далее используется операция побитового И (&) хэш-функции и n-1, где n - текущий размер массива бакетов (index = (n - 1) & hash).
▪️ Коллизии и цепочки: Если несколько ключей попадают в одну корзину (коллизия), HashMap использует связные списки для хранения этих значений. Когда длина связного списка превышает 8 элементов, HashMap автоматически преобразует его в красно-черное дерево для повышения эффективности поиска и вставки, обеспечивая O(log n) сложность для операций в таких корзинах.

🔹 Производительность

▪️ Добавление: За амортизированное O(1) время. При добавлении ключа HashMap сначала вычисляет хэш, а затем индекс корзины, где будет храниться элемент. Если корзина пуста, добавляется новый элемент. Если элемент с таким ключом уже есть, он заменяется.
▪️ Удаление: В зависимости от структуры корзины, время удаления элемента составляет O(1) для небольших корзин или O(log n) для корзин, содержащих красно-черное дерево.
▪️ Поиск: За амортизированное O(1) время при низком уровне коллизий. Однако в случае высоких коллизий и преобразования корзины в дерево сложность поиска возрастает до O(log n).

🔹 Использование памяти

Каждый элемент HashMap хранит не только ключ и значение, но также ссылки на следующий элемент в связном списке (или ссылки в дереве, если оно используется). Для эффективной работы HashMap настраивается порог "коэффициента загрузки" (load factor), после которого размер массива увеличивается вдвое, чтобы сократить количество коллизий.

🔹 Преимущества и недостатки

▪️ Преимущества:
- Доступ к элементам за амортизированное O(1).
- Возможность использования как связных списков, так и красно-черных деревьев позволяет HashMap эффективно справляться с коллизиями.

▪️ Недостатки:
- HashMap не гарантирует порядок элементов, в отличие от, например, TreeMap.
- Ссылки на элементы создают определенные накладные расходы, а при увеличении массива корзин в процессе реасширения требуются дополнительные ресурсы.