Перераспределяются ли элементы по новым корзинам при расширении HashMap

Что проверяют

Заглядывали ли вы внутрь HashMap или знаете его только как «ключ, значение». Вопрос с подвохом: почти все отвечают «да, перераспределяются, хеши пересчитываются», и вторая половина фразы неверна.

Как отвечать

Да, при расширении элементы переезжают, но пересчёта хеш-кодов не происходит. hashCode вызывается один раз при вставке, результат хранится в поле узла. Ёмкость всегда степень двойки, индекс корзины считается как (n - 1) & hash, то есть от хеша берутся младшие биты. При удвоении в игру входит ровно один новый бит, поэтому цепочка корзины делится надвое: элемент либо остаётся на прежнем индексе, либо уезжает на индекс + старая ёмкость, и решает это условие (hash & oldCap) == 0.

Дальше полезно назвать числа: коэффициент загрузки по умолчанию 0.75, начальная ёмкость 16, порог 12, таблица создаётся лениво на первой вставке. Длинная корзина при достаточно большой таблице превращается из списка в красно-чёрное дерево, а при расширении дерево тоже делится и может вернуться в список.

Где спотыкаются

Говорят про перехеширование и «новую хеш-функцию». Функция та же, меняется только маска индекса, и в Java это сделано так, чтобы разбирать корзину за один проход без вычисления хеша заново.

Второе: считают, что new HashMap<>(1000) вмещает тысячу записей без расширения. Порог это ёмкость, умноженная на коэффициент загрузки, так что запас нужен больше, либо используйте фабричный метод HashMap.newHashMap, который считает ёмкость сам.

Третье: путают расширение с потокобезопасностью. Одновременная запись из нескольких потоков ломает карту независимо от расширения: часть записей просто теряется. Для конкурентного доступа берётся ConcurrentHashMap, а не увеличенная начальная ёмкость.