Double Hashing

El double hashing es un método de tratamiento de colisiones en el que se aplica una segunda función de dispersión a la clave, y luego se comprueba a distancias h2(x), 2h2(x), y asísucesivamente.

De manera que si el hash de una llave nos da, por ejemplo 5, y ya existe un registro en esa posición, entonces se vuelve a aplicar otro hash que nos de una direcciónmás dispersa, por ejemplo 505, y de alguna manera nos garantice menos colisiones. Es importante aclarar que este método no elimina las colisiones, sólo no ayuda a encontrar másrápidamente un registro en un espacio donde de antemano sabemos que existe este problema.

La segunda función hash debe ser cuidadosamente seleccionada (por ejemplo, nunca debe evaluar a 0), ytodas las celdas deben ser capaces de ser probadas.


Dadas dos aleatorias, uniformes, e independientemente seleccionadas funciones de hash H1 y H2, la ubicación de orden “i” enla secuencia para el valor “k” en una tabla hash T es: h (i, k) = (H1 (k) + i * H2 (k)) \ mod |T|. Generalmente, H1 y H2 se seleccionan de un conjunto de funciones universales de hash.En los casos en los que T sea un número primo, siempre se encontrará un lugar vacío, debido a que al revisar todas las posibilidades, el resultado siempre será diferente.


Aligual que en el linear probing, se utiliza un valor hash como punto de partida y luego repetidamente se adelanta un intervalo hasta que el valor deseado se encuentra, un lugar vacío sealcanza, o toda la tabla ha sido buscada; pero este intervalo utiliza una segunda función independiente de hash. A diferencia de la linear probing y quadratic probing, el intervalodepende de los datos, de modo que incluso valores de asignación a la misma ubicación tienen diferentes secuencias; esto minimiza las colisiones repetidas y los efectos de la agrupación.