Taille de hash optimale

[Yann]

Je vais mettre à jour une des règles énoncées dans un précédent billet pour coller aux résultats expérimentaux.
Après avoir visualisé l'évolution du nombre de comparaisons en fonction de la profondeur de recherche, j'en arrive à la conclusion qu'une limite au nombre de collisions est atteinte non en fonction de la taille de la fenêtre, mais plutôt en fonction du nombre de combinaisons différentes, qui est surprenamment stable, dépendant essentiellement de la taille de la combinaison (4 caractères dans notre cas).
De fait, lorsqu'on augmente la profondeur de recherche, on n'augmente que de très peu la taille optimale de la table de hash.
Il en va de même lorsqu'on la réduit : on constate sur ce graphique que, même en dépassant la taille de la fenêtre de recherche (12 bits), on continue a diminuer significativement le nombre de collisions, jusque vers 14 bits, après quoi les gains deviennent faibles.



On en déduit un résultat important :
- la taille "optimale" de la table de hash est relativement stable, quelle que soit la profondeur de recherche (ok, elle augmente légèrement, mais de très peu).
- De plus, cette taille est à peu près la même pour tous les fichiers, qui convergent à peu près au même rythme (mais vers des seuils différents).

Voilà qui va nous servir pour l'étape suivante ...