El hashing cuco logra búsquedas en tiempo constante al desalojar una clave como un huevo de cuco

Las tablas hash estándar con direccionamiento abierto se degradan cuando las entradas se agrupan y las cadenas de sondeo se alargan. Rasmus Pagh y Flemming Friche Rodler se preguntaron qué ocurriría si cada clave tuviera exactamente dos posibles posiciones en lugar de una.

Su diccionario, presentado en 2001 en BRICS en Aarhus, utiliza dos funciones hash y dos tablas. Ante una colisión, la clave que llega desaloja al ocupante, que a su vez se traslada a su otro hogar de forma recursiva. La búsqueda está garantizada en como máximo dos sondeos.

Dado que las tablas solo necesitan estar llenas aproximadamente a la mitad en promedio, la estructura sigue siendo eficiente en memoria y, al mismo tiempo, ofrece una búsqueda en tiempo constante garantizada en el peor caso.

Dar a cada clave dos lugares y reubicar a la que pierde

Dos posiciones posibles acotan la búsqueda a dos sondeos, independientemente del conjunto de claves.

El desalojo resuelve las colisiones sin una larga cadena de sondeo ni una lista enlazada.

Mantiene una alta ocupación, por lo que aprovecha bien la memoria y sigue siendo favorable para la caché.

Elegir una estructura de datos rápida en el peor caso, no solo en promedio. El desalojo con dos opciones convierte una colisión rara y costosa en una búsqueda acotada de dos sondeos.

El hashing cuco se convirtió en un resultado de referencia en la teoría y la práctica de los diccionarios. Su garantía de tiempo constante y su localidad de caché lo hicieron atractivo para hardware y enrutamiento de alto rendimiento, y la idea de desalojo influyó en esquemas posteriores de hashing y sketching.