table de hachages

**Krustig** · 09/04/2007, 14h31

Bonjour,

Suis je obliger de créer ma propre class pour réaliser une table de hachage extern en C++ ?

La STL peut-être utile ?

Merci

**Laurent Gomila** · 09/04/2007, 14h37

En général les compilos / implémentations de la STL proposent leur propre extension pour les tables de hachage. On en a parlé y a pas si longtemps.

**alskaar** · 09/04/2007, 14h45

un petit lien

http://www.sgi.com/tech/stl/hash_map.html

**Krustig** · 09/04/2007, 15h09

merci pour le lien !

Cependant si je veux une table de hachage externe, je suis un peu bloquée.

ex:
si je dois indexer 2000 clients et que je fais une table ayant une taille utile de 200, j'aurais forcément des colisions que je devrais gérer à l'aide d'une liste chainée pour mon cas.

Une idée ?

Merci

**alskaar** · 09/04/2007, 19h42

a la lecture de la doc (cf lien) il y a des methodes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
size_type bucket_count() const
void resize(size_type n)

qui permettent de connaitre et modifier la taille de ta table de hash.
sinon la hash_table de la stl doit aussi avoir un system de liste ou autre conteneur pour tes pb de colisions mais ca marche sans soucis

pour rechercher un element dans une table de hash il faut la fonction de hash
et l'operateur= apres tous les mecanismes sont implementés

j'espere que ca repond a ton besoin !

**Krustig** · 09/04/2007, 19h47

merci !
Je vais tenter de faire fonctionner "le monstre" !
Sinon pour la fonction de hachage, c'est à moi de la definir ou la STL en a aussi une ? (obtenir une clé en fonction d'un nom et un prenom par ex)
J'ai regardé mais j'ai rien vue à ce sujet !

merci merci

**mchk0123** · 09/04/2007, 21h16

Autre chose que tu dois prendre en compte.

Il existe 2 types de "collisions". Celle qui est accidentelle sur valeur de hachage : par exemple sur quelques cas, malheureusement, la fonction de hachage donne 2 clefs identiques ou parce que la table est trop petite. Et la collision certaine sur clef, dans le cas par exemple ou tu as de homonymes dans ta DB.

Dans ce cas là tu peux aussi regarder le conteneur multi_hashmap qui peut être plus adaptée.