Recherche d'une bonne implémentation de table de hachage en C

Question

Je suis principalement intéressé par les clés à cordes. Quelqu'un peut-il m'indiquer une bibliothèque ?

Answer 1

J'avais le même besoin et j'ai fait quelques recherches. libcfu

Il est simple et lisible, donc si j'ai besoin de le modifier, je peux le faire sans passer trop de temps à le comprendre. Il est également sous licence BSD. Pas besoin de changer mes structs (pour embarquer disons un pointeur suivant)

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

• sglib --> c'est un labyrinthe de macros et je n'étais pas à l'aise pour déboguer/réaliser des changements sur une telle base de code en utilisant uniquement des macros.
• cbfalconer --> beaucoup de drapeaux rouges de licence, et le site était en panne et trop de discussions défavorables sur le web à propos du support/auteur ; je n'ai pas voulu prendre le risque.
• google sparce-hash --> comme déjà dit, c'est pour C++, pas 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'avais juste besoin des routines/fichiers C -- pas de l'environnement de développement complet
• Judy --> semble trop complexe pour une utilisation simple. Je n'étais pas non plus prêt à déboguer moi-même si je devais rencontrer des problèmes.
• npsml (mentionné ici) --> ne peut pas trouver la source
• strmap trouvé très simple et utile -- c'est juste trop simpliste que la clé et la valeur doivent être des chaînes de caractères ; la valeur étant une chaîne de caractères semble trop restrictive (devrait accepter void *)
• uthash --> semble bon (a été mentionné sur wikipedia sur hashtable) ; a trouvé qu'il exige que struct soit modifié -- ne voulait pas faire cela comme la performance n'est pas vraiment une préoccupation pour mon utilisation -- c'est plus de la vélocité de développement.

En résumé, pour une utilisation très simple, strmap est bon ; uthash si vous êtes concerné par l'utilisation de mémoire supplémentaire. Si la vitesse de développement ou la facilité d'utilisation est l'objectif principal, libcfu l'emporte [notez que libcfu effectue en interne l'allocation de mémoire pour maintenir les noeuds/tables de hachage]. Il est surprenant qu'il n'y ait pas beaucoup d'implémentations simples de hachage en C disponibles.

Answer 2

GLib est une excellente bibliothèque à utiliser comme base dans vos projets C. Elle propose quelques structures de données décentes, dont les tables de hachage : http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html (lien mis à jour le 4/6/2011)

Answer 3

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

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

Voici un Bibliothèque Judy sur C .

Une bibliothèque C qui fournit une technologie de base de pointe qui implémente un tableau dynamique épars. Les tableaux Judy sont déclarés simplement avec un pointeur nul. Un tableau Judy ne consomme de la mémoire que lorsqu'il est rempli, mais il peut croître pour profiter de toute la mémoire disponible si on le souhaite.

---

Autres références,
Ce site Référence de l'implémentation du hachage sur Wikipédia a quelques C des liens vers des sources ouvertes.
Aussi, cmph -- Une bibliothèque minimale de hachage parfait en C supporte plusieurs algorithmes.

Answer 4

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

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

Answer 5

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