Tabla hash (tabla hash)
Ventajas: la búsqueda uno a uno es muy eficiente.
Desventajas: una palabra clave puede corresponder a múltiples direcciones hash cuando necesita encontrar un rango, el efecto no es bueno; .
Debido a que la matriz es continua, cualquier elemento se puede leer y escribir de acuerdo con el subíndice O (1), por lo que su eficiencia de tiempo es muy alta. Basándonos en la ventaja de la alta eficiencia temporal de las matrices, podemos usar matrices para implementar tablas hash simples: establezca el subíndice de la matriz en el valor clave de la tabla hash y establezca cada número en la matriz en el valor de la tabla hash. , de modo que cada subíndice A y una matriz formen un par clave-valor. Con una tabla hash de este tipo, podemos buscar en O(1), resolviendo así muchos problemas de forma rápida y eficiente.
Es decir, se utiliza una función de algoritmo fijo, también conocida como función hash, para convertir la clave en un número entero y luego usar este número para calcular el resto de la longitud de la matriz, y el El resto se utiliza como subíndice de la matriz. Almacene valores en el espacio de una matriz, con números como subíndices. (O: convierta una entrada de longitud arbitraria (también llamada preimagen) en una salida de longitud fija mediante un algoritmo hash, y la salida es un valor hash. Esta conversión es un mapeo de compresión, es decir, el espacio del valor hash suele ser mayor que el de la entrada. El espacio es mucho más pequeño, diferentes entradas se pueden convertir en la misma salida, por lo que es imposible determinar de forma única el valor de entrada a partir del valor hash. En pocas palabras, es una función que comprime un valor arbitrario. mensaje de longitud fija en un resumen de mensaje de longitud fija)
Las características de las matrices son: fáciles de abordar, difíciles de insertar y eliminar;
Las características de las listas enlazadas son: difíciles de abordar. , fácil de insertar y eliminar;
¿Se pueden combinar las características de los dos para crear una estructura de datos que sea fácil de abordar, insertar y eliminar? La respuesta es sí, esta es la tabla hash de la que estamos hablando. Las tablas hash se pueden implementar de muchas maneras diferentes. A continuación, permítanme explicarles el método de cremallera más utilizado, que puede entenderse como una "matriz de lista vinculada". Como se muestra a continuación.
El lado izquierdo es obviamente una matriz. Cada miembro de la matriz contiene un puntero al encabezado de la lista vinculada. Por supuesto, esta lista vinculada puede estar vacía o puede tener muchos elementos. Asignamos elementos a diferentes listas vinculadas en función de algunas características de los elementos, buscamos la lista vinculada correcta en función de estas características y luego buscamos el elemento de la lista vinculada.
Buena función hash = cálculo simple + distribución uniforme (la dirección hash calculada se distribuye uniformemente)
Conflicto hash: diferentes palabras clave pasan la función hash Se calcula la misma dirección hash.
El más intuitivo es el método hash utilizado en la imagen de arriba. La fórmula es:
Índice = valor% 16
Todos los que han estudiado ensamblaje lo saben. que el módulo El número en realidad se obtiene mediante una operación de división, por lo que se llama "hash de división".
Buscar índices es una operación muy frecuente y la multiplicación requiere más tiempo que la división (para las CPU actuales, probablemente no podamos sentirlo), por lo que consideramos usar la multiplicación y una operación de desplazamiento en lugar de división. Fórmula:
Este método puede obtener buenos resultados si la distribución numérica es relativamente uniforme, pero el índice calculado del valor de cada elemento en la imagen que dibujé arriba es 0: un fracaso. Quizás tengas otra pregunta. ¿No se desbordará el valor*valor si el valor es grande? La respuesta es sí, pero en esta multiplicación no nos importa el desbordamiento porque no queremos obtener el resultado de la multiplicación en absoluto, sino el índice.
Las deficiencias del método de hash al cuadrado son obvias, entonces, ¿podemos encontrar un multiplicador ideal en lugar de usar el valor en sí como multiplicador? La respuesta es sí.
1. Para números enteros de 16 bits, este multiplicador es 40503.
2. Para un entero de 32 bits, el multiplicador es 2654435769.
3. Para enteros de 64 bits, este multiplicador es 11400714819323198485.
¿Cómo se obtienen estos “multiplicadores ideales”? Esto está relacionado con una regla llamada sección áurea, y la expresión más clásica para describir la sección áurea es sin duda la famosa secuencia de Fibonacci, que es una secuencia de esta forma: 0, 1, 1, 2, 3, 5, 8, 13,21,34,55,88.
610, 987, 1597, 2584, 4181, 6765, 10946,... Además, la secuencia de Fibonacci es sorprendentemente coherente con la relación de los radios orbitales de los ocho planetas del sistema solar.
Para nuestros enteros comunes de 32 bits, la fórmula es:
Si usa el hash de Fibonacci, la imagen de arriba se verá así:
El hash de Fibonacci El método será mucho mejor que el método de hash táctil original después del ajuste.
1. Crea una zona de amortiguamiento y coloca a cualquier persona con pinyin repetido en la zona de amortiguamiento. Cuando busqué personas por su nombre, me di cuenta de que lo que estaba buscando no era correcto, así que busqué en el buffer.
2. Basta con buscar en otra parte. Hay muchas formas de detectarlo.
(1) Encuentre la posición en el índice -1, índice +1, índice -2, índice +2, etc. Este método se llama redestección lineal.
(2) Búsqueda aleatoria alrededor del índice de posiciones de búsqueda. Esto se llama prueba aleatoria.
(3) Hash nuevamente. Es decir, cuando exista un conflicto, utilice otro método de mapeo para encontrarlo.