Как map хранит данные внутри?

Внутренняя структура map в Go

Map (хеш-таблица) в Go — это сложная структура данных, которая организована для обеспечения эффективных операций вставки, удаления и поиска при сохранении безопасности для конкурентного доступа (в рамках чтения).

Базовые компоненты

Внутри map представлена структурой hmap (объявлена в runtime/map.go):

type hmap struct {
    count     int    // количество элементов
    flags     uint8
    B         uint8   // log_2 от количества корзин (buckets = 2^B)
    noverflow uint16  // приблизительное количество переполненных корзин
    hash0     uint32  // seed для хеш-функции
    
    buckets    unsafe.Pointer // массив из 2^B корзин
    oldbuckets unsafe.Pointer // предыдущий массив корзин во время роста
    nevacuate  uintptr        // прогресс эвакуации
    
    extra *mapextra // дополнительные поля для хранения overflow корзин
}

Ключевые аспекты организации данных

1. Корзины (buckets) и хеширование

Каждая корзина содержит до 8 пар ключ-значение. При вставке элемента:

• Вычисляется хеш-код ключа через hash(key, hash0)
• Младшие B бит хеша определяют номер корзины
• Старшие 8 бит используются для быстрого сравнения ключей внутри корзины (tophash)

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

2. Разрешение коллизий методом цепочек

Если корзина заполнена (все 8 слотов заняты), создается новая overflow корзина, которая связывается через указатель overflow. Это реализует метод цепочек (chaining).

3. Отдельное хранение ключей и значений

В Go ключи и значения хранятся отдельно в памяти (как показано в bmap выше), что оптимизирует выравнивание памяти и уменьшает паддинг.

Динамический рост и рехеширование

Механизм постепенного роста (incremental resizing)

Когда количество элементов превышает loadFactor * 2^B (коэффициент загрузки ≈6.5), происходит увеличение размера:

1. Создается новый массив корзин в buckets (вдвое больше: B+1)
2. Старый массив сохраняется в oldbuckets
3. Эвакуация элементов происходит постепенно при последующих операциях с map
4. Старые корзины очищаются по мере эвакуации

// Пример логики эвакуации
if h.growing() {
    bucket := hash & bucketMask(h.B)
    if !evacuated(bucket) {
        evacuate(bucket) // перемещение элементов
    }
}

Особенности реализации

1. Оптимизация для мелких map

Для map с менее чем 8 элементами Go использует специальную оптимизацию, избегая выделения хеш-таблицы до достижения порогового размера.

2. Случайность итерации

Итерация по map происходит в случайном порядке благодаря:

• Использованию random hash0 при создании
• Случайному выбору начальной корзины при итерации
• Это предотвращает DoS-атаки через коллизии

3. Безопасность для конкурентного чтения

• Несколько горутин могут читать map одновременно
• Запись требует эксклюзивного доступа (нужна синхронизация)
• map не является thread-safe для записи

Пример внутренней работы

// Пример: что происходит при m[key] = value
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 1. Вычисление хеша
    hash := t.hasher(key, uintptr(h.hash0))
    
    // 2. Определение корзины
    bucket := hash & bucketMask(h.B)
    
    // 3. Поиск свободного слота
    for i := uintptr(0); i < bucketCnt; i++ {
        if b.tophash[i] == emptyRest {
            // Найден свободный слот
            b.tophash[i] = tophash(hash)
            b.keys[i] = key
            b.values[i] = value
            return b.values[i]
        }
    }
    
    // 4. Создание overflow корзины при необходимости
    return newOverflow(bucket)
}

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

1. Производительность: операции ~O(1) в среднем случае
2. Память: каждая корзина занимает фиксированный объем, overflow корзины выделяются по мере необходимости
3. Итерация: порядок недетерминирован, не следует полагаться на него
4. Рост: может вызывать паузы при больших размерах из-за рехеширования

Эта сложная внутренняя организация позволяет map в Go обеспечивать высокую производительность при сохранении безопасности и предсказуемого поведения в многопоточных сценариях.