Ответ
В текущей реализации map в Go каждый бакет (bucket) действительно может напрямую хранить до 8 пар ключ-значение. Это значение (bucketCnt = 8) — константа, выбранная разработчиками языка как эмпирический компромисс.
Почему именно 8?
Это баланс между скоростью доступа и использованием памяти:
- Если бы число было меньше (например, 4): Для хранения того же количества элементов потребовалось бы больше бакетов. Это увеличило бы расход памяти на метаданные и указатели, а также вероятность коллизий, требующих создания цепочек бакетов.
- Если бы число было больше (например, 16): Поиск элемента внутри одного бакета (который является линейным) стал бы медленнее. Кроме того, для маленьких
mapмного памяти внутри бакетов оставалось бы неиспользованной.
Число 8 обеспечивает хорошую производительность для большинства сценариев использования.
Что происходит при заполнении бакета?
Когда в бакет нужно добавить 9-й элемент (из-за коллизии хешей), происходит следующее:
Переполняющиеся бакеты (Overflow Buckets): Go не увеличивает размер самого бакета. Вместо этого он выделяет дополнительный "overflow" бакет и связывает его с основным, образуя связанный список бакетов. Поиск будет продолжаться по этой цепочке.
Рост карты (Map Growth / Rehashing): Важно понимать, что рост
map(выделение вдвое большего массива бакетов и перенос всех элементов) происходит не когда один конкретный бакет заполнился, а когда коэффициент загрузки (load factor) превышает определенное значение (около 6.5). Это означает, что в среднем на каждый бакет приходится 6.5 элементов (включая overflow-бакеты). Заполнение одного бакета — это лишь симптом, который способствует увеличению этого коэффициента.
Структура бакета (упрощенно):
// go/src/runtime/map.go
type bmap struct {
// tophash хранит старшие байты хешей для быстрого поиска
tophash [8]uint8
// далее идут непрерывные массивы ключей и значений
// keys [8]keytype
// values [8]valuetype
// overflow указывает на следующий бакет в цепочке
overflow *bmap
}