El hash Rayuela es un esquema en programación de computadoras para resolver colisiones hash de valores de funciones hash en una tabla usando direccionamiento abierto . También es muy adecuado para implementar una tabla hash concurrente . El hash Rayuela fue introducido por Maurice Herlihy , Nir Shavit y Moran Tzafrir en 2008. [1] El nombre se deriva de la secuencia de saltos que caracterizan el algoritmo de inserción de la tabla.
El algoritmo utiliza una única matriz de n depósitos. Para cada cubo, su vecindad es una pequeña colección de H cubos consecutivos (es decir, aquellos con índices cercanos al cubo hash original). La propiedad deseada del vecindario es que el costo de encontrar un artículo en los cubos del vecindario está cerca del costo de encontrarlo en el cubo en sí (por ejemplo, al tener cubos en el vecindario dentro de la misma línea de caché ). El tamaño del vecindario debe ser suficiente para acomodar un número logarítmico de elementos en el peor de los casos (es decir, debe acomodar log ( n ) elementos), pero solo un número constante en promedio. Si el vecindario de algún cubo está lleno, la tabla cambia de tamaño.
En el hash de rayuela, como en el hash de cuco , y a diferencia del sondeo lineal , un elemento determinado siempre se insertará y se encontrará en la vecindad de su cubo de hash. En otras palabras, siempre se encontrará en su entrada de matriz hash original o en una de las siguientes entradas vecinas H −1. H podría ser, por ejemplo, 32, un tamaño de palabra de máquina común. Por tanto, la vecindad es un depósito "virtual" que tiene un tamaño fijo y se superpone con los siguientes depósitos H- 1. Para acelerar la búsqueda, cada cubeta (entrada de matriz) incluye una palabra de "información de salto", un mapa de bits de H- bits que indica cuál de las siguientes entradas H- 1 contiene elementos que se han codificado con hash en el cubo virtual de la entrada actual. De esta manera, un elemento se puede encontrar rápidamente mirando la palabra para ver qué entradas pertenecen al depósito y luego escaneando el número constante de entradas (la mayoría de los procesadores modernos admiten operaciones especiales de manipulación de bits que hacen la búsqueda en el "salto -información "mapa de bits muy rápido).
A continuación, se explica cómo agregar el elemento x que se ha codificado en el depósito i :
- Si la palabra de información de salto para el depósito i muestra que ya hay H elementos en este depósito, la tabla está llena; expanda la tabla hash y vuelva a intentarlo.
- Comenzando en la entrada i , use una sonda lineal para encontrar una entrada vacía en el índice j . (Si no existe un espacio vacío, la mesa está llena).
- Mientras ( j - i ) mod n ≥ H , mueva la ranura vacía hacia i de la siguiente manera:
- Busque en las ranuras H −1 que preceden a j un elemento y cuyo valor hash k esté dentro de H −1 de j , es decir, ( j - k ) mod n < H . (Esto se puede hacer usando las palabras de información de salto).
- Si no existe tal elemento y dentro del rango, la tabla está llena.
- Mueva y a j , creando una nueva ranura vacía más cerca de i .
- Establezca j en el espacio vacío que dejó y y repita.
- Almacene x en la ranura j y regrese.
La idea es que el hash de la rayuela "mueve la ranura vacía hacia el cubo deseado". Esto lo distingue del sondeo lineal que deja la ranura vacía donde se encontró, posiblemente lejos del balde original, o del hash de cuco que, para crear un balde libre, mueve un artículo fuera de uno de los baldes deseados en el matrices de destino, y solo entonces intenta encontrar el elemento desplazado en un nuevo lugar.
Para eliminar un elemento de la tabla, uno simplemente lo elimina de la entrada de la tabla. Si los depósitos de vecindario están alineados en caché, entonces se podría aplicar una operación de reorganización en la que los elementos se mueven a la ubicación ahora vacante para mejorar la alineación.
Una ventaja del hash de la rayuela es que proporciona un buen rendimiento con factores de carga de mesa muy altos, incluso los que superan 0,9. Parte de esta eficiencia se debe al uso de una sonda lineal solo para encontrar una ranura vacía durante la inserción, no para cada búsqueda como en el algoritmo original de la tabla hash de sondeo lineal . Otra ventaja es que se puede usar cualquier función hash, en particular las simples que son casi universales.
Ver también
Referencias
- ^ Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Rayuela Hashing" (PDF) . DISC '08: Actas del 22º simposio internacional de Computación Distribuida . Arcachon, Francia: Springer-Verlag. págs. 350–364.
enlaces externos
- libhhash - una implementación de hash de rayuela en C
- rayuela-mapa: una implementación en C ++ de un mapa hash utilizando el hash rayuela
- Goossaert, Emmanuel (11 de agosto de 2013). "Hash de Rayuela" . Consultado el 16 de octubre de 2019 . Una descripción detallada y una implementación de ejemplo.