Doble hash

El hash doble es una técnica de programación informática que se utiliza junto con el direccionamiento abierto en las tablas hash para resolver colisiones de hash , mediante el uso de un hash secundario de la clave como compensación cuando se produce una colisión. El hash doble con direccionamiento abierto es una estructura de datos clásica en una tabla . ${\displaystyle T}$

La técnica de hash doble utiliza un valor hash como índice en la tabla y luego avanza repetidamente un intervalo hasta que se encuentra el valor deseado, se llega a una ubicación vacía o se ha buscado en toda la tabla; pero este intervalo lo establece una segunda función hash independiente . A diferencia de los métodos alternativos de resolución de colisiones de sondeo lineal y sondeo cuadrático , el intervalo depende de los datos, de modo que los valores que se asignan a la misma ubicación tienen diferentes secuencias de contenedores; esto minimiza las colisiones repetidas y los efectos de la agrupación .

Dadas dos funciones hash aleatorias, uniformes e independientes y , la ubicación n en la secuencia de cubos para el valor en una tabla hash de cubos es: Generalmente, y se seleccionan de un conjunto de funciones hash universales ; se selecciona para que tengan un rango de y para que tengan un rango de . El hash doble se aproxima a una distribución aleatoria; más precisamente, las funciones hash independientes por pares producen una probabilidad de que cualquier par de claves siga la misma secuencia de cubos. ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle |T|}$ ${\displaystyle h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.}$ ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle h_{1}}$ ${\displaystyle \{0,|T|-1\}}$ ${\displaystyle h_{2}}$ ${\displaystyle \{1,|T|-1\}}$ ${\displaystyle (n/|T|)^{2}}$

Selección de h2(k)

La función hash secundaria debe tener varias características: ${\displaystyle h_{2}(k)}$

• Nunca debería producir un índice de cero.
• Debería recorrer toda la tabla.
• Debería ser muy rápido de calcular.
• Debería ser independiente por pares de . ${\displaystyle h_{1}(k)}$
• Las características de distribución de son irrelevantes. Es análogo a un generador de números aleatorios. ${\displaystyle h_{2}}$
• Todos deben ser relativamente primos con respecto a | T |. ${\displaystyle h_{2}(k)}$

En la práctica:

• Si se utiliza el algoritmo de división para ambas funciones, los divisores se eligen como primos.
• Si | T | es una potencia de 2, el primer y el último requisito se satisfacen normalmente haciendo que siempre se devuelva un número impar. Esto tiene el efecto secundario de duplicar la probabilidad de colisión debido a un bit desperdiciado. ^[1] ${\displaystyle h_{2}(k)}$

Análisis

Sea el número de elementos almacenados en , entonces el factor de carga de es . Es decir, comience seleccionando aleatoriamente, de manera uniforme e independiente dos funciones hash universales y construya una tabla hash doble . Todos los elementos se colocan mediante hash doble utilizando y . Dada una clave , la ubicación hash -st se calcula mediante: ${\displaystyle n}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \alpha =n/|T|}$ ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle h_{1}}$ ${\displaystyle h_{2}}$ ${\displaystyle k}$ ${\displaystyle (i+1)}$

$${\displaystyle h(i,k)=(h_{1}(k)+i\cdot h_{2}(k)){\bmod {|}}T|.}$$

Supongamos que el factor de carga es fijo . Bradford y Katehakis ^[2] demostraron que el número esperado de sondeos para una búsqueda fallida en , aún utilizando estas funciones hash elegidas inicialmente, es independientemente de la distribución de las entradas. La independencia por pares de las funciones hash es suficiente. ${\displaystyle T}$ ${\displaystyle \alpha :1>\alpha >0}$ ${\displaystyle T}$ ${\displaystyle {\tfrac {1}{1-\alpha }}}$

Al igual que todas las demás formas de direccionamiento abierto, el hash doble se vuelve lineal a medida que la tabla hash se acerca a su capacidad máxima. La heurística habitual es limitar la carga de la tabla al 75 % de su capacidad. Con el tiempo, será necesario volver a aplicar el hash a un tamaño mayor, como ocurre con todos los demás esquemas de direccionamiento abierto.

Variantes

La tesis doctoral de Peter Dillinger ^[3] señala que el hash doble produce funciones hash equivalentes no deseadas cuando las funciones hash se tratan como un conjunto, como en los filtros Bloom : si y , entonces y los conjuntos de hashes son idénticos. Esto hace que una colisión sea dos veces más probable que la esperada . ${\displaystyle h_{2}(y)=-h_{2}(x)}$ ${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)}$ ${\displaystyle h(i,y)=h(k-i,x)}$ ${\displaystyle \left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y)\right\}}$ ${\displaystyle 1/|T|^{2}}$

Además, hay una cantidad significativa de conjuntos hash que en su mayoría se superponen; si y , entonces , y comparar valores hash adicionales (expandiendo el rango de ) no es de ayuda. ${\displaystyle h_{2}(y)=h_{2}(x)}$ ${\displaystyle h_{1}(y)=h_{1}(x)\pm h_{2}(x)}$ ${\displaystyle h(i,y)=h(i\pm 1,x)}$ ${\displaystyle i}$

Triple hash

Agregar un término cuadrático ^[4] (un número triangular ) o incluso ( triple hash ) ^[5] a la función hash mejora un poco la función hash ^[4] pero no soluciona este problema; si: ${\displaystyle i^{2},}$ ${\displaystyle i(i+1)/2}$ ${\displaystyle i^{2}\cdot h_{3}(x)}$

${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)+k^{2}\cdot h_{3}(x),}$

${\displaystyle h_{2}(y)=-h_{2}(x)-2k\cdot h_{3}(x),}$y

${\displaystyle h_{3}(y)=h_{3}(x).}$

entonces

${\displaystyle {\begin{aligned}h(k-i,y)&=h_{1}(y)+(k-i)\cdot h_{2}(y)+(k-i)^{2}\cdot h_{3}(y)\\&=h_{1}(y)+(k-i)(-h_{2}(x)-2kh_{3}(x))+(k-i)^{2}h_{3}(x)\\&=\ldots \\&=h_{1}(x)+kh_{2}(x)+k^{2}h_{3}(x)+(i-k)h_{2}(x)+(i^{2}-k^{2})h_{3}(x)\\&=h_{1}(x)+ih_{2}(x)+i^{2}h_{3}(x)\\&=h(i,x).\\\end{aligned}}}$

Hashing doble mejorado

La suma de un término cúbico ^[4] o (un número tetraédrico ), ^[1] resuelve el problema, una técnica conocida como hash doble mejorado . Esto se puede calcular de manera eficiente mediante la diferenciación hacia adelante : ${\displaystyle i^{3}}$ ${\displaystyle (i^{3}-i)/6}$

struct key ; /// Opaco /// Utilice otros tipos de datos cuando sea necesario. (Debe estar sin signo para garantizar el ajuste). extern unsigned int h1 ( struct key const * ), h2 ( struct key const * );           /// Calcula k valores hash a partir de dos funciones hash subyacentes /// h1() y h2() usando hash doble mejorado. Al regresar, /// hashes[i] = h1(x) + i*h2(x) + (i*i*i - i)/6. /// Aprovecha el encapsulado automático (reducción modular) /// de tipos sin signo en C. void ext_dbl_hash ( struct key const * x , unsigned int hashes [], unsigned int n ) { unsigned int a = h1 ( x ), b = h2 ( x ), i ;                   hashes [ i ] = a ; for ( i = 1 ; i < n ; i ++ ) { a += b ; // Agrega diferencia cuadrática para obtener cúbica b += i ; // Agrega diferencia lineal para obtener cuadrática // i++ agrega diferencia constante para obtener lineal hashes [ i ] = a ; } }                 

Además de corregir el problema de colisión, el doble hash mejorado también elimina las restricciones numéricas del doble hash en las propiedades de , lo que permite utilizar una función hash similar en propiedades a (pero aún independiente de). ^[1] ${\displaystyle h_{2}(x)}$ ${\displaystyle h_{1}}$

Véase también

• Hashing de cuco
• Hashing de 2 opciones

Referencias

1. Dillinger, Peter C.; Manolios, Panagiotis (15-17 de noviembre de 2004). Filtros Bloom en verificación probabilística (PDF) . Conferencia internacional de 5 h sobre métodos formales en diseño asistido por computadora (FMCAD 2004). Austin, Texas. CiteSeerX  10.1.1.119.628 . doi :10.1007/978-3-540-30494-4_26.
2. Bradford, Phillip G.; Katehakis, Michael N. (abril de 2007), "Un estudio probabilístico sobre expansores combinatorios y hash" (PDF) , SIAM Journal on Computing , 37 (1): 83–111, doi :10.1137/S009753970444630X, MR  2306284, archivado desde el original (PDF) el 25 de enero de 2016.
3. Dillinger, Peter C. (diciembre de 2010). Almacenamiento de estado aproximado adaptativo (PDF) (tesis doctoral). Northeastern University. págs. 93–112.
4. Kirsch, Adam; Mitzenmacher, Michael (septiembre de 2008). "Menos hash, mismo rendimiento: creación de un mejor filtro Bloom" (PDF) . Estructuras y algoritmos aleatorios . 33 (2): 187–218. CiteSeerX 10.1.1.152.579 . doi :10.1002/rsa.20208. 
5. Alternativamente definido con el número triangular, como en Dillinger 2004.

Enlaces externos

• Cómo afecta el almacenamiento en caché al hash por Gregory L. Heileman y Wenbin Luo 2005.
• Animación de tabla hash
• klib es una biblioteca C que incluye funcionalidad de doble hash.