Hogyan működik a Map a Go-ban?

A Go-ban a térkép egy hash-táblaként van megvalósítva.

A map szerkezet fő összetevői:

• Hash függvény: A kulcsokat hash értékekre (egész számokra) térképezi.
• Bucket tömb: Lista vagy tömbök halmaza, ahol a kulcs-érték párok tárolódnak. A bucket indexe a kulcs hash értékétől függ.
• Ütközések kezelése: Amikor különböző kulcsok ugyanazt a hash értéket kapják (ütközés), ezek az elemek ugyanabba a bucketbe kerülnek, általában láncolt lista vagy túlcsordulási bucket formájában.
• Terhelési tényező: Az elemek száma és a bucketek száma közötti arány. Amikor ez egy küszöböt meghalad, újrahash-elés történik: egy nagyobb bucket tömböt hoznak létre, és az összes régi bucket elemeit átmozgatják az újakba.

A Go-ban a map szerkezetet az hmap típus reprezentálja:

 type hmap struct {
    count     int // Elemek száma
    flags     uint8 // Állapot zászlók
    B         uint8 // log_2 a bucketek számáról (2^B a bucketek száma)
    noverflow uint16 // Túlsúlyos bucketek száma (csak statisztikára)
    hash0     uint32 // A hash függvény kezdőértéke

    buckets    unsafe.Pointer // Mutató a bucket tömbre
    oldbuckets unsafe.Pointer // Mutató a régi bucket tömbre migráció közben
    nevacuate  uintptr // Megmutatja, hogy melyik régi bucketnél fejeződött be a migráció

    extra *mapextra // További információk
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Túlsúlyos bucket tömbök mutatói
    oldoverflow *[2]*[]*bmap // Régi túlsúlyos bucket tömbök mutatói
    nextOverflow *bmap // Következő szabad túlsúlyos bucket
}

 type bmap struct {
    tophash [8]uint8 // Top hash (hash felső bitei) a keresés gyorsítására
    // Ezután jönnek a kulcsok, értékek és mutatók a következő bmap-re (ha a bucket tele van)
    // Az összes adat elrendezése az hmap.buckets-ben egyetlen malloc blokkban
    // részletekért lásd a ../../runtime/map.go-t
}

Műveletek:

• Beszúrás/Frissítés: A kulcs hash értékét számítja ki, meghatározza a bucketet. Ha a kulcs már létezik, az érték frissül. Egyébként a kulcs-érték pár hozzáadódik a buckethez. Túlsúly vagy Load Factor túllépése esetén rehash történhet.
• Keresés: A kulcs hash értékét számítja ki, meghatározza a bucketet. A bucket elemeit a top-hash szerint ellenőrzi, majd a teljes kulcsokat összehasonlítja. Az érték és a létezés flag-je visszaadásra kerül.
• Törlés: A kulcs hash értékét számítja ki, meghatározza a bucketet. A kiválasztott elem megjelölésre kerül töröltként (de nem törlődik azonnal a memóriából). A törlés későbbi műveletek vagy rehash során történik.

A Go-ban a térkép nincs szinkronizálva, és több goroutine által biztonságosan nem használható külső szinkronizáció nélkül.