examples - hash table in c example
Hash de cuco en C (8)
El hash de cuco está relativamente fuera de uso fuera de la academia (aparte de los cachés de hardware, que a veces toman prestado ideas de, pero realmente no implementan completamente). Requiere una tabla hash muy escasa para obtener un buen tiempo en las inserciones; realmente necesita tener el 51% de su tabla vacía para un buen rendimiento. Entonces, o es rápido y ocupa mucho espacio, o es lento y usa el espacio de manera eficiente, nunca ambos. Otros algoritmos son eficientes tanto en tiempo como en espacio, aunque son peores que cuckoo cuando solo se tiene en cuenta el tiempo o el espacio.
Aquí hay un generador de código para tablas de hash cuco . Verifique la licencia del generador para verificar que la salida no sea GPL. Debería ser, pero verifique de todos modos.
-Adán
¿Alguien tiene una implementación de hash Cuckoo en C? Si hubiera una versión Open Source, no GPL sería perfecto.
Desde que Adam lo mencionó en su comentario, ¿alguien sabe por qué no se usa mucho? ¿Es solo una cuestión de implementación o las buenas propiedades teóricas no se materializan en la práctica?
El idioma IO tiene uno, en PHash.c. Puede encontrar el código para IO en Github. IO tiene licencia BSD.
Veo el punto sobre la utilización, pero este fue mi razonamiento para probar este esquema de hashing en particular. Por favor, acuérdate de saber si me perdí algo.
Que yo sepa, las posibles alternativas a las tablas hash para crear un diccionario dinámico son árboles binarios (balanceados) y listas de skiplists. Solo para discusión, vamos a abstraernos de los tipos clave y de 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, suponiendo que los punteros tienen todos el mismo tamaño s , para almacenar n elementos necesitaré 4 s bytes.
Las listas salteadas son casi las mismas que el número promedio de punteros en un nodo es 2.
En una tabla hash tendria:
struct slot {
void *key;
void *value;
}
Por lo tanto, cada elemento solo requerirá 2 s bytes para almacenarse. Si el factor de carga es del 50%, para almacenar n elementos, necesitaré los mismos 4 bytes que los árboles.
No me parece demasiado 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 podría requerirse para almacenar información de equilibrio en el nodo.
Otros esquemas hashing podrían lograr un mejor factor de carga (digamos 75% u 80%) sin garantía en el peor momento de acceso (que incluso podría ser O (n)).
Por cierto, el hash cuckoo d-ary y el " hash cuckoo con un alijo " parecen ser capaces de aumentar el factor de carga sin dejar de mantener el tiempo de acceso constante.
El hashing del cuco me parece una técnica valiosa y pensé que ya se había explorado; ese es el motivo de mi pregunta.
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 ha sido generalizado para hashing de cuco dary, en el que cada tecla tiene d posibles lugares para anidar, a diferencia de 2 lugares en la versión simple.
El factor de carga aceptable aumenta rápidamente a medida que aumenta d . Solo por d = 3, ya puede usar alrededor de una tabla completa al 75%. El inconveniente es que necesita d funciones hash independientes. Soy fanático de las funciones hash de Bob Jenkins para este propósito (vea http://burtleburtle.net/bob/c/lookup3.c ), que puede encontrarle útil en una implementación de hash de cuco.
No puedo hablar de software, pero el hashing de cuco ciertamente se usa en hardware y se está volviendo muy popular. Los principales proveedores de equipos de red han estado buscando el hash del cuco y algunos ya lo usan. La atracción por el hashing del cuco proviene del tiempo constante de búsqueda, 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 memoria en promedio. ¡Eso es solo un 10% más que el mínimo absoluto! El acceso a memoria es a menudo el factor limitante en los equipos de red.
Las funciones de hash independientes son obligatorias y seleccionarlas correctamente es difícil. Buena suerte.
A raíz de un comentario de "onebyone", he implementado y probado un par de versiones de hash Cuckoo para determinar el requisito de memoria real.
Después de algún experimento, la afirmación de que no tiene que recargar hasta que la mesa esté casi llena en un 50% parece ser cierta, especialmente si el truco "oculto" está implícito.
El problema es cuando agrandas la mesa. El enfoque habitual es duplicar su tamaño, pero esto lleva a que la nueva tabla solo se utilice en un 25%.
De hecho, suponga que la tabla hash tiene 16 espacios, cuando inserte el 8º elemento, me quedaré sin tragamonedas y tendré que volver a ajustar. Lo doblaré y ahora la mesa tiene 32 máquinas tragamonedas con solo 8 de ellas ocupadas, ¡lo cual es un 75% de desperdicio!
Este es el precio a pagar para tener un tiempo de recuperación "constante" (en términos de límite superior para el número de acceso / comparación).
Sin embargo, he ideado un esquema diferente: comenzando con una potencia de 2 mayor que 1, si la tabla tiene n ranuras yn es una potencia de dos, agregue n / 2 ranuras de otro modo, agregue n / 3 ranuras:
+--+--+
| | | 2 slots
+--+--+
+--+--+--+
| | | | 3 slots
+--+--+--+
+--+--+--+--+
| | | | | 4 slots
+--+--+--+--+
+--+--+--+--+--+--+
| | | | | | | 6 slots
+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
| | | | | | | | | 8 slots
+--+--+--+--+--+--+--+--+
etc.
Junto con la suposición de que el reabastecimiento solo ocurrirá cuando la tabla esté 50% llena, esto lleva al hecho de que la mesa solo estará 66% vacía (1/3) en vez de 75% vacía (1/4) después de un recambio ( es decir, el peor caso).
También me he dado cuenta (pero aún tengo que verificar los cálculos matemáticos) de que al aumentar cada vez por sqrt (n), el espacio desperdiciado se acerca asintóticamente al 50%.
Por supuesto, el precio a pagar por el menor consumo de memoria es el aumento de la cantidad de reposición que se necesitará al final. Por desgracia, nada es gratis.
Voy a investigar más a fondo si alguien está interesado.
A pesar de que es una vieja pregunta, alguien todavía podría estar interesado :)
Este documento describe la implementación de un hash d-ary cuckoo paralelo en GPU (CUDA / OpenCL). Se describe muy bien y su implementación en base a la descripción es bastante fácil. Por lo general, vale la pena leerlo, si le interesa este tema. (Sin embargo, necesitará un inicio de sesión de ACM).