Что такое HashMap и как он работает внутри?

Принцип работы

При добавлении элемента в HashMap методом put(key, value), сначала вычисляется хеш-код ключа. По значению этого хеш-кода определяется индекс в массиве бакетов (корзин), куда будет помещена пара.

Java ExampleКопировать

Map<String, Integer> map = new HashMap<>();
map.put("key", 100);
// hash() вычисляется неявно внутри метода

Внутренняя структура

Основной массив состоит из объектов типа Node. Каждый Node содержит в себе:

• final int hash — хеш-код ключа
• final K key — ссылка на ключ
• V value — текущее значение
• Node next — ссылка на следующий элемент в случае цепочки

Коллизии и их разрешение

Коллизия возникает, когда два разных ключа попадают в один бакет. HashMap разрешает такие ситуации методом цепочек: элементы связываются в список внутри бакета.

Начиная с Java 8, если длина связного списка в бакете превышает 8 элементов, он преобразуется в сбалансированное красно-черное дерево, что снижает сложность поиска с O(n) до O(log n).