Discuter:Table de hachage

Un article de Wikipédia, l'encyclopédie libre.

	Table de hachage fait partie du projet Informatique, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés à l'informatique. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail informatique pourrait aussi vous intéresser.
B	Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. (Voir les statistiques)
Faible	Cet article a été classé comme d'Importance faible selon le Tableau d'évaluation du projet. (Contester?)

Tâches à accomplir pour Table de hachage modifier • suivre • rafraîchir • aide

	Tâches à accomplir pour Table de hachage	modifier • suivre • rafraîchir • aide
Pour créer la liste des tâches à accomplir pour cet article, vous pouvez : Soit cliquer sur ce lien rouge, y insérer une liste de tâches à faire (par exemple sous forme de liste à puces), puis sauvegarder. Soit modifier cette page-ci et compléter le modèle comme ceci : `{{todo\|Liste de tâches à faire}}`. Voir aussi la page d'aide.

Pour créer la liste des tâches à accomplir pour cet article, vous pouvez :

Soit cliquer sur ce lien rouge, y insérer une liste de tâches à faire (par exemple sous forme de liste à puces), puis sauvegarder.
Soit modifier cette page-ci et compléter le modèle comme ceci : {{todo|Liste de tâches à faire}}.

Voir aussi la page d'aide.

Sommaire

1 définition absconse et maladroite
2 Généralités
3 Implémentation et fonctions de hachage
- 3.1 Implémentation naïve
- 3.2 Injection et collisions en informatique

[modifier] 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).

[modifier] 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.

[modifier] Implémentation et fonctions de hachage

[modifier] 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$

[modifier] Injection et collisions en informatique

[modifier] 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 \ne 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}\,\!$

[modifier] 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.

[modifier] 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.

[modifier] 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.

[modifier] 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.

[modifier] Résolution des collisions par tableau de collisions

[modifier] Comment définir la taille d'une table de hachage