Как устроена и работает HashMap в Java?

HashMap<K, V> — это реализация интерфейса Map, основанная на хеш-таблице. Она хранит пары «ключ-значение» и обеспечивает константное время выполнения O(1) для основных операций (get, put) в среднем случае.

Принцип работы put(key, value):

1. Вычисляется хеш-код ключа с помощью метода key.hashCode().
2. На основе хеш-кода вычисляется индекс корзины (bucket) в массиве: index = (n - 1) & hash, где n — текущая емкость массива.
3. Если корзина по этому индексу пуста — в нее помещается новый узел (Node<K,V>).
4. Если корзина уже содержит элементы (коллизия):
   • В Java 7 и ранее элементы связывались в односвязный список.
   • В Java 8+, если список становится длиннее порога (обычно 8), он преобразуется в сбалансированное бинарное дерево (TreeNode) для восстановления производительности до O(log n).

Пример:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 10); // 1. hash("apple"), 2. вычисление индекса, 3. сохранение
Integer count = map.get("apple"); // Аналогичный расчет для быстрого поиска

Важные характеристики и настройки:

• Начальная емкость (capacity): По умолчанию 16. Размер внутреннего массива корзин.
• Коэффициент загрузки (load factor): По умолчанию 0.75. При достижении size > capacity * loadFactor происходит rehashing — увеличение емкости вдвое и перераспределение всех элементов.
• Порядок: Не гарантирует порядок элементов. Для сохранения порядка вставки используйте LinkedHashMap.
• Допустимые значения: Позволяет один ключ null и множество значений null.
• Потокобезопасность: HashMap не является потокобезопасной. Для многопоточных сценариев используйте ConcurrentHashMap или синхронизацию через Collections.synchronizedMap().