Doble hash

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

La técnica de doble hash utiliza un valor hash como índice en la tabla y luego avanza repetidamente un intervalo hasta que se localiza el valor deseado, se alcanza 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 asignados a la misma ubicación tienen diferentes secuencias de depósitos; esto minimiza las colisiones repetidas y los efectos de la agrupación .

Dadas dos funciones hash aleatorias, uniformes e independientes y , la enésima ubicación en la secuencia de depósitos para el valor en una tabla hash de depósitos es: Generalmente, y se seleccionan de un conjunto de funciones hash universales ; se selecciona para tener un rango de y tener un rango de . El doble hash se aproxima a una distribución aleatoria; más precisamente, las funciones hash independientes por pares generan una probabilidad de que cualquier par de claves siga la misma secuencia de depósitos. ${\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 h 2 (k)

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

• Nunca debería arrojar un índice de cero.
• Debería recorrer toda la tabla.
• Debería ser muy rápido de calcular.
• Debe 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}}$
• Todo debería ser relativamente primo para | T |. ${\displaystyle h_{2}(k)}$

En la práctica:

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

Análisis

Sea el número de elementos almacenados , entonces el factor de carga es . Es decir, comience seleccionando de forma aleatoria, uniforme e independiente dos funciones hash universales y construya una tabla hash doble . Todos los elementos se ingresan mediante doble hash usando y . Dada una clave , la ubicación del 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|.}$$

Tengamos un factor de carga fijo . Bradford y Katehakis ^[2] mostraron que el número esperado de sondas para una búsqueda fallida en , aún usando estas funciones hash inicialmente elegidas, 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 }}}$

Como todas las demás formas de direccionamiento abierto, el doble hash 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 mesa al 75% de su capacidad. Con el tiempo, será necesario repetirlo 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 doble hash 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 de lo esperado . ${\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 de hash, en su mayoría superpuestos; if y , entonces , y comparar valores hash adicionales (ampliando 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}}}$

Doble hash mejorado

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

clave de estructura ; /// Opaco /// Utilice otros tipos de datos cuando sea necesario. (Debe estar sin firmar para garantizar el ajuste). extern unsigned int h1 ( struct key const * ), h2 ( struct key const * );           /// Calcular k valores hash a partir de dos funciones hash subyacentes /// h1() y h2() utilizando doble hash mejorado. Al regresar, /// hashes[i] = h1(x) + i*h2(x) + (i*i*i - i)/6. /// Aprovecha el ajuste automático (reducción modular) /// de tipos sin firmar 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 ;                  for ( i = 0 ; i < n ; i ++ ) { hashes [ i ] = a ; a += b ; // Suma diferencia cuadrática para obtener cúbico b += i ; // Agrega diferencia lineal para obtener cuadrático // i++ agrega diferencia constante para obtener lineal } }                

Además de rectificar 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 propiedad (pero aún independiente de) . ^[1] ${\displaystyle h_{2}(x)}$ ${\displaystyle h_{1}}$

Ver también

• hashing de cuco
• hash de 2 opciones

Referencias

1. Dillinger, Peter C.; Manolios, Panagiotis (15 al 17 de noviembre de 2004). Filtros Bloom en verificación probabilística (PDF) . 5h Congreso Internacional 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 original (PDF) el 25/01/2016.
3. Dillinger, Peter C. (diciembre de 2010). Almacenamiento de estado aproximado adaptativo (PDF) (tesis doctoral). Universidad del Noroeste. págs. 93-112.
4. Kirsch, Adán; Mitzenmacher, Michael (septiembre de 2008). "Menos hash, mismo rendimiento: creación de un mejor filtro Bloom" (PDF) . Estructuras aleatorias y algoritmos . 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 el almacenamiento en caché afecta el hash por Gregory L. Heileman y Wenbin Luo 2005.
• Animación de tabla hash
• klib una biblioteca C que incluye funcionalidad de doble hash.