Ir a la estructura de datos del mapa
Principio de implementación y uso del mapa de profundidad de Go
El mapa en go también es un mapa hash y consta de una matriz de depósitos. Cada depósito puede almacenar varios elementos (el valor predeterminado es 8). Cuando hay más de 8 elementos, hmap usará el desbordamiento adicional para señalar un nuevo depósito para expandir el depósito.
Lista vinculada de desbordamiento de matriz de cubos a matriz de bytes de datos de matriz de hash
Estructura de datos después del conflicto de hash:
Desbordamiento significa desbordamiento.
El factor de carga se utiliza para indicar la situación de colisión de hash = número de claves/número de depósitos.
El factor hash debe controlarse en un tamaño adecuado. Si excede el umbral, es necesario repetirlo.
*El factor hash es demasiado pequeño, lo que indica una baja utilización del espacio.
*El factor hash es demasiado grande, lo que indica conflictos graves y baja eficiencia de acceso.
Cada implementación de tabla hash tiene una tolerancia diferente para los factores de carga. Cuando el factor de carga en redis es 1, se activa el refrito porque cada depósito de redis solo puede almacenar un par clave-valor. Go puede almacenar 8 y tiene un factor de carga de 6,5;
4.1 Requisitos previos para la expansión
Para garantizar la eficiencia del acceso, al agregar un nuevo elemento, comprobará si es necesario expandirse. La expansión es en realidad espacio.
4.2 Expansión incremental
Después de que el factor de carga exceda el umbral, cree un nuevo cubo con el doble de la longitud original y mueva gradualmente el. número de cubos viejos por barril nuevo.
Si la cantidad de datos es grande, se utilizará hash progresivo. Cada acceso al mapa activará una reubicación, dos pares clave-valor cada vez, y los oldbuckets se eliminarán una vez completada la reubicación. ;
4.3 Capacidad de contracción
A través de la eliminación continua; los pares clave-valor se concentran en unos pocos depósitos; y la mayoría de los desbordamientos están vacíos después de la reorganización, la cantidad de depósitos se reducirá; mejorando así la eficiencia del acceso.