Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

Table de hachage

En informatique, une table de hachage est une structure de données qui permet une association clé-élément.

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).

Sommaire

1 Généralités

2 Implémentation et fonctions de hachage

2.1 Implémentation naïve
2.2 Injection et collisions en informatique

2.2.1 Problème de l'injection et collisions
2.2.2 Fonctions de hachage
2.2.3 Résolution des collisions par chaînage externe
2.2.4 Résolution des collisions par tableau de collisions

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 table 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 \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}\,\!$

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 a calculer, mais $h(x) \mapsto x\,\!$ est un problème difficile
la fonction de table 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 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 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 tableau de collisions

Catégories: Algorithmique

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the