Cuckoo hashing

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

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

Teoría

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.

​

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,​ 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

Se dan las siguientes funciones de hash:

$h\left(k\right)=k\mod 11$
$h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor \mod 11$

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

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.

$h\left(6\right)=6\mod 11=6$
$h'\left(6\right)=\left\lfloor {\frac {6}{11}}\right\rfloor \mod 11=0$

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

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%.​ 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.​ Algunas personas recomiendan una simplificación generalizada de cuckoo hashing llamada skewed-associative-cache en la misma caché de la CPU.​

Un estudio realizado por Zukowski Et Al​ 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​ 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,​ con su rendimiento en comparación contra los esquemas de hash alternativos.

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

Véase también

• Colisión de hash
• Función hash

Enlaces externos

• A cool and practical alternative to traditional hash tables Archivado el 7 de abril de 2019 en Wayback Machine., U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
• Cuckoo Hashing, Theory and Practice (Part 1, Part 2 and Part 3), Michael Mitzenmacher, 2007.
• Naor, Moni; Segev, Gil; Wieder, Udi (2008). «History-Independent Cuckoo Hashing». International Colloquium on Automata, Languages and Programming (ICALP). Reykjavik, Iceland. Consultado el 21 de julio de 2008. 
• Algorithmic Improvements for Fast Concurrent Cuckoo Hashing, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.

Ejemplos

• implementación eficiente de cuckoo hashing escrito en C++
• cuckoo hashing escrito en C ++
• cuckoo estático generador de tabla hash para C/C ++
• cuckoo hashing escrito en Java Archivado el 16 de abril de 2014 en Wayback Machine.
• HashMap cuckoo hashing genérico en Java (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
• cuckoo hashing escrito en Haskell
• cuckoo hashing para Go

• Datos: Q1584911