Как работает HashMap? Какие механизмы обеспечивают константную сложность поиска?

1. Основные принципы:

• Данные хранятся в массиве Node<K,V>[].

• Индекс корзины: hash(key) % capacity.

2. Решение коллизий:

• До Java 8: связные списки в корзинах.

• Java 8+: при большом количестве коллизий список преобразуется в красно-чёрное дерево (O(log n) вместо O(n)).

Пример:

Map<String, Integer> map = new HashMap<>();
map.put("a", 1); // Хеш "a" определяет корзину

Оптимизации:

• Load factor (по умолчанию 0.75): когда размер превышает capacity * load factor, массив удваивается.

• Хеш-функция: Object.hashCode() может переопределяться для равномерного распределения.