Как работи Map в Go?

Map в Go е реализиран като хеш таблица.

Основните компоненти на структурата map:

• Хеш функция: Отразява ключовете към хеш стойности (цяли числа).
• Масив от кофи (buckets): Набор от списъци или масиви, където се съхраняват двойки ключ-стойност. Индексът на кофата се определя от хеш стойността на ключа.
• Обработка на колизии: При съвпадение на хешовете за различни ключове (колизия) елементите с тези ключове се съхраняват в една кофа, обикновено като свързан списък или преливане в съседна кофа.
• Натоварващ фактор: Отношението между броя на елементите и броя на кофите. При превишаване на определен праг се извършва рехеширане – създаване на нов, по-голям масив от кофите и преместване на всички елементи от старите кофите в новите.

Структурата map в Go е представена чрез типа hmap:

type hmap struct {
    count     int // Брой елементи
    flags     uint8 // Флагове за състояние
    B         uint8 // log_2 на броя кофите (броят кофите е 2^B)
    noverflow uint16 // Брой прелели кофите (само за статистика)
    hash0     uint32 // Начална стойност на хеш функцията

    buckets    unsafe.Pointer // указател към масив от кофите (основен и прелели)
    oldbuckets unsafe.Pointer // указател към стария масив от кофите по време на миграция
    nevacuate  uintptr // Обозначава до кой стар кофа е завършена миграцията

    extra *mapextra // Допълнителна информация (по избор)
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Указатели към масиви от прелели кофите
    oldoverflow *[2]*[]*bmap // Указатели към стари масиви от прелели кофите
    nextOverflow *bmap // Следващ свободен прелял кофа
}

type bmap struct {
    tophash [8]uint8 // Топ-хеш (горните бита на хеша) за ускоряване на търсенето в кофата
    // Следват ключове, стойности и указател към следващ bmap (ако кофата е преляла)
    // разположение на всички данни за hmap.buckets в един malloc блок
    // виж ../../runtime/map.go за подробности
}