El hash de cuco es un esquema de programación informática para resolver colisiones hash de valores de funciones hash en una tabla , con un tiempo de búsqueda constante en el peor de los casos . El nombre deriva del comportamiento de algunas especies de cuco , donde el polluelo de cuco empuja a los demás huevos o crías fuera del nido cuando nace; de manera análoga, insertar una nueva clave en una tabla de hashing de cuco puede empujar una clave anterior a una ubicación diferente en la tabla.
Historia
El hash del cuco fue descrito por primera vez por Rasmus Pagh y Flemming Friche Rodler en un documento de una conferencia de 2001. [1] El documento fue galardonado con el premio European Symposium on Algorithms Test-of-Time en 2020. [2]
Operación
El hash de cuco es una forma de direccionamiento abierto en el que cada celda no vacía de una 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 con ella) se puede encontrar examinando esa celda de la tabla. Sin embargo, el direccionamiento abierto sufre colisiones , que ocurren cuando se asigna más de una clave a la misma celda. La idea básica del hash de cuco es resolver colisiones mediante el uso de dos funciones hash en lugar de una sola. Esto proporciona dos posibles ubicaciones en la tabla hash para cada clave. En una de las variantes del algoritmo de uso común, 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. También es posible que ambas funciones hash proporcionen índices en una sola tabla.
La búsqueda requiere la inspección de solo dos ubicaciones en la tabla hash, lo que lleva un tiempo constante en el peor de los casos. Esto contrasta con muchos otros algoritmos de tablas hash, que pueden no tener un límite constante en el peor de los casos en el momento de realizar una búsqueda. También se pueden realizar eliminaciones poniendo en blanco la celda que contiene una clave, en un tiempo constante en el peor de los casos, más simplemente que algunos otros esquemas, como el sondeo lineal .
Cuando se inserta una nueva clave y una de sus dos celdas está vacía, se puede colocar en esa celda. Sin embargo, cuando ambas celdas ya estén llenas, será necesario mover otras llaves a sus segundas ubicaciones (o de regreso a sus primeras ubicaciones) para dejar espacio para la nueva llave. Se utiliza un algoritmo codicioso : la nueva clave se inserta en una de sus dos ubicaciones posibles, "expulsando", es decir, desplazando, cualquier clave que ya pueda residir en esta ubicación. Esta llave desplazada luego se inserta en su ubicación alternativa, nuevamente expulsando cualquier llave que pueda residir allí. El proceso continúa de la misma forma hasta que se encuentra una posición vacía, completando el algoritmo. Sin embargo, es posible que este proceso de inserción falle, ingresando un bucle infinito o encontrando una cadena muy larga (más larga que un umbral preestablecido que es logarítmico en el tamaño de la tabla). En este caso, la tabla hash se reconstruye in situ utilizando nuevas funciones hash :
No es necesario asignar nuevas tablas para el refrito: simplemente podemos ejecutar las tablas para eliminar y realizar el procedimiento de inserción habitual en todas las claves que no se encuentran en la posición deseada en la tabla.
- Pagh & Rodler, "Cuckoo Hashing" [1]
Teoría
Las inserciones tienen éxito en el tiempo constante esperado, [1] incluso considerando la posibilidad de tener que reconstruir la tabla, siempre y cuando el número de claves se mantenga por debajo de la mitad de la capacidad de la tabla hash, es decir, el factor de carga esté por debajo del 50%.
Un método para demostrar esto utiliza la teoría de gráficos aleatorios : se puede formar un gráfico no dirigido llamado "gráfico cucú" que tiene un vértice para cada ubicación de la tabla hash y un borde para cada valor hash, siendo los puntos finales del borde el dos posibles ubicaciones del valor. Luego, el algoritmo de inserción codicioso para agregar un conjunto de valores a una tabla hash de cuco tiene éxito si y solo si el gráfico de cuco para este conjunto de valores es un pseudoforestal , un gráfico con como máximo un ciclo en cada uno de sus componentes conectados . Cualquier subgrafo inducido por vértices con más aristas que vértices corresponde a un conjunto de claves para las que hay un número insuficiente de ranuras en la tabla hash. Cuando la función hash se elige al azar, el gráfico de cuco es un gráfico aleatorio en el modelo Erdős-Rényi . Con alta probabilidad, para un gráfico aleatorio en el que la relación entre el número de aristas y el número de vértices está delimitada por debajo de 1/2, el gráfico es un pseudoforestal y el algoritmo de hash de cuco logra colocar todas las claves. Además, la misma teoría también demuestra que el tamaño esperado de un componente conectado del gráfico de cuco es pequeño, lo que garantiza que cada inserción requiera un tiempo esperado constante. [3]
Práctica
En la práctica, el hash de cuco es aproximadamente un 20-30% más lento que el sondeo lineal , que es el más rápido de los enfoques comunes. [1] La razón es que el hash de cuco a menudo provoca dos fallos de caché por búsqueda, para comprobar las dos ubicaciones donde podría almacenarse una clave, mientras que el sondeo lineal suele provocar sólo un fallo de caché por búsqueda. Sin embargo, debido a sus peores garantías de casos en el tiempo de búsqueda, el hash de cuco aún puede ser valioso cuando se requieren tasas de respuesta en tiempo real . Una ventaja del hash de cuco es su propiedad libre de lista de enlaces, que se adapta bien al procesamiento de la GPU.
Ejemplo
Se proporcionan las siguientes funciones hash:
Las siguientes dos tablas muestran la inserción de algunos elementos de ejemplo. Cada columna corresponde al estado de las dos tablas hash a lo largo del tiempo. Se resaltan las posibles ubicaciones de inserción para cada nuevo valor.
Llave insertada | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
k | 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
h (k) | 9 | 6 | 9 | 9 | 1 | 1 | 6 | 3 | 3 | 6 | |
0 | |||||||||||
1 | 100 | 67 | 67 | 67 | 67 | 100 | |||||
2 | |||||||||||
3 | 3 | 36 | 36 | ||||||||
4 | |||||||||||
5 | |||||||||||
6 | 50 | 50 | 50 | 50 | 50 | 105 | 105 | 105 | 39 | ||
7 | |||||||||||
8 | |||||||||||
9 | 20 | 20 | 20 | 75 | 75 | 75 | 53 | 53 | 53 | 75 | |
10 |
Llave insertada | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
k | 20 | 50 | 53 | 75 | 100 | 67 | 105 | 3 | 36 | 39 | |
h ′ (k) | 1 | 4 | 4 | 6 | 9 | 6 | 9 | 0 | 3 | 3 | |
0 | 3 | 3 | |||||||||
1 | 20 | 20 | 20 | 20 | 20 | 20 | 20 | ||||
2 | |||||||||||
3 | |||||||||||
4 | 53 | 53 | 53 | 53 | 50 | 50 | 50 | 53 | |||
5 | |||||||||||
6 | 75 | 75 | 75 | 67 | |||||||
7 | |||||||||||
8 | |||||||||||
9 | 100 | 100 | 100 | 100 | 105 | ||||||
10 |
Ciclo
Si ahora intenta insertar el elemento 6, entra en un ciclo y falla. En la última fila de la tabla encontramos de nuevo la misma situación inicial que al principio.
tabla 1 | Tabla 2 |
---|---|
6 reemplaza a 50 en la celda 6 | 50 reemplaza a 53 en la celda 4 |
53 reemplaza 75 en la celda 9 | 75 reemplaza a 67 en la celda 6 |
67 reemplaza a 100 en la celda 1 | 100 reemplaza a 105 en la celda 9 |
105 reemplaza 6 en la celda 6 | 6 reemplaza a 3 en la celda 0 |
3 reemplaza a 36 en la celda 3 | 36 reemplaza 39 en la celda 3 |
39 reemplaza a 105 en la celda 6 | 105 reemplaza a 100 en la celda 9 |
100 reemplaza a 67 en la celda 1 | 67 reemplaza a 75 en la celda 6 |
75 reemplaza a 53 en la celda 9 | 53 reemplaza a 50 en la celda 4 |
50 reemplaza 39 en la celda 6 | 39 reemplaza a 36 en la celda 3 |
36 reemplaza a 3 en la celda 3 | 3 reemplaza 6 en la celda 0 |
6 reemplaza a 50 en la celda 6 | 50 reemplaza a 53 en la celda 4 |
Variaciones
Se han estudiado varias variaciones del hash de cuco, principalmente con el objetivo de mejorar su uso del espacio aumentando el factor de carga que puede tolerar a un número superior al umbral del 50% del algoritmo básico. Algunos de estos métodos también se pueden usar para reducir la tasa de fallas del hash de cuco, lo que hace que las reconstrucciones de la estructura de datos sean mucho menos frecuentes.
Se puede esperar que las generalizaciones de hash de cuco que usan más de dos funciones hash alternativas utilicen una parte mayor de la capacidad de la tabla hash de manera eficiente mientras sacrifican algo de velocidad de búsqueda e inserción. El uso de solo tres funciones hash aumenta la carga al 91%. [4] Otra generalización del hash de cuco, llamada hash de cuco bloqueado, consiste en usar más de una clave por cubo. El uso de solo 2 llaves por cubo permite un factor de carga superior al 80%. [5]
Otra variación del hash de cuco que se ha estudiado es el hash de cuco con un alijo . El alijo, en esta estructura de datos, es una matriz de un número constante de claves, que se utiliza para almacenar claves que no se pueden insertar correctamente en la tabla hash principal de la estructura. Esta modificación reduce la tasa de falla del hash de cuco a una función polinomial inversa con un exponente que puede hacerse arbitrariamente grande aumentando el tamaño de la reserva. Sin embargo, los alijos más grandes también significan búsquedas más lentas de claves que no están presentes o que están en el alijo. Un alijo se puede usar en combinación con más de dos funciones hash o con hash de cuco bloqueado para lograr factores de carga altos y tasas de falla pequeñas. [6] El análisis del hash de cuco con un alijo se extiende a funciones prácticas de hash, no solo al modelo de función de hash aleatorio comúnmente utilizado en el análisis teórico de hash. [7]
Algunas personas recomiendan una generalización simplificada del hash de cuco llamada caché asociativa sesgada en algunas cachés de CPU . [8]
Otra variación de una tabla hash de cuco, llamada filtro de cuco , reemplaza las claves almacenadas de una tabla hash de cuco con huellas dactilares mucho más cortas, calculadas aplicando otra función hash a las claves. Para permitir que estas huellas dactilares se muevan dentro del filtro de cuco, sin conocer las claves de las que provienen, las dos ubicaciones de cada huella dactilar pueden calcularse entre sí mediante una operación exclusiva bit a bit con la huella dactilar, o con un hash. de la huella dactilar. Esta estructura de datos forma una estructura de datos de pertenencia a un conjunto aproximado con las mismas propiedades que un filtro Bloom : puede almacenar los miembros de un conjunto de claves y probar si una clave de consulta es un miembro, con alguna posibilidad de falsos positivos (consultas que se informa incorrectamente como parte del conjunto) pero no falsos negativos . Sin embargo, mejora un filtro Bloom en múltiples aspectos: su uso de memoria es menor en un factor constante, tiene una mejor localidad de referencia y (a diferencia de los filtros Bloom) permite la eliminación rápida de elementos establecidos sin penalización de almacenamiento adicional. [9]
Un estudio de Zukowski et al. [10] ha demostrado que el hash de cuco es mucho más rápido que el hash encadenado para pequeñas tablas hash residentes en la caché en los procesadores modernos. Kenneth Ross [11] ha demostrado que las versiones en cubos de cuckoo hashing (variantes que usan cubos que contienen más de una clave) son más rápidas que los métodos convencionales también para tablas hash grandes, cuando la utilización del espacio es alta. El rendimiento de la tabla hash de cuco en cubos fue investigado más a fondo por Askitis, [12] comparándolo con esquemas alternativos de hash.
Una encuesta de Mitzenmacher [4] presenta problemas abiertos relacionados con el hash del cuco a partir de 2009.
Ver también
- Hash perfecto
- Hash doble
- Sondeo cuadrático
- Hash de rayuela
Referencias
- ^ a b c d Pagh, Rasmus ; Rodler, Flemming Friche (2001). "Cuco Hashing". Algoritmos - ESA 2001 . Apuntes de conferencias en Ciencias de la Computación. 2161 . págs. 121-133. CiteSeerX 10.1.1.25.4189 . doi : 10.1007 / 3-540-44676-1_10 . ISBN 978-3-540-42493-2.
- ^ Comité de premios: Uri Zwick , Samir Khuller , Edith Cohen . "ESA - European Symposium on Algorithms: ESA Test-of-Time Award 2020" . esa-symposium.org . Consultado el 22 de mayo de 2021 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Kutzelnigg, Reinhard (2006). Gráficos aleatorios bipartitos y hash de cuco (PDF) . Cuarto Coloquio de Matemáticas e Informática. Matemáticas discretas e informática teórica. AG . págs. 403–406.
- ^ a b Mitzenmacher, Michael (9 de septiembre de 2009 ). "Algunas preguntas abiertas relacionadas con el picadillo de cuco | Actas de la ESA 2009" (PDF) . Consultado el 10 de noviembre de 2010 . Cite journal requiere
|journal=
( ayuda ) - ^ Dietzfelbinger, Martin; Weidling, Christoph (2007), "Asignación equilibrada y diccionarios con contenedores de tamaño constante apretados", Theoret. Computación. Sci. , 380 (1–2): 47–68, doi : 10.1016 / j.tcs.2007.02.054 , MR 2330641.
- ^ Kirsch, Adam; Mitzenmacher, Michael D .; Wieder, Udi (2010), "Hashing más robusto: hashing de cuco con un alijo", SIAM J. Comput. , 39 (4): 1543-1561, doi : 10.1137 / 080728743 , MR 2580539.
- ^ Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp (2014), "Las familias de hachís explícitas y eficientes son suficientes para el hash de cuco con un alijo", Algorithmica , 70 (3): 428–456, arXiv : 1204.4431 , doi : 10.1007 / s00453-013-9840-x , MR 3247374.
- ^ "Microarquitectura" .
- ^ Fan, Bin; Andersen, Dave G .; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Filtro de cuco: Prácticamente mejor que Bloom", Proc. 10 ° ACM Int. Conf. Experimentos y tecnologías de redes emergentes (CoNEXT '14) , págs. 75–88, doi : 10.1145 / 2674005.2674994
- ^ Zukowski, Marcin; Heman, Sandor; Boncz, Peter (junio de 2006). "Hashing consciente de la arquitectura" (PDF) . Actas del Taller internacional sobre gestión de datos en hardware nuevo (DaMoN) . Consultado el 16 de octubre de 2008 . Cite journal requiere
|journal=
( ayuda ) - ^ Ross, Kenneth (8 de noviembre de 2006). "Sondas hash eficientes en procesadores modernos" (PDF) . Informe de investigación de IBM RC24100. RC24100 . Consultado el 16 de octubre de 2008 . Cite journal requiere
|journal=
( ayuda ) - ^ Askitis, Nikolas (2009). Tablas hash rápidas y compactas para claves enteras (PDF) . Actas de la 32ª Conferencia de Ciencias de la Computación de Australasia (ACSC 2009) . 91 . págs. 113-122. ISBN 978-1-920682-72-9. Archivado desde el original (PDF) el 16 de febrero de 2011 . Consultado el 13 de junio de 2010 .
enlaces externos
- Una alternativa fresca y práctica a las tradicionales tablas de hachís , U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
- Hashing de cuco para estudiantes, 2006 , R. Pagh, 2006.
- Hashing de cuco, teoría y práctica (Parte 1, Parte 2 y Parte 3 ), Michael Mitzenmacher, 2007.
- Naor, Moni; Segev, Gil; Wieder, Udi (2008). "Hashing de cuco independiente de la historia" . Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) . Reykjavik, Islandia . Consultado el 21 de julio de 2008 .
- Mejoras algorítmicas para el hash de cuco simultáneo rápido , X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.
Ejemplos de
- Hashtable Cuckoo de alto rendimiento concurrente escrito en C ++
- Mapa hash de cuco escrito en C ++
- Generador de tablas hash de cuco estático para C / C ++
- Tabla de hash de cuco escrita en Haskell
- Hashing de cuco para Go