Ako funguje Map v Go?

Map v Go je implementovaný ako hash tabuľka.

Hlavné komponenty štruktúry map:

• Hash funkcia: Mapuje kľúče na hash hodnoty (celé čísla).
• Pole košíkov (buckets): Súbor zoznamov alebo polí, kde sú uložené páry kľúč-hodnota. Index košíka je určený hash hodnotou kľúča.
• Spracovanie kolízií: Pri zhode hashov pre rôzne kľúče (kolízia) sú prvky s týmito kľúčmi uložené v jednom košíku, zvyčajne vo viazanom zozname alebo pretečení do susedného košíka.
• Zaťažovací faktor: Pomery medzi počtom prvkov a počtom košíkov. Pri prekročení určitého prahu dochádza k rehashovaniu – vytvoreniu nového, väčšieho poľa košíkov a presunu všetkých prvkov zo starých košíkov do nových.

Štruktúra map v Go je reprezentovaná typom hmap:

type hmap struct {
    count     int // Počet prvkov
    flags     uint8 // Stavové vlajky
    B         uint8 // log_2 počtu košíkov (počet košíkov je 2^B)
    noverflow uint16 // Počet pretečených košíkov (len pre štatistiku)
    hash0     uint32 // Počiatočná hodnota hash funkcie

    buckets    unsafe.Pointer // ukazovateľ na pole košíkov (hlavné a pretečené)
    oldbuckets unsafe.Pointer // ukazovateľ na staré pole košíkov počas migrácie
    nevacuate  uintptr // Označuje, do ktorého starého košíka bola migrácia dokončená

    extra *mapextra // Dodatočné informácie (voliteľné)
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Ukazovatele na pole pretečených košíkov
    oldoverflow *[2]*[]*bmap // Ukazovatele na staré pole pretečených košíkov
    nextOverflow *bmap // Nasledujúci voľný pretečený košík
}

type bmap struct {
    tophash [8]uint8 // Top hash (horné bity hashu) pre zrýchlenie vyhľadávania v košíku
    // Nasledujú kľúče, hodnoty a ukazovateľ na ďalší bmap (ak je košík pretečený)
    // rozloženie všetkých dát pre hmap.buckets v jednom malloc bloku
    // pozrite ../../runtime/map.go pre detaily
}