Hashing cuco en C
https://stackoverflow.com/questions/231438
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Alguien tiene una implementación de hashing de cuco en C? Si hubiera una versión de código abierto, no GPL, ¡sería perfecta!
Dado que Adam lo mencionó en su comentario, ¿alguien sabe por qué no se usa tanto? ¿Es solo una cuestión de implementación o las buenas propiedades teóricas no se materializan en la práctica?
Otros consejos
Como han señalado otras respuestas, es cierto que la tabla hash de cuco más simple requiere que la tabla esté medio vacía. Sin embargo, el concepto se ha generalizado a d , en particular el hash de cuco, en el que cada clave tiene d lugares posibles para anidar, en lugar de 2 lugares en la versión simple.
El factor de carga aceptable aumenta rápidamente a medida que aumenta d . Solo para d = 3, ya puede usar alrededor de una tabla completa del 75%. El inconveniente es que necesita
El hash de cuco no está siendo usado fuera de la academia (aparte de los cachés de hardware, que a veces toman ideas de, pero en realidad no se implementan completamente). Requiere una tabla hash muy dispersa para obtener un buen tiempo en las inserciones: realmente necesita tener el 51% de su tabla vacía para un buen rendimiento. Por lo tanto, es rápido y ocupa mucho espacio, o lento y utiliza el espacio de manera eficiente, nunca ambas cosas. Otros algoritmos son eficientes tanto en el tiempo como en el espacio, aunque son peores que el cuco cuando solo se tiene en cuenta el tiempo o el espacio.
Aquí hay un generador de código para tablas hash de cuco . Verifique la licencia del generador para verificar que la salida no sea GPL. Debería serlo, pero verifique de todos modos.
-Adam
Aunque es una pregunta antigua, alguien podría estar interesado :)
Este documento describe la implementación de un hash de cuco d-ary paralelo en GPU (CUDA / OpenCL). Se describe muy bien y su implementación basada en la descripción es bastante fácil. En general vale la pena leer, si está interesado en este tema. (Sin embargo, necesitará un inicio de sesión de ACM).
El idioma IO tiene uno, en PHash.c. Puede encontrar el código para IO en Github. IO tiene licencia BSD.
Veo el punto en la utilización, pero este fue mi razonamiento para probar este esquema de hashing en particular. Por favor, avíseme si me perdí algo.
Que yo sepa, las posibles alternativas a las tablas hash para crear un diccionario dinámico son los árboles binarios y los skiplists (equilibrados). Solo para discusión, abstraigámonos de los tipos de clave y valor y supongamos que accederemos a los valores a través de un void * .
Para un árbol binario tendría:
struct node {
void *key;
void *value;
struct node *left;
struct node *right;
}
Entonces, asumiendo que los punteros tienen todos los mismos s de tamaño, para almacenar n elementos, necesitaré 4 s bytes.
Las listas de listas son casi iguales, ya que el número promedio de punteros en un nodo es 2.
En una tabla hash tendría:
struct slot {
void *key;
void *value;
}
Por lo tanto, cada elemento solo requerirá 2 s bytes para ser almacenados. Si el factor de carga es del 50%, para almacenar n elementos, necesitaré los mismos 4 bytes de s como árboles.
No me parece tan malo: la tabla hash de cuco ocupará más o menos la misma cantidad de memoria que un árbol binario, pero me dará O (1) tiempo de acceso en lugar de O (log n).
Sin contar la complejidad de mantener el árbol equilibrado y la información adicional que se podría requerir para almacenar información de equilibrio en el nodo.
Otros esquemas de hashing podrían lograr un mejor factor de carga (por ejemplo, 75% u 80%) sin garantía en el peor momento de acceso (que podría ser O (n)).
Por cierto, has-cuckoo hashing y " hash de cuco con un alijo " parece ser capaz de aumentar el factor de carga manteniendo el tiempo de acceso constante.
El hash de cuco me parece una técnica valiosa y pensé que ya estaba explorada; Esa es la razón de mi pregunta.
No puedo hablar por el software, pero el hash cuckoo ciertamente se usa en hardware y se está volviendo muy popular. Los principales vendedores de equipos de redes han estado analizando el hash cuckoo y algunos ya lo utilizan. La atracción por el picadillo de cuco proviene del tiempo de búsqueda constante, por supuesto, pero también del tiempo de inserción casi constante.
Aunque la inserción puede ser teóricamente ilimitada, en la práctica puede limitarse a O (log n) del número de filas en la (s) tabla (s) y, cuando se mide, el tiempo de inserción es de aproximadamente 1.1 * d de accesos a la memoria en promedio. ¡Eso es solo un 10% más que el mínimo absoluto! El acceso a la memoria es a menudo el factor limitante en los equipos de red.
Las funciones hash independientes son imprescindibles y es difícil seleccionarlas correctamente. Buena suerte.
Después de un comentario de "onebyone", he implementado y probado un par de versiones de Cuckoo hashing para determinar el requisito de memoria real.
Después de algún experimento, la afirmación de que no tiene que volver a ver hasta que la tabla esté casi llena en un 50% parece ser cierta, especialmente si " stash " truco está implementado.
El problema es cuando amplía la tabla. El enfoque habitual es duplicar su tamaño, ¡pero esto hace que la nueva tabla se utilice solo en un 25%!
De hecho, suponga que la tabla hash tiene 16 ranuras, cuando inserte el octavo número de elemento, me quedaré sin buenas ranuras y tendré que volver a leer. ¡Lo duplicaré y ahora la mesa tiene 32 ranuras con solo 8 de ellas ocupadas, lo que representa un 75% de desperdicio!
Este es el precio a pagar para tener una "constante" tiempo de recuperación (en términos de límite superior para el número de acceso / comparación).
Sin embargo, he ideado un esquema diferente: a partir de una potencia de 2 mayor que 1, si la tabla tiene n ranuras yn es una potencia de dos, agregue n / 2 ranuras de otra manera agregue n / 3 ranuras:
+--+--+
| | | 2 slots
+--+--+
+--+--+--+
| | | | 3 slots
+--+--+--+
+--+--+--+--+
| | | | | 4 slots
+--+--+--+--+
+--+--+--+--+--+--+
| | | | | | | 6 slots
+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
| | | | | | | | | 8 slots
+--+--+--+--+--+--+--+--+
etc.
Junto con la suposición de que la confirmación solo se producirá cuando la tabla esté llena al 50%, esto lleva al hecho de que la tabla solo estará vacía al 66% (1 / 3rd) en lugar del 75% (1 / 4th) después de una reash (es decir, el peor de los casos).
También he descubierto (pero todavía tengo que revisar los cálculos) que al aumentar cada vez por sqrt (n), el espacio desperdiciado se acerca asintóticamente al 50%.
Por supuesto, el precio a pagar por menos consumo de memoria es el aumento de la cantidad de recursos que se necesitarán al final. Por desgracia, nada viene gratis.
Voy a investigar más si alguien está interesado.
