Le barème est donné à titre indicatif et est sus­cep­tible d'être adapté. Lisez at­ten­ti­ve­ment les explications. Commentez vos fonctions.

Soit Σ* l'ensemble (infini) des mots défini sur un alphabet fini Σ et n un entier strictement positif. Une fonction de hachage

calcule le haché h(x) (un entier codé sur n bits), d'un mot x de Σ* (une chaîne de caractères).

Exemple : la fonction h qui renvoie l'index dans l'alphabet latin de la première lettre d'un mot français est une fonction de hachage à valeurs dans [0,31] (les valeurs 26 à 31 ne sont donc pas utilisées). Ainsi h(examen) = 4.

Avec une bonne fonction de hachage, la moindre variation sur un mot se traduit par un haché différent. L'exemple ci-dessus est donc une mauvaise fonction de hachage, puisque deux mots totalement différents mais avec la même initiale auront le même haché.

Par construction, une fonction f de hachage ne peut pas être injective. Dès lors que l'on hache tous les mots d'un sous-ensemble D de Σ* tel que |D| > 2ⁿ, il y a des collisions, c'est-à-dire des mots différents qui ont le même haché. Dans l'idéal, une bonne fonction de hachage doit, entre autres propriétés, répartir uniformément ces collisions. Par exemple, s'il y a 4096 mots à hacher sur 8 bits, il devrait y avoir en moyenne 4096/256 ≈ 16 mots par haché possible de l'intervalle [0, 255].

1. Un premier objectif est de mesurer expérimentalement la distribution des hachés de nbmots mots tirés aléatoirement pour la fonction de hachage FNV (Fowler–Noll–Vo, elle est fournie dans le code source). On crée pour cela une table de hachage TH de 2ⁿ alvéoles (structure contenant une liste chaînée de chaînes de caractères et sa longueur). Chaque mot x est inséré à la tête de la liste de l'alvéole d'index h(x) dans la table TH (en incrémentant la longueur de la liste). Une fois les nbmots répartis dans les différentes listes de la table de hachage TH, on calcule alors le coefficient de variation de leurs tailles, c'est-à-dire le ratio entre l'écart type et la moyenne de ces tailles, ce qui fournit une mesure de la dispersion autour de la moyenne. Idéalement cette dispersion est nulle.
2. Dans un deuxième temps, on veut expérimenter le paradoxe des anniversaires : combien de mots faut-il tirer au hasard pour parvenir à une première collision ? Pour cela, on réalise plusieurs fois (nbexp) la même expérience qui consiste à tirer des mots au hasard jusqu'à obtenir une première collision en relevant le nombre de tirages aléatoires qui auront été nécessaires à chaque expérience. On peut alors calculer leur moyenne. En théorie, en tirant au hasard 1.18*(2^nbbits/2) mots, la probabilité d'obtenir une collision est supérieure à 0.5.

Sauvegardez le fichier source collision.c. Le fichier source contient des déclarations de types, de variables, de fonctions pré­dé­fi­nies commentées (la fonction de hachage, entre autres), dont certaines sont à compléter et font l'objet de ce contrôle. Ne modifiez pas les noms des variables, types, fonctions, etc. les correcteurs ne vont pas s'adapter aux différents styles d'écriture des 50 étudiants qui composent…

Une fois ces fonctions complétées et le programme compilé par la commande

$ gcc -o collision collision.c -lm -Wall

$ ./collision 8 4096 1000 

Coefficient de variation = 26.17% (M = 16.00)
Collision obtenue après 20.69 tirages en moyenne (18.88)

Les trois arguments 8, 4096 et 1000 sont respectivement:

1. Le nombre de bits pour coder un haché (nbbits). Il permet de fixer la taille 2^nbbits de la table de hachage TH.
2. Le nombre de mots (nbmots) à répartir dans TH pour vérifier la distribution des hachés et répondre à la question (1).
3. Le nombre de fois (nbexp) où il faut répéter l'expérience consistant à calculer le nombre de tirages de mots aléatoires nécessaires pour obtenir une première collision dans la table afin d'en calculer la moyenne et répondre à la question (2). (NB. La valeur (18.88) est le nombre de tirages théoriques pour que la probabilité d'obtenir une collision soit supérieure à 50%.)

Pour ne pas rester bloqué, vous pouvez demander la solution des questions 1 à 3 à votre surveillants (mais vous perdrez les points attribués à ces questions).