Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

TABLE DE HACHAGE - ANSI C


Information sur la source

Description

Ce code est une implémentation des tables de hachage en C ANSI.

Les types des éléments référencés peuvent être modifiés simplement. Il est de plus possible d’utiliser le code non pas pour faire un tableau associatif (clef => valeur) mais pour traiter des ensembles d’élément (simplement en ajoutant un #define HASH_TABLE_NOENTRY).

Un itérateur est disponible pour parcourir les éléments.

Dernier point : il y a une documentation faite avec Doxygen.

 

Source

  • /*#### Je met juste les principaux prototypes, pour donner une idée de la source. ####*/
  • /* Creation – destruction */
  • Hash_table hash_table_create (unsigned int(*hash)(const Key_t e1), int(*compare)(const Key_t e1, const Key_t e2));
  • int hash_table_free (Hash_table tab);
  • /* Utilisation */
  • char hash_table_get (Hash_table tab, Key_t k, Value_t *v);
  • char hash_table_replace (Hash_table tab, Key_t k, Value_t v);
  • char hash_table_add (Hash_table tab, Key_t k, Value_t v);
  • char hash_table_remove (Hash_table tab, Key_t k, Value_t *v);
  • /* Utilisation si HASH_TABLE_NOENTRY définit */
  • char hash_table_get (Hash_table tab, Key_t k);
  • char hash_table_add (Hash_table tab, Key_t k);
  • char hash_table_remove (Hash_table tab, Key_t k);
  • /* nombre d’éléments */
  • int hash_table_count (Hash_table tab);
  • /******* iterateur à la JAVA *******/
  • Hash_table_it it = hash_table_it_create( tab );
  • while( hash_table_it_hasNext( it ) ) {
  • hash_table_entry *elt = hash_table_it_next( it );
  • traiter( elt ); // utilisation
  • }
  • hash_table_it_free( it ); // désallocation
/*#### Je met juste les principaux prototypes, pour donner une idée de la source. ####*/

/* Creation – destruction */
Hash_table 	hash_table_create (unsigned int(*hash)(const Key_t e1), int(*compare)(const Key_t e1, const Key_t e2));
int 	hash_table_free (Hash_table tab);

/* Utilisation */
char 	hash_table_get (Hash_table tab, Key_t k, Value_t *v);
char 	hash_table_replace (Hash_table tab, Key_t k, Value_t v);
char 	hash_table_add (Hash_table tab, Key_t k, Value_t v);
char 	hash_table_remove (Hash_table tab, Key_t k, Value_t *v);

/* Utilisation si  HASH_TABLE_NOENTRY définit */
char 	hash_table_get (Hash_table tab, Key_t k);
char 	hash_table_add (Hash_table tab, Key_t k);
char 	hash_table_remove (Hash_table tab, Key_t k);

/* nombre d’éléments */
int 	hash_table_count (Hash_table tab);


/******* iterateur à la JAVA *******/
Hash_table_it it = hash_table_it_create( tab );
while( hash_table_it_hasNext( it ) ) {
     hash_table_entry *elt = hash_table_it_next( it );
     traiter( elt );               // utilisation
}
hash_table_it_free( it );          // désallocation

Conclusion

Je n’ai pas eu l’impression qu’il existe beaucoup de sources de structures de données en C ANSI sur le net, ce qui m’a poussé à en faire une (que j’espère) correcte.
 

Fichier Zip

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip

Commentaires et avis

signaler à un administrateur
Commentaire de Bel0 le 01/05/2007 20:31:54

2 petites remarques:
1) J'ai vu dans ton code que tu vérifiais que ton nombre de free était égale au nombre de malloc. C'est un début pour trouver des fuites mémoires. Toutefois, si tu travailles sous linux, il vaut mieux utiliser un outil beaucoup plus affûté, j'ai nommé *Valgrind* :)
2) Pour la réallocation de la hastable, tu devrais fournir un paramètre qui permet de définir à partir de quel moment, on doit réallouer. Je m'explique. Les fonctions de hachage n'étant pas parfait, il se peut que certains cases de ton tableau contiennent des collisions (plusieurs couples (clé,valeur)) alors que d'autre sont vides. C'est dû au fait que la fonction de hachage ne répartit pas les clés de manières uniformes sur l'ensemble du tableau. Il est donc courant de définir un taux d'occupation du tableau (50%-80%) au delà duquel on force la réallocation de la hashtable.

Sinon c'est plutot propre comme implémentation. J'aime bien ce style "pseudo orienté object" en C :)

signaler à un administrateur
Commentaire de gengiskhan1985 le 01/05/2007 21:53:29

@BelO :
1) Je suis sous Windows - mais si jamais je travaille sous linux, je penserai à ta remarque ;).
2) Pour moi ce que tu mentionne correspond à mes macros HASH_TABLE_EXTEND_TEST et HASH_TABLE_SHRINK_TEST définies dans hash_types.h
#define HASH_TABLE_EXTEND_TEST(TABSIZE, ELTCOUNT)   (((ELTCOUNT)*8)/10 >= TABSIZE)
correspond à une extention de la table à partir de 80% d'occupation (<nombre d'élement>*8/10 >= <taille du tableau>).
Sauf si tu le voulais paramétrable pendant l'execution.

Je viens tout droit de JAVA, ca doit être pour ca que c'est un peu proche de l'orienté objet ^^

signaler à un administrateur
Commentaire de Bel0 le 02/05/2007 18:33:38

Je pensais par exemple à un paramètre à la création de la hashtable.

PS: on ne voit presque pas tes origines orientées objet :P

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

creer une table de hachage avec des elements d'un fichier texte [ par nedri ] bonjour!j'ai un projet a faire en C mais je ne suis pas très forte.j'ai realisé un traitement d'un fichier source en C d'ou je tire tous les identific gros fichiers [ par gegeambro ] Bonjours à tous,Je suis actuellement étudiant à la fac en licence informatique. Mon problème viens sur la gestion des gros fichiers ( par exemple 200 Table de hachage externe [ par nrgumn ] Bonjour,J'ai un programme &#224; coder en C, mais je bolque au niveau de la table de hachage.J'ai un fichier qui contient des mots. Chaque mot dois &# création d'une table de hachage dynamique [ par makdand ] bonjour tout le monde,mon problème consiste dans la création d'une table de hachage dynamique à partir des clés de hachage des chaines de caractères l Table de hachage externe [ par eraus ] Bonjour,Je m'en remet à vous, car depuis quelques semaine je but sur ce même problème, qui pourra parraitre bête à certains d'entre vous. Je dois réal Arbre de hachage [ par cyrina84 ] Bonsoir à tous les developpeurs ici présents, j'ai probleme et je compte sur vous pour me trouver une solution. Je veux crere une table de hachage( ma table de hachage et liste chainée [ par cyrina84 ] bonjour à tous, je voudrais bien  savoir  comment créer une application d'apprentissage automatique.on m'a demandé de réaliser une application qui per table de hachage chainée [ par cyrina84 ] Bonjour à tous, je possede d'unt table de hachage chainée (chaque element de la table est relié à une liste chainée), donc j'aimerais quelqun qui peut table de hachage [ par cyrina84 ] bonjour à tous, jai une table de hachage chainée: chaque element de la table est lié à une liste chainé.je voudrais savoir pour supprimer un element d remplir une table de hachage [ par cyrina84 ] Bonjourj'ai un probleme :j'ai une table de hachage  voial sa structure :typedef struct L2{     int freq;     mots *m;     Coordonnees *c;      struct


Nos sponsors

Sondage...

CalendriCode

Juillet 2009
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Téléchargements

Logiciels à télécharger sur le même thème :

Comparez les prix Nouvelle version


HTC Magic

Entre 429€ et 429€


Photothèque Nouveau !



Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés
Temps d'éxécution de la page : 0,655 sec

Google Coop CodeS-SourceS Google Coop CodeS-SourceS


Certaines images présentes sur le site (notament certains avatars) sont issues des collections IconShock, donc si vous souhaitez utiliser ces icons vous devez les acheter, ne les copiez pas et ne utilisez pas dans vos sites et applications sans les avoir commandé.