Vous recherchez une bonne implémentation de table de hachage en C

J’ai eu le même besoin et fait des recherches et j’ai fini par utiliser libcfu

C’est simple et lisible, donc si j’ai besoin de modifier, je peux le faire sans passer trop de temps à comprendre. C’est aussi de la licence BSD. Pas besoin de changer mes structures (pour intégrer un pointeur suivant)

J’ai dû rejeter les autres options pour les raisons suivantes (mes raisons personnelles, YMMV):

• sglib -> c’est un labyrinthe de macro et je ne me sentais pas à l’aise de déboguer / apporter des modifications sur une telle base de code en utilisant uniquement des macros
• cbfalconer -> beaucoup de redflags de licences, et le site était en panne et trop de discussions défavorables sur le web concernant le support / author; ne voulait pas prendre le risque
• google sparce-hash -> comme déjà dit, c’est pour C ++, pas pour C
• glib (gnome hash) – semblait très prometteur; mais je n’ai pas trouvé de moyen facile d’installer le kit de développement; J’ai juste besoin des routines / fichiers C – pas de l’environnement de développement complet
• Judy -> semble trop complexe pour une utilisation simple .. aussi n’était pas prêt à me déboguer si je devais rencontrer des problèmes
• npsml (mentionné ici) -> ne trouve pas la source
• strmap s’est avéré très simple et utile – il est trop simpliste que clé et valeur soient des chaînes; valeur étant chaîne semble trop ressortingctif (devrait accepter vide *)
• uthash -> semble bon (a été mentionné sur Wikipedia sur hashtable); trouvé qu’il faut struct pour être modifié – ne voulait pas le faire car performace n’est pas vraiment un souci pour mon utilisation – c’est plus de la vitesse de développement.

En résumé pour une utilisation très simple, strmap est bien; uthash si vous êtes concerné par l’utilisation de mémoire supplémentaire. Si la rapidité de développement ou la facilité d’utilisation sont les objectives principaux, libcfu gagne [notez que libcfu effectue en interne une allocation de mémoire pour maintenir les nœuds / hashtables]. Il est surprenant qu’il n’y ait pas beaucoup d’implémentations simples de hash C disponibles.

GLib est une excellente bibliothèque à utiliser comme base dans vos projets C. Ils ont des offres de structure de données décentes, y compris des tables de hachage: http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (lien mis à jour le 4/6/2011)

Pour les cordes, le Judy Array pourrait être bon.

Un tableau Judy est une structure de données associative complexe mais très rapide pour stocker et rechercher des valeurs à l’aide de clés entières ou de chaînes. Contrairement aux tableaux normaux, les tableaux de Judy peuvent être rares; c’est-à-dire qu’ils peuvent avoir de grandes plages d’indices non atsortingbués.

Voici une bibliothèque Judy en C.

Bibliothèque AC qui fournit une technologie de base à la pointe de la technologie qui implémente un tableau dynamic fragmenté. Les tableaux de Judy sont déclarés simplement avec un pointeur nul. Un tableau Judy ne consum de la mémoire que lorsqu’il est rempli, mais peut évoluer pour tirer parti de toute la mémoire disponible si vous le souhaitez.

Autres références,
Cette référence d’implémentation de hachage Wikipedia contient des liens C open source.
De plus, cmph – Une bibliothèque de hachage parfaite minimale en C , supporte plusieurs algorithmes.

Il y a quelques bonnes réponses ici:
Classe de conteneur / bibliothèque pour C

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

Les interfaces et implémentations C de Dave Hanson incluent une table de hachage fine et plusieurs autres structures de données bien conçues. Il y a aussi une belle interface de traitement de chaîne. Le livre est génial si vous pouvez vous le permettre, mais même si ce n’est pas le cas, j’ai trouvé ce logiciel très bien conçu, assez petit pour apprendre dans son intégralité et facile à réutiliser dans plusieurs projets différents.

Il y a longtemps que j’ai posé cette question … Je peux maintenant append ma propre bibliothèque de domaine public à la liste:

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

C Interfaces et implémentations discute des implémentations de tables de hachage en C. Le code source est disponible en ligne . (Ma copie du livre est au travail donc je ne peux pas être plus précis.)

La bibliothèque APR d’Apache a sa propre implémentation de hachage . Il est déjà porté sur tout ce qui est exécuté par Apache et la licence Apache est plutôt libérale.

khash.h de samtools / bwa / seqtk / klib

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

via http://www.biostars.org/p/10353/

Je ne l’ ai jamais utilisé mais Google Sparsehash peut fonctionner

Téléchargez tcl et utilisez leur fonction de hachage tcl éprouvée. C’est facile. L’API TCL est bien documentée.

Gperf – Générateur de fonctions de hachage parfait

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

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

Fonctions définies

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

Exemple d’utilisation

  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)); resortingeve_key = (struct some_key *) malloc(sizeof(struct some_key)); v = (struct some_value *) malloc(sizeof(struct some_value)); (You should initialise insert_key, resortingeve_key and v here) if (! hashtable_insert(h,insert_key,v) ) { exit(-1); } if (NULL == (found = hashtable_search(h,resortingeve_key) )) { printf("not found!"); } if (NULL == (found = hashtable_remove(h,resortingeve_key) )) { printf("Not found\n"); } hashtable_destroy(h,1); /* second arg indicates "free(value)" */ 

stl a map et hash_map (hash_map est seulement dans certaines implémentations) qui sont la clé de la valeur si vous pouvez utiliser C ++.

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