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

HashMap внутри использует массив, а bucket — это элемент этого массива.

Что такое bucket

Bucket — это контейнер для элементов с одинаковым индексом хеша.

Индекс вычисляется на основе:

• hashCode() ключа

• размера внутреннего массива

Что хранится внутри bucket

Внутри bucket может быть:

• пусто — если ключей нет

• один элемент — наиболее частый случай

• несколько элементов — при коллизиях

Если элементов несколько:

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

• при превышении порога список преобразуется в дерево

Зачем нужен bucket

Bucket:

• локализует поиск

• уменьшает количество сравнений

• повышает производительность

Без bucket’ов HashMap пришлось бы искать ключи по всей структуре.

Влияние качества hashCode

Хороший hashCode():

• равномерно распределяет ключи

• уменьшает коллизии

• снижает нагрузку на bucket’ы

Плохой hashCode():

• перегружает отдельные bucket’ы

• замедляет операции

Вывод: bucket — ключевой элемент производительности HashMap, напрямую зависящий от качества hashCode().