Y'a un pb. Tu as fait bosser mon code sur une table de quelle taille ? Tu as pris en compte les cases vides ?

tu trouve plus interessant "nbelement/nbcase" ? (ce qui est calculé par thibaut pour la moyenne ? c'est meme pas lié a la fonction de hashage...)

Ouai mais je pense que Pollux et moi on est d'accord sur le fait que la meilleure façon de résoudre la question posée par le topic et dans le contexte du topic, c'est de calculer l'écart type (qu'on a indirectement par la variance, qui permet des comparaisons plus précises étant donné qu'on bosse sur des entiers).
Voici mon raisonnement :

But : On cherche à rendre minimiser le nombre moyen d'itération lors de la recherche linéaire qui fait suite au hachage.

Si on a un algo qui donne un grand écart type, ça signifie que certaines listes chaînées pointées par la table de hachage sont plus longues que d'autres.
Autrement dit, ces listes concentrent un plus grand nombre de mots, et les petites listes concentrent peu de mots.
Encore dit autrement, la probabilité pour qu'un mot choisi au hasard soit situé dans une longue liste est plus grande que la probabilité pour qu'un mot se trouve dans une liste courte.

Avec un algo de hachage qui construit une table peu homogène, le nombre moyen d'itérations pour trouver un mot sera plus élevé qu'avec un algo qui donne une table parfaitement homogène.
Au contraire, avec une table parfaitement homogène, toutes les cases ont la même probabilité de pointer sur la liste contenant le mot recherché. On doit donc chercher à minimiser le nombre moyen d'itérations pour trouver un mot dans tout ce bordel.


Voilà pourquoi mon critère est unique : l'écart type (qui prend en compte les cases vides, puisque celles-ci impliquent le fait que d'autres cases sont trop pleines). La table idéale, donc l'algo idéal, produit un écart type de zéro.