Kako funkcioniše Map u Go?

Map u Go je implementiran kao hash tabela.

Glavne komponente strukture map:

• Hash funkcija: Mapira ključeve na hash vrednosti (celobrojne brojeve).
• Niz bačvi (buckets): Skup listi ili nizova, gde se čuvaju parovi ključ-vrednost. Indeks bačve se određuje hash vrednošću ključa.
• Obrada kolizija: Pri poklapanju hashova za različite ključeve (kolizija) elementi sa tim ključevima se čuvaju u jednoj bačvi, obično u obliku povezane liste ili prelivanja u susednu bačvu.
• Faktor opterećenja: Odnos između broja elemenata i broja bačvi. Kada se prekorači određeni prag, vrši se rehashovanje – kreiranje nove, veće bačve i premještanje svih elemenata iz starih bačvi u nove.

Struktura map u Go je predstavljena tipom hmap:

type hmap struct {
    count     int // Broj elemenata
    flags     uint8 // Stanja zastavice
    B         uint8 // log_2 broja bačvi (broj bačvi je 2^B)
    noverflow uint16 // Broj prelivanja bačvi (samo za statistiku)
    hash0     uint32 // Početna vrednost hash funkcije

    buckets    unsafe.Pointer // pokazivač na niz bačvi (glavni i prelivene)
    oldbuckets unsafe.Pointer // pokazivač na stari niz bačvi tokom migracije
    nevacuate  uintptr // Označava do kojeg starog bačva je migracija završena

    extra *mapextra // Dodatne informacije (opciono)
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Pokazivači na nizove prelivene bačvi
    oldoverflow *[2]*[]*bmap // Pokazivači na stare nizove prelivene bačvi
    nextOverflow *bmap // Sledeći slobodni preliveni bačva
}

type bmap struct {
    tophash [8]uint8 // Top hash (gornji bita hasha) za ubrzanje pretrage u bačvi
    // Sledi ključ, vrednosti i pokazivač na sledeći bmap (ako je bačva prelivena)
    // raspored svih podataka za hmap.buckets u jednom malloc bloku
    // pogledajte ../../runtime/map.go za detalje
}