Чӣ гуна Map дар Go кор мекунад?

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

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

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

Структура 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 для деталей
}