Compartir tecnología

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

Explicación detallada de Map para comenzar con el lenguaje Go

1.Definición básica

map es una colección desordenada de pares clave-valor en formato kv

(1) Características

• Características del tipo: el mapa es un tipo de referencia, por lo que actualizar el valor en la función lo cambiará permanentemente.
• Características secuenciales: el recorrido del mapa está desordenado porque la capa inferior es una tabla hash y la tabla hash está desordenada.
• Uso de inicialización: el valor 0 o el valor no inicializado es nulo no se puede asignar; de lo contrario, entrará en pánico directamente.
• Par clave-valor: la clave y el valor siempre aparecen en pares, la clave es única y puede ser de cualquier tipo comparable
• Dinámico: los pares clave-valor se pueden agregar o eliminar dinámicamente en tiempo de ejecución sin necesidad de declarar el tamaño por adelantado
• Búsqueda rápida: el mapa proporciona operaciones rápidas de búsqueda, inserción y eliminación, con una complejidad de tiempo promedio de O (1)
• Concurrencia: no es seguro para subprocesos, se requiere bloqueo para garantizar la seguridad

(2) Declaración de definición

var name map[key_type]value_type
1

• nombre: nombre de la variable
• key_type: tipo de clave
• tipo_valor: 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) Agregar elementos

• 1. El método más común es agregarlo al declarar el mapa mediante literales, como se muestra en el método 2 anterior.
• 2. El segundo paso es establecer directamente el valor correspondiente para la clave especificada.

mapName[key] = value

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

(2) Eliminar elementos

Elimine elementos según claves y no se informará ningún error al eliminar claves inexistentes.

delete(mapName, key)  

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

(3) Modificar elementos

Para modificar, puede modificar directamente el valor correspondiente a la clave especificada.

mapName[key] = newValue 

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

(4) Obtener elementos

Obtenga el valor de acuerdo con la clave, está bien si se encuentra el bit de bandera, el tipo es booleano

Si no se encuentra el valor, no se informará ningún error y se devolverá un valor nulo del tipo correspondiente.

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

(5) Atravesar todos los elementos

Nota: el recorrido del mapa no está ordenado

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

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

3. Principios subyacentes

La esencia subyacente del mapa en el lenguaje golang es utilizarhashmapestá implementado, por lo que el mapa es esencialmente哈希表。

哈希表es un uso哈希函数Organice los datos en estructuras de datos que admitan una inserción y búsqueda rápidas.

哈希函数 , también conocida como función hash, es una función que convierte una entrada de cualquier longitud (como una cadena) en una salida de longitud fija mediante un algoritmo hash específico. Los valores hash generalmente se almacenan en forma de matriz para garantizar el rendimiento del acceso a los valores hash.

Si el rango de la entrada excede el rango de la salida asignada, puede causar que diferentes entradas obtengan la misma salida.哈希冲突。

Generalmente hay dos formas de solucionar este problema:开放地址法y拉链法

(1) Plan de implementación del mapa

Método de dirección abierta:

Las estructuras de datos generalmente se implementan mediante matrices.

• 1. Primero, la matriz se compone de diferentes valores hash, lo que se denomina tabla hash.
• 2. Luego realice muchas claves y realice una función hash para confirmar que la dirección está colocada en la posición correspondiente. Si esta ranura de la tabla hash ya está ocupada, use una secuencia de detección (como detección lineal, detección secundaria o doble hash). , etc.) para encontrar la siguiente clave. Una ranura disponible y almacenar las claves conflictivas allí.

defecto:

Este enfoque requiere más espacio para resolver conflictos porque no solo se almacenan los datos, sino que también se requiere espacio adicional para resolver las colisiones.

Método de cremallera (Go Language Map utiliza este método):

Las matrices y las listas enlazadas se suelen utilizar como estructuras de datos subyacentes.

• 1. En primer lugar, la matriz se compone de diferentes valores hash, llamados tabla hash. Cada ranura de la tabla hash almacenará una lista vinculada.
• 2. Luego entrarán muchas claves. Después de aplicar hash a diferentes claves, el valor hash se calcula de forma modular y se vincula a la matriz. En el caso del mismo valor hash (colisión de hash), la nueva clave se colgará en la lista de claves existente. . más tarde
• 3. Cuando necesite encontrar una clave específica, primero use una función hash para determinar su ubicación y luego realice una búsqueda lineal en la lista vinculada en esa ubicación hasta que encuentre una clave coincidente o llegue al final de la lista vinculada.

Una lista vinculada vinculada en diferentes índices de una matriz también se denomina depósito.

(2) La estructura subyacente del mapa.

Mapa de la Humanidad

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

mapa b

En el código fuente, el tipo bmap tiene solo un campo tophash.Pero durante la compilación, el compilador Go inyectará automáticamente la clave, el valor y otras estructuras correspondientes de acuerdo con el código del usuario.

Mapa de 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

mapa b 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 subyacente del mapa

Ampliación del mapa

En el lenguaje Go, la expansión del mapa se realiza automáticamente para mantener el rendimiento del mapa.

Primero, al escribir, el mapa pasa.runtime.mapassignDeterminar si se necesita expansión

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

Según el código anterior, existen dos condiciones para juzgar la expansión:

• El factor de carga supera el umbral 6,5:overLoadFactor(h.count+1, h.B) , factor de carga = número de elementos ÷ número de cubos
• Se utilizaron demasiados depósitos de desbordamiento (superaron 32768):tooManyOverflowBuckets(h.noverflow, h.B))

Método de expansión:

• Expansión incremental:

Cuando el factor de carga es demasiado grande, se crea un nuevo depósito. La longitud del nuevo depósito es el doble de la longitud original y luego los datos del depósito anterior se mueven al nuevo depósito.

• Ampliación de capacidad igual

No hay muchos datos, pero hay demasiados depósitos desbordados.Durante la expansión, la cantidad de depósitos permanece sin cambios. Se vuelven a realizar operaciones de reubicación similares a la expansión incremental y los pares clave-valor sueltos se reorganizan para aumentar el uso del depósito y garantizar un acceso más rápido.

Pasos de expansión:

• 1. Nueva matriz de depósitos:Crea uno nuevo con el tamaño originaldobleLa nueva matriz de depósitos se marcará 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. Refrito: Use oldbuckets para apuntar a la matriz de depósitos original, depósitos para apuntar a la nueva matriz de depósitos, recorra todos los pares clave-valor en la matriz de depósitos anterior y use la función hash para recalcular la posición de cada clave e insertarlas en la nueva matriz de cubos.

// 这个是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. Migración gradual: Para evitar pausar todo el programa durante la expansión, la implementación del Mapa de Go puede elegir渐进式驱逐 Migrar pares clave-valor. Esto significa que durante la expansión, la matriz de depósitos anterior y la nueva matriz de depósitos existirán al mismo tiempo, los pares clave-valor recién insertados se colocarán directamente en el depósito nuevo y el acceso al depósito anterior desencadenará una operación de migración.

// 进入后是一个简单的判断，之后的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. Actualizar el estado interno: Cuando se reubiquen todos los pares clave-valor en los oldbuckets, el estado interno del Mapa se actualizará y los oldbuckets se eliminarán.

4.Escenarios de uso

• 1.búsqueda rápida: Cuando necesita buscar rápidamente un valor basado en una clave, Map proporciona un rendimiento de búsqueda con una complejidad de tiempo promedio de O(1).
• 2.Eliminar duplicados: Cuando es necesario almacenar claves únicas, no se permite repetir las claves de mapa y, naturalmente, se puede lograr la función de deduplicación.
• 3.colección dinámica: Map proporciona operaciones flexibles cuando es necesario agregar o eliminar pares clave-valor de forma dinámica.
• 4.Datos vinculados: El mapa es una buena opción cuando los datos existen en forma de pares clave-valor y deben actualizarse o consultarse con frecuencia.

5. Sugerencias de uso

1. preasignado: Intente utilizar la función make para asignar capacidad a un mapa de tamaño conocido.
2. Selección de tipo de datos: utilice tipos de datos más grandes, comointoint64。
3. Almacenamiento de puntero: Para estructuras o variables con grandes cantidades de datos, intente utilizar punteros para transferir y almacenar valores.
4. Control de concurrencia: Para acceso simultáneo, utilicesync.MapO implemente su propio mapa simultáneamente seguro.

6.Materiales de referencia

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