При каком значении load factor происходит рехэширование map в Go?

Что такое load factor и рехэширование в Go map?

В Go map реализована как хеш-таблица с корзинами (buckets). Каждая корзина может хранить до 8 пар ключ-значение. Load factor — это среднее количество элементов, приходящихся на одну корзину. Когда load factor превышает 6.5, Go инициирует рехэширование (rehash) — процесс увеличения количества корзин и перераспределения всех элементов.

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

Значение 6.5 выбрано как компромисс между производительностью и использованием памяти. При load factor меньше 6.5 корзины заполнены не полностью, что тратит память. При load factor больше 6.5 возрастает вероятность коллизий, что замедляет операции вставки и поиска. Экспериментально установлено, что 6.5 обеспечивает хороший баланс.

Как происходит рехэширование?

Когда load factor превышает 6.5, Go создает новый массив корзин в 2 раза больше текущего. Затем все существующие элементы перехешируются и помещаются в новые корзины. Во время рехэширования map временно использует больше памяти, но после завершения процесса старая память освобождается.

Пример кода

package main

import "fmt"

func main() {
    m := make(map[int]int)
    // Добавляем элементы, пока не произойдет рехэширование
    for i := 0; i < 100; i++ {
        m[i] = i
    }
    fmt.Println("Map size:", len(m))
    // При добавлении большого количества элементов load factor растет
    // Когда он превышает 6.5, Go автоматически увеличивает количество корзин
}

Вывод

Понимание load factor и рехэшинга важно для оптимизации производительности map в Go. Если вы ожидаете большое количество элементов, можно заранее задать начальный размер map с помощью make(map[K]V, hint), чтобы уменьшить количество рехэшингов и повысить скорость работы.