Hashing de cuco

Esquema de hash de estructura de datos

Ejemplo de hash de Cuckoo. Las flechas muestran la ubicación alternativa de cada clave. 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 se volvería a expulsar.

El hash de cuco es un esquema de programación informática para resolver colisiones 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 nacen en una variación del comportamiento conocido como parasitismo de cría ; análogamente, insertar una nueva clave en una tabla hash de cuco puede empujar una clave anterior a una ubicación diferente en la tabla.

Historia

El hash Cuckoo fue descrito por primera vez por Rasmus Pagh y Flemming Friche Rodler en un artículo de conferencia de 2001. ^[1] El artículo recibió el premio Test-of-Time del Simposio Europeo sobre Algoritmos en 2020. ^{[2] : 122}

Operaciones

El hash de cuco es una forma de direccionamiento abierto en la 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 de colisiones , que ocurren cuando más de una clave se asigna a la misma celda. La idea básica del hash de cuco es resolver las 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 comúnmente 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 hash de Cuckoo 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 es la clave y es el conjunto cuyas claves se almacenan en de o de . 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 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 se realiza ningún sondeo. Esto ignora el costo de la operación de reducción si la tabla es demasiado dispersa. ^{[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 tabla está ocupada. Si no lo está, el elemento se inserta en esa ranura. Sin embargo, si la ranura está ocupada, el elemento existente se elimina y se inserta en . Luego, se inserta en la tabla siguiendo el mismo procedimiento. El proceso continúa hasta que se encuentra una posición vacía para insertar la clave. ^{[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 vuelven a codificar con nuevas funciones hash y se repite el procedimiento de inserción. El siguiente es el 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 "método del cuco" de patear otras teclas que ocupan repeticiones hasta que cada tecla tenga su propio "nido", es decir, que el elemento se inserte en una ranura vacía en cualquiera de las dos tablas. La notación expresa el 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 se realizan en el tiempo constante esperado, ^[1] incluso considerando la posibilidad de tener que reconstruir la tabla, siempre que 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 sea inferior al 50%.

Un método para probar esto utiliza la teoría de grafos aleatorios : se puede formar un grafo no dirigido llamado "grafo de cuco" que tiene un vértice para cada ubicación de la tabla hash y una arista para cada valor hash, con los puntos finales de la arista siendo las dos posibles ubicaciones del valor. Entonces, el algoritmo de inserción voraz para agregar un conjunto de valores a una tabla hash de cuco tiene éxito si y solo si el grafo de cuco para este conjunto de valores es un pseudobosque , un grafo 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 hay un número insuficiente de ranuras en la tabla hash. Cuando la función hash se elige aleatoriamente, el grafo de cuco es un grafo aleatorio en el modelo de Erdős–Rényi . Con una alta probabilidad, para un factor de carga menor a 1/2 (que corresponde 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 de hash cuckoo logra colocar todas las claves. La misma teoría también demuestra que el tamaño esperado de un componente conectado del gráfico cuckoo es pequeño, lo que garantiza que cada inserción tome un tiempo esperado constante. Sin embargo, también con una alta probabilidad, un factor de carga mayor a 1/2 conducirá a un componente gigante con dos o más ciclos, lo que hará que la estructura de datos falle y deba redimensionarse. ^[3]

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

Práctica

En la práctica, el hash cuckoo 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 cuckoo a menudo causa dos errores de caché por búsqueda, para verificar las dos ubicaciones donde se puede 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 hash cuckoo aún puede ser valioso cuando se requieren tasas de respuesta en tiempo real .

Ejemplo

Se dan las siguientes funciones hash (los dos dígitos menos significativos de k en base 11):

${\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 destacan las posibles ubicaciones de inserción para cada nuevo valor. La última columna ilustra una inserción fallida debido a un ciclo; los detalles se encuentran a continuación.

Ciclo

Si se intenta introducir el elemento 45 se entra en un ciclo y se fracasa. En la última fila de la tabla encontramos nuevamente la misma situación inicial que al principio.

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

Variaciones

Se han estudiado varias variaciones del algoritmo Cuckoo Hashing, principalmente con el objetivo de mejorar su uso del espacio incrementando 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 fallos del algoritmo Cuckoo Hashing, lo que hace que las reconstrucciones de la estructura de datos sean mucho menos frecuentes.

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

Otra generalización del hash cuckoo, llamada hash cuckoo bloqueado, utiliza más de una clave por contenedor y un esquema de asignación equilibrado. El uso de solo dos claves por contenedor permite un factor de carga superior al 80 %. ^[8]

Otra variación del hash cuco que se ha estudiado es el hash cuco con un stash . El stash, 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 fallos del hash cuco a una función polinómica inversa con un exponente que se puede hacer arbitrariamente grande aumentando el tamaño del stash. Sin embargo, los stash más grandes también significan búsquedas más lentas de claves que no están presentes o que están en el stash. Un stash se puede utilizar en combinación con más de dos funciones hash o con hash cuco bloqueado para lograr factores de carga altos y pequeñas tasas de fallo. ^[9] El análisis del hash cuco con un stash se extiende a las funciones hash prácticas, no solo al modelo de función hash aleatoria que se utiliza comúnmente en el análisis teórico del hash. ^[10]

Algunas personas recomiendan una generalización simplificada del hash cuckoo llamada caché asociativa sesgada en algunos 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 de cuco, sin saber las claves de las que provienen, las dos ubicaciones de cada huella digital se pueden calcular una a partir de la otra mediante una operación exclusiva bit a bit o con la huella digital, o con un hash de la huella digital. Esta estructura de datos forma una estructura de datos de pertenencia a un conjunto aproximado con propiedades muy similares a las de un filtro Bloom : puede almacenar los miembros de un conjunto de claves y comprobar si una clave de consulta es un miembro, con cierta posibilidad de falsos positivos (consultas que se informan incorrectamente como parte del conjunto) pero sin falsos negativos . Sin embargo, mejora un filtro Bloom en múltiples aspectos: su uso de memoria es menor por un factor constante, tiene una mejor localidad de referencia y (a diferencia de los filtros Bloom) permite la eliminación rápida de elementos del conjunto sin penalización de almacenamiento adicional. ^[12]

Comparación con estructuras relacionadas

Un estudio de Zukowski et al. ^[13] ha demostrado que el hash cuckoo 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 contenedores del hash cuckoo (variantes que utilizan contenedores 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 cuckoo en contenedores y lo comparó con esquemas de hash alternativos.

Una encuesta realizada por Mitzenmacher ^[7] presenta problemas abiertos relacionados con el hash cuckoo a partir de 2009.

Usuarios conocidos

El hash Cuckoo se utiliza en el sistema de recomendaciones de TikTok para resolver el problema de las "colisiones de tablas de incrustación", que pueden dar como resultado una reducción de la calidad del modelo. El sistema de recomendaciones de TikTok "Monolith" aprovecha la resolución de colisiones del hash Cuckoo para evitar que se asignen diferentes conceptos a los mismos vectores. ^[16]

Véase también

• Hashing perfecto
• Doble hash
• Sondeo cuadrático
• Hashing 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 de CS1: otros ( enlace )
3. Kutzelnigg, Reinhard (2006). Grafos aleatorios bipartitos y algoritmos hash cuckoo (PDF) . Cuarto Coloquio sobre Matemáticas y Ciencias de la Computación. Matemáticas discretas y ciencias de la computación teórica. Vol. AG. págs. 403–406.
4. Cohen, Jeffrey S. y Daniel M. Kane. "Límites de la independencia requerida para el hash cuckoo". ACM Transactions on Algorithms (2009).
5. Pǎtraşcu, Mihai y Mikkel Thorup. "El poder del hash de tabulación simple". Journal of the ACM (JACM) 59.3 (2012): 1-50.
6. Aumüller, Martin, Martin Dietzfelbinger y Philipp Woelfel. "Las familias de hash explícitas y eficientes son suficientes para el hash cuckoo con un stash". Algorithmica 70.3 (2014): 428-456.
7. Mitzenmacher, Michael (9 de septiembre de 2009). "Algunas preguntas abiertas relacionadas con el hash Cuckoo" (PDF) . Actas de la ESA 2009. Consultado el 10 de noviembre de 2010 .
8. Dietzfelbinger, Martin; Weidling, Christoph (2007). "Asignación equilibrada y diccionarios con compartimentos de tamaño constante y muy compactos". Theoret. Comput. Sci . 380 (1–2): 47–68. doi : 10.1016/j.tcs.2007.02.054 . MR  2330641.
9. Kirsch, Adam; Mitzenmacher, Michael D.; Wieder, Udi (2010). "Hash más robusto: hashing cuckoo con un stash". SIAM J. Comput . 39 (4): 1543–1561. doi :10.1137/080728743. MR  2580539.
10. Aumüller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp (2014). "Las familias hash explícitas y eficientes son suficientes para el hash cuckoo con un stash". Algorithmica . 70 (3): 428–456. arXiv : 1204.4431 . doi :10.1007/s00453-013-9840-x. MR  3247374. S2CID  1888828.
11. "Microarquitectura".
12. Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014), "Filtro Cuckoo: prácticamente mejor que Bloom", Proc. 10th ACM Int. Conf. Experimentos y tecnologías de redes emergentes (CoNEXT '14) , págs. 75–88, doi : 10.1145/2674005.2674994
13. Zukowski, Marcin; Heman, Sandor; Boncz, Peter (junio de 2006). "Architecture-Conscious Hashing" (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 de 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 Ciencias Informáticas de Australasia (ACSC 2009) (PDF) . Vol. 91. págs. 113–122. ISBN 978-1-920682-72-9Archivado desde el original (PDF) el 16 de febrero de 2011. Consultado el 13 de junio de 2010 .
16. "Monolith: el sistema de recomendaciones detrás de TikTok". gantry.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). "History-Independent Cuckoo Hashing". Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP) . Reykjavik, Islandia . Consultado el 21 de julio de 2008 .
• Mejoras algorítmicas para hash Cuckoo 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 Cuckoo escrito en C++
• Generador de tabla hash estática de cuckoo para C/C++
• Tabla hash de Cuckoo escrita en Haskell
• Hashing de cuco para Go