modulo

La fonction de hashage la plus basique qui soit est la fonction modulo. si N est la taille du hash, tu as:

hash(a) ≡ a [2^N] (formule 1)
hash(b) ≡ b [2^N] (formule 2)

hors tu sais que :

ab = a*2^(8*taille_en_octets(b))+b (formule 3)

et si on note :

decal(b) = 2^(8*taille_en_octets(b))

la formule 3 se réecrit en :
ab = a*decal(b)+b (formule 4)

d'ou :

hash(ab) ≡ a*decal(b)+b [2^N] (formule 5)

rappelons que (théorème 1) :

si a1 ≡ b1 [n] et a2 ≡ b2 [n] => a1+a2 ≡ b1+b2 [n] et a1*a2 ≡ b1*b2 [n]

et posons alors :

hash(decal(b)) ≡ decal(b) [2^N] (formule 6)

ce qui donne en multipliant la formule 1 et 6 à l'aide du théorème 1 :


hash(a)*hash(decal(b)) ≡ a*decal(b) [2^N] (formule 7)

en recomposant la formule 7 avec la formule 2 on obtient alors :

hash(a)*hash(decal(b))+hash(b) ≡ a*decal(b)+b [2^N]

on reconnait dans la partie de droite la formule 5, on en déduit imédiatement que :

hash(ab) ≡ hash(a)*hash(decal(b))+hash(b) [2^N]

j'espère que ça pourrra t'aider!