Hash de cuco

Cuckoo hashing  es un algoritmo para resolver colisiones de valores hash en una tabla con un tiempo de búsqueda constante en el peor de los casos .

Propuesto en 2001 [1] . El nombre hace referencia al comportamiento de algunas especies de cucos , cuando el polluelo empuja los huevos u otros polluelos fuera del nido; De manera similar, el algoritmo prevé la posibilidad de sacar la llave antigua al insertar una nueva.

Operaciones

Cuckoo hashing es un tipo de direccionamiento abierto en el que cada celda no vacía de la tabla hash contiene una clave o un par clave-valor . Se utiliza una función hash para determinar la ubicación de cada clave, y su presencia en la tabla (o el valor asociado a ella) se puede encontrar examinando esa celda de la tabla. Sin embargo, el direccionamiento abierto sufre colisiones , que ocurren cuando más de una clave termina en la misma celda. La idea básica del cuckoo hashing es resolver colisiones usando dos funciones hash en lugar de una. Esto proporciona dos posiciones posibles en la tabla hash para cada clave. En una de las variantes habituales del algoritmo, la tabla hash se divide en dos tablas más pequeñas de menor tamaño, y cada función hash proporciona un índice en una de estas dos tablas. También es posible asegurarse de que ambas funciones hash estén indexadas dentro de la misma tabla.

La obtención requiere mirar solo dos lugares en la tabla hash, lo que requiere un tiempo constante en el peor de los casos ( ver "o" grande y "o" pequeña ). Esto contrasta con muchos otros algoritmos de tablas hash que no proporcionan tiempos de recuperación constantes en el peor de los casos. La eliminación también se puede hacer borrando la celda que contiene la clave en tiempo constante en el peor de los casos, lo cual es más fácil que en otros esquemas como el sondeo lineal .

Cuando se inserta una nueva clave y una de las dos celdas está vacía, la clave se puede colocar en esa celda. En el caso de que ambas celdas estén ocupadas, es necesario mover otras llaves a otros lugares (o, por el contrario, a sus lugares anteriores) para dejar espacio para una nueva llave. Se utiliza un algoritmo codicioso  : la tecla se coloca en una de las posiciones posibles, "empujando" cualquier tecla que estuviera en esta posición. Luego, la llave expulsada se coloca en su posición alternativa, expulsando nuevamente cualquier llave que haya estado allí. El proceso continúa hasta que se encuentra una posición vacía. Es posible, sin embargo, que el proceso de inserción falle, entrando en un bucle infinito , o cuando la cadena sea demasiado larga (más larga que un umbral predeterminado que depende logarítmicamente de la longitud de la tabla). En este caso, la tabla hash se reconstruye en su lugar con nuevas funciones hash :

No hay necesidad de configurar una nueva tabla para el refrito; simplemente podemos revisar la tabla para eliminar y volver a insertar cualquier clave que no esté en la posición en la que debería estar. [una]Pagh y Rodler, "Hashing de cuco"

Complejidad computacional

El tiempo de inserción esperado es constante [1] , incluso teniendo en cuenta la posible necesidad de reconstruir la tabla, siempre que el número de claves sea inferior a la mitad de la capacidad de la tabla hash, es decir, el factor de carga es menos de 50%.

Para garantizar esto, se utiliza la teoría de gráficos aleatorios  : puede formar un gráfico no dirigido , llamado "gráfico de cuco", en el que los vértices son las celdas de la tabla hash y los bordes de cada hashable conectan dos posiciones posibles (celdas de la tabla hash). tabla de picadillo). Entonces, el algoritmo codicioso para insertar un conjunto de valores en una tabla hash de cuco tiene éxito si y solo si el gráfico de cuco para este conjunto de valores es un pseudobosque , un gráfico con como máximo un ciclo en cada componente conectado . Cualquier subgrafo generado por vértices con más aristas que el número de vértices corresponde a un conjunto de claves para las que no hay suficientes ranuras en la tabla hash. Si la función hash se elige aleatoriamente, el gráfico de cuco será un gráfico aleatorio en el modelo Erdős-Rényi . Con un alto grado de probabilidad, para un grafo aleatorio en el que la relación entre el número de aristas y el número de vértices está acotada por encima de 1/2, el grafo es un pseudobosque y el algoritmo cuckoo hashing localiza con éxito todas las claves. Además, la misma teoría prueba que el tamaño esperado de los componentes conectados de un gráfico de cuco es pequeño, lo que asegura un tiempo de inserción esperado constante [2] .

Ejemplo

Dadas las siguientes dos funciones hash:


k h(k) h'(k)
veinte 9 una
cincuenta 6 cuatro
53 9 cuatro
75 9 6
100 una 9
67 una 6
105 6 9
3 3 0
36 3 3
39 6 3

Las columnas de las siguientes dos tablas muestran el estado de la tabla hash después de que se hayan insertado los elementos.

1. tabla para h(k)
veinte cincuenta 53 75 100 67 105 3 36 39
0
una 100 67 67 67 67 100
2
3 3 36 36
cuatro
5
6 cincuenta cincuenta cincuenta cincuenta cincuenta 105 105 105 cincuenta
7
ocho
9 veinte veinte 53 75 75 75 53 53 53 75
diez
2. tabla para h'(k)
veinte cincuenta 53 75 100 67 105 3 36 39
0 3 3
una veinte veinte veinte veinte veinte veinte veinte veinte
2
3 39
cuatro 53 53 53 cincuenta cincuenta cincuenta 53
5
6 75 75 75 67
7
ocho
9 100 100 100 100 105
diez

Ciclos

Si desea insertar el elemento 6, obtendrá un bucle infinito. En la última fila de la tabla encontramos la misma situación inicial que al principio.



llave tabla 1 Tabla 2

valor antiguo		 nuevo
valor
valor antiguo		 nuevo
valor
6 cincuenta 6 53 cincuenta
53 75 53 67 75
67 100 67 105 100
105 6 105 3 6
3 36 3 39 36
39 105 39 100 105
100 67 100 75 67
75 53 75 cincuenta 53
cincuenta 39 cincuenta 36 39
36 3 36 6 3
6 cincuenta 6 53 cincuenta

Variaciones

Se han explorado algunas variaciones de cuckoo hash, principalmente con el objetivo de mejorar la utilización del espacio aumentando el factor de carga . En estas variantes se puede alcanzar un umbral de carga de más del 50%. Algunos de estos métodos se pueden usar para reducir significativamente la cantidad de reconstrucciones de estructuras de datos requeridas.

Se puede esperar que una generalización del cuckoo hash usando más de dos funciones hash haga un mejor uso de la tabla hash, sacrificando algo de velocidad de búsqueda e inserción. El uso de tres funciones hash aumenta el factor de carga al 91% [3] . Otra generalización del hash cuckoo, llamado hashing cuckoo de bloque , contiene más de una clave por celda. El uso de dos llaves por celda permite aumentar la carga por encima del 80% [4] .

Otra opción que se ha estudiado es el cuckoo hash con margen . "Stock" es una matriz de claves de longitud constante que se utiliza para almacenar claves que no se pueden insertar correctamente en la tabla hash maestra. Esta modificación reduce el número de fallas a una función polinomial inversa con un grado que puede ser arbitrariamente grande al aumentar el tamaño del margen. Sin embargo, un margen grande significa una búsqueda más lenta de una clave que no está en la tabla principal, o si está en el margen. El stock se puede utilizar en combinación con más de dos funciones hash o hashing cuckoo de bloque para lograr una alta utilización y pocas fallas de inserción [5] . El análisis hash Cuckoo se ha extendido con creces a las funciones hash prácticas, no solo a los modelos hash aleatorios utilizados en el análisis hash teórico [6] .

Algunos investigadores proponen utilizar una generalización simplificada de cuckoo hash en algunas cachés de procesador denominada caché asociativa asimétrica . [7]

Comparación con estructuras similares

Hay otros algoritmos que usan varias funciones hash, en particular el filtro Bloom  , una estructura de datos eficiente en memoria para conjuntos borrosos. Una estructura de datos alternativa para problemas con los mismos conjuntos difusos, basada en cuckoo hash, llamada filtro cuckoo , usa incluso menos memoria y (a diferencia de los filtros Bloom clásicos) permite la eliminación de elementos, no solo la inserción y la verificación de existencia. Sin embargo, el análisis teórico de estos métodos es mucho más débil que el análisis de los filtros Bloom [8] .

Estudios realizados en 2006 [9] demostraron que cuckoo hashing es significativamente más rápido que el método de encadenamiento para pequeñas tablas hash ubicadas en la memoria caché de los procesadores modernos. En el mismo año [10] , se desarrolló una versión en bloques de cuckoo hash (un bloque contiene más de una clave), que es más rápida que los métodos convencionales para grandes tablas hash en el caso de un alto factor de carga. La velocidad de la versión en bloque de la tabla hash cuckoo se investigó en 2009 [11] .

Véase también

Notas

  1. ↑ 1 2 3 Pagh, Rodler, 2001 , pág. 121–133.
  2. ↑ Kutzelnigg, 2006 , pág. 403–406.
  3. ↑ Mitzenmacher, 2009 .
  4. ↑ Dietzfelbinger y Weidling 2007 , p. 47–68.
  5. ↑ Kirsch, Mitzenmacher, Wieder, 2010 , pág. 1543-1561
  6. ↑ Aumüller, Dietzfelbinger, Woelfel, 2014 , pág. 428–456.
  7. ↑ "Microarquitectura" .
  8. ↑ Fan, Kaminsky, Andersen, 2013 , pág. 36–40.
  9. ↑ Zukowski, Hemán, Boncz, 2006 .
  10. ↑ Ross, 2006 .
  11. ↑ Askitis, 2009 , pág. 113–122.

Literatura

Enlaces

Ejemplos