Почему в бакете map хранится 8 элементов?

Краткий ответ

Корректнее сказать, что бакет (bucket) в map Go изначально рассчитан на хранение до 8 пар ключ-значение. Это значение выбрано как компромисс между производительностью поиска, эффективностью использования памяти и уменьшением количества коллизий. Когда бакет заполняется, происходит разделение (splitting), и map растет.

Детальное объяснение

Архитектура map в Go

Map в Go реализована как хэш-таблица с отдельной цепочкой (chaining), но с важной особенностью:

// Упрощенная структура (runtime/map.go)
type hmap struct {
    count     int    // количество элементов
    flags     uint8
    B         uint8  // логарифм количества бакетов (2^B)
    noverflow uint16 // приблизительное количество переполненных бакетов
    buckets   unsafe.Pointer // массив из 2^B бакетов
    // ... другие поля
}

// Каждый бакет содержит:
type bmap struct {
    tophash  [bucketCnt]uint8 // массив хэшей
    keys     [bucketCnt]keytype
    values   [bucketCnt]valuetype
    overflow *bmap // указатель на следующий бакет при переполнении
}

bucketCnt определен в runtime как константа:

const bucketCnt = 8 // abi.MapBucketCount

Почему именно 8?

1. Производительность процессора и кэш-память

• 8 пар ключ-значение хорошо укладываются в кэш-линии современных процессоров (обычно 64 байта)
• При поиске в бакете процессор загружает в кэш сразу всю структуру, что минимизирует промахи кэша
• Меньшие бакеты увеличили бы накладные расходы (больше бакетов, больше указателей)
• Большие бакеты увеличили бы время поиска внутри бакета (линейный поиск)

2. Эффективность памяти

// Пример размера (для map[int]int, 64-битная система)
// Бакет содержит:
// - 8 байт tophash[0]    → 8 байт
// - 8 ключей по 8 байт   → 64 байта  
// - 8 значений по 8 байт → 64 байта
// - указатель overflow   → 8 байт
// Итого: ~144 байта на бакет

8 элементов — это баланс между плотностью данных и накладными расходами.

3. Статистика коллизий

• При хорошей хэш-функции вероятность коллизий для 8 элементов достаточно низка
• Формула вероятности коллизий при равномерном распределении показывает, что 8 — разумный порог
• Если хэш-функция качественная, большинство бакетов не будут заполняться полностью

4. Алгоритмическая эффективность

Поиск внутри бакета — линейный O(n):

// Упрощенный алгоритм поиска
for i := 0; i < bucketCnt; i++ {
    if b.tophash[i] == top {
        k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
        if key == k {
            // нашли ключ
            v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            return v
        }
    }
}

• 8 итераций — достаточно мало для быстрого линейного поиска
• Компилятор может оптимизировать цикл с фиксированным размером

Что происходит при переполнении?

Когда бакет заполняется 8 элементами и добавляется 9-й:

1. Создается overflow bucket (дополнительный бакет)
2. Новый элемент помещается в overflow bucket
3. Бакеты связываются в односвязный список через поле overflow

// Добавление при переполнении
if inserti == nil {
    // все бакеты заполнены, создаем новый
    newb := h.newoverflow(t, b)
    inserti = &newb.tophash[0]
    insertk = add(unsafe.Pointer(newb), dataOffset)
    val = add(insertk, bucketCnt*uintptr(t.keysize))
}

Динамический рост map

Когда слишком много overflow-бакетов (примерно 20% от общего числа), происходит rehashing:

• Увеличивается B (количество бакетов удваивается)
• Элементы перераспределяются по новым бакетам
• Этот процесс amortized O(1) благодаря инкрементальному перемещению ("evacuation")

func growWork(t *maptype, h *hmap, bucket uintptr) {
    // Перемещаем bucket и его overflow-цепочку
    evacuate(t, h, bucket&h.oldbucketmask())
    
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

Практические последствия

1. Предсказуемая производительность: Разработчики могут рассчитывать на определенное поведение
2. Хорошая локализация данных: Связанные элементы часто попадают в один бакет
3. Эффективная итерация: Данные хранятся плотно, что ускоряет итерацию по map

Пример в коде

package main

import (
    "fmt"
    "unsafe"
)

func main() {
    m := make(map[int]string)
    
    // Добавляем 9 элементов с коллизиями
    for i := 0; i < 9; i++ {
        // Используем ключи, которые могут давать коллизии
        m[i*16] = fmt.Sprintf("value%d", i)
    }
    
    // Начиная с 9-го элемента для одного бакета,
    // создается overflow bucket
    fmt.Printf("Длина map: %d\n", len(m))
    
    // Пример проверки наличия overflow
    // (в реальности нужен доступ к внутренней структуре)
}

Заключение

Число 8 в размере бакета map Go — результат тщательного инженерного компромисса, основанного на:

• Анализе производительности современных процессоров
• Эффективности использования памяти
• Статистических моделях коллизий хэшей
• Практических измерениях реальных workloads

Это значение позволяет достичь амортизированной O(1) сложности операций при разумном использовании ресурсов, что подтверждено годами эксплуатации в production-системах.