Ein tiefer Tauchgang in Slice- und Map-Expansion in Go

In der Untersuchung der Go-Sprache ist die Expansionsstrategie von Arrays und Maps ein häufiges und klassisches Thema. Dieser Artikel zielt darauf ab, die Expansionsstrategien von Arrays und Maps zusammenzufassen und zu erläutern.

Array-Expansion

In Go werden dynamische Arrays als Slices bezeichnet. Ein Slice bietet eine flexible und dynamisch dimensionierte Array-Lösung. Wenn die Funktion append verwendet wird, um Elemente zu einem Slice hinzuzufügen, entscheidet Go, ob die Kapazität basierend auf der aktuellen Kapazität des Slice erweitert werden soll.

Die Strategie für die Slice-Expansion in Go ist wie folgt:

1. Erstens, wenn die neu angeforderte Kapazität größer als das Doppelte der alten Kapazität ist, ist die endgültige Kapazität die neu angeforderte Kapazität;
2. Andernfalls, wenn die Länge des alten Slice weniger als 1024 beträgt, ist die endgültige Kapazität das Doppelte der alten Kapazität;
3. Andernfalls, wenn die Länge des alten Slice größer oder gleich 1024 ist, erhöht sich die endgültige Kapazität iterativ um ein Viertel der alten Kapazität, bis sie die neu angeforderte Kapazität erreicht oder überschreitet;
4. Wenn die Berechnung der endgültigen Kapazität überläuft, ist die endgültige Kapazität die neu angeforderte Kapazität.

Hash-Tabellen-Expansion

In Go ist Map eine häufig verwendete Datenstruktur zum Speichern von Schlüssel-Wert-Paaren. Sein Expansionsmechanismus ist entscheidend für das Verständnis der Leistung und Speichernutzung von Map.

Es gibt zwei Arten von Expansionen in Go Maps:

• Verdopplungs-Expansion: Wenn die Anzahl der Schlüssel-Wert-Paare das 6,5-fache der aktuellen Bucket-Array-Kapazität überschreitet, bedeutet dies, dass die Buckets bald voll sind. An diesem Punkt wird die Expansion ausgelöst und die Anzahl der Buckets verdoppelt. Der Zweck besteht darin, Hash-Kollisionen zu reduzieren und die Abfrageeffizienz zu verbessern;
• Gleichgroße Expansion: Wenn es zu viele Overflow-Buckets gibt (z. B. verursachen häufige Einfügungen und Löschungen eine Streuung der Daten), aber die Gesamtzahl der Schlüssel-Wert-Paare gering ist, bleibt die Anzahl der Buckets unverändert. Stattdessen werden die Daten neu angeordnet, redundante Overflow-Buckets werden zusammengeführt und die Verteilung der Daten wird kompakter, wodurch die Abfrageleistung verbessert wird.

Zugrunde liegende Struktur von Map

Die zugrunde liegende Implementierung von Map in Go ist eine Hashmap. Der Go-Quellcode lautet wie folgt:

// runtime/map.go
// A header for a Go map.
type hmap struct {
 count     int // number of key-value pairs currently in the hash table
 flags     uint8
 B         uint8  // number of buckets currently held by the hash table. Since the number of buckets always expands by a factor of 2, this field stores the exponent, i.e. len(buckets) == 2^B
 noverflow uint16 // approximate number of overflow buckets
 hash0     uint32 // hash seed

 buckets    unsafe.Pointer // array storing 2^B buckets
 oldbuckets unsafe.Pointer // used to save the previous buckets during expansion, size is half of buckets
 nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

 extra *mapextra // optional fields
}

// mapextra mainly maintains overflow buckets when some buckets in hmap have overflowed
// but have not yet reached the threshold for expansion
type mapextra struct {
 overflow    *[]*bmap
 oldoverflow *[]*bmap

 // nextOverflow holds a pointer to a free overflow bucket.
 nextOverflow *bmap
}

Einige wichtige Felderklärungen sind wie folgt:

• count: gibt die Anzahl der Schlüssel-Wert-Paare in der Hash-Tabelle an;
• B: dies ist der Exponent mit der Basis 2, der verwendet wird, um die Anzahl der Buckets zu bestimmen. Wenn beispielsweise B = 1 ist, beträgt die Anzahl der Buckets 2^1 = 2; wenn B = 2 ist, beträgt die Anzahl der Buckets 2^2 = 4 usw.;
• hash0: ein Faktor, der bei der Berechnung des Hash-Werts eines Schlüssels verwendet wird;
• buckets: ein Zeiger auf das Bucket-Array, wobei jeder Bucket zum Speichern von Schlüssel-Wert-Paaren verwendet wird;
• overflow: Wenn ein Bucket nicht mehr Elemente aufnehmen kann und ein Schlüssel in diesen Bucket gehasht wird, wird das Element in einem Overflow-Bucket platziert, und das Overflow-Feld des ursprünglichen Buckets verweist auf den Overflow-Bucket (Verkettungsmethode).

Expansionsmechanismus: Verdopplungs-Expansion

Auslösebedingung:

Wenn die Last einer Map einen bestimmten Schwellenwert überschreitet, wird die Verdopplungs-Expansion ausgelöst. Die Last wird als die Anzahl der Elemente (count) dividiert durch die Anzahl der Buckets (2^B) berechnet. Wenn dieses Verhältnis größer oder gleich 6,5 ist, wird die Last als überschritten betrachtet.

Wenn beispielsweise B = 2 ist, gibt es 2^2 = 4 Buckets. Wenn die Elementanzahl count 26 beträgt (26 / 4 = 6,5), wird die Verdopplungs-Expansion ausgelöst.

Die relevante Logik im Quellcode lautet wie folgt:

// assume h is a pointer to the map structure
if !h.flags&hashWriting && h.count > int(float64(1<<h.B)*loadFactor) {
    // trigger doubling expansion logic
}

Expansionsprozess:

Während der Verdopplungs-Expansion erhöht sich der Wert von B um 1, wodurch sich die Anzahl der Buckets verdoppelt. Wenn beispielsweise ursprünglich B = 2 mit 4 Buckets war, ist nach der Expansion B = 3 mit 2^3 = 8 Buckets.

Beim Migrieren von Daten werden Elemente in den ursprünglichen Buckets neu auf die neuen Buckets verteilt. Im Einzelnen wird die neue Bucket-Position basierend auf dem Hash-Wert des Schlüssels neu berechnet.

Angenommen, der Hash-Wert eines Schlüssels ist hash. Die ursprüngliche Anzahl der Buckets war 2^B1, und nach der Expansion wird sie zu 2^B2. Dann werden die Daten vom ursprünglichen Bucket (hash % 2^B1) zum neuen Bucket (hash % 2^B2) migriert.

Zum Beispiel:

• Wenn der Hash-Wert 10 ist und B = 2 (4 Buckets), dann ist 10 % 4 = 2, also werden die Daten im Bucket mit Index 2 gespeichert;
• Nach der Expansion mit B = 3 (8 Buckets) ist 10 % 8 = 2, die Daten befinden sich immer noch im Bucket mit Index 2. Jetzt ist die Bucket-Verteilung jedoch spärlicher, wodurch die Wahrscheinlichkeit von Hash-Kollisionen verringert wird.

Expansionsmechanismus: Gleichgroße Expansion

Auslösebedingung:

Wenn eine große Anzahl von Schlüsseln gelöscht wird, was zu vielen Overflow-Buckets führt, kann eine gleichgroße Expansion ausgelöst werden. Hier beziehen sich Overflow-Buckets auf die Situation, in der ein Bucket mit 8 Elementen voll ist und neue Elemente in Overflow-Buckets gespeichert werden. Overflow-Buckets werden nicht zur Gesamtzahl der Buckets gezählt.

Wenn die Anzahl der Overflow-Buckets größer oder gleich 2^B ist, kann eine gleichgroße Expansion ausgelöst werden. Wenn jedoch Overflow-Buckets aufgrund von Hash-Kollisionen übermäßig sind und die Last überschritten wird, wird zuerst die Verdopplungs-Expansion ausgelöst.

Die relevante Logik im Quellcode lautet wie folgt:

// assume h is a pointer to the map structure, noverflow is the number of overflow buckets
if noverflow >= uint16(1)<<(h.B) {
    if h.B < 15 {
        // may trigger same-size or doubling expansion logic
    }
}

Expansionsprozess:

Die gleichgroße Expansion organisiert hauptsächlich die Buckets, um leere Speicherplätze zu entfernen. Es wird ein neues Bucket-Array erstellt, und das alte Bucket-Array wird durchlaufen, um nicht leere Schlüssel-Wert-Paare wieder in das neue Array einzufügen, während die ursprünglichen Overflow-Buckets freigegeben werden.

Da der Hash-Faktor, der B-Wert und der Hash-Algorithmus unverändert bleiben, werden die Positionen der Schlüssel-Wert-Paare in den neuen Buckets auf die gleiche Weise wie zuvor berechnet. Es werden nur die leeren Speicherplätze entfernt, wodurch die Schlüssel-Wert-Paare kompakter werden und die Effizienz nachfolgender Operationen verbessert wird.

---

Wir sind Leapcell, Ihre erste Wahl für das Hosting von Go-Projekten.

Leapcell ist die Serverless-Plattform der nächsten Generation für Webhosting, asynchrone Aufgaben und Redis:

Multi-Sprachen-Unterstützung

• Entwickeln Sie mit Node.js, Python, Go oder Rust.

Stellen Sie unbegrenzt Projekte kostenlos bereit

• zahlen Sie nur für die Nutzung – keine Anfragen, keine Gebühren.

Unschlagbare Kosteneffizienz

• Pay-as-you-go ohne Leerlaufgebühren.
• Beispiel: 25 $ unterstützen 6,94 Millionen Anfragen bei einer durchschnittlichen Antwortzeit von 60 ms.

Optimierte Entwicklererfahrung

• Intuitive Benutzeroberfläche für mühelose Einrichtung.
• Vollständig automatisierte CI/CD-Pipelines und GitOps-Integration.
• Echtzeitmetriken und -protokollierung für umsetzbare Erkenntnisse.

Mühelose Skalierbarkeit und hohe Leistung

• Automatische Skalierung zur einfachen Bewältigung hoher Parallelität.
• Kein Betriebsaufwand – konzentrieren Sie sich einfach auf das Bauen.

Erfahren Sie mehr in der Dokumentation!

Folgen Sie uns auf X: @LeapcellHQ