Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Ausführliche Erklärung von Map für den Einstieg in die Go-Sprache

1.Grundlegende Definition

Map ist eine ungeordnete Sammlung von Schlüssel-Wert-Paaren im KV-Format

(1) Funktionen

• Typeigenschaften: Map ist ein Referenztyp, daher wird eine Aktualisierung des Werts in der Funktion ihn dauerhaft ändern.
• Sequentielle Merkmale: Die Kartendurchquerung ist ungeordnet, da die unterste Ebene eine Hash-Tabelle ist und die Hash-Tabelle ungeordnet ist.
• Initialisierungsverwendung: 0-Wert oder nicht initialisierter Wert ist Null. Der nicht initialisierte Wert kann nicht zugewiesen werden, da es sonst direkt zu einer Panik kommt.
• Schlüssel-Wert-Paar: Schlüssel und Wert erscheinen immer paarweise, der Schlüssel ist eindeutig und kann von jedem vergleichbaren Typ sein
• Dynamisch: Schlüssel-Wert-Paare können zur Laufzeit dynamisch hinzugefügt oder gelöscht werden, ohne dass die Größe im Voraus angegeben werden muss
• Schnelle Suche: Map bietet schnelle Such-, Einfüge- und Löschvorgänge mit einer durchschnittlichen Zeitkomplexität von O(1)
• Parallelität: Nicht threadsicher, zur Gewährleistung der Sicherheit ist eine Sperre erforderlich

(2) Definitionserklärung

var name map[key_type]value_type
1

• Name: Variablenname
• key_type: Schlüsseltyp
• value_type: Werttyp

// 方式一
var m map[int]string = map[int]string{}

// 方式二
m := map[int]string{
    1 : "老一",
    2 : "老二",
    3 : "老三",
}

// 方式三：5代表容量，也就是在内存中占用多大的空间，可以省略
m := make(map[int]string,5)
1
2
3
4
5
6
7
8
9
10
11
12

2.Grundlegende Verwendung

(1) Elemente hinzufügen

• 1. Die gebräuchlichste Methode besteht darin, es hinzuzufügen, wenn die Karte über Literale deklariert wird, wie in Methode 2 oben gezeigt.
• 2. Der zweite Schritt besteht darin, den entsprechenden Wert für den angegebenen Schlüssel direkt festzulegen.

mapName[key] = value

// 假设map名为m，key为int，value为string
m[5] = "老五"
1
2
3
4

(2) Elemente löschen

Löschen Sie Elemente basierend auf Schlüsseln. Beim Löschen nicht vorhandener Schlüssel wird kein Fehler gemeldet.

delete(mapName, key)  

// 假设map名为m，key为int，value为string
delete(m, 5)
1
2
3
4

(3) Elemente ändern

Zum Ändern können Sie den Wert, der dem angegebenen Schlüssel entspricht, direkt ändern.

mapName[key] = newValue 

// 假设map名为m，key为int，value为string
m[5] = "五"
1
2
3
4

(4) Elemente abrufen

Holen Sie sich den Wert gemäß dem Schlüssel. Ok ist das Flag-Bit, ob er gefunden wird. Der Typ ist Boolesch

Wenn der Wert nicht gefunden wird, wird kein Fehler gemeldet und ein Nullwert des entsprechenden Typs zurückgegeben.

value, ok := mapName[key]
if !ok {
		fmt.Println(ok)
	}
1
2
3
4

(5) Durchqueren Sie alle Elemente

Hinweis: Die Kartendurchquerung ist ungeordnet

for key, value := range myMap {
   // 处理每对键值
}

// 例子
for i, s := range m {
		fmt.Println(i, s)
	}
1
2
3
4
5
6
7
8

3. Grundprinzipien

Die zugrunde liegende Essenz der Karte in der Golang-Sprache ist die Verwendunghashmapimplementiert ist, also ist die Karte im Wesentlichen哈希表。

哈希表ist eine Verwendung哈希函数Organisieren Sie Daten in Datenstrukturen, die schnelles Einfügen und Suchen unterstützen.

哈希函数 , auch als Hash-Funktion bekannt, ist eine Funktion, die eine Eingabe beliebiger Länge (z. B. eine Zeichenfolge) über einen bestimmten Hash-Algorithmus in eine Ausgabe fester Länge umwandelt. Um die Zugriffsleistung von Hash-Werten sicherzustellen, werden Hash-Werte üblicherweise in einer Array-ähnlichen Form gespeichert.

Wenn der Bereich der Eingabe den Bereich der zugeordneten Ausgabe überschreitet, kann dies dazu führen, dass verschiedene Eingaben die gleiche Ausgabe erhalten哈希冲突。

Normalerweise gibt es zwei Möglichkeiten, dieses Problem zu lösen:开放地址法Und拉链法

(1) Kartenimplementierungsplan

Offene Adressmethode:

Datenstrukturen werden normalerweise mithilfe von Arrays implementiert

• 1. Zunächst besteht das Array aus verschiedenen Hash-Werten, einer sogenannten Hash-Tabelle.
• 2. Führen Sie dann viele Schlüssel aus und führen Sie eine Hash-Funktion aus, um zu bestätigen, dass die Adresse an der entsprechenden Position platziert ist. Wenn dieser Slot der Hash-Tabelle bereits belegt ist, verwenden Sie eine Erkennungssequenz (z. B. lineare Erkennung, sekundäre Erkennung oder doppeltes Hashing). usw.), um den nächsten Schlüssel zu finden und dort widersprüchliche Schlüssel zu speichern.

Mangel:

Dieser Ansatz erfordert mehr Speicherplatz zum Lösen von Konflikten, da nicht nur die Daten gespeichert werden, sondern auch zusätzlicher Speicherplatz zum Lösen von Kollisionen erforderlich ist.

Zipper-Methode (Go Language Map verwendet diese Methode):

Als zugrunde liegende Datenstrukturen werden üblicherweise Arrays und verknüpfte Listen verwendet

• 1. Zunächst besteht das Array aus verschiedenen Hash-Werten, die als Hash-Tabelle bezeichnet werden. In jedem Slot der Hash-Tabelle wird eine verknüpfte Liste gespeichert.
• 2. Dann kommen viele Schlüssel rein. Nach dem Hashing verschiedener Schlüssel wird der Hashwert modulo berechnet und mit dem Array verknüpft. Bei gleichem Hashwert (Hashkollision) wird der neue Schlüssel in die bestehende Schlüsselliste eingehängt . später
• 3. Wenn Sie einen bestimmten Schlüssel finden müssen, verwenden Sie zunächst eine Hash-Funktion, um dessen Position zu bestimmen, und führen Sie dann eine lineare Suche in der verknüpften Liste an dieser Position durch, bis Sie einen passenden Schlüssel finden oder das Ende der verknüpften Liste erreichen.

Eine verknüpfte Liste, die an verschiedenen Indizes eines Arrays verknüpft ist, wird auch Bucket genannt.

(2) Die zugrunde liegende Struktur der Karte

hmap

type hmap struct {
 count     int // 当前哈希表中的元素数量，即键值对数量，可用内置函数len()获取
 flags     uint8  // 标志位，标记map状态和属性的字段，如正在迭代等状态
 B         uint8  // 表示哈希表桶（buckets）的数量为2的B次方
 noverflow uint16 // 溢出桶的大致数量，扩容时会用到
 hash0     uint32 // 哈希种子，对key做哈希是加入种子计算哈希值，确保map安全性

 buckets    unsafe.Pointer // 存储桶数组的指针
 oldbuckets unsafe.Pointer // 扩容时用于保存旧桶数组的指针 , 大小为新桶数组的一半
 nevacuate  uintptr        // 扩容时的迁移进度器，迁移桶下标小于此值说明完成迁移

 extra *mapextra // 溢出桶的指针，指向mapextra结构体，用于存储一些额外的字段和信息
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// mapextra 处理桶溢出的结构体
type mapextra struct {
 overflow    *[]*bmap    // 溢出桶数组指针，仅当key和elem非指针时才使用
 oldoverflow *[]*bmap    // 旧的溢出桶数组指针，仅当key和elem非指针时才使用

 nextOverflow *bmap      // 下一个可用的溢出桶地址
}

1
2
3
4
5
6
7
8

bmap

Im Quellcode verfügt der Bmap-Typ nur über ein Tophash-Feld.Während der Kompilierung fügt der Go-Compiler jedoch automatisch entsprechende Schlüssel, Werte und andere Strukturen entsprechend dem Benutzercode ein.

Oberflächen-Bmap

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 [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

1
2
3
4
5
6
7
8
9
10
11
12

tatsächliche Bmap

// 编译期间会动态地创建一个新的结构：
type bmap struct {
   topbits  [8]uint8   // 这里存储哈希值的高八位，用于在确定key的时候快速试错，加快增删改查寻址效率,有时候也叫tophash
   keys     [8]keytype   // 存储key的数组，这里bmap最多存储8个键值对
   elems   [8]valuetype    // 存储value的数组，这里bmap也最多存储8个键值对
   ...
   overflow uintptr     // 溢出桶指针
}

1
2
3
4
5
6
7
8
9

zugrunde liegendes Diagramm zuordnen

Erweiterung der Karte

In der Go-Sprache wird die Kartenerweiterung automatisch durchgeführt, um die Kartenleistung aufrechtzuerhalten.

Beim Schreiben geht zunächst die Karte durchruntime.mapassignStellen Sie fest, ob eine Erweiterung erforderlich ist

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 // If we hit the max load factor or we have too many overflow buckets,
 // and we're not already in the middle of growing, start growing.
 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again // Growing the table invalidates everything, so try again
 }
...
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
 if B > 15 {
  B = 15
 }
 return noverflow >= uint16(1)<<(B&15)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Gemäß dem obigen Code gibt es zwei Bedingungen für die Beurteilung der Expansion:

• Lastfaktor überschreitet Schwellenwert 6,5:overLoadFactor(h.count+1, h.B) , Lastfaktor = Anzahl der Elemente ÷ Anzahl der Eimer
• Zu viele Überlaufeimer verwendet (32768 überschritten):tooManyOverflowBuckets(h.noverflow, h.B))

Erweiterungsmethode:

• Inkrementelle Erweiterung:

Wenn der Lastfaktor zu groß ist, wird ein neuer Bucket erstellt. Die neue Bucket-Länge beträgt das Doppelte der ursprünglichen Länge, und dann werden die alten Bucket-Daten in den neuen Bucket verschoben.

• Gleichmäßige Kapazitätserweiterung

Es gibt nicht viele Daten, aber zu viele Überlaufbuckets.Während der Erweiterung bleibt die Anzahl der Buckets unverändert, ähnlich wie bei der inkrementellen Erweiterung, und lose Schlüssel-Wert-Paare werden neu angeordnet, um die Bucket-Nutzung zu erhöhen und einen schnelleren Zugriff zu gewährleisten.

Ausbauschritte:

• 1. Neues Bucket-Array:Erstellen Sie ein neues mit der OriginalgrößedoppeltDas neue Bucket-Array wird als erweitert markiert.

func hashGrow(t *maptype, h *hmap) {
 ...
 // 原有桶设置给oldbuckets
 oldbuckets := h.buckets   
 // 创建新桶
 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

 flags := h.flags &^ (iterator | oldIterator)
 if h.flags&iterator != 0 {
  flags |= oldIterator
 }
 // commit the grow (atomic wrt gc)
 h.B += bigger
 h.flags = flags
 h.oldbuckets = oldbuckets
 h.buckets = newbuckets
 h.nevacuate = 0
 h.noverflow = 0

 ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 2. Aufwärmen: Verwenden Sie oldbuckets, um auf das ursprüngliche Bucket-Array zu zeigen, Buckets, um auf das neue Bucket-Array zu zeigen, alle Schlüssel-Wert-Paare im alten Bucket-Array zu durchlaufen und die Hash-Funktion zu verwenden, um die Position jedes Schlüssels neu zu berechnen und sie in das neue einzufügen Bucket-Array.

// 这个是mapdelete函数中的处理迁移的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
 if h.growing() {
  // 
  growWork(t, h, bucket)
 }
...
}

1
2
3
4
5
6
7
8
9
10

• 3. Allmähliche Migration: Um zu vermeiden, dass das gesamte Programm während der Erweiterung angehalten wird, kann die Kartenimplementierung von Go ausgewählt werden渐进式驱逐 Schlüssel-Wert-Paare migrieren. Dies bedeutet, dass während der Erweiterung das alte Bucket-Array und das neue Bucket-Array gleichzeitig vorhanden sind, neu eingefügte Schlüssel-Wert-Paare direkt im neuen Bucket platziert werden und der Zugriff auf den alten Bucket einen Migrationsvorgang auslöst.

// 进入后是一个简单的判断，之后的evacuate是核心逻辑处理，特别多，感兴趣自己看源码
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

• 4. Internen Status aktualisieren: Wenn alle Schlüssel-Wert-Paare in den Oldbuckets verschoben werden, wird der interne Status der Karte aktualisiert und die Oldbuckets werden gelöscht.

4. Nutzungsszenarien

• 1.schnelle Suche: Wenn Sie schnell einen Wert basierend auf einem Schlüssel nachschlagen müssen, bietet Map eine Suchleistung mit einer durchschnittlichen Zeitkomplexität von O(1).
• 2.Duplikate entfernen: Wenn eindeutige Schlüssel gespeichert werden müssen, dürfen Kartenschlüssel nicht wiederholt werden, und die Deduplizierungsfunktion kann natürlich erreicht werden.
• 3.dynamische Sammlung: Map bietet flexible Operationen, wenn Schlüssel-Wert-Paare dynamisch hinzugefügt oder gelöscht werden müssen.
• 4.Verknüpfte Daten: Map ist eine gute Wahl, wenn Daten in Form von Schlüssel-Wert-Paaren vorliegen und häufig aktualisiert oder abgefragt werden müssen.

5. Nutzungsvorschläge

1. vorab zugeteilt: Versuchen Sie, die Make-Funktion zu verwenden, um einer Karte bekannter Größe Kapazität zuzuweisen.
2. Auswahl des Datentyps: Verwenden Sie größere Datentypen, zintoderint64。
3. Zeigerspeicher: Versuchen Sie bei Strukturen oder Variablen mit großen Datenmengen, Zeiger zum Übertragen und Speichern von Werten zu verwenden.
4. Parallelitätskontrolle: Für gleichzeitigen Zugriff verwenden Siesync.MapOder implementieren Sie Ihre eigene gleichzeitig sichere Karte.

6.Referenzmaterialien

• https://cloud.tencent.com/developer/article/2400014
• https://blog.csdn.net/qq_35289736/article/details/137480760/
• https://zhuanlan.zhihu.com/p/675715169/