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 se produce una colisión. El hash doble con direccionamiento abierto es una estructura de datos clásica en una tabla.
La técnica de doble hash utiliza un valor hash como índice en la tabla y luego avanza repetidamente un intervalo hasta que se encuentra 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, por lo que los valores que se asignan a la misma ubicación tienen diferentes secuencias de cubos; esto minimiza las colisiones repetidas y los efectos de la agrupación.
Dadas dos funciones hash aleatorias, uniformes e independientes y , la th ubicación en la secuencia del balde para valor en una tabla hash de cubos es: Generalmente, y se seleccionan de un conjunto de funciones hash universales ; se selecciona para tener un rango de y tener una gama 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 llaves seguirá la misma secuencia de cubos.
Selección de h 2 (k)
La función hash secundaria debe tener varias características:
- nunca debería dar un índice de cero
- debería recorrer toda la tabla
- debería ser muy rápido de calcular
- debe ser por pares independiente de
- Las características de distribución de son irrelevantes. Es análogo a un generador de números aleatorios; solo es necesario que ser '' primo relativo '' a | T |.
En la práctica, si se usa hash de división para ambas funciones, los divisores se eligen como primos.
Análisis
Dejar ser el número de elementos almacenados en , luego El factor de carga es . Es decir, comience seleccionando de forma aleatoria, uniforme e independiente dos funciones hash universales y para construir una tabla de hashing doble . Todos los elementos se ponen en por doble hash usando y . Dada una clave, la -st ubicación hash se calcula mediante:
Dejar tener factor de carga fijo .
Bradford y Katehakis [1] mostraron el número esperado de sondas para una búsqueda fallida en, todavía usando estas funciones hash elegidas inicialmente, es independientemente de la distribución de los insumos. La independencia por pares de las funciones hash es suficiente.
Como todas las otras formas de direccionamiento abierto, el doble hash se vuelve lineal a medida que la tabla hash se acerca a la capacidad máxima. La heurística habitual es limitar la carga de la tabla al 75% de su capacidad. Con el tiempo, será necesario realizar un refrito a un tamaño mayor, como ocurre con todos los demás esquemas de direccionamiento abiertos.
Hash doble mejorado
La tesis doctoral de Peter Dillinger [2] 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 , luego y los conjuntos de hashes Son identicos. Esto hace que una colisión sea dos veces más probable que la esperada..
Además, hay un número significativo de conjuntos hash que se superponen en su mayoría; Si y , luego y comparar valores hash adicionales (expandiendo el rango de ) no es de ayuda.
Agregar un término cuadrático [3] (un número triangular ) o incluso( triple hash ) a la función hash mejora un poco la función hash [3] pero no soluciona este problema; Si:
- y
luego
Agregar un término cúbico [3] o(un número tetraédrico ), [4] resuelve el problema, una técnica conocida como doble hash mejorado . Esto se puede calcular de manera eficiente mediante diferenciación directa :
clave de estructura ; // Opaco extern unsigned int h1 ( struct key const * ), h2 ( struct key const * );// Calcula k valores hash 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 ajuste automático (reducción modular) // de tipos sin firmar en C. void hash ( estructura clave const * x , unsigned int hashes [], unsigned int n ) { unsigned int a = h1 ( x ), b = h2 ( x ), i ;para ( i = 0 ; i < n ; i ++ ) { hashes [ i ] = a ; a + = b ; // Suma la diferencia cuadrática para obtener cúbico b + = i ; // Agrega una diferencia lineal para obtener una cuadrática // i ++ agrega una diferencia constante para obtener una lineal } }
Ver también
Referencias
- ^ Bradford, Phillip G .; Katehakis, Michael N. (abril de 2007), "A Probabilistic Study on Combinatorial Expanders and Hashing" (PDF) , SIAM Journal on Computing , 37 (1): 83-111, doi : 10.1137 / S009753970444630X , MR 2306284 , archivado de la original (PDF) el 2016-01-25.
- ^ Dillinger, Peter C. (diciembre de 2010). Almacenamiento estatal aproximado adaptativo (PDF) (tesis doctoral). Universidad del Noroeste. págs. 93-112.
- ^ a b c Kirsch, Adam; Mitzenmacher, Michael (septiembre de 2008). "Menos hash, mismo rendimiento: creación de un mejor filtro de floración" (PDF) . Estructuras y algoritmos aleatorios . 33 (2): 187–218. CiteSeerX 10.1.1.152.579 . doi : 10.1002 / rsa.20208 .
- ^ Dillinger, Peter C .; Manolios, Panagiotis (15-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 .
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 de C que incluye la funcionalidad de doble hash.