Quel est l'intérêt d'avoir une table de hachage dont la taille est une puissance de 2 ?
Cela accélère énormément le calcul final, celui que vous trouverez à la fin de chaque fonction. Le calcul d'un modulo est parmi les instructions les plus lentes à réaliser pour un microprocesseur. Quand le dénominateur d'un modulo est une puissance de 2, le calcul est sensiblement accéléré (on passe de 70 cycles processeur à 4 ou 6 cycles). Certes, la table est légèrement moins homogène, donc la recherche linéaire est un peu plus longue en moyenne (en pratique la différence d'homogénéité est très très faible, cf le comparatif du post ./216). Mais le temps gagné lors du calcul compense le temps perdu dans la recherche linéaire.Cela est particulièrement vrai quand le nombre de collisions est raisonnable, par exemple quand 10.000 chaînes ou moins sont réparties sur une table de taille 1024. D'une manière générale, il semblerait que plus la table de hachage est grande, plus on a intérêt à lui donner une taille puissance de 2. En effet, le nombre moyen de collisions diminuant, la recherche linéaire est plus rapide et le léger défaut d'homogénéité est moins sensible, donc le temps gagné dans le calcul du modulo est plus flagrant.
Dites moi si je raconte de la merde
