resolucion - utilizacion de tablas hash
Estoy principalmente interesado en las llaves de cadena. ¿Puede alguien señalarme hacia una biblioteca?
Descargue tcl y use su función de hash tcl comprobada en el tiempo. Es fácil. La API de TCL está bien documentada.
GLib es una gran biblioteca para utilizar como base en tus proyectos C. Tienen algunas ofertas de estructura de datos decentes que incluyen Hash Tables: http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (enlace actualizado 4/6/2011)
Gperf - Perfect Hash Function Generator
http://www.ibm.com/developerworks/linux/library/l-gperf.html
Ha pasado mucho tiempo desde que hice esta pregunta ... Ahora puedo agregar mi propia biblioteca de dominio público a la lista:
La biblioteca APR de Apache tiene su propia hash-implementation . Ya está portado a todo lo que Apache ejecuta y la licencia de Apache también es bastante liberal.
Las interfaces e implementaciones C de Dave Hanson incluyen una tabla de hash fina y varias 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.
Nunca lo usaste , pero Google Sparsehash puede funcionar
Para cuerdas, 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 usando 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 una biblioteca de Judy en C.
Biblioteca de CA que proporciona una tecnología básica de vanguardia 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,
Esta referencia de implementación hash de Wikipedia tiene algunos enlaces C código abierto.
Además, cmph - Una biblioteca mínima perfecta Hashing en C , admite varios algoritmos.
Tuve la misma necesidad e hice una investigación 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 es necesario cambiar mis estructuras (para insertar, decir el siguiente puntero)
Tuve que rechazar las otras opciones por los siguientes motivos (mis razones personales, YMMV):
- sglib -> es un laberinto macro y no me sentía cómodo depurando / haciendo cambios en una base de código con macros
- ccfalconer -> gran cantidad de licencias de banderas rojas, y el sitio estaba caído y demasiadas discusiones desfavorables en la web sobre soporte / autor; no quería tomar el riesgo
- google sparce-hash -> como ya se dijo, es para C ++, no para 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 tenía que encontrarme con algún problema
- npsml (mencionado aquí) -> no puede encontrar la fuente
- strmap encontró muy simple y útil; es demasiado simplista que tanto la clave como el valor deben ser cadenas; el valor de ser cadena parece demasiado restrictivo (debe aceptar el vacío *)
- 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.
khash.h de samtools / bwa / seqtk / klib
curl https://raw.github.com/attractivechaos/klib/master/khash.h
a través de http://www.biostars.org/p/10353/
stl tiene mapa y hash_map (hash_map solo está en algunas implementaciones) que son clave para valorar si puede usar C ++.
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)" */
C Interfaces e implementaciones discute las implementaciones de la tabla hash en C. El código fuente está disponible en línea . (Mi copia del libro está en el trabajo, así que no puedo ser más específico).