Kuidas töötab Map Go-s?

Go-s kaart on rakendatud kui hajus tabel.

map struktuuri põhikomponendid:

• Hash-funktsioon: Määrab võtmed hash-väärtustele (täisarvud).
• Kastide massiiv: Komplekt nimekirjadest või massiividest, kus hoitakse võti-väärtus paare. Kasti indeks määratakse võtme hash-väärtuse järgi.
• Kollisioonide töötlemine: Kui erinevate võtmete hashid kattuvad (kollisioon), salvestatakse need elemendid ühte kasti, tavaliselt seotud nimekirja või ülevoo vormis naabruses.
• Laadimistegur: Elementide arv ja kastide arv. Kui see ületab teatud piiri, toimub uus hajutustabeli loomine ning kõik elemendid liigitatakse vanadest kastidest uutesse.

Go-s on map struktuur esitatud tüübi hmap kaudu:

type hmap struct {
    count     int // Elementide arv
    flags     uint8 // Seisundi lipud
    B         uint8 // log_2 kastide arv (2^B)
    noverflow uint16 // Ülevoogude kastide arv (ainult statistika jaoks)
    hash0     uint32 // Algväärtus hash-funktsioonile

    buckets    unsafe.Pointer // Näitaja kastide massiivile (peamine ja ülevood)
    oldbuckets unsafe.Pointer // Näitaja vanale kastide massiivile migratsiooni ajal
    nevacuate  uintptr // Märgib, millisesse vana kastisse migratsioon on lõpetatud

    extra *mapextra // Täiendav teave
}

type mapextra struct {
    overflow    *[2]*[]*bmap // Näitaja ülevoogude kastide massiividele
    oldoverflow *[2]*[]*bmap // Näitaja vanade ülevoogude kastide massiividele
    nextOverflow *bmap // Järgmine vaba ülevoogude kast
}

type bmap struct {
    tophash [8]uint8 // Ülahašš (ülemised bitid) kiirendamiseks otsingus kastis
    // Järgnevad võtmed, väärtused ja näitaja järgmisele bmap-ile (kui kast on ülevoog)
    // Kõigi andmete paigutus `hmap.buckets` ühes malloc plokis
    // Vaadake ../../runtime/map.go detailide jaoks
}