Buscando una buena implementación de tabla hash en C

Question

Estoy interesado principalmente en claves de cadena. ¿Puede alguien señalarme hacia una biblioteca?

Answer 1

Para cadenas, el Judy Array podría ser bueno.

Una matriz de Judy es una estructura de datos de matriz asociativa compleja pero muy rápida para almacenar y buscar valores utilizando enteros o claves de cadena. A diferencia de las matrices normales, las matrices Judy pueden ser dispersas; es decir, pueden tener grandes rangos de índices no asignados.

Aquí hay un Judy library in C.

Una biblioteca de C que proporciona una tecnología de núcleo de última generación que implementa una matriz dinámica dispersa. Las matrices Judy se declaran simplemente con un puntero nulo. Una matriz de Judy consume memoria solo cuando está poblada, pero puede crecer para aprovechar toda la memoria disponible si así lo desea.

---

Otras referencias,
Este Wikipedia hash implementation reference tiene algunas C enlaces de código abierto.
Además, cmph - Una biblioteca mínima de Perfect Hashing en C, admite varios algoritmos.

Answer 2

nunca utilizamos pero Google Sparsehash pueden trabajar

Answer 3

http://www.cl.cam.ac.uk/~cwc22/hashtable/

funciones definidas

* create_hashtable 
* hashtable_insert 
* hashtable_search 
* hashtable_remove 
* hashtable_count 
* hashtable_destroy 

Ejemplo de uso

struct hashtable *h; 
    struct some_key *k; 
    struct some_value *v; 

    static unsigned int   hash_from_key_fn(void *k); 
    static int     keys_equal_fn (void *key1, void *key2); 

    h = create_hashtable(16, hash_from_key_fn, keys_equal_fn); 

    insert_key = (struct some_key *) malloc(sizeof(struct some_key)); 
    retrieve_key = (struct some_key *) malloc(sizeof(struct some_key)); 

    v = (struct some_value *) malloc(sizeof(struct some_value)); 

    (You should initialise insert_key, retrieve_key and v here) 

    if (! hashtable_insert(h,insert_key,v)) 
    {  exit(-1);    } 

    if (NULL == (found = hashtable_search(h,retrieve_key))) 
    { printf("not found!");     } 

    if (NULL == (found = hashtable_remove(h,retrieve_key))) 
    { printf("Not found\n");     } 

    hashtable_destroy(h,1); /* second arg indicates "free(value)" */ 

Answer 4

Hay algunas buenas respuestas aquí:
Container Class/Library for C

http://sglib.sourceforge.net.
http://cbfalconer.home.att.net/download/

Answer 5

Descargar tcl y utilizar su función de hash tcl a prueba de tiempo. Es fácil. La API de TCL está bien documentada.

Answer 6

C Interfaces and Implementations discute las implementaciones de tablas hash en C. El código fuente es available online. (Mi copia del libro está en el trabajo, así que no puedo ser más específico.)

Answer 7

GLib es una gran biblioteca para utilizar como base en sus proyectos C. Tienen algunas ofertas decentes estructura de datos, incluyendo las tablas hash: http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (enlace actualiza 4/6/2011)

Answer 8

gperf - Perfecto generador de funciones Hash

http://www.ibm.com/developerworks/linux/library/l-gperf.html

Answer 9

Dave Hanson C Interfaces and Implementations incluye una tabla de dispersión fina y varios otras estructuras de datos bien diseñadas.También hay una bonita interfaz de procesamiento de cadenas. El libro es excelente si puedes pagarlo, pero incluso si no, he encontrado que este software está muy bien diseñado, lo suficientemente pequeño como para aprenderlo en su totalidad, y fácil de reutilizar en varios proyectos diferentes.

Answer 10

stl tiene un mapa y hash_map (hash_map solo está en algunas implementaciones) que son clave de valor si puede usar C++.

http://www.cplusplus.com/reference/stl/map/

Answer 11

ha pasado mucho tiempo desde que hice esta pregunta ... ahora puedo añadir mi propia biblioteca de dominio público a la lista:

http://sourceforge.net/projects/npsml/

Answer 12

que tenían la misma necesidad y Hice algunas investigaciones y terminé usando libcfu

Es simple y legible, así que si tengo que modificarlo, puedo hacerlo sin perder demasiado tiempo para entenderlo. También es de licencia BSD. No hay necesidad de cambiar mis estructuras (a incrustar decir un siguiente puntero)

tuve que rechazar las otras opciones por las siguientes razones (mis razones personales, tu caso es distinto):

• sglib -> es un laberinto macro y no me sentía cómodo depurando/haciendo cambios en en una base de código con macros
• cbfalconer -> gran cantidad de licencias de banderas rojas, y el sitio estaba abajo y demasiadas discusiones desfavorables en la web sobre soporte/autor; no quería correr el riesgo
• google sparce-hash -> como se dijo anteriormente, es para C++, no C
• glib (gnome hash) -> parecía muy prometedor; pero no pude encontrar ninguna manera fácil de instalar el kit de desarrollo; Solo necesitaba las rutinas/archivos C - no el entorno de desarrollo completo
• Judy -> parece demasiado complejo para un uso simple ... tampoco estaba listo para depurarme si tuviera que encontrarme con algún problema
• npsml (mencionado aquí) -> no se puede encontrar la fuente
• strmap encontrado muy simple y útil - es demasiado simplista que tanto la clave como el valor deben ser cadenas; valor siendo cadena parece demasiado restrictivo (debe aceptar nulo *)
• uthash -> parece bueno (ha sido mencionado en wikipedia en hashtable); encontré que requiere que struct se modifique - no quería hacer eso, ya que el rendimiento no es realmente una preocupación para mi uso, es más velocidad de desarrollo.

En resumen, para un uso muy simple strmap es bueno; uthash si le preocupa el uso de memoria adicional. Si solo la velocidad de desarrollo o la facilidad de uso es el objetivo principal, libcfu gana [note libcfu internamente hace la asignación de memoria para mantener los nodos/hashtables]. Es sorprendente que no haya muchas implementaciones simples de hash C disponibles.

Answer 13

La biblioteca APR de Apache tiene su propia hash-implementation. Ya está portado a todo lo que Apache ejecuta y el Apache license es bastante liberal también.

Answer 14

khash.h de samtools/BWA/seqtk/klib

enrollamiento https://raw.github.com/attractivechaos/klib/master/khash.h

través http://www.biostars.org/p/10353/