Kaip veikia Map Go?

Go kalba įgyvendinta kaip žemės žemėlapis.

Pagrindiniai map struktūros komponentai:

• Hesh funkcija: Nurodo raktus į žemės reikšmes (visas skaičius).
• Dėžučių masyvas: Rinkinys sąrašų arba masyvų, kur saugomos raktų-vertės poros. Dėžutės indeksas nustatomas pagal rakto hesh reikšmę.
• Kolizijų apdorojimas: Kai skirtingų raktų hesh reikšmės sutampa (kolizija), šie elementai saugomi vienoje dėžutėje, dažniausiai kaip susietas sąrašas arba perteklius į šalia esančią dėžutę.
• Įkrovimo faktorius: Elementų skaičius ir dėžučių skaičius. Kai viršijama tam tikra riba, atliekama nauja žemės žemėlapio kūrimas ir visi elementai perkeliami iš senų dėžučių į naujas.

Go map struktūra yra atvaizduojama kaip hmap tipas:

type hmap struct {
    count     int // Elementų skaičius
    flags     uint8 // Būsenos žymės
    B         uint8 // log_2 dėžučių skaičius (2^B)
    noverflow uint16 // Perteklių dėžučių skaičius (tik statistikai)
    hash0     uint32 // Pradinis žemės žemėlapio funkcijos reikšmė

    buckets    unsafe.Pointer // Rodyklė į dėžučių masyvą (pagrindinį ir perteklių)
    oldbuckets unsafe.Pointer // Rodyklė į seną dėžučių masyvą migracijos metu
    nevacuate  uintptr // Žymi, kuriame senos dėžutės pabaigoje baigėsi migracija

    extra *mapextra // Papildoma informacija
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Rodyklės į perteklių dėžučių masyvus
    oldoverflow *[2]*[]*bmap // Rodyklės į senus perteklių dėžučių masyvus
    nextOverflow *bmap // Sekantis laisvas perteklių dėžutė
}

type bmap struct {
    tophash [8]uint8 // Viršutinis žemės žemėlapio reikšmės (hash) bitas
    // Toliau eina raktai, reikšmės ir rodyklė į kitą bmap (jei dėžutė perpilama)
    // Visų duomenų išdėstymas `hmap.buckets` viename malloc bloke
    // Daugiau informacijos žiūrėkite ../../runtime/map.go
}