Julien Sopena

TD 01 – Fonctions de hachage : Codage et Adressage

Exercice 1: Fonction de hachage par division

Une université veut se constituer une base de données pour le passage au LMD. Chaque module a ses données propres. Chacune de ces entités est accompagnée d'une clé. Les clés sont construites sur le modèle suivant :
<NOM_MODULE>[L1|L2|L3|M1|M2|D].

Le programmeur choisit d'utiliser une fonction de hachage par division :
h(k) = k modulo (m) avec m=256

Question 1.1 )

Dans un premier temps, pour coder la clé, le programmeur va la considérer comme étant déjà un nombre.

Calculez le code des clés en base 10 : ALGL3 et BDL3.

Question 1.2 )

Dans un second temps, il va utiliser un codage en bit : concaténation de l'écriture en bit du code ASCII de chaque caractère. Calculez le code des clés : ALGL3 et BDL3. Quel est l'avantage d'un tel codage ?

Question 1.3 )

Comparez ces deux codages. Quelle sont leurs avantages et limites respectifs ?

Question 1.4 )

Le programmeur choisit d'utiliser une fonction de hachage (d'adressage) par division h(k) = k modulo (m) avec m=256. Calculez la valeur de hachage des deux clés : ALGL3 et BDL3 pour chaque codage. Que remarquez vous ? Expliquez ce résultat.

Question 1.5 )

Que doit faire le programmeur ? Concluez par une remarque générale sur les fonctions de hachage par division.

Question 1.6 )

Maintenant le programmeur va utiliser un codage alphabétique : chaque lettre est remplacée par sa position dans l'alphabet. Le résultat est interprété comme un nombre en base dix. Calculez le code des clés : ALGL3 et BDL3.

Question 1.7 )

A la suite des remarques précédentes, le programmeur choisit d'utiliser m=9 comme coefficient de la fonction de hachage (d'adressage) par division h(k) = k modulo (m). Calculez la valeur de hachage des deux clés : ALGL3 et GLA3 pour chaque codage. Que remarquez vous ? Expliquez ce résultat.

Question 1.8 )

Montrez que l'on peut étendre le cas précédent aux clés codées en base B avec un coefficient B−1

Exercice 2: Fonction de hachage par multiplication

On se propose ici d'étudier le coefficient multiplicateur dans une fonction de hachage avec un adressage par multiplication. Soit la fonction :

h(k)= ⌊ m (A k modulo(1)) ⌋, avec 0<A<1

Question 2.1 )

Considérons l'ensemble de clés k ∈ { 0,⋯,255}. Quels inconvénients présente le coéfficient :
A=1−10−4

Question 2.2 )

Le problème est-il différent avec l'ensemble de clés k ∈ { 0,⋯,1023 }  ?

Question 2.3 )

On suppose maintenant que les clés sont codées dans la base B. Peut on choisir A voisin de 0 si (BA) modulo 1 est voisin de zéro ?

Exercice 3: Fonction de hachage polynomiale

Soit k un entier formé des chiffres c1c2cn et la fonction :

f(k)=f(c1c2⋯ cn)=c1+c2*10+c3*102+⋯+cn*10n

Question 3.1 )

Cette fonction est-elle injective ?

Question 3.2 )

Cette fonction peut-elle servir de fonction de hachage ? Proposez une fonction de hachage utilisant cette fonction.

Question 3.3 )

Quel intérêt présente cette fonction pour faire une fonction de hachage? Donnez un exemple d'ensemble (Univers) de clés pour lequel cette fonction est particulièrement bien adaptée.

Designed by OWSD.org. Valid CSS & XHTML
Ce site et l'ensemble de son contenu est mis à disposition sous un contrat Creative Commons.
Creative Commons License