Ir al contenido

Cuckoo hashing

De Wikipedia, la enciclopedia libre
Cuckoo hashing. Las flechas muestran la ubicación alternativa de cada clave. Un nuevo elemento se inserta en el lugar de A moviendo A a su ubicación alternativa, actualmente ocupado por B y B en movimiento a su ubicación alternativa que se encuentra actualmente disponible. La inserción de un nuevo elemento en la ubicación de H no tendría éxito: H es parte de un ciclo (junto con W), el nuevo elemento sería expulsado de nuevo

Cuckoo Hashing (hash del cuco) es un estructura de datos usada en la programación informática para la resolución de colisiones hash de los valores de la función de hash en una Tabla, con caso peor constante en tiempo de búsqueda. El nombre deriva del comportamiento de algunas especies de cuculidae, donde la cría del cuco empuja los otros huevos o crías del nido cuando incuba; análogamente, la inserción de una nueva clave en una tabla cuckoo hashing puede empujar una clave más para una ubicación diferente en la tabla.

Historia

[editar]

Cuckoo hashing fue descrita por primera vez por Rasmus Pagh y Flemming Friche Rodler en 2001.[1]

Teoría

[editar]

La idea básica es usar dos funciones hash en lugar de sólo una. Esto proporciona dos posibles ubicaciones en la tabla hash para cada clave única. En una de las variantes de uso común del algoritmo, la tabla hash se divide en dos tablas más pequeñas de igual tamaño, y cada función hash proporciona un índice en una de estas dos tablas.

Cuando se inserta una nueva clave, un algoritmo voraz es usado para insertar el duplicado de la clave en una de sus dos posibles ubicaciones, "patear", es decir, desplazar, cualquier clave que podría residir en esta ubicación. Luego se inserta esta clave desplazada en su lugar alternativo, de nuevo expulsar a cualquier clave que podría residir en ese lugar, hasta que se encuentre un puesto disponible, o el procedimiento podría caer en un ciclo infinito. En este último caso, la tabla hash se reconstruye en el lugar con una nueva función hash:

No hay necesidad de asignar nuevas tablas para el rehashing: Podemos simplemente ejecutar a través de las tablas de eliminar, y realizar el procedimiento de inserción habitual para todas las claves encontradas que no están en su posición prevista en la tabla.
[1]

Las operaciones de búsqueda requieren la inspección de sólo dos lugares en la tabla hash, que toma tiempo constante en el peor de los casos (ver Cota superior asintótica). Esto está en contraste con muchos otros algoritmos de tabla de hash, que pueden no tener una constante peor de los casos, con destino en el tiempo para hacer una búsqueda.

También puede demostrarse que las inserciones pueden tener éxito en la constante de tiempo esperado,[1]​ incluso teniendo en cuenta la posibilidad de tener que reconstruir la tabla, siempre y cuando se mantiene el número de claves por debajo de la mitad de la capacidad de la tabla hash, es decir, el factor de carga es inferior a 50%. Un método para probar esto utiliza la teoría de grafos aleatorios: uno puede formar un grafo no dirigido llamado el "grafo cuckoo" que tiene un vértice para cada ubicación en la tabla hash, y una arista para cada valor hash, con los extremos de la arista siendo las dos posibles ubicaciones del valor. Entonces, el algoritmo de inserción por adición de un conjunto de valores de una tabla hash cuckoo tiene éxito si y sólo si el grafo cuckoo para este conjunto de valores es un pseudoforest, un grafo con al menos un ciclo por cada una de sus componentes conexas, como cualquier subgrafo inducido con más aristas que vértices correspondiente a un juego de claves para los que hay un número insuficiente de lugares en la tabla hash. Esta propiedad se cumple con alta probabilidad para un grafo aleatorio en el que el número de aristas es menor que la mitad del número de vértices.

Ejemplo

[editar]

Se dan las siguientes funciones de hash:



k h(k) h'(k)
20 9 1
50 6 4
53 9 4
75 9 6
100 1 9
67 1 6
105 6 9
3 3 0
36 3 3
39 6 3

Las columnas en las dos tablas siguientes muestran el estado de las tablas hash con el tiempo a medida que se insertan los elementos.

1. tabla para h(k)
20 50 53 75 100 67 105 3 36 39
0
1 100 67 67 67 67 100
2
3 3 3 36
4
5
6 50 50 50 50 50 105 105 105 50
7
8
9 20 20 20 20 20 20 53 53 53 75
10
2. tabla para h'(k)
20 50 53 75 100 67 105 3 36 39
0 3
1 20 20 20 20
2
3 36 39
4 53 53 53 53 50 50 50 53
5
6 75 75 75 75 75 75 67
7
8
9 100 100 100 100 105
10

Ciclo

[editar]

Si ahora se desea insertar el elemento 6, se cae dentro de un ciclo. En la última fila de la tabla encontramos la misma situación inicial como en el principio otra vez.


considered key table 1 table 2
valor anterior nuevo valor valor anterior nuevo valor
6 50 6 53 50
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 50 53
50 39 50 36 39
36 3 36 6 3
6 50 6 53 50

Las generalizaciones y aplicaciones

[editar]

Las generalizaciones de cuckoo hashing que utilizan más de 2 funciones hash pueden utilizar una mayor parte de la capacidad de la tabla hash de manera eficiente, mientras que sacrifican algo de velocidad en búsqueda e inserción. Utilizando sólo tres funciones hash aumenta la carga al 91%.[2]​ Otra generalización de cuckoo hashing consiste en utilizar más de una clave por cada bucket. Usando sólo 2 claves por bucket permite un factor de carga superior al 80%.

Otros algoritmos que utilizan múltiples funciones hash incluyen el filtrado de Bloom. Un filtro cuckoo emplea principios cuckoo hashing para implementar una estructura de datos equivalente a un filtro Bloom.[3]​ Algunas personas recomiendan una simplificación generalizada de cuckoo hashing llamada skewed-associative-cache en la misma caché de la CPU.[4]

Un estudio realizado por Zukowski Et Al[5]​ ha demostrado que el cuckoo hashing es mucho más rápido que chained hashing para las cache con menos capacidad (tablas hash residentes en los procesadores modernos). Kenneth Ross[6]​ ha mostrado versiones bucketized de cuckoo hashing (variantes que utilizan bucket que contienen más de una clave) para ser más rápido que los métodos convencionales también para grandes tablas hash, cuando la utilización del espacio es alto. El rendimiento de la tabla cuckoo hashing bucketized se procedió a investigar por Askitis,[7]​ con su rendimiento en comparación contra los esquemas de hash alternativos.

Una encuesta realizada por Michael Mitzenmacher[2]​ presenta problemas abiertos relacionados con el hash de cuckoo a partir de 2009.[8]

Véase también

[editar]

Referencias

[editar]
  1. a b c Pagh, Rasmus; Rodler, Flemming Friche (2001). «Cuckoo Hashing». Algorithms — ESA 2001. Lecture Notes in Computer Science 2161. pp. 121-133. ISBN 978-3-540-42493-2. doi:10.1007/3-540-44676-1_10. 
  2. a b Mitzenmacher, Michael (9 de septiembre de 2009). Some Open Questions Related to Cuckoo Hashing | Proceedings of ESA 2009 (PDF). Consultado el 10 de noviembre de 2010. 
  3. Fan, Bin; Kaminsky, Michael; Andersen, David (agosto de 2013). «Cuckoo Filter: Better Than Bloom» (PDF). ;login: (USENIX) 38 (4): 36-40. Consultado el 12 de junio de 2014. 
  4. «"Micro-Architecture"». Irisa fr. 
  5. Zukowski, Marcin; Heman, Sandor; Boncz, Peter (junio de 2006). Architecture-Conscious Hashing (PDF). Proc. of the International Workshop on Data Management on New Hardware (DaMoN). Consultado el 16 de octubre de 2008. 
  6. Ross, Kenneth (8 de noviembre de 2006). Efficient Hash Probes on Modern Processors (PDF). IBM Research Report RC24100. RC24100. Archivado desde el original el 28 de noviembre de 2019. Consultado el 16 de octubre de 2008. 
  7. Askitis, Nikolas (2009). «Fast and Compact Hash Tables for Integer Keys». Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) 91. pp. 113-122. ISBN 978-1-920682-72-9. Archivado desde el original el 16 de febrero de 2011. Consultado el 10 de noviembre de 2015. 
  8. Zukowski, Marcin; Heman, Sandor; Boncz, Peter (junio de 2006). Architecture-Conscious Hashing (PDF). Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Consultado el 16 de octubre de 2008. 

Enlaces externos

[editar]

Ejemplos

[editar]