Wir werden die Implementierung von Map in einer Sprache ohne Generika diskutieren, überlegen, was eine Hash-Tabelle ist, wie sie in Go angeordnet ist, welche Vor- und Nachteile diese Implementierung hat und worauf Sie bei der Verwendung dieser Struktur achten sollten.
Details unter dem Schnitt.
Achtung! Wenn Sie bereits mit Hash-Tabellen in Go vertraut sind, empfehle ich Ihnen, die Grundlagen zu überspringen und
hierher zu gehen. Andernfalls besteht die Gefahr, dass Sie den interessantesten Moment satt haben.
Was ist eine Hash-Tabelle?
Zunächst möchte ich Sie daran erinnern, was eine Hash-Tabelle ist. Dies ist eine Datenstruktur, mit der Sie Schlüssel-Wert-Paare speichern können und in der Regel über folgende Funktionen verfügen:
- Zuordnung:
map(key) → value
insert(map, key, value) : insert(map, key, value)
- Löschungen:
delete(map, key)
- Suche:
lookup(key) → value
Hash-Tabelle in Go-Sprache
Eine Hash-Tabelle in der Sprache go wird durch das Schlüsselwort map dargestellt und kann auf eine der folgenden Arten deklariert werden (dazu später mehr):
m := make(map[key_type]value_type) m := new(map[key_type]value_type) var m map[key_type]value_type m := map[key_type]value_type{key1: val1, key2: val2}
Die Hauptoperationen werden wie folgt ausgeführt:
- Einfügen:
m[key] = value
- Entfernung:
delete(m, key)
- Suche:
value = m[key]
oder
value, ok = m[key]
Gehen Sie um einen Tisch herum
Betrachten Sie das folgende Programm:
package main import "fmt" func main() { m := map[int]bool{} for i := 0; i < 5; i++ { m[i] = ((i % 2) == 0) } for k, v := range m { fmt.Printf("key: %d, value: %t\n", k, v) } }
Start 1:
key: 3, value: false key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true
Lauf 2:
key: 4, value: true key: 0, value: true key: 1, value: false key: 2, value: true key: 3, value: false
Wie Sie sehen können, variiert die Ausgabe von Lauf zu Lauf. Und das alles, weil die Karte in Go ungeordnet ist, dh nicht geordnet. Dies bedeutet, dass Sie sich beim Herumlaufen nicht auf Ordnung verlassen müssen. Der Grund kann im Quellcode der Sprachlaufzeit gefunden werden:
Der Suchort wird
zufällig bestimmt, denken Sie daran! Gerüchten zufolge zwingen Laufzeitentwickler Benutzer dazu, sich nicht auf die Reihenfolge zu verlassen.
Gehen Sie zur Tabellensuche
Schauen wir uns noch einmal einen Code an. Angenommen, wir möchten Paare "Nummer" - "Nummer mal 10" erstellen:
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} fmt.Println(m, m[0], m[1], m[2]) }
Wir starten:
map[0:0 1:10] 0 10 0
Und wir sehen, dass wir beim Versuch, den Wert von zwei zu erhalten (den wir vergessen haben zu setzen), 0 erhalten haben. In der
Dokumentation finden wir Zeilen, die dieses Verhalten erklären: „Ein Versuch, einen Kartenwert mit einem Schlüssel abzurufen, der nicht in der Karte vorhanden ist, gibt den Wert Null für zurück der Typ der Einträge in der Karte. “, aber ins Russische übersetzt, bedeutet dies, dass wir, wenn wir versuchen, den Wert von der Karte zu erhalten, aber nicht vorhanden sind, einen„ Wert vom Typ Null “erhalten, der im Fall der Zahl 0 gilt. ob wir zwischen den Fällen 0 und 2 unterscheiden wollen? Zu diesem Zweck haben wir eine spezielle Form der "Mehrfachzuweisung" entwickelt - eine Form, bei der die Karte anstelle des üblichen Einzelwerts ein Paar zurückgibt: den Wert selbst und einen anderen Booleschen Wert, der die Frage beantwortet, ob der angeforderte Schlüssel in der Karte vorhanden ist oder nicht.
Richtig sieht der vorherige Code folgendermaßen aus:
package main import ( "fmt" ) func main() { m := map[int]int{0: 0, 1: 10} m2, ok := m[2] if !ok {
Und beim Start bekommen wir:
map[0:0 1:10] 0 10 20
Erstellen Sie eine Tabelle in Go.
Angenommen, wir möchten die Anzahl der Vorkommen jedes Wortes in einer Zeichenfolge zählen, ein Wörterbuch dafür starten und es durchgehen.
package main func main() { var m map[string]int for _, word := range []string{"hello", "world", "from", "the", "best", "language", "in", "the", "world"} { m[word]++ } for k, v := range m { println(k, v) } }
Sehen Sie einen
Gopher- Fang? - Und er ist!
Wenn wir versuchen, ein solches Programm zu starten, bekommen wir eine Panik und die Meldung "Zuordnung zum Eintrag in keine Karte". Und alles, da mapa ein Referenztyp ist und es nicht ausreicht, eine Variable zu deklarieren, müssen Sie sie initialisieren:
m := make(map[string]int)
Etwas tiefer wird klar, warum dies so funktioniert. Zu Beginn wurden bereits vier Möglichkeiten zum Erstellen einer Karte vorgestellt, von denen zwei von uns untersucht wurden - diese Deklaration als Variable und die Erstellung durch make. Sie können auch mit dem Design "
Zusammengesetzte Literale " erstellen
map[key_type]value_type{}
Wenn Sie möchten, können Sie diese Methode auch sofort mit Werten initialisieren. Was die Erstellung mit new betrifft, ist dies meiner Meinung nach nicht sinnvoll, da diese Funktion Speicher für eine Variable reserviert und einen Zeiger darauf zurückgibt, der mit einem Nullwert des Typs gefüllt ist, der im Fall von map null ist (wir erhalten das gleiche Ergebnis wie in var genauer gesagt ein Zeiger darauf).
Wie wird die Karte an eine Funktion übergeben?
Angenommen, wir haben eine Funktion, die versucht, die an sie übergebene Nummer zu ändern. Mal sehen, was vor und nach dem Anruf passiert:
package main func foo(n int) { n = 10 } func main() { n := 15 println("n before foo =", n) foo(n) println("n after foo =", n) }
Ein Beispiel, denke ich, ist ziemlich offensichtlich, enthält aber immer noch die Schlussfolgerung:
n before foo = 15 n after foo = 15
Wie Sie wahrscheinlich vermutet haben, wurde die Funktion n nach Wert und nicht nach Referenz angegeben, sodass sich die ursprüngliche Variable nicht geändert hat.
Machen wir einen ähnlichen Mapa-Trick:
package main func foo(m map[int]int) { m[10] = 10 } func main() { m := make(map[int]int) m[10] = 15 println("m[10] before foo =", m[10]) foo(m) println("m[10] after foo =", m[10]) }
Und siehe da:
m[10] before foo = 15 m[10] after foo = 10
Der Wert hat sich geändert. "Nun, Mapa wird als Referenz übergeben?", Fragen Sie.
Nein. Es gibt keine Links in Go. Es ist unmöglich, 2 Variablen mit 1 Adresse zu erstellen, wie zum Beispiel in C ++. Dann können Sie jedoch zwei Variablen erstellen, die auf dieselbe Adresse verweisen (dies sind jedoch Zeiger, und sie befinden sich in Go).
Angenommen, wir haben eine Funktion fn, die die Karte m initialisiert. In der Hauptfunktion deklarieren wir einfach eine Variable, senden sie zur Initialisierung und schauen, was danach passiert ist.
package main import "fmt" func fn(m map[int]int) { m = make(map[int]int) fmt.Println("m == nil in fn?:", m == nil) } func main() { var m map[int]int fn(m) fmt.Println("m == nil in main?:", m == nil) }
Fazit:
m == nil in fn?: false
m == nil in main?: true
Die Variable m wurde also als
Wert übergeben , daher änderte sie sich nicht, wie im Fall der Übergabe eines regulären int an die Funktion (die lokale Kopie des Werts in fn wurde geändert). Warum ändert sich dann der in m selbst liegende Wert? Betrachten Sie zur Beantwortung dieser Frage den Code aus der Sprachlaufzeit:
Map in Go ist nur ein Zeiger auf die hmap-Struktur. Dies ist die Antwort auf die Frage, warum sich die Werte selbst ändern, obwohl die Karte als Wert an die Funktion übergeben wird - es geht nur um den Zeiger. Die hmap-Struktur enthält außerdem Folgendes: die Anzahl der Elemente, die Anzahl der „Buckets“ (dargestellt als Logarithmus zur Beschleunigung der Berechnungen), Startwert für die Randomisierung von Hashes (um das Hinzufügen zu erschweren - versuchen Sie, Schlüssel so aufzunehmen, dass es zu kontinuierlichen Kollisionen kommt), alle Arten von Servicefeldern und vor allem ein Zeiger auf Buckets, in denen die Werte gespeichert sind. Schauen wir uns das Bild an:
Das Bild zeigt ein schematisches Bild der Struktur im Speicher - es gibt einen hmap-Header, dessen Zeiger eine Karte in Go ist (sie wird erstellt, wenn sie mit var deklariert wird, aber nicht initialisiert, was dazu führt, dass das Programm beim Versuch, sie einzufügen, abstürzt). Das Buckets-Feld ist ein Repository von Schlüssel-Wert-Paaren. Es gibt mehrere solcher Buckets, die jeweils 8 Paare enthalten. Zuerst im "Bucket" befinden sich Slots für zusätzliche Hash-Bits (e0..e7 heißt e - weil
zusätzliche Hash-Bits). Als nächstes werden die Schlüssel und Werte zuerst als Liste aller Schlüssel und dann als Liste aller Werte angezeigt.
Der Hash der Funktion bestimmt, in welchen Bucket wir den Wert eingeben. In jedem Bucket können bis zu 8 Kollisionen auftreten. Am Ende jedes Buckets befindet sich ein Zeiger auf einen weiteren, wenn der vorherige überläuft.
Wie wächst die Karte?
Im Quellcode finden Sie die Zeile:
Das heißt, wenn in jedem Bucket durchschnittlich mehr als 6,5 Elemente vorhanden sind, tritt eine Erhöhung des Buckets-Arrays auf. In diesem Fall wird das Array zweimal mehr zugewiesen, und die alten Daten werden bei jedem Einfügen oder Löschen in kleinen Abschnitten in das Array kopiert, um keine sehr großen Verzögerungen zu verursachen. Daher werden alle Vorgänge beim Evakuieren von Daten etwas langsamer sein (auch bei der Suche müssen wir an zwei Stellen suchen). Nach einer erfolgreichen Evakuierung werden neue Daten verwendet.
Nehmen Sie die Adresse des Kartenelements.
Ein weiterer interessanter Punkt - ganz am Anfang der Verwendung der Sprache, die ich so machen wollte:
package main import ( "fmt" ) func main() { m := make(map[int]int) m[1] = 10 a := &m[1] fmt.Println(m[1], *a) }
Aber Go sagt: "Ich kann die Adresse von m [1] nicht annehmen." Die Erklärung, warum es unmöglich ist, die Adresse des Wertes zu ermitteln, liegt im Datenevakuierungsverfahren. Stellen Sie sich vor, wir haben die Adresse des Werts genommen, und dann ist die Mapa gewachsen, neuer Speicher wurde zugewiesen, die Daten wurden evakuiert, die alten wurden gelöscht, der Zeiger wurde falsch, sodass solche Vorgänge verboten sind.
Wie wird Map ohne Generika implementiert?
Weder eine leere Schnittstelle noch die Codegenerierung haben etwas damit zu tun. Das Ganze besteht darin, sie beim Kompilieren zu ersetzen. Überlegen Sie, was aus den bekannten Funktionen von Go wird:
v := m["k"] → func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer v, ok := m["k"] → func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) m["k"] = 9001 → func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer delete(m, "k") → func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
Wir sehen, dass es Mapaccess-Funktionen für Zugriffe zum Schreiben und Löschen von Mapassign bzw. Mapdelete gibt. Alle Operationen verwenden unsafe.Pointer, wobei es egal ist, auf welchen Typ er zeigt, und Informationen zu jedem Wert werden durch einen Typdeskriptor beschrieben.
type mapType struct { key *_type elem *_type ...} type _type struct { size uintptr alg *typeAlg ...} type typeAlg struct { hash func(unsafe.Pointer, uintptr) uintptr equal func(unsafe.Pointer, unsafe.Pointer) bool...}
MapType speichert die Deskriptoren (_type) des Schlüssels und des Werts. Für einen Typdeskriptor werden Vergleichsoperationen (typeAlg) definiert, die einen Hash, eine Größe usw. verwenden, sodass wir immer wissen, wie sie erstellt werden.
Ein bisschen mehr darüber, wie es funktioniert. Wenn wir v = m [k] schreiben (versuchen, den Wert von v aus dem Schlüssel k zu erhalten), generiert der Compiler Folgendes:
kPointer := unsafe.Pointer(&k) vPointer := mapaccess1(typeOf(m), m, kPointer) v = *(*typeOfvalue)vPointer
Das heißt, wir nehmen einen Zeiger auf einen Schlüssel, die mapType-Struktur, aus der wir herausfinden, welche Deskriptoren des Schlüssels und des Werts, den Zeiger auf hmap selbst (dh map), und übergeben alles an mapaccess1, wodurch ein Zeiger auf den Wert zurückgegeben wird. Wir setzen den Zeiger auf den gewünschten Typ, dereferenzieren und erhalten den Wert.
Schauen wir uns nun den Suchcode aus der Laufzeit an (der zum Lesen leicht angepasst ist):
func lookup(t *mapType, m *mapHeader, key unsafe.Pointer) unsafe.Pointer {
Die Funktion sucht nach dem Schlüssel in der Zuordnung und gibt einen Zeiger auf den entsprechenden Wert zurück. Die Argumente sind uns bereits bekannt. Dies ist mapType, in dem Deskriptoren der Schlüsseltypen und -werte gespeichert werden, map selbst (mapHeader) und ein Zeiger auf den Speicher, in dem der Schlüssel gespeichert ist. Wir geben einen Zeiger auf den Speicher zurück, in dem der Wert gespeichert ist.
if m == nil || m.count == 0 { return zero }
Als nächstes prüfen wir, ob der Zeiger auf den Map-Header nicht null ist, wenn dort 0 Elemente vorhanden sind, und geben gegebenenfalls einen Nullwert zurück.
hash := t.key.hash(key, m.seed)
Wir berechnen den Schlüssel-Hash (wir wissen, wie man für einen bestimmten Schlüssel aus einem Typdeskriptor berechnet). Dann versuchen wir zu verstehen, welchen „Eimer“ Sie sehen müssen (der Rest der Division durch die Anzahl der „Eimer“ wird nur geringfügig beschleunigt). Dann berechnen wir den zusätzlichen Hash (wir nehmen die 8 höchstwertigen Bits des Hash) und bestimmen die Position des „Buckets“ im Speicher (Adressarithmetik).
for { for i := 0; i < 8; i++ { if b.extra[i] != extra {
Die Suche ist nicht so kompliziert: Wir gehen die Ketten der "Eimer" durch und fahren mit der nächsten fort, wenn Sie sie nicht gefunden haben. Die Suche im "Bucket" beginnt mit einem schnellen Vergleich des zusätzlichen Hashs (deshalb sind diese e0 ... e7 am Anfang eines jeden ein "Mini" -Hash des Paares für einen schnellen Vergleich). Wenn es nicht übereinstimmt, gehen Sie weiter, wenn dies der Fall ist, überprüfen wir es genauer - wir bestimmen, wo der Schlüssel, nach dem gesucht wird, im Speicher liegt, und vergleichen, ob er dem entspricht, was angefordert wurde. Wenn gleich, bestimmen Sie die Position des Werts im Speicher und kehren Sie zurück. Wie Sie sehen können, nichts Übernatürliches.
Fazit
Verwenden Sie Karten, aber wissen und verstehen Sie, wie sie funktionieren! Sie können den Rake vermeiden, indem Sie einige der Feinheiten verstehen - warum Sie die Adresse des Werts nicht übernehmen können, warum während der Deklaration alles ohne Initialisierung fällt, warum es besser ist, Speicher im Voraus zuzuweisen, wenn die Anzahl der Elemente bekannt ist (wir werden Evakuierungen vermeiden) und vieles mehr.
Referenzliste:
"Go Maps in Aktion", Andrew Gerrand„Wie die Go-Laufzeit Karten effizient implementiert“, sagt Dave Cheney"Typ in go verstehen", William KennedyInnerhalb der Kartenimplementierung Keith RandallKartenquellcode, Go RuntimeGolang speceffektiv gehenGopher-Bilder