Discussion:Table de hachage

définition absconse et maladroite

je trouve la définition de la fonction de hachage particulièrement maladroite. La définir comme injective alors que le but d'une fonction de hachage est précisément de ne PAS etre injective !! et l'idée de dire que c'est l'ensemble fonction de hash+résolution des collisions qui est injectif (heureusement !) ok mais l'ensemble n'est pas une fonction de hash !! de plus il y a mélange de table de hachage et fonction de hachage, et les notations sont lourdingues ;-)

bref c'est particulièrement confus, et je proposerais bien de supprimer le tout pour le remplacer par une traduction de la version anglaise qui est excellente et très claire :-)
des remarques ?
Sylenius 9 février 2006 à 22:25 (CET)

Je ne suis pas contre une traduction de la version anglaise :) Cela fait longtemps que cet article est dans cet état. Dake* 21 février 2006 à 15:38 (CET)

Moi je trouve que si la fonction n'est pas injective, on n'aurait pas des élements de V qui auront le même élement de H, mais plutot le contraire des élement de H qui seront associés à la même valeurs de V

bon je l'aimais pas, l'article, je le met ici et je le remplace par une ébauche de la traduction anglaise (à compléter) Sylenius 1 mai 2006 à 22:41 (CEST)

En informatique, une table de hachage est une structure de données qui permet une association clé-élément, c'est-à-dire une implémentation du type abstrait table de symboles.

On accède à chaque élément de la table via sa clé. Il s'agit d'un tableau ne comportant pas d'ordre (un tableau est indexé par des entiers).

Attention la fonction de hachage est surjective, puisque le résultat est en général plus petit que les données d'entrées ... ce n'est pas possible que ce soit injectif!! en plus si c'était injectif il n'y aurait aucun problème de collision ... Malo77 (discuter) 2 décembre 2020 à 09:03 (CET)

Généralités

Soient ${\mathcal {K}}$ et ${\mathcal {V}}$ deux ensembles quelconques. On définit l'application suivante :

${\begin{matrix}H:&{\mathcal {K}}&\rightarrow &{\mathcal {V}}\\\ &k&\mapsto &v\end{matrix}}\,\!$

Si H est injective, alors H est une fonction de hachage.

Pourquoi injective ?

H doit être injective pour assurer l'unicité de l'accès aux données stockées : en effet, dans le cas contraire, des éléments différents de ${\mathcal {V}}$ pourraient être accessibles par la même clé.

H n'est pas nécessairement surjective.

Implémentation et fonctions de hachage

Implémentation naïve

L'implémentation la plus courante fait appel à une fonction injective :

${\begin{matrix}h_{n}:&{\mathcal {K}}&\rightarrow &[0,n-1]\subset \mathbb {N} \\\ &k&\mapsto &h(k)\end{matrix}}\,\!$

L'entier résultant est utilisé pour retrouver $v\in {\mathcal {V}}$ dans un tableau (un n-uplet) de ${\mathcal {V}}^{n}$

Injection et collisions en informatique

Problème de l'injection et collisions

Il est souvent très difficile de trouver une fonction de hachage injective simple de ${\mathcal {K}}$ sur ${\mathcal {V}}$. Pour pallier ce défaut, on introduit le mécanisme suivant :

on choisit une fonction de hachage (non nécessairement injective) qui fait correspondre à la clé un hachage h :

${\begin{matrix}hash:&{\mathcal {K}}&\rightarrow &{\mathcal {H}}\\\ &k&\mapsto &h\end{matrix}}\,\!$

On prend souvent un hachage entier : ${\mathcal {H}}=[m,n]\subset \mathbb {N}$

Cette fonction n'étant pas injective, on introduit un risque de collisions :

$\exists (k_{1},k_{2})\in {\mathcal {K}}^{2},k_{1}\neq k_{2}\wedge hash(k_{1})=hash(k_{2})$

c’est-à-dire qu'à deux clés différentes, on fait correspondre le même hachage. Le terme de collision vient de l'approche naïve : si l'on désire stocker les valeurs v₁ et v₂ relatives aux clés k₁ et k₂ dans un tableau, les deux indices h(k₁) et h(k₂) étant égaux alors v₁ et v₂ se cognent dans la même cellule.

On choisit donc un mécanisme de résolution des collisions :

${\begin{matrix}rescol:&{\mathcal {K}}\times {\mathcal {H}}&\rightarrow &{\mathcal {V}}\\\ &(k,h)&\mapsto &v\end{matrix}}\,\!$

L'ensemble doit vérifier : $rescol(k,hash(k))\,\!$ injective

On a alors la table de hachage suivante :

${\begin{matrix}H:&{\mathcal {K}}&\rightarrow &{\mathcal {V}}\\\ &k&\mapsto &rescol(k,hash(k))\end{matrix}}\,\!$

Fonctions de hachage

Le terme francisé de fonction de hash recouvre au moins deux sens :

• la somme de contrôle : $x\mapsto h(x)\,\!$ est simple à calculer, mais $h(x)\mapsto x\,\!$ est un problème difficile
• la fonction de table de hachage : si $h(x)=h(y)\,\!$, alors on a probablement $x=y\,\!$

Bien sûr, la distinction entre ces deux sens n'est pas évidente ; d'ailleurs, ces deux visions ne s'opposent en rien : une somme de contrôle peut faire une très bonne fonction de hachage pour une table de hachage (puisque si $h(x)=h(y)\,\!$, alors on a très probablement $x=y\,\!$).

On se reportera aux articles : Fonction de hash, Cryptologie, Cryptographie.

Résolution des collisions par adressage ouvert

Quand il y a collision, on examine les positions suivantes et on met la clé dans la 1ère position libre. C’est simple, mais il va y avoir accumulation.

Résolution des collisions par chaînage externe

Ce mécanisme de résolution de collisions utilise une liste (ou un arbre de recherche). Pour chaque hachage, on stocke dans une liste dédiée tous les éléments de ${\mathcal {V}}$ qui correspondent à ce hachage.

Résolution des collisions par chaînage combiné

Afin d'avoir une table entière dans la même zone mémoire, on utilise la même règle que l’adressage ouvert mais les synonymes (même valeur de hash) ainsi que les entrées ultérieures rentrant en collision avec l’un des éléments d’une sous-liste sont dans la même sous-liste chaînée. Au prix d’un champ de pointeur, la recherche est accélérée par rapport à l’adressage ouvert.