Maps in Go meistern: Alles, was Sie wissen müssen

Eine Map (auch bekannt als assoziatives Array, Hash-Tabelle, Hash-Map, Hash-Set, Dict) ist eine wesentliche Datenstruktur zum Lösen verschiedener algorithmischer Probleme bei der täglichen Arbeit, bei Programmierwettbewerben oder bei Vorstellungsgesprächen. Daher ist es wichtig zu verstehen, welche Funktionen Maps Ihnen als Entwickler bieten: die von ihnen unterstützten Operationen, die zeitliche und räumliche Komplexität verschiedener Operationen und wie diese Struktur im Code verwendet wird. Mit diesem Wissen und etwas praktischer Erfahrung können Sie Fälle erkennen, in denen Sie eine Map anwenden müssen, um Ihr Problem zu lösen. Der Artikel, den Sie gerade lesen, bietet eine umfassende Anleitung zur Verwendung von Maps. Wir beginnen mit einem kurzen Überblick über die Map-Datenstruktur im Allgemeinen und tauchen dann tief in die Implementierung von Maps in der Programmiersprache Go ein und diskutieren Strategien für die Verwendung von Maps in gleichzeitigem Code.

Karte für Anfänger

Assoziatives Array

Beginnen wir mit der Erörterung eines wichtigen Konzepts, das allen in verschiedenen Programmiersprachen implementierten Datenstrukturen zugrunde liegt: dem abstrakten Datentyp. Dabei handelt es sich um ein mathematisches Modell, das zur Beschreibung eines Datentyps anhand der vom Datentyp unterstützten Operationen, des Verhaltens dieser Operationen und der möglichen Werte verwendet wird, die an ihn übergeben oder von ihm empfangen werden können. Es gibt auch einen abstrakten Datentyp für eine Map, der als assoziatives Array bezeichnet wird.

Ein assoziatives Array ist ein abstrakter Datentyp, der zum Speichern einer Sammlung von Schlüssel- und Wertepaaren verwendet wird, wobei jeder Schlüssel nur einmal in der Sammlung vorkommt, oder anders ausgedrückt, es gibt nur einen Wert für jeden Schlüssel in der Sammlung. Es unterstützt die Operationen get , set und delete .

Stellen wir uns vor, wir haben eine Implementierung eines assoziativen Arrays in der Programmiersprache Go, das Schlüssel- und Wertepaare speichern kann, wobei sowohl Schlüssel als auch Wert Zeichenfolgen sind, und schauen wir uns an, wie die Operationen aussehen.

 package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set the value for the key "Alice". associativeArray.Set("Alice", "apple") // Attempt to retrieve and print the value associated with "Alice". valueForAlice, found := associativeArray.Get("Alice") if found { fmt.Println(valueForAlice) // Output: "apple" } else { fmt.Println("No value found for Alice.") } // Delete the entry associated with "Alice". associativeArray.Delete("Alice") // Attempt to retrieve the value for "Alice" after deletion to check error handling. valueForAlice, found = associativeArray.Get("Alice") if !found { fmt.Println("No value found for Alice. (Deleted)") } // Attempt to retrieve the value for "Bob" which was never set. valueForBob, found := associativeArray.Get("Bob") if !found { fmt.Println("No value found for Bob. (Never set)") } }

Das Setzen eines Schlüssels, der zuvor gesetzt wurde, ist eine gültige Operation, aber in diesem Fall wird dem alten Schlüssel ein neuer Wert zugeordnet und es ist unmöglich, den vorherigen Wert abzurufen. Er könnte gelöscht oder verdeckt werden, je nach Implementierung des assoziativen Arrays.

 package main import ( "fmt" ) // type AssociativeArray implementation somewhere here func main() { // Initialize a new associative array. associativeArray := NewAssociativeArray() // Set value associated with "Alice" key associativeArray.Set("Alice", "apple") // Get value associated with "Alice" key valueForAlice := associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "apple" // Set new value associated with "Alice" key associativeArray.Set("Alice", "orange") // Get new value associated with "Alice" key valueForAlice = associativeArray.Get("Alice") fmt.Println(valueForAlice) // This line will print "orange" }

Das ist großartig, aber Sie fragen sich vielleicht, wie man ein assoziatives Array im wirklichen Leben implementiert. Tatsächlich gibt es bei der Implementierung keine Grenzen. Sie können es auf jede erdenkliche Weise implementieren; Sie müssen nur die erforderlichen Operationen für diesen abstrakten Datentyp unterstützen. Es gibt jedoch mehrere Ansätze, die am häufigsten verwendet werden: die Hash-Map und der binäre Suchbaum. Die Unterschiede zwischen ihnen liegen in ihrer zeitlichen und räumlichen Komplexität und natürlich in den Algorithmen zum Speichern und Abrufen von Schlüsseln und Werten. Im Folgenden konzentrieren wir uns auf Hash-Map-Implementierungen, aber es ist erwähnenswert, dass ein binärer Suchbaum auch zur Implementierung eines assoziativen Arrays verwendet werden kann.

Hash-Karte

Wir haben herausgefunden, dass eine Hash-Map eine Datenstruktur ist, die assoziative Array-Operationen implementiert: Festlegen eines Werts für einen Schlüssel, Abrufen eines Werts nach Schlüssel und Löschen eines mit einem Schlüssel verknüpften Werts. Aber wie funktioniert eine Hash-Map eigentlich im Hintergrund? Lassen Sie es uns herausfinden.

Die Kernidee verbirgt sich hier hinter dem Wort „Hash“. Eine Hash-Map verwendet eine Hash-Funktion, um den Index der Stelle im Array zu berechnen, an der der Wert gespeichert wird, indem der Schlüssel an die Hash-Funktion übergeben wird. Versuchen wir, eine einfache Hash-Map mit der Programmiersprache Go zu implementieren, um zu sehen, wie die Hash-Funktion und das Array zusammenarbeiten, um eine Hash-Map zu erstellen.

 package main import "fmt" func main() { // Define an array to hold string data array := make([]string, 10) // Hash function that returns an integer based on the key and array length hash := func(key string, length int) int { calculatedHash := 0 for _, char := range key { calculatedHash += int(char) } return calculatedHash % length } // Set operation: store a value associated with a key index := hash("Alice", len(array)) array[index] = "apple" // Get operation: retrieve the value associated with a key index = hash("Alice", len(array)) fmt.Println(array[index]) // Should print "apple" // Delete operation: remove the value associated with a key index = hash("Alice", len(array)) array[index] = "" // Setting it to empty string, assuming nil is not an option // Check if the deletion was successful index = hash("Alice", len(array)) if array[index] == "" { fmt.Println("Value deleted successfully.") } else { fmt.Println("Value still exists:", array[index]) } }

Dies ist eigentlich eine vereinfachte Darstellung der Funktionsweise einer echten Hash-Map. Möglicherweise stellen Sie fest, dass unsere Implementierung in einigen Fällen nicht funktioniert. Wenn Sie dies nicht bemerkt haben, denken Sie vor dem Weiterlesen über mögliche Probleme nach.

Kollisionen

Haben Sie herausgefunden, wo das Problem in der vorherigen Implementierung liegt? Es handelt sich um eine Situation, in der zwei verschiedene Zeichenfolgen denselben Hash ergeben können. Genau, wir haben nur len(array) mögliche Hashwerte, aber eine unendliche Anzahl verschiedener Schlüssel, und nach dem Schubfachprinzip können wir zwei verschiedene Schlüssel finden, die denselben Hash erzeugen, und das bedeutet, dass sie derselben Position im Array entsprechen.

Was werden wir damit machen? Wir müssen einen Weg finden, mit dieser Situation umzugehen. Glücklicherweise haben kluge Leute dieses Problem bereits gelöst und mehrere bekannte Lösungen implementiert, also lasst uns diese einfach nutzen, anstatt das Rad neu zu erfinden.

• Separate Verkettung.

  Bei diesem Ansatz speichern wir die Werte nicht direkt im Array, sondern für jeden Index eine verknüpfte Liste im Array. Wenn wir der Karte einen neuen Wert hinzufügen, suchen wir zuerst, ob ein Element mit demselben Schlüssel vorhanden ist. Wenn ja, aktualisieren wir einfach den Wert. Andernfalls fügen wir der verknüpften Liste ein neues Element hinzu.

  
  

• Offene Adressierung

  Offene Adressierung ist ein weiterer Ansatz zur Kollisionsbehebung. Jetzt speichern wir an jeder Array-Position ein Schlüssel-Wert-Paar. Wenn wir versuchen, einen neuen Wert hinzuzufügen und auf eine Situation stoßen, in der sich an dieser Position bereits ein Wert befindet, beginnen wir mit der Sondierung. Die Sondierung kann linear, quadratisch, mithilfe einer anderen Hash-Funktion oder sogar zufällig erfolgen. Bei der linearen Sondierung beginnen Sie, den Index um eins zu erhöhen, bis Sie freien Speicherplatz in Ihrem zugrunde liegenden Array finden. Derselbe Prozess findet statt, wenn Sie versuchen, einen Wert aus dem Array abzurufen und auf eine Situation stoßen, in der der Schlüssel an der Array-Position nicht dem Suchschlüssel entspricht.

Schauen wir uns die Implementierung des separaten Verkettungsansatzes an, da dieser dem in Go implementierten Ansatz sehr ähnlich ist. Doch bevor wir das Schema untersuchen, schauen wir uns erst einmal an, wie unsere Hash-Map aussehen wird.

 package main import ( "fmt" "hash/fnv" ) // Entry represents a key-value pair in the linked list type Entry struct { Key string Value string Next *Entry } // HashMap represents the hash table structure type HashMap struct { Buckets []*Entry Size int } // NewHashMap creates a new hash map with a given size func NewHashMap(size int) *HashMap { return &HashMap{ Buckets: make([]*Entry, size), Size: size, } } // HashFunction computes the bucket index for a given key func (h *HashMap) HashFunction(key string) int { hasher := fnv.New32() hasher.Write([]byte(key)) return int(hasher.Sum32()) % h.Size } // Insert adds a new key-value pair to the hash map func (h *HashMap) Set(key, value string) { index := h.HashFunction(key) entry := &Entry{Key: key, Value: value} if h.Buckets[index] == nil { h.Buckets[index] = entry } else { current := h.Buckets[index] for current.Next != nil { current = current.Next } current.Next = entry } } // Search finds the value for a given key in the hash map func (h *HashMap) Get(key string) (string, bool) { index := h.HashFunction(key) current := h.Buckets[index] for current != nil { if current.Key == key { return current.Value, true } current = current.Next } return "", false } // Delete removes an entry from the hash map based on the key func (h *HashMap) Delete(key string) { index := h.HashFunction(key) if h.Buckets[index] != nil { if h.Buckets[index].Key == key { h.Buckets[index] = h.Buckets[index].Next } else { current := h.Buckets[index] for current.Next != nil { if current.Next.Key == key { current.Next = current.Next.Next break } current = current.Next } } } } func main() { hm := NewHashMap(10) hm.Set("name", "John") hm.Set("age", "30") value, exists := hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } hm.Delete("name") value, exists = hm.Get("name") if exists { fmt.Println("Found:", value) } else { fmt.Println("Not found") } } // OUTPUT: // Found: John // Not found

Komplexität

Dies könnte ein fortgeschrittenes Thema für Personen sein, die mit dem Konzept der algorithmischen Komplexität nicht vertraut sind. Wenn Sie sich in dieser Beschreibung wiedererkennen, folgen Sie diesem Link und erfahren Sie mehr über dieses Konzept.

Zeit- und Raumkomplexität sind sehr wichtig, wenn wir über Algorithmen und Datenstrukturen nachdenken, da sie die Leistung unseres Codes direkt beeinflussen. Versuchen wir, die Komplexität der im vorherigen Kapitel beschriebenen Implementierung herauszufinden.

Um einer Hash-Map ein neues Schlüssel-Wert-Paar hinzuzufügen, müssen wir den Hash berechnen, die am Index befindliche verknüpfte Liste finden und die verknüpfte Liste durchlaufen, um unseren Schlüssel zu finden. Das erste, was die Zeitkomplexität beeinflussen kann, ist die Schlüsselgröße. Wir gehen davon aus, dass die durchschnittliche Schlüsselgröße klein ist und die Zeitkomplexität der Hash-Funktion linear von der Schlüsselgröße abhängt. In diesem Fall können wir davon ausgehen, dass die durchschnittliche Zeitkomplexität zum Berechnen des Schlüssel-Hashes O(1) beträgt. Als Nächstes müssen wir alle Elemente in der verknüpften Liste durchlaufen. Die Anzahl der Elemente hängt davon ab, wie viele Kollisionen auftreten, und im schlimmsten Fall beträgt sie O(n) , wenn alle Elemente demselben Hash entsprechen. Die gesamte Zeitkomplexität für den Additionsvorgang beträgt also im schlimmsten und im Durchschnitt O(1) + O(n) = O(n) .

Wir können die durchschnittliche Zeitkomplexität reduzieren, indem wir die Größenanpassung des zugrunde liegenden Arrays auf der Grundlage einer Heuristik namens Ladefaktor implementieren. Dabei handelt es sich einfach um die Anzahl der Schlüssel in der Hash-Map geteilt durch die Anzahl der Slots im zugrunde liegenden Array. Wenn dieser Wert einen bestimmten Schwellenwert überschreitet, können wir die Größe des zugrunde liegenden Arrays anpassen und alle Werte in das neue Array kopieren. Danach ist die Größe jeder verknüpften Liste im Durchschnitt begrenzt. In diesem Fall können wir einen Ladefaktorwert so finden, dass die durchschnittliche Zeitkomplexität in den meisten Fällen O(1) beträgt. Wir werden hier nicht auf die Berechnung eingehen, aber es ist wichtig, das zu verstehen.

Somit weist die Hash-Map die folgenden zeitlichen und räumlichen Komplexitätsbeschränkungen auf:

Zeitliche Komplexität: O(1) im Durchschnitt für alle Operationen.

Speicherkomplexität: O(n) , da wir für jeden Schlüssel eine verknüpfte Listenentität speichern.

Karte in Go

Ausgestattet mit dem Wissen über die Theorie der Implementierung einer Hash-Map schauen wir uns an, welchen integrierten Typ für Maps die Programmiersprache Go uns bietet. Es gibt mehrere Möglichkeiten, eine Map in Go zu erstellen:

 package main func main() { // Using the make Function: This is the most common way to create a map. // You specify the type of the keys and values. m1 := make(map[string]int) // Create a map with string keys and integer values. // You can also optionally set the size of the underlying array using a second argument if // you know how many items you will store in the map before creation. m2 := make(map[string]int, 10) // Using Map Literals: This method is similar to array or slice literals and is // useful for initializing a map with some values. m3 := map[string]int{"one": 1, "two": 2} // Creates and initializes a map. // Nil Map: A map can also be declared without initialization. Such a map // is nil and has no keys, nor can it be added to. var m4 map[string]int // m4 is nil and you cannot add keys to it without initializing it first. // To add keys to a nil map, it must first be initialized using the make function. // m3["hello"] = 1 // Would panic. Map m3 is not nil here and will not cause a panic, this comment should refer to m4 or another nil map. m4 = make(map[string]int) // Now m4 is initialized and ready for use. }

Der in Go integrierte Map-Typ implementiert außerdem alle drei Operationen, die ein assoziatives Array erfordert, sowie eine zusätzliche Funktion zum Iterieren über Map-Elemente:

 package main import "fmt" func main() { m := make(map[string]int) // Adding or updating an element. m["one"] = 1 // Retrieving an element and checking if a key exists. value, ok := m["four"] if ok { fmt.Println("Value exists in map:", value) } else { fmt.Println("Value doesn't exist.") } // Deleting an element. delete(m, "one") // You can iterate over a map using a for loop along with the range keyword. // This gives you access to each key and value in the map. // You shouldn't rely on the order of items; even if you run the for loop several times // in sequence, you can get a different order of items. It's a property of hash tables // in general. Items in the hash table do not have a particular order. for key, value := range m { fmt.Println(key, value) } }

Jeder vergleichbare Typ kann ein Schlüssel in Go-Maps sein. Zu vergleichbaren Typen gehören Boolesche, numerische, Zeichenfolgen-, Zeiger-, Kanal- und Schnittstellentypen sowie Strukturen oder Arrays, die nur vergleichbare Typen enthalten. Außerdem gibt es praktisch keine Einschränkungen hinsichtlich der Typen, die als Werte in einer Map verwendet werden können. Sie können alles sein, von einfachen Typen wie Ganzzahlen und Zeichenfolgen bis hin zu komplexen Typen wie Slices, anderen Maps oder sogar Funktionen.

Detaillierter Einblick in Go Maps

Nun werden wir die Implementierung von Maps untersuchen, indem wir den Map-Quellcode untersuchen. Dadurch können wir besser verstehen, wie Maps intern implementiert werden. Den Quellcode für Gos Map finden Sie hier .

Eine Map in Go ist eine Implementierung der zuvor besprochenen Hash-Map. In unserem vorherigen Beispiel haben wir eine verknüpfte Liste zur Kollisionsauflösung verwendet. Go verwendet einen anderen Ansatz; statt einer verknüpften Liste gibt es Buckets – andere Subarrays an jedem zugrunde liegenden Array-Index. Das zugrunde liegende Array ist also im Wesentlichen ein zweidimensionales Subarray. Jeder Bucket enthält bis zu 8 Schlüssel-Wert-Paare. Wenn mehr als 8 Schlüssel zu einem Bucket gehasht werden, ketten wir zusätzliche Buckets an den verbleibenden Bucket – den Überlauf-Bucket. Die niederwertigsten Bits des Hashs werden verwendet, um einen Bucket auszuwählen. Jeder Bucket enthält einige höherwertige Bits jedes Hashs, um die Einträge innerhalb eines einzelnen Buckets zu unterscheiden. Wenn die Map wächst, weisen wir ein neues, doppelt so großes Bucket-Array zu. Buckets werden inkrementell vom alten Bucket-Array in das neue Bucket-Array kopiert.

Die Hauptstrukturen, die die Karte darstellen, heißen hmap und bmap . Der Einfachheit halber lassen wir einige Hilfsfelder in der Struktur weg. Für das Verständnis der Idee des Algorithmus sind sie nicht wichtig:

 type hmap struct { count int // # of live cells == size of map. Must be first (used by len() builtin) buckets unsafe.Pointer // array of 2^B Buckets; may be nil if count==0. oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing // some other fields... } // A bucket for a Go map. type bmap struct { // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. tophash [abi.MapBucketCount]uint8 // Followed by bucketCnt keys and then bucketCnt elems. // Followed by an overflow pointer. }

count ist die Anzahl der aktuell in der Karte gespeicherten Elemente. buckets ist das zugrunde liegende Array, in dem wir neue Elemente speichern, und oldbuckets ist das Array, in dem wir Elemente gespeichert haben, bevor die Größe der Karte geändert wurde. Anstatt die Kartenelemente beim Ändern der Größe zu verschieben, tut Go dies schrittweise. buckets und oldbuckets sind Zeiger, die auf die bmap Struktur zeigen, die tophash speichert – ein Array des ersten Hash-Bytes für jeden im Bucket gespeicherten Schlüssel – gefolgt von MapBucketCount -Schlüsseln und MapBucketCount Werten, mit einem Überlaufzeiger am Ende. MapBucketCount ist ein architekturspezifischer Wert, laut Dokumentation nicht mehr als 8. Um besser zu verstehen, wie eine Karte im Speicher aussieht, hier ein Bild.

Um den mit einem Schlüssel verbundenen Wert zu finden, müssen wir zuerst den Hash berechnen, mit dem wir den Bucket bestimmen, in dem sich unser Schlüssel befindet. Dazu verwendet Go je nach Architektur und zu hashendem Typ unterschiedliche Hashfunktionen. Nach der Berechnung des Hashs berechnet Go anhand einiger letzter Bits den Index, in dem sich unser Schlüssel befinden könnte. Go speichert außerdem das erste Byte des Hashs im tophash -Array, und mithilfe des Hashs des Schlüssels können Sie mit tophash ganz einfach den möglichen Schlüsselindex im Bucket finden. Danach müssen wir den gesuchten Schlüssel auch noch mit dem im Bucket gespeicherten Schlüssel vergleichen, da es auch zu Kollisionen zwischen dem ersten Byte des Hashs kommen kann. Dieser Vorgang ist in der Abbildung dargestellt.

Parallelität: Map vs. sync.Map

Gleichzeitige Karte

Wir haben die interne Implementierung einer Map betrachtet, aber Go ist eine Sprache, die für die Entwicklung von hochgradig parallelem Code entwickelt wurde. Wie arbeiten wir mit einer Map, wenn zwei oder mehr Goroutinen gleichzeitig Operationen an der Map durchführen? Betrachten wir zwei Fälle: Zwei gleichzeitig laufende Goroutinen lesen einige Werte aus einer zuvor initialisierten Map und wenn Goroutinen Schreiboperationen durchführen.

Wenn zwei Goroutinen gleichzeitig ausgeführt werden, um einige Werte aus einer gemeinsam genutzten Karte zu lesen, treten keine Probleme auf, da sich der interne Zustand der Karte während des Lesevorgangs nicht ändert. Daher können wir problemlos gleichzeitig lesen.

 package main import ( "fmt" "sync" ) func main() { var wg sync.WaitGroup m := make(map[string]int) m["a"] = 1 m["b"] = 2 readMap := func(key string) { value, ok := m[key] if ok { fmt.Println("Read:", key, value) } else { fmt.Println("Key not found:", key) } wg.Done() } wg.Add(2) go readMap("a") go readMap("b") wg.Wait() }

Wenn wir andererseits gleichzeitige Schreibvorgänge durchführen, kann die Karte während des Schreibvorgangs ihren Zustand ändern. Wie wir bereits im vorherigen Abschnitt untersucht haben, ist der Schreibvorgang nicht atomar. Das bedeutet, dass zwischen den Schritten der Kartenänderung andere Vorgänge stattfinden können, und wenn wir während eines anderen Schreibvorgangs versuchen zu lesen oder zu schreiben, kann es sein, dass wir eine Karte in einem falschen Zustand vorfinden. Go ist intelligent genug, um zu erkennen, wenn Sie versuchen, gleichzeitige Schreibvorgänge in einer Karte durchzuführen, und wird einen fatal error: concurrent map writes .

Um dieses Problem zu lösen, müssen wir ein Mutex verwenden. Ein Mutex ist ein Synchronisierungsprimitiv, das verhindert, dass der Status von mehreren Ausführungsthreads gleichzeitig geändert oder abgerufen wird. Es unterstützt zwei Operationen, Sperren und Entsperren, die atomar ausgeführt werden und daher sicher sind. Tatsächlich können wir RWMutex verwenden, das das Sperren für das Lesen durch mehrere Leser, aber nur eines für das Schreiben ermöglicht. Dies kann uns helfen, die Leistung in Fällen zu optimieren, in denen viele Lesevorgänge stattfinden. Sehen wir uns die Implementierung für eine gleichzeitig sichere Karte an.

 package main import ( "fmt" "sync" ) // ConcurrentMap wraps a Go map with a sync.RWMutex to manage concurrent access with optimized read performance type ConcurrentMap struct { sync.RWMutex items map[string]interface{} } // NewConcurrentMap creates a new concurrent map func NewConcurrentMap() *ConcurrentMap { return &ConcurrentMap{ items: make(map[string]interface{}), } } // Set adds or updates an element in the map func (m *ConcurrentMap) Set(key string, value interface{}) { m.Lock() defer m.Unlock() m.items[key] = value } // Get retrieves an element from the map func (m *ConcurrentMap) Get(key string) (interface{}, bool) { m.RLock() defer m.RUnlock() value, exists := m.items[key] return value, exists } // Delete removes an element from the map func (m *ConcurrentMap) Delete(key string) { m.Lock() defer m.Unlock() delete(m.items, key) } // Items returns a copy of all items in the map for safe iteration func (m *ConcurrentMap) Items() map[string]interface{} { m.RLock() defer m.RUnlock() itemsCopy := make(map[string]interface{}) for key, value := range m.items { itemsCopy[key] = value } return itemsCopy } func main() { cmap := NewConcurrentMap() cmap.Set("name", "John Doe") cmap.Set("age", 30) if name, ok := cmap.Get("name"); ok { fmt.Println("Name:", name) } if age, ok := cmap.Get("age"); ok { fmt.Println("Age:", age) } items := cmap.Items() fmt.Println("All items:", items) }

synchronisieren.Karte

Es gibt noch eine weitere Implementierung einer gleichzeitig sicheren Map im Standardpaket: sync.Map. Aber wann sollten wir sync.Map oder eine Map mit einem Mutex verwenden? Es ist Zeit, das herauszufinden. Laut der Dokumentation ist der Map-Typ für zwei gängige Anwendungsfälle optimiert:

1. Wenn der Eintrag für einen bestimmten Schlüssel immer nur einmal geschrieben, aber viele Male gelesen wird, wie in Caches, die nur wachsen

2. Wenn mehrere Goroutinen Einträge für disjunkte Schlüsselsätze lesen, schreiben und überschreiben. In diesen beiden Fällen kann die Verwendung einer Map Sperrkonflikte im Vergleich zu einer Go-Map in Kombination mit einem separaten Mutex oder RWMutex erheblich reduzieren.

   
   

Um besser zu verstehen und ein Gefühl dafür zu entwickeln, warum sync.Map in diesen Fällen besser funktioniert als eine Map mit Mutex, sollten wir den Quellcode von sync.Map untersuchen.

 type Map struct { mu Mutex read atomic.Pointer[readOnly] dirty map[any]*entry // some other fields... } // readOnly is an immutable struct stored atomically in the Map.read field. type readOnly struct { m map[any]*entry amended bool // true if the dirty map contains some key not in m. } // An entry is a slot in the map corresponding to a particular key. type entry struct { p atomic.Pointer[any] }

Die Map verwaltet zwei Darstellungen der Map-Daten: read und dirty . Read Map ( read ): Dies ist der primäre Datenspeicher für die Map und ist für gleichzeitigen Lesezugriff vorgesehen. Sie wird durch einen atomic.Pointer auf eine readOnly Struktur dargestellt, die atomare und sperrenfreie Lesevorgänge des Snapshots der Map gewährleistet. Wenn ein Schlüssel gesucht wird, wird zuerst die read Map geprüft. Wenn der Schlüssel nicht gefunden wird und die Map als amended markiert ist (was darauf hinweist, dass es neue Schlüssel in der dirty Map gibt, die noch nicht in der read Map sind), wird die dirty Map unter einer Mutex-Sperre ( mu ) geprüft. Dirty Map ( dirty ): Diese Map speichert Einträge, die geändert werden, und neue Einträge, die noch nicht in der read Map sichtbar sind. Der Zugriff auf diese Map erfordert das Halten der Mutex-Sperre, um exklusiven Zugriff sicherzustellen. Wenn bei einem Schreibvorgang der Schlüssel nicht in der read Map ist oder aktualisiert werden muss, wird der Vorgang mit der dirty Map fortgesetzt. Wenn die dirty Map nil ist, wird sie initialisiert, indem eine oberflächliche Kopie der read Map erstellt wird, die nicht mehr gültige Einträge ausschließt. Nach einer bestimmten Anzahl von „Fehlern“ (fehlgeschlagene Suchvorgänge, die ein Zurückgreifen auf die dirty Map erforderlich machten) wird die dirty Map zur neuen read Map befördert und bei Bedarf wird eine neue dirty Map vorbereitet.

Unterschiede zu einer integrierten Go-Map mit Mutex

Jetzt können wir herausfinden, was der Unterschied zwischen einer integrierten Map mit Mutex und sync.Map ist:

1. Sperrkonflikt :
   • sync.Map : Entwickelt, um Sperrkonflikte zu minimieren. Für die meisten Lesevorgänge sind aufgrund des atomaren read keine Sperren erforderlich. Schreib- und Löschvorgänge, die nur einen kleinen Teil der Map betreffen, minimieren ebenfalls die Sperrdauer, da sie nur die dirty Map sperren.
   • Integrierte Karte mit Mutex : Jeder Zugriff (Lesen oder Schreiben) erfordert den Erwerb des Mutex, was in Szenarien mit hoher Parallelität zu einem Engpass werden kann.
2. Speicheraufwand und Komplexität :
   • sync.Map : Behält zwei Versionen der Karte bei und kann speicherintensiver sein. Die Logik zum Verwalten dieser Versionen erhöht die Komplexität.
   • Integrierte Map mit Mutex : Einfacher und verbraucht weniger Speicher als sync.Map , da nur eine Version der Map verwaltet wird.
3. Anwendungsfall-Spezifität :
   • sync.Map : Optimiert für Anwendungsfälle, in denen Schlüssel hauptsächlich gelesen und nicht häufig aktualisiert werden oder in denen viele Vorgänge an disjunkten Schlüsselsätzen erfolgen.
   • Integrierte Karte mit Mutex : Allgemein einsetzbar, unkompliziert zu verwenden, aber aufgrund universeller Sperrkonflikte ist die Leistung in bestimmten Szenarien mit hoher Parallelität möglicherweise nicht so gut.

Zusammenfassend lässt sich sagen, dass sync.Map auf Szenarien spezialisiert ist, die seine Parallelitätsoptimierungen nutzen können, um Sperrkonflikte zu reduzieren, auf Kosten erhöhter Komplexität und Speichernutzung. Im Gegensatz dazu ist eine Standard-Go-Map mit einem Mutex eine einfachere und allgemeinere Lösung, kann aber in Umgebungen mit hoher Parallelität unter Leistungsproblemen leiden.

Einpacken

In diesem Artikel haben wir die Feinheiten der Verwendung von Map-Datenstrukturen untersucht und uns dabei insbesondere auf ihre Implementierung und Verwendung in der Programmiersprache Go konzentriert. Ausgehend vom Grundkonzept eines assoziativen Arrays haben wir uns mit der Mechanik von Hash-Maps befasst und ihre Betriebsverfahren, zeitlichen und räumlichen Komplexitäten sowie verschiedene Ansätze wie separate Verkettung und offene Adressierung zur Behandlung von Kollisionen besprochen.

Im Bereich Go haben wir untersucht, wie Maps genutzt und in die Sprache integriert werden, und dabei die zugrunde liegenden Strukturen wie hmap und bmap untersucht. Diese Untersuchung umfasste praktische Codebeispiele, die demonstrierten, wie Maps in Go-Anwendungen initialisiert, bearbeitet und effektiv eingesetzt werden. Darüber hinaus haben wir die potenziellen Fallstricke der Parallelität bei der Verwendung von Maps hervorgehoben und sync.Map für Szenarien eingeführt, die gleichzeitigen Zugriff erfordern, was Sperrkonflikte reduziert und die Leistung optimiert.

Das Verständnis dieser Aspekte von Map-Datenstrukturen erweitert nicht nur Ihr Codierungs-Toolkit, sondern bereitet Sie auch darauf vor, gängige Programmierherausforderungen effizienter und sicherer anzugehen. Egal, ob Sie einfache Anwendungen oder komplexe Systeme entwickeln, die optimale Leistung in parallelen Umgebungen erfordern, das Wissen darüber, wie und wann unterschiedliche Map-Typen verwendet werden, ist von unschätzbarem Wert. Während Sie Ihre Programmierkenntnisse weiter ausbauen, experimentieren Sie weiter mit diesen Strukturen und ihren verschiedenen Implementierungen, um ihr Potenzial in Ihren Projekten voll auszuschöpfen.