Sujet: fonction de hachage, collisions et paradoxe des anniversaires.

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

h: Σ* → [0, 2n − 1]

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| > 2n, 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 2n 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*(2nbbits/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

L'appel 
$ ./collision 8 4096 1000
affichera par exemple : 
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 2nbbits 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).

Question 1 [+1] Complétez la fonction uint len(tmot mot) qui renvoie la longueur de la chaîne de caractère mot.
Indication : on rappelle qu'une chaîne se termine par le caractère '\0'.
Question 2 [+2] Complétez la fonction tmot GenMot(uchar lmin, uchar lmax) qui renvoie un mot dont la longueur a été tirée au hasard entre lmin et lmax (inclus) et dont les lettres ont été tirées au hasard dans l'ensemble des symboles {A, B, …, Z} (uniquement les majuscules).
Indication : utilisez la fonction prédéfinie randint. On rappelle que 'A' est l'entier qui code le caractère A.
Question 3 [+2] Complétez la fonction ttabhach AllouerTable(ullong nbalv) qui alloue une table de hachage de nbalv alvéoles dont les listes sont initialisées à la liste vide et les longueurs à 0, et la renvoie.
Question 4 [+3] Complétez la fonction tliste Trier(ttabhach TH) qui renvoie la liste des mots dans l'ordre croissant des valeurs des hachés. Le principe de construction de la liste est identique au tri par répartition quand on vide les casiers. Indication: utilisez les fonctions Depiler et Empiler. NB. Cette question est indépendante du sujet général.
Question 5 [+4] Complétez la fonction void MesurerUniformite(uint nbmots) qui alloue une table de hachage TH, y range nbmots générés aléatoirement et l'affiche (les longueurs des mots seront tirées au hasard entre 8 et 32). La fonction affichera ensuite le coefficient de variation puis libèrera toute la mémoire, i.e. les listes des alvéoles de TH puis TH.
Question 6 [+4] Complétez la fonction uint ChercherCollision(ttabhach TH) qui ajoute des mots générés aléatoirement dans la table TH jusqu'à trouver une première collision et renvoie le nombre de mots qui ont été nécessaires pour l'obtenir (les longueurs des mots sont tirées au hasard entre 8 et 32).
Question 7 [+4] Complétez la fonction void EstimerNbTirages(uint nbexp) qui répète nbexp fois l'expérience consistant à obtenir une collision, calcule la moyenne du nombres de mots nécessaires et l'affiche.