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

HashMap основан на массиве бакетов (Node<K, V>[] table), где каждый бакет содержит связанный список или дерево.

🔹 Ключевые моменты

— Для хеширование ключа вызывается hashCode(), после чего вычисляется индекс массива через (n - 1) & hash, где n – размер массива.
— Если несколько ключей попадают в один бакет, создаётся связанный список. Если число элементов в бакете превысит 8, список заменяется на красно-чёрное дерево для ускорения поиска.
— Если загрузка (size / capacity) превышает 0.75, размер массива увеличивается в 2 раза, а элементы перераспределяются.
— Поиск идёт по бакету: если элементов несколько, перебирается список (или дерево), сравниваются hashCode() и equals().
— HashMap обеспечивает O(1) для операций get() / put(), но при частых коллизиях или неправильных hashCode() может деградировать до O(log n).