Hash doble

Cuando doble método del valor de propagación o doble dispersión ( Inglés doble dispersión ) es un método para realizar una cerrada método de hash . En los procedimientos de hash cerrados, se intenta acomodar a los desertores en la tabla hash en lugar de almacenarlos dentro de la celda (por ejemplo, como una lista). (Los procedimientos de hash abiertos pueden asignar entradas dos veces y, por lo tanto, no requieren ningún sondeo). Atención: Como se encuentra en la tabla hash de artículos en "Variantes del procedimiento hash", los términos "hash abierto" o "hash cerrado" se utilizan exactamente de la manera opuesta.

Para hacer esto, el doble hash usa una función de sondeo que incluye una función de hash secundaria, p. B. , y que se utiliza si el índice calculado por la función hash primaria ya está ocupado. ${\ Displaystyle \; s (j, k): = j \ cdot h '(k)}$${\ Displaystyle \; h (k)}$

La función hash completa entonces lee:, donde j es el número de índices ya "probados", i. Esto significa que j aumenta en 1 cada vez que ya se utiliza un índice. ${\ Displaystyle \; h (k) -s (j, k)}$

Se supone que la función de sondeo forma una permutación de los índices de la tabla hash. ${\ Displaystyle \; s (j, k)}$

La secuencia de funciones hash que ahora se forman usando y se ve así: ${\ Displaystyle h}$${\ Displaystyle h '}$

${\ Displaystyle h_ {j} (k) = (h (k) + h '(k) \ cdot j) ~ {\ bmod {~}} m}$

El costo de este método está cerca del costo del hash ideal.

Independencia de las funciones hash

El hash doble utiliza dos funciones hash independientes y . Estos se denominan independientes si la probabilidad de una llamada doble colisión, es decir, H. , es menor o igual que, y por lo tanto mínimo, donde es el tamaño de la matriz. ${\ Displaystyle h}$${\ Displaystyle h '}$${\ Displaystyle h (k) = h (y) \ land h '(k) = h' (y)}$${\ Displaystyle 1 / m ^ {2}}$${\ Displaystyle m}$

Ejemplos

Funciones de ejemplo

Tamaño de la matriz: m

Índices: {0; m-1}

Función hash principal: ( método de división del resto ) ${\ Displaystyle h (k): = k \; {\ bmod {\;}} m}$

Función hash secundaria: ${\ Displaystyle \; h '(k): = k \; {\ bmod {\;}} (m-2) +1}$

Función exploratoria: ${\ Displaystyle \; s (j, k): = j \ cdot (k \; {\ bmod {\;}} (m-2) +1)}$

Función de doble hash completa: ${\ Displaystyle \; h_ {j} (k): = (k \; {\ bmod {\;}} m + j \ cdot (k \; {\ bmod {\;}} (m-2) +1 )) {\ bmod {m}}}$

Ejemplo de cálculo

Tamaño de la matriz: m = 7

Funciones hash

${\ Displaystyle h (k): = k \; {\ bmod {\;}} 7}$

${\ Displaystyle h '(k): = k \; {\ bmod {\;}} 5 + 1}$

Función exploratoria

${\ Displaystyle h_ {j} (k): = (h (k) + j \ cdot h '(k)) \; {\ bmod {\;}} m}$

Tabla de picadillo:

La matriz se llenó con la ayuda de la tabla hash y la función de sonda:

Explicación utilizando el ejemplo : ${\ Displaystyle k = 31}$

${\ Displaystyle k = 10}$y no generan una colisión y por lo tanto no necesitan la función de doble hash . El índice de la función hash se puede leer aquí. crea una colisión en la matriz en el punto , por lo que ahora usa la función doble hash con : ${\ Displaystyle k = 19}$${\ Displaystyle h_ {j}}$${\ Displaystyle h}$${\ Displaystyle k = 31}$${\ Displaystyle 3}$${\ Displaystyle h_ {j}}$${\ Displaystyle j = 1}$

${\ Displaystyle h_ {1} (31) = (h (31) +1 \ cdot h '(31)) \; {\ bmod {\;}} 7 \ ​​equiv (3 + 1 \ cdot 2) \; { \ bmod {\;}} 7 \ ​​equiv 5 \; {\ bmod {\;}} 7 \ ​​equiv 5}$

El punto crea una colisión de nuevo, por lo que la siguiente se llama con: ${\ Displaystyle 5}$${\ Displaystyle h_ {j}}$${\ Displaystyle j = 2}$

${\ Displaystyle h_ {2} (31) = (h (31) +2 \ cdot h '(31)) \; {\ bmod {\;}} 7 \ ​​equiv (3 + 2 \ cdot 2) \; { \ bmod {\;}} 7 \ ​​equiv 7 \; {\ bmod {\;}} 7 \ ​​equiv 0}$

El puesto está vacante y por tanto recibe el contenido . ${\ displaystyle 0}$${\ Displaystyle 31}$

enlaces web

• Hash cerrado
• Hash abierto