Dictionnaire (bis)

Objectif

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.

Paramètres

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.

Implantation

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é.

Performances

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 ?