Wie ist eine Map in Go aufgebaut?

Map in Go wird als Hashtabelle implementiert.

Die Hauptkomponenten der map-Struktur:

• Hash-Funktion: Ordnet Schlüssel Hash-Werten (Ganzzahlen) zu.
• Bucket-Array: Eine Sammlung von Listen oder Arrays, in denen Schlüssel-Wert-Paare gespeichert werden. Der Index des Buckets wird durch den Hash-Wert des Schlüssels bestimmt.
• Kollisionen behandeln: Bei Kollisionen (verschiedene Schlüssel mit demselben Hash) werden die Elemente in einem Bucket gespeichert, meist in einer verketteten Liste oder in einem Overflow-Bucket.
• Ladefaktor: Verhältnis zwischen Anzahl der Elemente und Anzahl der Buckets. Überschreitet es eine Schwelle, erfolgt ein Rehashing: Es wird ein neues, größeres Bucket-Array erstellt und alle Elemente der alten Buckets werden in die neuen verschoben.

Die map-Struktur in Go wird durch den Typ hmap dargestellt:

 type hmap struct {
    count     int // Anzahl der Elemente
    flags     uint8 // Status-Flags
    B         uint8 // log_2 der Anzahl der Buckets (Anzahl der Buckets ist 2^B)
    noverflow uint16 // Anzahl der Buckets mit Overflow (nur für Statistik)
    hash0     uint32 // Anfangswert der Hash-Funktion

    buckets    unsafe.Pointer // Zeiger auf das Bucket-Array (Haupt- und Overflow-Buckets)
    oldbuckets unsafe.Pointer // Zeiger auf das alte Bucket-Array während der Migration
    nevacuate  uintptr // Gibt an, bis zu welchem alten Bucket die Migration abgeschlossen ist

    extra *mapextra // Zusätzliche Informationen (optional)
}

 type mapextra struct {
    overflow    *[2]*[]*bmap // Zeiger auf Overflow-Bucket-Arrays
    oldoverflow *[2]*[]*bmap // Zeiger auf alte Overflow-Bucket-Arrays
    nextOverflow *bmap // Nächster freier Overflow-Bucket
}

 type bmap struct {
    tophash [8]uint8 // Top-Hash (obere Bits des Hashes) zur Beschleunigung der Suche im Bucket
    // Es folgen Schlüssel, Werte und Zeiger auf den nächsten bmap (falls Bucket voll)
    // Alle Daten für hmap.buckets in einem einzigen malloc-Block
    // Details siehe ../../runtime/map.go
}

Operationen:

• Einfügen/Aktualisieren: Hash der Schlüssel berechnen, Bucket bestimmen. Wenn der Schlüssel bereits existiert, Wert aktualisieren. Andernfalls Paar Schlüssel-Wert zum Bucket hinzufügen. Bei Overflow oder Überschreitung des Load Factors kann ein Rehashing erfolgen.
• Suche: Hash der Schlüssel berechnen, Bucket bestimmen. Elemente im Bucket nach Top-Hash durchgehen, dann vollständigen Schlüssel vergleichen. Gibt den Wert und einen Existenz-Flag zurück.
• Löschen: Hash der Schlüssel berechnen, Bucket bestimmen. Element wird als gelöscht markiert (aber nicht sofort aus dem Speicher entfernt). Das Löschen erfolgt bei späteren Operationen oder beim Rehashing.

Die Map in Go ist nicht synchronisiert und kann ohne externe Synchronisation nicht sicher von mehreren Goroutinen verwendet werden.