Какие ключевые изменения были внесены в HashMap в Java 8?

В Java 8 HashMap был значительно оптимизирован для обработки коллизий и итерации.

Основные изменения:

1. Переход на красно-черное дерево в корзинах с коллизиями

   • Было: При коллизиях (одинаковый hashCode для разных ключей) элементы в одной корзине хранились в односвязном списке. В худшем случае поиск был O(n).
   • Стало: Когда размер списка в корзине превышает порог (TREEIFY_THRESHOLD = 8), он преобразуется в красно-черное дерево. Поиск в худшем случае становится O(log n). При уменьшении размера дерево снова преобразуется в список.

2. Улучшение хеш-функции

   • Изменен алгоритм вычисления индекса корзины для снижения вероятности коллизий при плохих хеш-кодах.

3. Оптимизация итераторов

   • Введен улучшенный Spliterator для более эффективного параллельного обхода.

Пример и последствия:

HashMap<KeyWithBadHash, Integer> map = new HashMap<>();
// Если множество ключей возвращает один hashCode(),
// в Java 7 поиск по map.get() деградировал до O(n).
// В Java 8 при >8 коллизий в корзине поиск будет O(log n).

Итог: Эти изменения защитили HashMap от атак на производительность через искусственное создание коллизий и улучшили работу в высоконагруженных сценариях.