Table de hachage - ansi c

Soyez le premier à donner votre avis sur cette source.

Vue 19 487 fois - Téléchargée 2 007 fois

Télécharger le projet
Commenter

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 / Exemple : 


/*#### 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.
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Signaler
Bel0
Messages postés
71
Date d'inscription
mercredi 14 avril 2004
Statut
Membre
Dernière intervention
14 septembre 2007
 -
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
gengiskhan1985
Messages postés
12
Date d'inscription
jeudi 22 avril 2004
Statut
Membre
Dernière intervention
1 mai 2007
 -
@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
Bel0
Messages postés
71
Date d'inscription
mercredi 14 avril 2004
Statut
Membre
Dernière intervention
14 septembre 2007
 -
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
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.