Compartilhamento de tecnologia

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

Explicação detalhada do Map para começar a usar a linguagem Go

1.Definição básica

map é uma coleção não ordenada de pares de valores-chave no formato kv

(1) Recursos

• Características do tipo: map é um tipo de referência, portanto, atualizar o valor na função irá alterá-lo permanentemente.
• Características sequenciais: a travessia do mapa não é ordenada, porque a camada inferior é uma tabela hash e a tabela hash não é ordenada.
• Uso de inicialização: o valor 0 ou o valor não inicializado é nulo. O valor não inicializado não pode ser atribuído, caso contrário, entrará em pânico diretamente.
• Par chave-valor: chave e valor sempre aparecem em pares, a chave é única e pode ser de qualquer tipo comparável
• Dinâmico: pares chave-valor podem ser adicionados ou excluídos dinamicamente em tempo de execução sem a necessidade de declarar o tamanho antecipadamente
• Pesquisa rápida: o mapa fornece operações rápidas de pesquisa, inserção e exclusão, com uma complexidade de tempo média de O(1)
• Simultaneidade: Não é seguro para threads, o bloqueio é necessário para garantir a segurança

(2) Declaração de definição

var name map[key_type]value_type
1

• nome: nome da variável
• key_type: tipo de chave
• value_type: tipo de valor

// 方式一
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 básico

(1) Adicionar elementos

• 1. O método mais comum é adicioná-lo ao declarar o mapa por meio de literais, conforme mostrado no método 2 acima.
• 2. A segunda etapa é definir diretamente o valor correspondente para a chave especificada.

mapName[key] = value

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

(2) Excluir elementos

Exclua elementos com base em chaves e nenhum erro será relatado ao excluir chaves inexistentes.

delete(mapName, key)  

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

(3) Modificar elementos

Para modificar, você pode modificar diretamente o valor correspondente à chave especificada.

mapName[key] = newValue 

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

(4) Obtenha elementos

Obtenha o valor de acordo com a chave, ok é o bit do sinalizador se for encontrado, o tipo é Booleano

Se o valor não for encontrado, nenhum erro será relatado e um valor nulo do tipo correspondente será retornado.

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

(5) Percorra todos os elementos

Nota: a travessia do mapa não é ordenada

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

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

3. Princípios subjacentes

A essência subjacente do mapa na linguagem golang é usarhashmapé implementado, então map é essencialmente哈希表。

哈希表é um uso哈希函数Organize os dados em estruturas de dados que suportam inserção e pesquisa rápidas.

哈希函数 , também conhecida como função hash, é uma função que converte uma entrada de qualquer comprimento (como uma string) em uma saída de comprimento fixo por meio de um algoritmo hash específico. Os valores de hash geralmente são armazenados em formato de array para garantir o desempenho de acesso dos valores de hash.

Se o intervalo da entrada exceder o intervalo da saída mapeada, isso poderá fazer com que entradas diferentes obtenham a mesma saída.哈希冲突。

Geralmente existem duas maneiras de resolver esse problema:开放地址法e拉链法

(1) Plano de implementação do mapa

Método de endereço aberto:

Estruturas de dados geralmente são implementadas usando arrays

• 1. Primeiro, a matriz é composta por diferentes valores hash, chamados de tabela hash.
• 2. Em seguida, execute várias teclas e execute uma função hash para confirmar se o endereço está colocado na posição correspondente. Se este slot da tabela hash já estiver ocupado, use uma sequência de detecção (como detecção linear, detecção secundária ou hash duplo). , etc.) para encontrar o próximo slot disponível e armazenar chaves conflitantes lá.

deficiência:

Essa abordagem requer mais espaço para resolver conflitos porque não apenas os dados são armazenados, mas também é necessário espaço adicional para resolver colisões.

Método Zipper (o mapa de idiomas go usa este método):

Matrizes e listas vinculadas são geralmente usadas como estruturas de dados subjacentes

• 1. Em primeiro lugar, o array é composto por diferentes valores hash, chamados de tabela hash. Cada slot da tabela hash armazenará uma lista vinculada.
• 2. Então, muitas chaves entrarão. Após o hash de chaves diferentes, o valor do hash é calculado modularmente e vinculado ao array. No caso do mesmo valor de hash (colisão de hash), a nova chave será pendurada na lista de chaves existente. . mais tarde
• 3. Quando você precisar encontrar uma chave específica, primeiro use uma função hash para determinar sua localização e, em seguida, execute uma pesquisa linear na lista vinculada naquele local até encontrar uma chave correspondente ou chegar ao final da lista vinculada.

Uma lista vinculada vinculada a diferentes índices de um array também é chamada de bucket.

(2) A estrutura subjacente do mapa

mapa h

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

No código-fonte, o tipo bmap possui apenas um campo tophash.Porém, durante a compilação, o compilador Go injetará automaticamente a chave, o valor e outras estruturas correspondentes de acordo com o código do usuário.

Bmap de superfície

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 real

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

Diagrama subjacente do mapa

Expansão do mapa

Na linguagem Go, a expansão do mapa é realizada automaticamente para manter o desempenho do mapa.

Primeiro, ao escrever, o mapa passaruntime.mapassignDetermine se a expansão é necessária

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

De acordo com o código acima, existem duas condições para julgar a expansão:

• O fator de carga excede o limite 6,5:overLoadFactor(h.count+1, h.B) , fator de carga = número de elementos ÷ número de buckets
• Muitos buckets de estouro usados ​​(excederam 32.768):tooManyOverflowBuckets(h.noverflow, h.B))

Método de expansão:

• Expansão incremental:

Quando o fator de carga é muito grande, um novo intervalo é criado. O novo comprimento do intervalo é o dobro do comprimento original e, em seguida, os dados do intervalo antigo são movidos para o novo intervalo.

• Expansão igual de capacidade

Não há muitos dados, mas há muitos buckets de estouro.Durante a expansão, o número de buckets permanece inalterado. Operações de realocação semelhantes à expansão incremental são executadas novamente e pares de valores-chave soltos são reorganizados para aumentar o uso do bucket e garantir acesso mais rápido.

Etapas de expansão:

• 1. Nova matriz de baldes:Crie um novo com o tamanho originaldobroA nova matriz de buckets será marcada como expandida.

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. Repetir: Use oldbuckets para apontar para a matriz de bucket original, buckets para apontar para a nova matriz de bucket, percorra todos os pares de valores-chave na matriz de bucket antiga e use a função hash para recalcular a posição de cada chave e inseri-los no novo matriz de balde.

// 这个是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. Migração gradual: Para evitar pausar todo o programa durante a expansão, a implementação do Go's Map pode escolher渐进式驱逐 Migre pares de valores-chave. Isso significa que durante a expansão, a matriz de bucket antiga e a nova matriz de bucket existirão ao mesmo tempo, os pares de valores-chave recém-inseridos serão colocados diretamente no novo bucket e o acesso ao bucket antigo acionará uma operação de migração.

// 进入后是一个简单的判断，之后的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. Atualize o status interno: quando todos os pares de valores-chave nos oldbuckets forem realocados, o estado interno do mapa será atualizado e os oldbuckets serão excluídos.

4. Cenários de uso

• 1.pesquisa rápida: quando você precisa pesquisar rapidamente um valor com base em uma chave, o Map fornece desempenho de pesquisa com uma complexidade de tempo média de O(1).
• 2.Remover duplicatas: Quando chaves exclusivas precisam ser armazenadas, as chaves do mapa não podem ser repetidas e a função de desduplicação pode ser alcançada naturalmente.
• 3.coleção dinâmica: o mapa fornece operações flexíveis quando pares de valores-chave precisam ser adicionados ou excluídos dinamicamente.
• 4.Dados vinculados: o mapa é uma boa opção quando os dados existem na forma de pares de valores-chave e precisam ser atualizados ou consultados com frequência.

5. Sugestões de uso

1. pré-alocado: tente usar a função make para alocar capacidade para um mapa de tamanho conhecido.
2. Seleção de tipo de dados: use tipos de dados maiores, comointouint64。
3. Armazenamento de ponteiro: Para estruturas ou variáveis ​​com grandes quantidades de dados, tente usar ponteiros para transferir e armazenar valores.
4. Controle de simultaneidade: Para acesso simultâneo, usesync.MapOu implemente seu próprio mapa simultaneamente seguro.

6.Materiais de referência

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