Cuckoo hashing
# Cuckoo hashing

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:

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) :

| | 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 1 | table 2 | 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.

