Descripción detallada de la tabla hash
La idea básica del almacenamiento hash es establecer la relación correspondiente entre la palabra clave y su ubicación de almacenamiento, o en otras palabras, la dirección de almacenamiento de los datos está determinada por el valor del código clave. .
De esta forma no es necesaria ninguna comparación y el método de búsqueda del elemento buscado se puede obtener en una sola visita.
Ventajas: La velocidad de búsqueda es extremadamente rápida (O (1)) y la eficiencia de la búsqueda no tiene nada que ver con la cantidad de elementos n.
Método Hash (Método Hash)
Seleccione una función según la cual la ubicación de almacenamiento del elemento se calcula en función de la palabra clave y se almacena en consecuencia durante la búsqueda, la misma función también Calcular; la dirección para un valor dado K y compare K con el contenido de la dirección para determinar si la búsqueda fue exitosa.
Función hash (función hash)
La función de conversión utilizada en el hash se llama función hash. La correspondencia entre la clave de un registro y la dirección de almacenamiento del registro.
Existe una secuencia de elementos de datos (14, 23, 39, 9, 25, 11). Si la dirección de almacenamiento de cada elemento K se especifica como H (k) = k, H (k) se denomina función hash y se dibuja un diagrama de estructura de almacenamiento.
De acuerdo con la función hash h(k) = k, se puede ver que el elemento 14 debe almacenarse en la unidad con dirección 14, y el elemento 23 debe almacenarse en la unidad con dirección 23.
Según la expresión de la función hash H(k) utilizada en el almacenamiento, ¡el resultado se puede encontrar inmediatamente!
Por ejemplo, al buscar la clave=9 se accederá a la dirección H(9)=9. Si el contenido es 9, será exitoso.
Si no, debes intentarlo; Devuelve un valor especial, como un puntero nulo o un registro nulo.
Obviamente, la eficiencia espacial de este método de búsqueda es demasiado baja.
La función hash se puede escribir como: addr(ai)=H(ki)
Elija una función en función de la cual se calcule la ubicación de almacenamiento del elemento en función de la palabra clave y almacenado en consecuencia; en Al buscar, la misma función también calcula la dirección para un valor dado K y compara K con el contenido de la dirección para determinar si la búsqueda fue exitosa. La función de conversión utilizada en el hash se denomina función hash. Es una relación de correspondencia que se establece entre el código clave del registro y la dirección de almacenamiento del registro.
Por lo general, el conjunto de códigos clave es mucho mayor que el conjunto de direcciones hash, por lo que se pueden asignar diferentes códigos clave a la misma dirección hash después de ser transformados por la función hash. Esta situación se denomina conflicto.
Existen seis códigos clave: (14, 23, 39, 9, 25, 11).
Seleccione la función entre el código de clave y la posición del elemento como H(k)=k mod 7.
Según la función hash, se descubre que la misma dirección tiene varias claves, lo que genera un conflicto.
En el método de búsqueda de hash, los conflictos son inevitables y sólo pueden reducirse tanto como sea posible.
Por lo tanto, el método hash debe resolver los siguientes dos problemas:
1) La función hash construida.
(a) La función seleccionada es lo más simple posible para aumentar la velocidad de conversión.
(b) Las direcciones calculadas por la función seleccionada para el código clave deben concentrarse; y distribuido de manera aproximadamente uniforme en la dirección Hash para reducir el desperdicio de espacio.
2) Desarrollar un plan de resolución de conflictos.
Al realizar la búsqueda, si la palabra clave no se puede encontrar en la dirección calculada por la función hash, se deben consultar periódicamente otras unidades relacionadas de acuerdo con las reglas de resolución de conflictos.
De los dos ejemplos anteriores, podemos sacar las siguientes conclusiones:
La función Hash es solo una imagen, por lo que la configuración de la función hash es muy flexible, siempre que el El valor de la función hash de cualquier clave se encuentra dentro. Puede estar dentro del rango permitido de longitud de la tabla.
Conflicto: clave1≠clave2, pero H(clave1)=H(clave2).
Sinónimo: dos claves con el mismo valor de función
Las colisiones de funciones hash son inevitables y solo se pueden minimizar.
Por lo tanto, el método hash resuelve dos problemas:
Función hash construida;
Desarrollar requisitos básicos para la resolución de conflictos:
Requisito uno: N Solo los datos originalmente ocupados N direcciones. Aunque la búsqueda de hash intercambia espacio por tiempo, todavía esperamos que el espacio de direcciones del hash sea lo más pequeño posible.
Requisito 2: No importa qué método de almacenamiento se utilice, el propósito es almacenar los elementos de la manera más uniforme posible para evitar conflictos.
Hash (clave) = a clave b (a y b son constantes)
Ventajas: al tomar un valor de función lineal de la clave clave como dirección hash, no habrá conflicto .
Desventajas: Ocupa un espacio de direcciones continuo y tiene una baja eficiencia de espacio.
Por ejemplo, el conjunto de códigos de clave es {100, 300, 500, 700, 800, 900},
Seleccione la función hash como Hash(key)=key/100,
La estructura de almacenamiento (tabla hash) es la siguiente:
Hash(key)=key mod p (p es un número entero)
Característica: toma el resto de dividir la clave por p como dirección hash.
Clave: ¿Cómo elegir la P adecuada? Si P no se elige bien, pueden aparecer sinónimos fácilmente.
Consejo: Si la longitud de la tabla hash diseñada es m, generalmente p≤m es un número primo.
(También puede ser un número compuesto, pero no puede contener factores primos menores que 20).
Hash(clave)=? b(mod 1 con un clic)?
(ayb son constantes, 0
Características: multiplica la clave por a, toma la parte decimal, luego amplifica b veces y redondea a la dirección hash.
Ejemplo: Para procesar los dos últimos dígitos del número de estudiante, la función hash debe ser:
h(k)= 100(0.01k 1)
De hecho, también se puede utilizar la implementación del Método 2: H (k) = k 100.
Características: seleccione algunas palabras clave para formar una dirección hash. El principio de selección debe ser: la frecuencia de aparición de varios símbolos. en este bit es más o menos lo mismo.
p>Por ejemplo: hay un grupo (por ejemplo, 80) códigos clave, sus estilos son los siguientes:
Discusión:
①El primer y segundo dígito son "3, 4". El tercer bit es solo "7, 8, 9", por lo que estos bits no se pueden usar y los cuatro bits restantes están distribuidos uniformemente y se pueden usar. como dirección hash
(2) Si la dirección hash toma dos dígitos (porque solo hay 80 elementos), dos de estos cuatro bits se pueden combinar en una dirección hash, o dos de ellos. se puede sumar con los otros dos bits y los dos dígitos inferiores se pueden usar como dirección hash
Características: después de elevar al cuadrado el código clave, los bits del medio se toman como dirección hash según el tamaño. de la tabla hash (aplicable a situaciones donde no se conocen todas las claves)
Razón: porque el número en el medio está relacionado con cada bit de los datos.
Ejemplo. El valor cuadrado de 2589 es 6702921, y el 029 en el medio se puede usar como dirección.
Características: Cambie el código clave desde la izquierda. Divídalo en varias partes con dígitos iguales a la derecha (el. la última parte puede ser más corta), luego superponga y sume estas partes, y tome los últimos dígitos como la dirección hash de acuerdo con la longitud de la tabla hash
Adecuado para: Hay muchos bits de código clave, y la probabilidad de cada símbolo en cada bit es aproximadamente la misma.
Método 1: método de desplazamiento: alinee y agregue el último bit de cada parte.
Método 2: método de superposición de límites. - después de doblar hacia adelante y hacia atrás a lo largo de la línea divisoria de un extremo al otro, se alinea y se agrega el último dígito
Por ejemplo: elemento 42751896,
Uso 1: 427. 518 96 = 1041.
Uso 2: 427 518 96—> 724 518 69 = 1311
7. Método de números aleatorios
Hash(clave) = aleatorio. (clave) (aleatorio es una función pseudoaleatoria)
Aplicable a: palabras clave de diferentes longitudes.
Es muy conveniente fabricar y encontrar relojes.
Resumen: Principios para construir funciones hash:
(1) Velocidad de ejecución (es decir, el tiempo necesario para calcular la función hash);
②Palabras clave La longitud ;
③El tamaño de la tabla hash;
④Distribución de palabras clave;
⑤Frecuencia de búsqueda.
Idea de diseño: cuando hay un conflicto, busque la siguiente dirección hash vacía. Siempre que la tabla hash sea lo suficientemente grande, siempre se encontrará una dirección hash vacía y se almacenará el elemento de datos.
1) Método de detección lineal
hi =(Hash(key) di)mod m(1≤I lt; m)
Incluyendo:
p>Hash(clave) es una función hash.
m es la longitud de la tabla hash.
Di es la secuencia incremental 1, 2,...m-1, di = i.
El código clave establecido es {47, 7, 29, 11, 16, 92, 22, 8, 3}.
Supongamos: la longitud de la tabla hash es m = 11;
La función hash es hash(key) = keymod 11
Un método de detección lineal; Se propone afrontar el conflicto. Construya la tabla hash de la siguiente manera:
Explicación:
① 47 y 7 son las direcciones hash libres de conflictos obtenidas por la función hash;
② Hash( 29)=7, conflicto de dirección hash. Necesitamos encontrar la siguiente dirección hash vacía: de h 1 = (Hash(29) 1)mod 11 = 8, la dirección hash 8 está vacía, por lo que almacenaremos 29.
③ Además, 22, 8 y 3 también tienen conflictos en las direcciones hash, y H1 también encuentra la dirección hash vacía.
Tres movimientos consecutivos (agregación secundaria)
Ventajas del método de detección lineal: siempre que la tabla hash no esté llena, se garantiza que se encontrará una unidad de dirección vacía para almacenar los conflictos. elements ;
Desventajas del método de detección lineal: es posible almacenar sinónimos de la I-ésima dirección hash en la I-ésima dirección hash, de modo que el elemento que debe almacenarse en la I-ésima La dirección hash se convierte en sinónimo de dirección hash Ith.
Como resultado, muchos elementos pueden "apilarse" en direcciones hash adyacentes, lo que reduce en gran medida la eficiencia de la búsqueda.
Solución: Se puede utilizar un método de detección secundario o un método de detección pseudoaleatorio para mejorar el problema de "acumulación".
2) Método de detección secundario
Tomemos el ejemplo anterior como ejemplo. El segundo método de detección se utiliza para manejar conflictos. La tabla es la siguiente:
Donde: Hash(key) es la función hash.
m es la longitud de la tabla hash y se requiere que m sea un número primo de 4k 3;
Di es 1 2, -1 2, 2 2, -2 2,..., q ^ 2. Secuencia incremental
Nota: Sólo 3 difiere del ejemplo anterior en el manejo de conflictos.
Hash(3)=3, conflicto de dirección hash, causado por
h 1 =(hash(3) 1 2)mod 11 = 4, todavía en conflicto
;H2 =(hash(3)-1 2)mod 11 = 2, busque una dirección hash vacía y guárdela.
3) Si di = secuencia pseudoaleatoria, se denomina método de detección pseudoaleatoria.
Idea básica: vincular registros con la misma dirección hash (los códigos clave son todos sinónimos) en una única lista vinculada, configurar m listas únicas vinculadas para m direcciones hash y luego usar una matriz para almacenar m listas enlazadas individuales. El puntero principal de la lista enlazada forma una estructura dinámica.
Supongamos que la función hash de {47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89} es:
Hash(clave) =key mod 11,
Utilice el método de cremallera para manejar conflictos y luego cree la tabla como se muestra.
Hi=RHi(key) i=1, 2,...,k
RHi es una función hash diferente. Cuando ocurre una colisión, se calcula otra función hash hasta que ya no ocurren colisiones.
Ventajas: no es fácil de recopilar;
Desventajas: mayor tiempo de cálculo.
Idea: además de la tabla hash básica, también se configura otra tabla de vectores de desbordamiento.
Todos los registros cuyas palabras clave sean sinónimos en la tabla base, independientemente de si sus direcciones se obtienen a través de la función hash, se completarán en la tabla de desbordamiento en caso de conflictos.
Claro: No existe una fórmula general "universal" (método Hash) para la función hash, y debe construirse por separado de acuerdo con las características de la colección de elementos.
Discusión: ¿La velocidad de búsqueda de hash es realmente O(1)?
No. Debido a conflictos, el proceso de búsqueda de la tabla hash aún debe compararse y medirse mediante la longitud de búsqueda promedio ASL.
En términos generales, ASL depende del factor de llenado α de la tabla hash, y α representa el grado de llenado de la tabla hash.
0≤α≤1
Cuanto mayor es α, más registros hay en la tabla, lo que significa que la tabla está más llena, la posibilidad de conflicto es mayor y el número de las comparaciones son mayores.
Se conocen un conjunto de palabras clave (19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79).
La función hash es: H(key)=key MOD 13, la longitud de la tabla hash es m=16,
Supongamos que la probabilidad de búsqueda de cada registro es igual.
(1) Los conflictos se repiten utilizando sondas lineales, es decir, hi = (h (clave) di) mod m.
(2) Utilice la segunda sonda y luego el hash para manejar la colisión, es decir, hi = (h (clave) di) mod m.
(3) Utilice el método de dirección en cadena para manejar conflictos.
1) ¿Qué tan eficiente es la búsqueda de almacenamiento de hash?
Respuesta: ¡ASL está relacionado con el factor de llenado α! No es estrictamente O(1) ni O(n).
2) ¿Es el “conflicto” particularmente molesto?
Respuesta: ¡No necesariamente! ¡Debido al conflicto, el archivo no se puede descifrar después del cifrado! Las funciones hash unidireccionales son irreversibles y se usan comúnmente en firmas digitales y cifrado indirecto.
Usa tablas hash: Pequeños cambios en el archivo fuente pueden generar grandes cambios en la tabla hash.