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 de hash , utilizando un hash secundario de la clave como desplazamiento cuando se produce 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 explorado 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 cubetas; esto minimiza las colisiones repetidas y los efectos de la agrupación .

Dadas dos funciones hash aleatorias, uniformes e independientes${\displaystyle h_{1}}$y${\displaystyle h_{2}}$, el${\displaystyle i}$ubicación en la secuencia de cubetas para el valor${\displaystyle x}$en una tabla hash de${\displaystyle |T|}$cubos es:${\displaystyle h(i,x)=(h_{1}(x)+i\cdot h_{2}(x)){\bmod {|}}T|.}$Las ubicaciones se pueden calcular convenientemente incrementando el hash anterior en${\displaystyle h_{2}(x)}$, es decir${\displaystyle h(i+1,x)=(h(i,x)+h_{2}(x)){\bmod {|}}T|.}$

Generalmente,${\displaystyle h_{1}}$y${\displaystyle h_{2}}$se seleccionan de un conjunto de funciones hash universales ;${\displaystyle h_{1}}$se selecciona para tener una gama de${\displaystyle \{0,|T|-1\}}$y${\displaystyle h_{2}}$tener una gama de${\displaystyle \{1,|T|-1\}}$El doble hash se aproxima a una distribución aleatoria; más precisamente, las funciones hash independientes por pares producen una probabilidad de${\displaystyle (n/|T|)^{2}}$que cualquier par de claves seguirá la misma secuencia de cubos.

La función hash secundaria${\displaystyle h_{2}(x)}$debe tener varias características: ^{[ 1 ]}

1. Nunca debería devolver un índice de cero. Cuando se devuelve 0, solo se examina un índice.
2. Todo${\displaystyle h_{2}(x)}$debería ser relativamente primordial para${\displaystyle |T|}$De lo contrario, el número de índices sondeados sobre k elementos sería${\displaystyle \min(k,|T|/h_{2}(x))}$, que podría ser tan pequeño como 2.
3. Debería recorrer toda la tabla.
4. Debería ser muy rápido de calcular.
5. Debe ser independiente por pares de${\displaystyle h_{1}(x)}$.

Las características de distribución de${\displaystyle h_{2}}$son irrelevantes. Es análogo a un generador de números aleatorios.

En la práctica:

• Si se utiliza el hash de división para ambas funciones, los divisores se eligen como números primos.
• Si${\displaystyle |T|}$es una potencia de 2, los dos primeros requisitos generalmente se satisfacen haciendo${\displaystyle h_{2}(x)}$siempre devuelve un número impar estableciendo el bit menos significativo en 1 (${\displaystyle h_{2}(x)=h_{2,{\text{orig}}}(x)|1}$). Esto tiene el efecto secundario de duplicar la probabilidad de colisión debido a un bit desperdiciado. ^{[ 1 ]}

Supongamos que se seleccionan dos funciones hash.${\displaystyle h_{1}}$y${\displaystyle h_{2}}$y se insertan${\displaystyle \alpha |T|}$elementos en una tabla hash con${\displaystyle |T|}$ranuras. Supongamos que cada inserción de una clave${\displaystyle x}$coloca la llave en la primera ranura disponible de la secuencia${\displaystyle h(0,x),h(1,x),h(2,x),\ldots }$definido por

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

Dada esta configuración, los análisis teóricos buscan determinar el tiempo necesario para realizar una inserción adicional (o, equivalentemente, el tiempo necesario para realizar una búsqueda infructuosa). Guibas y Szemerédi ^{[ 2 ]} demostraron en 1978 que, si ${\displaystyle h_{1}}$y${\displaystyle h_{2}}$son uniformemente aleatorios y${\displaystyle \alpha <0,319}$, entonces el tiempo esperado es${\displaystyle O(1)}$. El trabajo posterior de Lueker y Molodowitch ^{[ 3 ]} demostró un límite de${\displaystyle 1/(1-\alpha )}$para cualquier${\displaystyle \alpha }$y establecieron que el comportamiento de la tabla hash puede acoplarse directamente al de una solución estándar basada en sondeo aleatorio. Mucho más recientemente, en 2007, Bradford y Katehakis ^{[ 4 ]} demostraron que incluso el uso de funciones hash universales , en lugar de funciones totalmente aleatorias, es suficiente para obtener una${\displaystyle 1/(1-\alpha )}$atado.

Al igual que otros métodos 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 consiste en limitar la carga de la tabla al 75 % de su capacidad. Eventualmente, será necesario volver a generar el hash para aumentar su tamaño, como ocurre con todos los demás esquemas de direccionamiento abierto.

La tesis doctoral de Peter Dillinger 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 de Bloom : Si${\displaystyle h_{2}(y)=-h_{2}(x)}$y${\displaystyle h_{1}(y)=h_{1}(x)+k\cdot h_{2}(x)}$, entonces${\displaystyle h(i,y)=h(ki,x)}$y los conjuntos de hashes${\displaystyle \left\{h(0,x),...,h(k,x)\right\}=\left\{h(0,y),...,h(k,y)\right\}}$ son idénticos. Esto hace que una colisión sea dos veces más probable que lo esperado.${\displaystyle 1/|T|^{2}}$. ^{[ 5 ]}

Además, hay un número significativo de conjuntos hash que se superponen en su mayoría; si${\displaystyle h_{2}(y)=h_{2}(x)}$y${\displaystyle h_{1}(y)=h_{1}(x)\pm h_{2}(x)}$, entonces${\displaystyle h(i,y)=h(i\pm 1,x)}$y comparando valores hash adicionales (ampliando el rango de${\displaystyle i}$) no sirve de nada.

from collections.abc import Iterator , Callable from typing import TypeVarT = TypeVar ( 'T' ) hashfunc = Callable [ T , int ] # se asume que h1, h2, h3 están definidos y son de tipo hashfuncMÓDULO = ( 1 << 32 )def triple_hash ( key : T , k : int ) -> Iterator [ int ]: """Devuelve k iteraciones de un triple hash.""" x , y , z = h1 ( key ), h2 ( key ), h3 ( key ) yield x for i in range ( 1 , k - 1 ): x = ( x + y ) % MODULUS y = ( y + z ) % MODULUS yield x

struct key ; /// Opaco /// Reemplace "unsigned int" con otros tipos según sea necesario. (Debe ser unsigned para garantizar el encapsulamiento). typedef unsigned int hashfunc ( struct key const * ); extern hashfunc h1 , h2 ;/// Calcula 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 encapsulamiento automático (reducción modular) /// de los 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 = 0 ;hashes [ i ] = a ; para ( i = 1 ; i < n ; i ++ ) { a += b ; // Sumar diferencia cuadrática para obtener cúbica b += i ; // Sumar diferencia lineal para obtener cuadrática // i++ suma diferencia constante para obtener lineal hashes [ i ] = a ; } }

• Hashing de cuco
• Hash de dos opciones

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