hashing de cuco

Esquema de hash de estructura de datos

Ejemplo de hash de cuco. Las flechas muestran la ubicación alternativa de cada tecla. Se insertaría un nuevo elemento en la ubicación de A moviendo A a su ubicación alternativa, actualmente ocupada por B, y moviendo B a su ubicación alternativa que actualmente está vacía. La inserción de un nuevo elemento en la ubicación de H no tendría éxito: dado que H es parte de un ciclo (junto con W), el nuevo elemento sería expulsado nuevamente.

El hashing cuco es un esquema en programación de computadoras 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 otros huevos o crías fuera del nido cuando eclosiona, en una variación del comportamiento denominado parasitismo de cría ; De manera análoga, insertar una nueva clave en una tabla hash cuco puede empujar una clave más antigua a una ubicación diferente en la tabla.

Historia

El hashing de cuco fue descrito por primera vez por Rasmus Pagh y Flemming Friche Rodler en un artículo de una conferencia de 2001. ^[1] El artículo recibió el premio Prueba de tiempo del Simposio europeo sobre algoritmos en 2020. ^{[2] : 122}

Operaciones

El hash 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 a ella) se puede encontrar examinando esa celda de la tabla. Sin embargo, el direccionamiento abierto sufre colisiones , lo que ocurre cuando se asigna más de una clave a la misma celda. La idea básica del hash cuco es resolver colisiones utilizando dos funciones hash en lugar de solo una. Esto proporciona dos posibles ubicaciones en la tabla hash para cada clave. En una de las variantes más utilizadas 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. También es posible que ambas funciones hash proporcionen índices en una sola tabla. ^{[1] : 121-122}

Buscar

El hashing cuco utiliza dos tablas hash y . Suponiendo que es la longitud de cada tabla, las funciones hash para las dos tablas se definen como, y donde está la clave y es el conjunto cuyas claves se almacenan en of o of . La operación de búsqueda es la siguiente: ^{[1] : 124} ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle r}$ ${\displaystyle h_{1},\ h_{2}\ :\ \cup \rightarrow \{0,...,r-1\}}$ ${\displaystyle \forall x\in S}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle T_{1}}$ ${\displaystyle h_{2}(x)}$ ${\displaystyle T_{2}}$

El o lógico ( ) denota que el valor de la clave se encuentra en o , que es en el peor de los casos. ^{[1] : 123} ${\displaystyle \vee }$ ${\displaystyle x}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle O(1)}$

Supresión

La eliminación se realiza a tiempo ya que no implica ningún sondeo. Esto ignora el costo de la operación de reducción si la tabla es demasiado escasa. ^{[1] : 124-125} ${\displaystyle O(1)}$

Inserción

Al insertar un nuevo elemento con clave , el primer paso consiste en examinar si la ranura de la mesa está ocupada. Si no es así, el artículo se inserta en esa ranura. Sin embargo, si el espacio está ocupado, el elemento existente se elimina y se inserta en . Luego, se inserta en la mesa siguiendo el mismo procedimiento. El proceso continúa hasta encontrar una posición vacía para insertar la llave. ^{[1] : 124-125} Para evitar un bucle infinito , se especifica un umbral. Si el número de iteraciones excede este umbral fijo, tanto y se repiten con nuevas funciones hash y se repite el procedimiento de inserción. El siguiente es un pseudocódigo para la inserción: ^{[1] : 125} ${\displaystyle x}$ ${\displaystyle h_{1}(x)}$ ${\displaystyle T_{1}}$ ${\displaystyle x'}$ ${\displaystyle x}$ ${\displaystyle T_{1}[h_{1}(x)]}$ ${\displaystyle x'}$ ${\displaystyle T_{2}}$ ${\displaystyle {\text{Max-Loop}}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

En las líneas 10 y 15, el "enfoque del cuco" de patear otras llaves que ocupan se repite hasta que cada llave tiene su propio "nido", es decir, el elemento se inserta en una ranura vacía en cualquiera de las dos tablas. La notación expresa intercambio y . ^{[1] : 124-125} ${\displaystyle T_{1,2}[h_{1,2}(x)]}$ ${\displaystyle x}$ ${\displaystyle x\leftrightarrow y}$ ${\displaystyle x}$ ${\displaystyle y}$

Teoría

Las inserciones tienen éxito en un 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 de cuco" 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 los dos posibles ubicaciones del valor. Entonces, el codicioso algoritmo de inserción 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 pseudobosque , 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 cuales no hay un número suficiente 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 factor de carga inferior a 1/2 (correspondiente a un gráfico aleatorio en el que la relación entre el número de aristas y el número de vértices está limitada por debajo de 1/2), el gráfico es un pseudobosque y el algoritmo hash de cuco. logra colocar todas las llaves. 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. Sin embargo, también con una alta probabilidad, un factor de carga superior a 1/2 dará lugar a un componente gigante con dos o más ciclos, lo que provocará que la estructura de datos falle y sea necesario cambiar su tamaño. ^[3]

Dado que una función hash aleatoria teórica requiere demasiado espacio para su uso práctico, una cuestión teórica importante es qué funciones hash prácticas son suficientes para el hash Cuckoo. Un enfoque es utilizar hash independiente de k . En 2009 se demostró ^[4] que -la independencia es suficiente y al menos 6-se necesita independencia. Otro enfoque es utilizar el hashing de tabulación , que no es independiente de 6, pero en 2012 ^[5] se demostró que tiene otras propiedades suficientes para el hash de Cuckoo. Un tercer enfoque de 2014 ^[6] es modificar ligeramente la tabla hash cuco con un llamado alijo, que permite utilizar nada más que 2 funciones hash independientes. ${\displaystyle O(\log n)}$

Práctica

En la práctica, el hash cuco es entre un 20% y un 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 cuco a menudo causa dos errores de caché por búsqueda, para verificar las dos ubicaciones donde se podría almacenar una clave, mientras que el sondeo lineal generalmente causa solo un error de caché por búsqueda. Sin embargo, debido a sus garantías en el peor de los casos en cuanto al tiempo de búsqueda, el hashing cuco aún puede ser valioso cuando se requieren tasas de respuesta en tiempo real . Una ventaja del hashing cuco es su propiedad sin lista vinculada, que se adapta bien al procesamiento de GPU.

Ejemplo

Se proporcionan las siguientes funciones hash:

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

Las dos tablas siguientes 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.

Ciclo

Si ahora intenta insertar el elemento 6, entrará en un ciclo y fallará. En la última fila de la tabla volvemos a encontrar la misma situación inicial que al principio.

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

Variaciones

Se han estudiado varias variaciones del hashing cuco, principalmente con el objetivo de mejorar su uso del espacio aumentando el factor de carga que puede tolerar a un número mayor que el umbral del 50% del algoritmo básico. Algunos de estos métodos también se pueden utilizar para reducir la tasa de fallas del hash cuco, lo que hace que las reconstrucciones de la estructura de datos sean mucho menos frecuentes.

Se puede esperar que las generalizaciones del hash cuco que utilizan más de dos funciones hash alternativas utilicen una mayor parte de la capacidad de la tabla hash de manera eficiente y al mismo tiempo sacrifiquen algo de velocidad de búsqueda e inserción. Usar solo tres funciones hash aumenta la carga al 91%. ^[7]

Otra generalización del hash de cuco llamado hash de cuco bloqueado utiliza más de una clave por depósito y un esquema de asignación equilibrado. El uso de sólo 2 llaves por cubo permite un factor de carga superior al 80%. ^[8]

Otra variación del hashing 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 con éxito en la tabla hash principal de la estructura. Esta modificación reduce la tasa de falla del hash cuco a una función polinómica inversa con un exponente que puede hacerse arbitrariamente grande aumentando el tamaño del alijo. 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. ^[9] El análisis del hash cuco con un alijo se extiende a funciones hash prácticas, no solo al modelo de función hash aleatoria comúnmente utilizado en el análisis teórico del hash. ^[10]

Algunas personas recomiendan una generalización simplificada del hash cuco llamada caché asociativa sesgada en algunas cachés de CPU . ^[11]

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 digitales mucho más cortas, calculadas aplicando otra función hash a las claves. Para permitir que estas huellas digitales se muevan dentro del filtro cuco, sin conocer las claves de donde provienen, las dos ubicaciones de cada huella digital pueden calcularse entre sí mediante una operación exclusiva bit a bit con la huella digital o con un hash. de la huella dactilar. Esta estructura de datos forma una estructura de datos de membresía de conjunto aproximado con prácticamente 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 cierta posibilidad de falsos positivos (consultas que se informan incorrectamente como parte del conjunto) pero no hay 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. ^[12]

Comparación con estructuras relacionadas.

Un estudio de Zukowski et al. ^[13] ha demostrado que el hash cuco es mucho más rápido que el hash encadenado para tablas hash pequeñas residentes en caché en procesadores modernos. Kenneth Ross ^[14] ha demostrado que las versiones en cubos de hash cuco (variantes que utilizan 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. Askitis ^[15] investigó más a fondo el rendimiento de la tabla hash de cuco en cubos, comparándolo con esquemas de hash alternativos.

Un estudio de Mitzenmacher ^[7] presenta problemas abiertos relacionados con el hash cuco desde 2009.

Aplicaciones

Cuckoo Hashing se utiliza en el sistema de recomendación de TikTok para resolver el problema de las "colisiones de tablas incrustadas", que pueden resultar en una reducción de la calidad del modelo. El sistema de recomendación de TikTok "Monolith" aprovecha la resolución de colisión del hash cuco para evitar que diferentes conceptos se asignen a los mismos vectores. ^[dieciséis]

Ver también

• hash perfecto
• Doble hash
• Sondeo cuadrático
• hash de rayuela

Referencias

1. Pagh, Rasmus ; Rodler, Flemming Friche (2001). "Hashing de cuco". Algoritmos: ESA 2001 . Apuntes de conferencias sobre informática. vol. 2161. CiteSeerX  10.1.1.25.4189 . doi :10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
2. "ESA - Simposio europeo sobre algoritmos: Premio ESA Test-of-Time 2020". esa-symposium.org . Comité de adjudicación: Uri Zwick , Samir Khuller , Edith Cohen . Archivado desde el original el 22 de mayo de 2021 . Consultado el 22 de mayo de 2021 .{{cite web}}: Mantenimiento CS1: otros ( enlace )
3. Kutzelnigg, Reinhard (2006). Gráficos aleatorios bipartitos y hash de cuco (PDF) . Cuarto Coloquio de Matemáticas e Informática. Matemática Discreta e Informática Teórica. vol. AG. págs. 403–406.
4. Cohen, Jeffrey S. y Daniel M. Kane. "Límites de la independencia necesaria para el hash cuco". Transacciones ACM sobre algoritmos (2009).
5. Pǎtraşcu, Mihai y Mikkel Thorup. "El poder del hash de tabulación simple". Revista de la ACM (JACM) 59.3 (2012): 1-50.
6. Aumüller, Martin, Martin Dietzfelbinger y Philipp Woelfel. "Para hacer hash cuco con un alijo, basta con familias de hash explícitas y eficientes". Algorítmica 70.3 (2014): 428-456.
7. Mitzenmacher, Michael (9 de septiembre de 2009). "Algunas preguntas abiertas relacionadas con Cuckoo Hashing" (PDF) . Actas de la ESA 2009 . Consultado el 10 de noviembre de 2010 .
8. Dietzfelbinger, Martín; Weidling, Christoph (2007). "Asignación equilibrada y diccionarios con contenedores de tamaño constante muy apretados". Teoría. Computadora. Ciencia . 380 (1–2): 47–68. doi : 10.1016/j.tcs.2007.02.054 . SEÑOR  2330641.
9. Kirsch, Adán; Mitzenmacher, Michael D.; Wieder, Udi (2010). "Hashing más robusto: hash de cuco con un alijo". SIAM J. Computación . 39 (4): 1543-1561. doi : 10.1137/080728743. SEÑOR  2580539.
10. Aumüller, Martín; Dietzfelbinger, Martín; Woelfel, Philipp (2014). "Las familias de hash explícitas y eficientes son suficientes para el hash cuco con un alijo". Algorítmica . 70 (3): 428–456. arXiv : 1204.4431 . doi :10.1007/s00453-013-9840-x. SEÑOR  3247374. S2CID  1888828.
11. "Microarquitectura".
12. Ventilador, contenedor; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Filtro 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
13. Zukowski, Marcin; Hemán, Sandor; Boncz, Peter (junio de 2006). "Hashing consciente de la arquitectura" (PDF) . Actas del Taller internacional sobre gestión de datos en nuevo hardware (DaMoN) . Consultado el 16 de octubre de 2008 .
14. Ross, Kenneth (8 de noviembre de 2006). Sondas Hash eficientes en procesadores modernos (PDF) (Informe de investigación). IBM. RC24100 . Consultado el 16 de octubre de 2008 .
15. Askitis, Nikolas (2009). "Tablas hash rápidas y compactas para claves enteras". Actas de la 32ª Conferencia de Informática de Australasia (ACSC 2009) (PDF) . vol. 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 .
16. "Monolith: el sistema de recomendación detrás de TikTok". pórtico.io . Consultado el 30 de mayo de 2023 .

enlaces externos

• Una alternativa interesante y práctica a las tablas hash tradicionales Archivado el 7 de abril de 2019 en Wayback Machine , U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing para estudiantes universitarios, 2006, R. Pagh, 2006.
• Cuckoo Hashing, teoría y práctica (Parte 1, Parte 2 y Parte 3), Michael Mitzenmacher, 2007.
• Naor, Moni; Segev, Gil; Wieder, Udi (2008). "Hash de cuco independiente de la historia". Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) . Reikiavik, Islandia . Consultado el 21 de julio de 2008 .
• Mejoras algorítmicas para Cuckoo Hashing concurrente rápido, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.

Ejemplos

• Tabla hash Cuckoo concurrente de alto rendimiento escrita en C++
• Mapa hash de cuco escrito en C++
• Generador de tabla hash de cuco estático para C/C++
• Tabla hash de cuco escrita en Haskell
• Hashing de cuco para Go