Discussion :

[scorbo]

Salut,

j'ai recherché sur les différents forums pour trouver une fonction de hachage qui me conviennent et je n'en ai pas trouvée !

Mon problème est que j'ai un dictionnaire de 211 000 mots et que lorsque je rempli ma table de hachage à l'aide de ma fonction, j'ai un taux de remplissage de 63% seulement alors qu'il faudrait 80% !

J'ai mis en place la fonction de Horner:

Code :

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

1
2
3
4
 
k=0;
for(i=0; i<strlen(mot); i++)
    k = (k*31 + mot[i])%NB_CASES

en plus, si je ne me trompe pas, c'est également la fonction utilisée en java.



je sais qu'il existe des livres qui traitent des problèmes de hachage tels que Horowitz ou encore Froidevaux, mais j'ai pas trop envi de les acheté juste pour çà !

Alors si quelqu'un à une idée, elle sera la bien venue.

PS: les collisions sont gérées par une liste chaînée (çà fait donc baisser le taux)

REPS: NB_LISTES est fixée à 211 000 (le nombre de mots)
l'idéal est d'avoir également 1 à 3 mots par cases

[Vincent PETIT]

Essai d'augmenter dans

Code :

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

k = (k*31 + mot[i])%NB_CASES

La constante 31

Code :

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

k = (k*256 + mot[i])%NB_CASES

Cela n'aura peut être pas beaucoup d'impacte mais sait on jamais ?

Sinon je pense que tu va devoir augmenter la variable NBR_CASES, cela va te coûter en mémoire mais la dispertion des mots va être plus grande.

un sujet avait était posté ici mais ne traitant pas de la dispertion.
http://www.developpez.net/forums/viewtopic.php?t=135628

[scorbo]

Effectivement, çà n'a pas beaucoup d'impact.
De plus le fait d'augmenter le nb de cases, diminue le taux de remplissage mais augmente le nb de collisions.

je peux toujours diminue le nb de cases, mais après, il va falloir que je le justifie ! Et à part le trouver à taton !

[Vincent PETIT]

De plus le fait d'augmenter le nb de cases, diminue le taux de remplissage mais augmente le nb de collisions.

C'est impossible, en augmentant le nombre de case, on diminue les collisions et en diminuant le nombre de case on augmente le nombre de collisions car les mots ont les même clefs (index).

Tu peux faire un essai simple: déclare un petit tableau, 5 par exemples (donc avec peu de cases) et là le nombre de collision va être incroyable, les listes chaînées vont augmenter car il y aura plein de mots qui aurons la même (clef) index, donc collisions.

@ bientôt
Vincent

[scorbo]

Effectivement, il y a une erreur dans ce que j'ai écrit.

Le fait d'augmenter le nb de cases, diminue le taux de remplissage (à moins que je le calcul mal !), bien qu'il baisse le nombre de collisions.

le calcul du taux est: (nb_cases - nb_cases_vides) / nb_cases

[Vincent PETIT]

Oui en effet tu as tout a fait raison, cela baisse le taux de remplissage mais hélas on a affaire à un compromis.

Car comme tu le dis, le seul moyen d'éviter des collisions c'est d'augmenter le nombre de case mais cela baisse le taux de remplissage.

• - Taux de remplissage optimum => baisser le nombre de case, les listes chaînées s'allongent ce qui cause un temps d'accès à la table plus long
  
  - Taux de collision minimum => augmenter le nombre de case, petites voir aucune listes chaînées mais coûte en emplacement mémoire, et le taux de remplissage est moindre (grande table pour pas grand chose)

Par contre si tu regardes mon exemple (le lien du poste 2e poste) on s'appeçoit que les allocations dynamiques des listes chaînées n'ont lieu que si elles contiennent quelques choses. En faite je ne déclare qu'un tableau de pointeurs de structure et non pas un tableau de structure, qui auraient pris beaucoup plus de place.

Bref, si tu as procédé comme je l'ai fait alors ta table a un taux optimum car les endroits vide sont initialisé à NULL.