Что происходит с `map` в Go, когда она переполняется, и как называется этот процесс?

Этот процесс называется рехешированием (rehashing).

Он запускается, когда количество элементов в map превышает определенный порог (коэффициент загрузки, load factor, в Go ~6.5).

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

1. Выделение новой памяти: Go создает новый массив бакетов (корзин), обычно в два раза большего размера.
2. Постепенное копирование (Incremental Copying): Вместо того чтобы остановить все операции и скопировать все данные сразу (что вызвало бы большую задержку), Go делает это постепенно. При каждой операции записи или удаления в map перемещается несколько старых бакетов в новый массив.
3. Амортизированная стоимость: Такой подход «размазывает» стоимость рехеширования по нескольким операциям, обеспечивая в среднем O(1) сложность для вставки и поиска, хотя отдельная операция может занять больше времени, если она инициирует копирование.

package main

import "fmt"

func main() {
    // Изначально map имеет небольшое количество бакетов
    m := make(map[int]int)

    // При добавлении большого количества элементов
    // Go будет несколько раз выполнять рехеширование,
    // увеличивая внутренний массив бакетов.
    for i := 0; i < 1000; i++ {
        m[i] = i
    }

    fmt.Println("Map успешно заполнена")
}

Ключевой вывод: Рехеширование — это автоматический механизм, который позволяет map эффективно расти, сохраняя высокую производительность в среднем.