При полном ли заполнении Map начинается эвакуация

Эвакуация карт (Map Evacuation) в Go

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

Ключевые термины и механизмы

Карта в Go — это хеш-таблица, состоящая из ведёр (buckets). Каждое ведро может содержать до 8 пар ключ-значение. Процесс роста карты включает:

• Увеличение количества вёдер (обычно в 2 раза).
• Перераспределение элементов (эвакуация) в новые вёдра.

Порог начала эвакуации

Эвакуация начинается не при полном заполнении карты, а при превышении коэффициента загрузки (load factor). В исходном коде Go (актуально для версий 1.20+) этот коэффициент установлен как 6.5 (на одно ведро, учитывая что в ведре 8 слотов). Это означает, что в среднем при 6.5 элементах на ведро запускается процесс роста.

Пример для иллюстрации:

package main

import "fmt"

func main() {
    m := make(map[int]string)
    // Заполняем карту
    for i := 0; i < 100; i++ {
        m[i] = fmt.Sprintf("value%d", i)
        // В какой-то момент произойдёт рост и эвакуация
    }
    fmt.Println("Размер карты:", len(m))
}

Как работает процесс

1. Триггер роста: При добавлении нового элемента, если средняя нагрузка превышает 6.5, карта помечается для роста.

2. Постепенная эвакуация: В Go рост карты и эвакуация элементов происходят инкрементально (постепенно), а не мгновенно:

   • Создаётся новый массив вёдер большего размера.
   • Эвакуация выполняется по мере последующих операций с картой (вставка, удаление, доступ).
   • Это позволяет избежать резких скачков производительности.

3. Дополнительные триггеры: Эвакуация также может начаться из-за:

   • Слишком много переполненных вёдер (overflow buckets), даже если общий коэффициент загрузки ниже порога.
   • Операций удаления, которые могут привести к фрагментации.

Пример с детализацией

Рассмотрим карту с 8 вёдрами (начальный размер):

m := make(map[string]int)
// Каждое ведро вмещает до 8 элементов, но порог роста ~6.5 элементов/ведро
// Общий порог для 8 вёдер: 8 * 6.5 ≈ 52 элемента
for i := 0; i < 53; i++ {
    key := fmt.Sprintf("key%d", i)
    m[key] = i
    // При i=52 может активироваться рост (эвакуация)
}

Важные нюансы

• Точное значение может меняться в разных версиях Go, но принцип остаётся.
• Эвакуация не синхронна — она выполняется фоново, что делает операции с картой эффективными.
• Двойной рост: При большом количестве переполненных вёдер размер может увеличиться более чем в 2 раза.

Вывод

Эвакуация в картах Go начинается не при 100% заполнении, а при достижении коэффициента загрузки ~6.5 элементов на ведро. Это спроектировано для баланса между производительностью и использованием памяти. Механизм инкрементальной эвакуации делает рост карт плавным, минимизируя влияние на производительность программ.