Condivisione della tecnologia

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

Spiegazione dettagliata della mappa per iniziare con la lingua Go

1.Definizione di base

map è una raccolta non ordinata di coppie chiave-valore in formato kv

(1) Caratteristiche

• Caratteristiche del tipo: map è un tipo di riferimento, quindi l'aggiornamento del valore nella funzione lo modificherà in modo permanente.
• Caratteristiche sequenziali: l'attraversamento della mappa non è ordinato, perché il livello inferiore è una tabella hash e la tabella hash non è ordinata.
• Utilizzo dell'inizializzazione: il valore 0 o il valore non inizializzato è pari a zero. Il valore non inizializzato non può essere assegnato, altrimenti si verificherà direttamente il panico.
• Coppia chiave-valore: chiave e valore vengono sempre visualizzati in coppia, la chiave è univoca e può essere di qualsiasi tipo comparabile
• Dinamico: le coppie chiave-valore possono essere aggiunte o eliminate dinamicamente in fase di runtime senza la necessità di dichiararne anticipatamente la dimensione
• Ricerca veloce: la mappa consente operazioni di ricerca, inserimento e cancellazione veloci, con una complessità temporale media pari a O(1)
• Concorrenza: non thread-safe, è necessario il blocco per garantire la sicurezza

(2) Dichiarazione di definizione

var name map[key_type]value_type
1

• nome: nome della variabile
• key_type: tipo di chiave
• value_type: tipo di valore

// 方式一
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.Uso di base

(1) Aggiungi elementi

• 1. Il metodo più comune è aggiungerlo quando si dichiara map through letterali, come mostrato nel metodo 2 sopra.
• 2. Il secondo passaggio consiste nell'impostare direttamente il valore corrispondente per la chiave specificata.

mapName[key] = value

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

(2) Elimina elementi

Elimina gli elementi in base alle chiavi e non verrà segnalato alcun errore durante l'eliminazione di chiavi inesistenti.

delete(mapName, key)  

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

(3) Modificare gli elementi

Per modificare, è possibile modificare direttamente il valore corrispondente alla chiave specificata.

mapName[key] = newValue 

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

(4) Ottieni elementi

Ottieni il valore in base alla chiave, ok è il bit flag se viene trovato, il tipo è booleano

Se il valore non viene trovato, non verrà segnalato alcun errore e verrà restituito un valore nullo del tipo corrispondente.

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

(5) Attraversa tutti gli elementi

Nota: l'attraversamento della mappa non è ordinato

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

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

3. Principi fondamentali

L'essenza sottostante della mappa nella lingua golang è l'usohashmapimplementato, quindi la mappa è essenzialmente哈希表。

哈希表è un uso哈希函数Organizzare i dati in strutture dati che supportano l'inserimento e la ricerca rapidi.

哈希函数 , nota anche come funzione hash, è una funzione che converte un input di qualsiasi lunghezza (come una stringa) in un output di lunghezza fissa attraverso uno specifico algoritmo hash. I valori hash vengono generalmente archiviati in una forma simile a un array per garantire le prestazioni di accesso dei valori hash.

Se l'intervallo dell'input supera l'intervallo dell'output mappato, è possibile che input diversi ottengano lo stesso output哈希冲突。

Di solito ci sono due modi per risolvere questo problema:开放地址法E拉链法

(1) Piano di attuazione della mappa

Metodo indirizzo aperto:

Le strutture dati vengono solitamente implementate utilizzando array

• 1. Prima di tutto, l'array è composto da diversi valori hash, che viene chiamata tabella hash.
• 2. Quindi eseguire molti tasti ed eseguire una funzione hash per confermare che l'indirizzo è posizionato nella posizione corrispondente. Se questo slot della tabella hash è già occupato, utilizzare una sequenza di rilevamento (come rilevamento lineare, rilevamento secondario o doppio hashing , ecc.) per trovare la chiave successiva Uno slot disponibile e memorizzare lì le chiavi in ​​conflitto.

discordanza:

Questo approccio richiede più spazio per risolvere i conflitti perché non solo i dati vengono archiviati, ma è necessario spazio aggiuntivo per risolvere le collisioni.

Metodo Zipper (la mappa della lingua Go utilizza questo metodo):

Gli array e gli elenchi collegati vengono solitamente utilizzati come strutture dati sottostanti

• 1. Prima di tutto, l'array è composto da diversi valori hash, chiamati tabella hash. Ciascuno slot della tabella hash memorizzerà un elenco collegato.
• 2. Successivamente arriveranno molte chiavi. Dopo l'hashing di chiavi diverse, il valore hash viene calcolato in modo modulare e collegato all'array. Nel caso dello stesso valore hash (collisione hash), la nuova chiave verrà appesa nell'elenco delle chiavi esistente . Dopo
• 3. Quando è necessario trovare una chiave specifica, utilizzare prima una funzione hash per determinarne la posizione, quindi eseguire una ricerca lineare sull'elenco collegato in quella posizione finché non si trova una chiave corrispondente o si raggiunge la fine dell'elenco collegato.

Una lista concatenata collegata a diversi indici di un array è anche chiamata bucket.

(2) La struttura sottostante della mappa

mappa

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

mappa b

Nel codice sorgente, il tipo bmap ha un solo campo tophash.Ma durante la compilazione, il compilatore Go inietterà automaticamente la chiave, il valore e altre strutture corrispondenti in base al codice utente.

Bmap di superficie

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

bmap effettiva

// 编译期间会动态地创建一个新的结构：
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

Mappa diagramma sottostante

Espansione della mappa

Nella lingua Go, l'espansione della mappa viene eseguita automaticamente per mantenere le prestazioni della mappa.

Innanzitutto, durante la scrittura, passa la mapparuntime.mapassignDetermina se è necessaria l'espansione

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

Secondo il codice di cui sopra, ci sono due condizioni per giudicare l’espansione:

• Il fattore di carico supera la soglia 6,5:overLoadFactor(h.count+1, h.B) , fattore di carico = numero di elementi ÷ numero di benne
• Sono stati utilizzati troppi contenitori di overflow (superati 32768):tooManyOverflowBuckets(h.noverflow, h.B))

Metodo di espansione:

• Espansione incrementale:

Quando il fattore di carico è troppo grande, viene creato un nuovo bucket la cui lunghezza è doppia rispetto a quella originale, quindi i vecchi dati del bucket vengono spostati nel nuovo bucket.

• Equa espansione della capacità

Non ci sono molti dati, ma ci sono troppi contenitori di overflow.Durante l'espansione, il numero di bucket rimane invariato. Le operazioni di riposizionamento simili all'espansione incrementale vengono eseguite nuovamente e le coppie chiave-valore sciolte vengono riorganizzate per aumentare l'utilizzo dei bucket e garantire un accesso più rapido.

Passaggi di espansione:

• 1. Nuovo array di bucket:Creane uno nuovo con le dimensioni originaliDoppioIl nuovo array di bucket verrà contrassegnato come espanso.

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. Ripetizione: utilizza oldbuckets per puntare all'array di bucket originale, bucket per puntare al nuovo array di bucket, attraversa tutte le coppie chiave-valore nel vecchio array di bucket e utilizza la funzione hash per ricalcolare la posizione di ciascuna chiave e inserirle nel nuovo matrice di secchi.

// 这个是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. Migrazione graduale: Per evitare di mettere in pausa l'intero programma durante l'espansione, è possibile scegliere l'implementazione di Go's Map渐进式驱逐 Migrare le coppie chiave-valore. Ciò significa che durante l'espansione, il vecchio bucket array e il nuovo bucket array esisteranno contemporaneamente, le coppie chiave-valore appena inserite verranno inserite direttamente nel nuovo bucket e l'accesso al vecchio bucket attiverà un'operazione di migrazione.

// 进入后是一个简单的判断，之后的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. Aggiorna lo stato interno: quando tutte le coppie chiave-valore nei oldbuckets verranno riposizionate, lo stato interno della mappa verrà aggiornato e i oldbuckets verranno eliminati.

4.Scenari di utilizzo

• 1.ricerca rapida: quando è necessario cercare rapidamente un valore in base a una chiave, Map fornisce prestazioni di ricerca con una complessità temporale media di O(1).
• 2.Rimuovi i duplicati: Quando è necessario memorizzare chiavi univoche, le chiavi mappa non possono essere ripetute e la funzione di deduplicazione può essere ottenuta naturalmente.
• 3.raccolta dinamica: Map fornisce operazioni flessibili quando è necessario aggiungere o eliminare dinamicamente coppie chiave-valore.
• 4.Dati collegati: Map è una buona scelta quando i dati esistono sotto forma di coppie chiave-valore e devono essere aggiornati o interrogati frequentemente.

5. Suggerimenti per l'uso

1. preassegnato: Prova a utilizzare la funzione make per allocare capacità su una mappa di dimensioni note.
2. Selezione del tipo di dati: utilizza tipi di dati più grandi, comeintOint64。
3. Memorizzazione del puntatore: Per strutture o variabili con grandi quantità di dati, provare a utilizzare i puntatori per trasferire e memorizzare valori.
4. Controllo della concorrenza: Per l'accesso simultaneo, utilizzaresync.MapOppure implementa la tua mappa contemporaneamente sicura.

6.Materiali di riferimento

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