Método de construcción de la función hash
1 Método de direccionamiento directo
Utilice la palabra clave o el valor de la función lineal de la palabra clave como dirección hash. Es decir: H (clave) = clave o H (clave) = una clave b Donde a y b son constantes (esta función hash se denomina función propia).
2. Método de análisis numérico
Supongamos que la palabra clave es un número basado en R (como un número decimal basado en 10) y que todas las palabras clave posibles en la tabla hash han sido pre- Si lo sabe, puede utilizar varios dígitos de la palabra clave para formar una dirección hash.
3. La plaza adopta el estilo francés.
El número del medio después de elevar al cuadrado la palabra clave es la dirección hash. Esta es una forma común de construir una función hash. A menudo, al elegir una función hash, es posible que no conozca todas las palabras clave y que no sea apropiado elegir cuáles, pero el dígito central del cuadrado de un número está asociado con cada dígito de ese número.
4. Método de plegado
Divida la palabra clave en varias partes con el mismo número de dígitos (el número de dígitos en la última parte puede ser diferente) y luego agregue la suma de superposición. (redondeado) de estas partes como dirección Hash. Este método se llama plegado. Cuando hay muchas palabras clave y el número de cada palabra clave está distribuido casi uniformemente, la dirección hash se puede obtener mediante el método de plegado.
5, excepto el resto.
El resto obtenido al dividir la palabra clave por un número p no mayor que la longitud de la tabla hash m es la dirección hash. Es decir, H (clave) = clave MOD p, pm. Esta es la forma más sencilla y común de construir una función hash. No solo puede tomar directamente el módulo (MOD) de la palabra clave, sino también tomar el módulo después de las operaciones de plegado y promediado cuadrado.
6. Método de número aleatorio
Elija una función aleatoria y utilice el valor de la función aleatoria de la palabra clave como su dirección hash, es decir, H (clave) = aleatorio (clave). donde aleatorio es una función aleatoria. Generalmente, es más apropiado utilizar este método para construir una función hash cuando las palabras clave tienen longitudes diferentes.
Manejo de conflictos:
En la tabla hash, diferentes valores clave corresponden a la misma ubicación de almacenamiento. Es decir, la palabra clave K1≠K2, pero H(k 1) = H(K2). Una función hash unificada puede reducir las colisiones, pero no puede evitarlas. Después de que ocurre un conflicto, se debe resolver; es decir, debemos encontrar la siguiente dirección disponible y resolver el conflicto:
1. Método de vinculación (método de cremallera): los registros con la misma dirección hash se almacenan en una lista lineal enlazada en el medio. Por ejemplo, en el método restante, sea la clave (18, 14, 01, 68, 27, 55, 79), el divisor sea 13 y la dirección hash sea (5, 1, 1).
2. Método de direccionamiento abierto: si H(k) ya está ocupado, detecte en el siguiente orden: (H(k) P(1)) Tsize, (H(k) P(2) ). ) ¿Tamaño? , (h(k) p(I)) TTamaño,? donde h(k) es la función hash, TSize es la longitud de la tabla hash y p(I) es la función de detección.
Basado en h(k) p(I-1)) tsize, si se encuentra un conflicto, se realiza una nueva detección usando el incremento p(I) hasta que no ocurra ningún conflicto.
Según las diferentes funciones de detección p (I), el método de direccionamiento abierto se puede dividir en método de detección lineal (p (I) = I: 1, 2, 3,?), método de exploración secundaria ( p(I)=(-1)(I-1)*((I 1)/2) 2. La secuencia de exploración es: 1, -1, 4).
Método de detección aleatoria (p (I): número aleatorio), método de función hash doble (función hash doble h (tecla), HP (tecla) si h (tecla) entra en conflicto, use HP (tecla) para encuentre la dirección hash La secuencia de exploración es: h(k), h(k) HP(k),? h(k) I * HP(k)
3. El cubo es un espacio de almacenamiento lo suficientemente grande.
El direccionamiento de depósito asocia un depósito con cada dirección de la tabla. Si el depósito está lleno, se puede gestionar mediante el método de direccionamiento abierto. Por ejemplo, inserte A5, A2, A3, B5, A9, B2, B9, C2 y resuelva conflictos mediante exploración lineal.