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

Question

HashMap использует hashCode() ключа для вычисления номера bucket. Хеш дополнительно обрабатывается, а затем применяется операция по модулю размера массива. Это позволяет равномерно распределять элементы. В одном bucket может храниться несколько элементов при коллизиях.

YeaHub · Accepted Answer

При добавлении элемента HashMap должен определить, в какую ячейку внутреннего массива его положить.Общий принципОпределение:Bucket — это позиция во внутреннем массиве HashMap, в которой хранятся элементы с одинаковым индексом.Этапы выбора bucketПроцесс состоит из нескольких шагов.Получение hashCodeвызывается метод hashCode() у ключаключ обязан соблюдать контракт equals / hashCodeДополнительное перемешиваниестаршие и младшие биты комбинируютсяэто снижает вероятность коллизийВычисление индексаиспользуется побитовая операцияиндекс попадает в диапазон массиваint hash = key.hashCode();
int index = (hash ^ (hash >>> 16)) & (n - 1);
Что происходит при коллизииэлементы попадают в один bucketсначала используется связанный списокпри большом количестве элементов — деревоВажные последствияплохой hashCode() ведет к деградации производительностиизменение ключа после вставки ломает доступ к элементуКраткий выводBucket в HashMap выбирается на основе обработанного hashCode() ключа, а качество этого хеша напрямую влияет на производительность структуры.