Как устроен HashMap

HashMap — это хэш-таблица, состоящая из массива «корзин» (buckets). Каждая корзина хранит ссылку на связный список (или красно-черное дерево с Java 8) объектов Node<K,V>.

Алгоритм добавления элемента (put):

1. Вычисляется hashCode() ключа.
2. Хэш дополнительно перемешивается: hash = hashCode ^ (hashCode >>> 16) (для лучшего распределения).
3. Определяется индекс корзины: index = hash & (capacity - 1).
4. Если корзина пуста — создается новый Node.
5. Если корзина занята — обходится список/дерево в корзине, сравнивая ключи через equals(). Если ключ найден — значение заменяется. Если не найден — элемент добавляется в конец.
6. Если количество элементов в корзине достигает порога TREEIFY_THRESHOLD (8) — список преобразуется в красно-черное дерево (при условии, что общая capacity >= 64).

Алгоритм поиска (get): аналогичен шагам 1-3, затем поиск в списке/дереве корзины через equals().

На собеседовании: объясните полный цикл put: hashCode -> перемешивание -> индекс корзины -> обход списка -> treeification. Упомяните TREEIFY_THRESHOLD = 8.