Hachage universel

Cette section se réfère au cas du hachage d'entiers qui tiennent dans un mot machine. Dans ce cas les opérations addition, multiplication, et division sont exécutées directement sur le processeur et coûtent très peu de ressources. À partir de ce point on considère l'univers à hacher ${\displaystyle U=\{0,\dots ,m-1\}}$.

La proposition initiale de Carter et Wegman[1] était de choisir un entier premier ${\displaystyle p\geq m}$ et définir

${\displaystyle h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m}$

où ${\displaystyle a,b}$ est un couple d'entiers choisis aléatoirement modulo ${\displaystyle p}$ avec ${\displaystyle a\neq 0}$. (Cela correspond à un pas d'itération d'un générateur congruentiel linéaire.)

Pour vérifier que ${\displaystyle H=\{h_{a,b}\}}$ est bien une famille universelle, notez que ${\displaystyle h(x)=h(y)}$ ne tient que si

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}}}$

pour un certain entier ${\displaystyle i}$ compris entre ${\displaystyle 0}$ et ${\displaystyle (p-1)/m}$. Si leur différence, ${\displaystyle x\neq y}$, est non nulle et possède un inverse modulo ${\displaystyle p}$. Chercher ${\displaystyle a}$ revient à résoudre :

${\displaystyle a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}}$.

Il y a ${\displaystyle p-1}$ choix possibles pour ${\displaystyle a}$ (${\displaystyle a=0}$ est exclu) et pour ${\displaystyle i}$pris dans l'intervalle autorisé, il y a ${\displaystyle \lfloor (p-1)/m\rfloor }$ valeurs pour les côtés droits et gauche. La probabilité de collision est alors de

${\displaystyle \lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m}$.

Une autre manière de prouver que ${\displaystyle H}$ est une famille universelle passe par la notion de distance statistique. On écrit la différence ${\displaystyle h(x)-h(y)}$ comme :

${\displaystyle h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}}$.

Étant donné que ${\displaystyle x-y}$ est non nul et que ${\displaystyle a}$ est uniformément distribué dans ${\displaystyle \{1,\dots ,p\}}$, on déduit que ${\displaystyle a(x-y)}$ modulo ${\displaystyle p}$ est aussi uniformément distribué dans ${\displaystyle \{1,\dots ,p\}}$. La distribution de ${\displaystyle (h(x)-h(y))~{\bmod {~}}m}$ est ainsi presque uniforme, avec une différence de probabilité au maximum de ${\displaystyle \pm 1/p}$ entre les échantillons. Il en résulte que la distance statistique à une famille uniforme est ${\displaystyle O(m/p)}$, qui devient négligeable quand ${\displaystyle p\gg m}$.

La famille la plus simple de fonctions de hachage, ${\displaystyle h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m}$, est seulement approximativement universelle : ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$ pour tout ${\displaystyle x\neq y}$[1]. De plus, cette analyse est assez fine ; Carter et Wegman[1] ont montré que ${\displaystyle \Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m-1)}$ pour tout ${\displaystyle (p-1)~{\bmod {~}}m=1}$.

La méthode la plus populaire dans le hachage d'entier est la méthode « multiplie et décale » décrit par Dietzfelbinger et al. en 1997[7]. En évitant l'arithmétique modulaire, cette méthode est plus simple à implémenter et est significativement plus rapide en pratique (usuellement plus rapide d'un facteur 4)[8]).

Cette méthode suppose que le nombre de fragments binaires soit une puissance de deux, ${\displaystyle m=2^{M}}$. Soit ${\displaystyle w}$ le nombre de bits dans un mot machine. Les fonctions de hachage sont paramétrées par des entiers positifs impairs ${\displaystyle a<2^{w}}$ (qui tiennent dans un mot de ${\displaystyle w}$ bits). Pour calculer ${\displaystyle h_{a}(x)}$, on multiplie ${\displaystyle x}$ par ${\displaystyle a}$ modulo ${\displaystyle 2^{w}}$ et ensuite on garde les ${\displaystyle M}$ bits de poids fort du résultat comme hash. En notation mathématique cela s'écrit :

${\displaystyle h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{w-M}}$

et peut être implémenté dans un langage de la famille du C par le code :

${\displaystyle h_{a}(x)=}$ (unsigned) (a*x) >> (w-M)

Ce schéma ne satisfait pas la propriété de différence uniforme et est seulement ${\displaystyle 2/m}$-presque-universel ; pour tout ${\displaystyle x\neq y}$, ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$.

Pour comprendre le comportement de la fonction de hachage, remarquez que si ${\displaystyle ax{\bmod {2}}^{w}}$ et ${\displaystyle ay{\bmod {2}}^{w}}$ ont les mêmes 'M' bits de poids fort alors ${\displaystyle a(x-y){\bmod {2}}^{w}}$ n'a que des 1 ou que des 0 dans ses 'M' bits de poids fort (cela dépend du maximum entre ${\displaystyle ax{\bmod {2}}^{w}}$ et ${\displaystyle ay{\bmod {2}}^{w}}$). Supposons maintenant que les bits de poids faible de ${\displaystyle x-y}$ apparaissent en position ${\displaystyle w-c}$. Comme ${\displaystyle a}$ est un entier impair et que les entiers impairs possèdent un inverse dans l'anneau ${\displaystyle Z_{2^{w}}}$, on déduit que ${\displaystyle a(x-y){\bmod {2}}^{w}}$ sera uniformément distribué parmi les entiers de ${\displaystyle w}$ bits avec le bit de poids le plus faible situé à la position ${\displaystyle w-c}$. La probabilité que ces bits soient tous égaux à 0 ou à 1 est donc au plus de ${\displaystyle 2/2^{M}=2/m}$. D'autre part si ${\displaystyle c<M}$, alors les M bits de poids fort de ${\displaystyle a(x-y){\bmod {2}}^{w}}$ contiennent des 0 et des 1 et on est certain que ${\displaystyle h(x)\neq h(y)}$. Finalement, si ${\displaystyle c=M}$ alors le bit ${\displaystyle w-M}$ de ${\displaystyle a(x-y){\bmod {2}}^{w}}$ vaut 1 et ${\displaystyle h_{a}(x)=h_{a}(y)}$ si et seulement si les bits ${\displaystyle w-1,\ldots ,w-M+1}$ valent également 1, ce qui arrive avec la probabilité de ${\displaystyle 1/2^{M-1}=2/m}$.

Cette analyse est difficile, comme on peut le constater avec les exemples ${\displaystyle x=2^{w-M-2}}$ et ${\displaystyle y=3x}$. Pour obtenir une fonction de hachage 'vraiment' universelle, on peut utiliser la méthode multiplie et additionne.

${\displaystyle h_{a,b}(x)=((ax+b){\bmod {2}}^{w})\,\mathrm {div} \,2^{w-M}}$

qui peut être implémenté en langages de la famille du C par

${\displaystyle h_{a,b}(x)=}$ (unsigned) (a*x+b) >> (w-M)

où ${\displaystyle a}$ est un entier pair positif tiré aléatoirement, ${\displaystyle a<2^{w}}$, et ${\displaystyle b}$ un entier positif tiré aléatoirement ${\displaystyle b<2^{w-M}}$. Avec ce choix de ${\displaystyle a}$ et ${\displaystyle b}$, ${\displaystyle \Pr\{h_{a,b}(x)=h_{a,b}(y)\}\leq 1/m}$ pour tout ${\displaystyle x\not \equiv y{\pmod {2^{w}}}}$[9]. Ceci diffère légèrement, mais sur un point important, de l'erreur de traduction de l'article en anglais[10].

Cette section concerne le hachage de vecteur de mots dont la longueur est fixée à l'avance. Interpréter l'entrée comme un vecteur ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{k-1})}$ de ${\displaystyle k}$ mots machine (entiers de ${\displaystyle w}$ bits chacun). Si ${\displaystyle H}$ est une famille universelle qui vérifie la propriété de différence uniforme, la famille suivante, trouvée par Carter et Wegman[1], possède également la propriété de différence uniforme (et donc est universelle) :

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$, où chaque ${\displaystyle h_{i}\in H}$ est choisi de manière aléatoire et indépendante.

Si ${\displaystyle m}$ est une puissance de deux, la somme peut être remplacée par une opération ou exclusif[11].

En pratique si l'arithmétique en double précision est disponible, on utilise la famille de fonction de hachage « multiplie et décale »[12]. On initialise la fonction avec un vecteur ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$ d'entiers pairs de ${\displaystyle 2w}$ bits de long. Ensuite si le nombre de fragments est ${\displaystyle m=2^{M}}$, avec ${\displaystyle M\leq w}$

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

Il est possible de diviser le nombre de multiplication par 2, ce qui se traduit par un calcul à peu près deux fois plus rapide en pratique[11]. Initialiser la fonction de hachage avec un vecteur ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$ de nombres entiers impairs chacun de ${\displaystyle 2w}$ bits de long. La famille de hachage ainsi produite est universelle[13] :

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

Si les opérations en double précision ne sont pas disponibles, on peut interpréter l'entrée comme un vecteur de demi-mots (des entiers de ${\displaystyle w/2}$ bits de longs). L'algorithme va alors utiliser ${\displaystyle \lceil k/2\rceil }$ multiplications, avec k le nombre de demi mots du vecteur. Ainsi l'algorithme tourne à un "taux" d'une multiplicatio par mot d'entrée.

Ce schéma peut également être utilisé pour hacher des entiers en considérant que leurs bits sont un vecteur d'octets. Dans cette variante, la technique est appelée hachage tabulaire et fournit une alternative pratique aux fonctions de hachage universelle basées sur des multiplications[14].

L'universalité forte à grande vitesse est également possible[15]. Initialiser la fonction de hachage avec un vecteur ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k})}$ d'entiers pris au hasard de ${\displaystyle 2w}$ bits de long. Calculer :

${\displaystyle h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}}$.

Le résultat est fortement universel sur ${\displaystyle w}$ bits. Expérimentalement cette méthode consomme 0.2 cycle CPU par octet sur les dernières puces Intel pour ${\displaystyle w=32}$.

Cette section vise le cas de vecteur de mots de taille variable. Si la taille de la chaîne peut être majorée par un petit nombre, il est préférable d'utiliser la méthode avec des vecteurs de taille définie en complétant la chaîne à hacher par des zéros au besoin. L'espace mémoire requis pour le calcul est la longueur maximale de la chaîne, mais le temps de calcul dépend uniquement de la longueur de ${\displaystyle h(s)}$. Tant qu'on interdit les zéros dans la chaîne, on peut ignorer le remplissage d'une chaîne par des zéros terminaux sans que la propriété d'universalité en soit affectée[11]. Noter que si on autorise la présence de zéros dans la chaîne alors le problème d'ajout de zéros terminaux se règle en choisissant d'ajouter un caractère non nul, qui balisera la fin de la chaîne à toutes les chaînes en entrée avant le traitement[15].

Maintenant supposons qu'il faille hacher ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{\ell })}$, sans qu'on puisse avoir d'estimation correcte de ${\displaystyle \ell }$. Une famille de hachage universelle[12] traite la chaîne ${\displaystyle x}$ comme les coefficients d'un polynôme modulo un grand nombre premier. Si ${\displaystyle x_{i}\in [u]}$, soit ${\displaystyle p\geq \max\{u,m\}}$ un nombre premier, on définit :

${\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{i}{\big )}{\bmod {~}}p\right)}$, où ${\displaystyle a\in [p]}$ est uniformément aléatoire et ${\displaystyle h_{\mathrm {int} }}$ est tiré aléatoirement d'une famille aléatoire universelle qui indexe l'ensemble des entiers ${\displaystyle [p]\mapsto [m]}$.

En utilisant les propriétés de l'arithmétique modulaire, la formule ci-dessus peut être calculée sans produire de grands nombres par le code suivant[16] :

uint hash(String x, int a, int p)
	uint h = INITIAL_VALUE
	for (uint i=0 ; i < x.length ; ++i)
		h = ((h*a) + x[i]) mod p
	return h

L'algorithme ci-dessus est également connu en tant que fonction de hachage multiplicative[17]. En pratique l'opérateur modulo et le paramètre p peuvent être évités tous les deux simplement en autorisant les entiers à dépasser leur taille maximale (overflow) car cette opération est équivalente à un modulo MAX_INT_VALUE + 1 dans beaucoup de langages de programmation. Ci-dessous, un tableau de valeurs choisies pour initialiser h dans quelques implémentations populaires.

Soient deux chaînes ${\displaystyle {\bar {x}},{\bar {y}}}$ et ${\displaystyle \ell }$ la taille de la plus longue des deux ; pour les besoins de l'analyse on supposera que la seconde chaîne est complétée par des zéros jusqu'à atteindre la longueur ${\displaystyle \ell }$. Une collision avant d'appliquer ${\displaystyle h_{\mathrm {int} }}$ implique que ${\displaystyle a}$ est une racine du polynôme dont les coefficients sont ${\displaystyle {\bar {x}}-{\bar {y}}}$. Ce polynôme a au plus ${\displaystyle \ell }$ racines modulo ${\displaystyle p}$, donc la probabilité de collision est au plus de ${\displaystyle \ell /p}$. La probabilité de collision à travers l'aléa ${\displaystyle h_{\mathrm {int} }}$ descend la probabilité totale de collision à ${\displaystyle {\frac {1}{m}}+{\frac {\ell }{p}}}$. Ainsi si le nombre premier ${\displaystyle p}$ est suffisamment grand comparé à la longueur des chaînes à hacher, la famille est très proche d'une famille universelle (en termes de distance statistique).

Pour limiter la consommation de ressources par les calculs d'arithmétique modulaire, deux astuces sont utilisées en pratique[11] :

1. On peut choisir le nombre premier ${\displaystyle p}$ proche d'une puissance de 2, un nombre premier de Mersenne par exemple. Cela permet d'implémenter les opérations de modulo sans utiliser de division (en utilisant des opérations plus rapides comme les additions et les décalages de bits). Par exemple sur des architectures modernes on peut travailler avec ${\displaystyle p=2^{61}-1}$, alors que les ${\displaystyle x_{i}}$ sont stockés sur 32 bits.
2. On peut appliquer un hachage vectoriel sur des blocs de données de l'entrée. Par exemple, on hache l'entrée par vecteurs de 16 mots et on applique le hachage de chaîne aux ${\displaystyle \lceil k/16\rceil }$ hashs obtenus. Le hachage de chaîne, très lent, étant appliqué à un ensemble de données significativement plus petit le calcul devient presque aussi rapide que le hachage vectoriel.
3. On peut choisir une puissance de deux comme diviseur ce qui permet de réduire l'opération modulo à un masquage de bits plus rapide que les divisions. La famille de fonctions NH utilise cette méthode.

• K-independent hashing (en)
• Rolling hash (en)
• Tabulation hashing (en)
• MinHash (en)
• Fonction de hachage universelle à sens unique
• Suite à discrépance faible
• Fonction de hachage parfait

(en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition]

(en) Open Data Structures - Section 5.1.1 - Multiplicative Hashing