Le TP précédent
avait pour but l'établissement d'un dictionnaire,
à l'aide d'un arbre qui représente le dictionnaire par
une structure arborescente.
On essaiera ici de réaliser un programme qui aura les
mêmes fonctionnalités, avec une table de hachage.
Il s'agit de trouver une fonction injective de
l'ensemble à indexer (le dictionnaire) vers un intervalle
[0, N].
Puisque le nombre de mots de /usr/local/util/lib/words.french
est de l'ordre de 130000, N vaudra par exemple 218.
On propose l'algorithme suivant pour calculer la clef associée
à un mot :
on initialise une variable k à 0x12345,
on lit les caractères de ce mot un par un, chaque caractère modifiant
k comme suit :
k = (k + k * s[i] ^ (s[i] + k / s[i])) & 0x3FFFF.
Une première version du programme travaillera avec
un hachage à adressage ouvert : dans chaque case du tableau
de hachage on stocke la chaîne. Si la case est occupée, on
utilise la case suivante.
On étudiera les phénomènes de regroupement, avec /usr/dict/words
puis avec /usr/local/util/lib/words.french.
On fera ensuite un double hachage, où la fonction de calcul du second hachage est similaire à celle du premier, en initialisant h à 0x12, et en calculant h = (h + h * s[i]) % 0xFB.
Voici un exemple de corrigé.
Comparez les performances (utilisation de mémoire et rapidité de recherche) de cette méthode et de celle du TP précédent.
Peut-on combiner les deux ?