Как выбирается bucket при добавлении элемента в HashMap?

При добавлении элемента HashMap должен определить, в какую ячейку внутреннего массива его положить.

Общий принцип

Определение:
Bucket — это позиция во внутреннем массиве HashMap, в которой хранятся элементы с одинаковым индексом.

Этапы выбора bucket

Процесс состоит из нескольких шагов.

1. Получение hashCode

   • вызывается метод hashCode() у ключа

   • ключ обязан соблюдать контракт equals / hashCode

2. Дополнительное перемешивание

   • старшие и младшие биты комбинируются

   • это снижает вероятность коллизий

3. Вычисление индекса

   • используется побитовая операция

   • индекс попадает в диапазон массива

int hash = key.hashCode();
int index = (hash ^ (hash >>> 16)) & (n - 1);

Что происходит при коллизии

• элементы попадают в один bucket

• сначала используется связанный список

• при большом количестве элементов — дерево

Важные последствия

• плохой hashCode() ведет к деградации производительности

• изменение ключа после вставки ломает доступ к элементу

Краткий вывод

Bucket в HashMap выбирается на основе обработанного hashCode() ключа, а качество этого хеша напрямую влияет на производительность структуры.