Что такое bucket в HashMap и что в нем хранится?

Question

Bucket — это ячейка внутреннего массива HashMap. В bucket хранятся все элементы, у которых совпал индекс после вычисления hashCode(). Если элементов несколько, они объединяются в структуру внутри bucket’а. Это может быть список или дерево. Bucket используется для локального поиска ключей.

YeaHub · Accepted Answer

HashMap внутри использует массив, а bucket — это элемент этого массива.Что такое bucketBucket — это контейнер для элементов с одинаковым индексом хеша.Индекс вычисляется на основе:hashCode() ключаразмера внутреннего массиваЧто хранится внутри bucketВнутри bucket может быть:пусто — если ключей нетодин элемент — наиболее частый случайнесколько элементов — при коллизияхЕсли элементов несколько:сначала используется связанный списокпри превышении порога список преобразуется в деревоЗачем нужен bucketBucket:локализует поискуменьшает количество сравненийповышает производительностьБез bucket’ов HashMap пришлось бы искать ключи по всей структуре.Влияние качества hashCodeХороший hashCode():равномерно распределяет ключиуменьшает коллизииснижает нагрузку на bucket’ыПлохой hashCode():перегружает отдельные bucket’ызамедляет операцииВывод: bucket — ключевой элемент производительности HashMap, напрямую зависящий от качества hashCode().