Hoe werkt een Map in Go?

Map in Go wordt geïmplementeerd als een hashtabel.

De belangrijkste componenten van de map structuur:

• Hashfunctie: Map de sleutels naar hash-waarden (hele getallen).
• Array van buckets: Een verzameling lijsten of arrays waarin sleutel-waarde paren worden opgeslagen. De index van de bucket wordt bepaald door de hash-waarde van de sleutel.
• Omgaan met botsingen: Wanneer verschillende sleutels dezelfde hash hebben (botsing), worden de elementen met die sleutels opgeslagen in dezelfde bucket, meestal in de vorm van een gekoppelde lijst of een overflow bucket.
• Ladingsfactor: Verhouding tussen het aantal elementen en het aantal buckets. Wanneer een drempel wordt overschreden, wordt een herhashing uitgevoerd: er wordt een nieuwe, grotere array van buckets gemaakt en alle elementen uit de oude buckets worden naar de nieuwe verplaatst.

De map structuur in Go wordt weergegeven door het type hmap:

 type hmap struct {
    count     int // Aantal elementen
    flags     uint8 // Statusvlaggen
    B         uint8 // log_2 van het aantal buckets (aantal buckets is 2^B)
    noverflow uint16 // Aantal buckets met overflow (alleen voor statistieken)
    hash0     uint32 // Initiële waarde van de hashfunctie

    buckets    unsafe.Pointer // Punter naar de array van buckets (hoofd- en overflow-buckets)
    oldbuckets unsafe.Pointer // Punter naar de oude array van buckets tijdens migratie
    nevacuate  uintptr // Geeft aan tot welke oude bucket de migratie is voltooid

    extra *mapextra // Extra informatie (optioneel)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Pointers naar arrays van overflow-buckets
    oldoverflow *[2]*[]*bmap // Pointers naar oude arrays van overflow-buckets
    nextOverflow *bmap // Volgende vrije overflow-bucket
}

 type bmap struct {
    tophash [8]uint8 // Top-hash (bovenste bits van de hash) voor versnelde zoekopdrachten in de bucket
    // Vervolgens sleutels, waarden en pointers naar de volgende bmap (als de bucket vol is)
    // Verdeel alle gegevens voor hmap.buckets in één enkele malloc-blok
    // Zie ../../runtime/map.go voor details
}

Operaties:

• Invoegen/Bijwerken: Bereken de hash van de sleutel, bepaal de bucket. Als de sleutel al bestaat, wordt de waarde bijgewerkt. Anders wordt het paar sleutel-waarde toegevoegd aan de bucket. Bij overflow of overschrijding van de Load Factor kan een herhashing plaatsvinden.
• Zoeken: Bereken de hash van de sleutel, bepaal de bucket. Doorloop de elementen in de bucket op basis van de top-hash, vergelijk vervolgens de volledige sleutels. Retourneer de waarde en een flag voor aanwezigheid.
• Verwijderen: Bereken de hash van de sleutel, bepaal de bucket. Het element wordt gemarkeerd als verwijderd (maar wordt niet onmiddellijk uit het geheugen verwijderd). Verwijdering gebeurt tijdens latere operaties of tijdens herhashing.

De map in Go is niet gesynchroniseerd en kan niet veilig door meerdere goroutines worden gebruikt zonder externe synchronisatie.