HashMap в Java 8.

О работе HashMap спрашивают и джуниоров, и сеньоров. Часто всё сводится к рассказу о бакетах и оценке сложности на базе статей 1998 года. С тех времён много изменилось. Этот пост о текущей структуре, особенностях и недостатках HashMap.

❓Как устроен HashMap?
В основе HashMap лежит массив начальных элементов, которые называют бакетами. Их количество зависит от количества элементов — подбирается ближайшая степень двойки. Если элементов 20, то создаётся 32 бакета.
Если хэш-функция ключа распределяет значения равномерно, то в каждом бакете будет 0 или 1 элемент.
На практике такое происходит редко, и значения хэшей элементов иногда совпадают. Тогда элементы с одинаковым хэш кодом организуются в список. Если их становится больше 8, то элементы перестраиваются в двоичное дерево.

❓Как определяется нужный бакет?
Популярное заблуждение - по остатку деления хэша на количество бакетов. Это не совсем так. Количество бакетов кратно степени двойки, и при вычислении используется логическое И.
В массиве из 16 бакетов последний элемент имеет номер 15, в битовом представлении это 1111. Операция & оставит последние 4 бита числа.
Сравним:

hash % 16
hash & 15

Результат будет одинаковый, но логическое И выполняется в 2 раза быстрее. Вычисление бакета — частая операция в HashMap, и такая микрооптимизация даёт хороший прирост в производительности.

❓Что такое load factor и зачем он нужен?
HashMap быстро работает, когда в бакете 0 или 1 элемент. При добавлении элементов повышается шанс, что в одном бакете их будет несколько, a HashMap станет менее эффективен. Поэтому HashMap периодически расширяется. Параметр load factor определяет, когда это происходит. По умолчанию равен 0.75.
Пример: в HashMap 20 элементов и 32 бакета. Когда элементов будет 32*0.75=24, количество бакетов удвоится и элементы перераспределятся по ним.

❓Какие недостатки у HashMap?
1️⃣ Cильная зависимость от функции распределения хэшей.
2️⃣ Неэкономный расход памяти. При load factor = 0.75 будет пустовать 25% памяти. При неравномерном распределении хэшей — ещё больше.

❓В конструкторе HashMap проставляются свойства, а массив бакетов создаётся только при первой вставке. Зачем нужна ленивая инициализация?
Расширение HashMap — долгая операция. Когда добавляется набор элементов, можно сразу увеличить массив до необходимого размера. Очень популярный случай - когда в пустой HashMap добавляютcя элементы другой map:

Map result=new HashMap();
...
result.putAll(anotherMap);

Если бы внутренняя структура result создавалась в конструкторе, пришлось бы тут же её расширять. С отложенной инициализацией можно этого избежать.

А теперь разберём вопрос про порядок элементов:
✅ Обход HashMap происходит последовательно - бакет за бакетом. Поэтому задание сводится к определению бакетов, в которые попадут значения. Это и будет порядок вывода элементов:

10 % 16 = 10
20 % 16 = 4
30 % 16 = 14

Ответ: 20 10 30