Kha-tastrophe.net

Le site kha-tastrophique de Kha

> Cours > Informatique> Algorithmique et Analyse > Hachage

4. Hachage

4.1. Ranger et retrouver rapidement l'information

C'est toujours un problème majeur ; par exemple : la liste des commandes pour un système UNIX, la liste des identificateurs d'un programme soumis à un compilateur, une liste des références d'articles dans un catalogue, une liste des noms d'étudiants...

Nous avons vu le rangement séqauentiel dans une liste, de manipulation aisée mais lent pour retrouver : complexité Θ(n) ; nous avons aussi étudié le rangement ordonné dans un tableau qui est plus rapide pour retrouver : Θ(log(n)) mais lent à créer et à modifier : la complexité des meilleurs algorithmes vaut Θ(n (log(n))).

Puisqu'il est clair que la structure de tableau est bien adaptée à un accès rapide, l'idéal serait de disposer d'une méthode qui permette de calculer la place d'une information dans un tableau, directement à partir de cette information elle-même. La difficulté vient du fait que cette information peut, en général, prendre un nombre énorme de valeurs (en fait, seulement une très petite partie de ces valeurs possibles seront effectivement présentes). Par exemple, pour un compilateur FORTRAN 77, le nombre de noms de variables possibles (identificateurs à 6 caractères alphanumériques) est de l'ordre de 26 x 365 ≈ 1.6 109, un programme raisonnable comprend quelques dizaines d'identificateurs.

Il faut donc imaginer une fonction (calculable simplement) : la fonction de "hachage", qui applique ces trop nombreuses valeurs possibles de la clé sur un ensemble beaucoup plus petit ; l'idéal serait que l'ensemble résultant soit de la même taille que l'ensemble des clés présentes à classer. Il est inévitable que la fonction de hachage puisse donner le même résultat pour des clés de valeurs différentes, ce qui s'appelle une "collision". On peu monter que si la fonction de hachage peut prendre h valeurs distinctes, la probabilité que n clés distinctes n'entrent pas en collision vaut : h! / (h-n)! / hn.

Le principe de fonctionnement du hachage est le suivant : la fonction de hachage appliquée à une clé rend une valeur entière, le "hash-code", dont l'étendue des valeurs possibles est très réduite par rapport à l'étendue des valeurs possibles pour la clé ; puis, par une opération de modulo1, l'étendue des valeurs de ce hash-code est ramenée à la taille du tableau dans lequel on désire ranger la clé (ce tableau doit évidemment être plus grand que l'ensemble des clés à traiter).

1. Il faut être attentif à ce que cette opération de modulo engendre aussi peu de collisions artificielles que possible et ne détruise pas l'équirépartition des valeurs de clé.

fermer cette précision

4.2. Gestion des collisions

4.2.1. Méthode directe : hachage linéaire

De nombreuses méthodes, d'intérêt surtout historique, procèdent en stockant chaque clé rencontrée directement dans le tableau des clés. Elles détectent une collision en regardant au préalable si l'élément choisi est "vide" (N.B. y aurait-il une valeur "vide" qui soit interdite aux clés??) ; les collisions sont traitées en recherchant un autre élément qui soit vide... (cf. le "surbooking" des organisateurs de voyages). On voit sur l'exemple que cette méthode engendre, en plus des collisions liées à la fonction de hachage, des collisions artificielles (quand une valeur de clé trouve sa place occupée par une clé placée à cet endroit pour résoudre une collision précédente) ; de plus cette méthode rend très difficile l'élimination d'une clé (comment savoir si il n'y a de clés déplacées candidates à la place libérée ? en fait il faut "re-hacher" complètement la table...)

L'exemple ci-dessous illustre le fonctionnement de la méthode :

Exemple de résolution des collisions par méthode directe : hachage linéaire

Illustration du fonctionnement de la méthode de hachage linéaire

  • les clés sont les mots d'un texte,
  • la fonction de hachage est la longueur (nombre de caractères) de ces mots,
  • les mots sont placés au fur et à mesure de leur introduction dans la case d'indice égal à leur hash-code ; si cette place est déjà occupée, ils sont installés à la première place libre qui suit ;
  • le texte est le célèbre : "longtemps je me suis couché de bonne heure"
    • (nombre de caractères du mot : 9 2 2 4 6 2 5 5)
    • (les flèches montrent les éléments déplacés pour cause de collision, la flèche grasse montre une collision induite par la méthode linéaire).

4.2.2. Méthode indirecte avec chaînage séparé

Le tableau ne contient pas directement les clés, mais des pointeurs sur des têtes de liste, dans chaque liste se trouvent les clés en collision, c.-à-d. de mêmes valeurs de hash-code.

On est donc ramené à un problème de gestion de listes.

La méthode de hachage sera d'autant plus efficace que les listes de collisions seront les plus courtes possibles (idéalement de longueur 1). Il faut donc que le nombre de têtes de listes possibles soit autant que possible supérieur au nombre de clés à traiter (cf. formule citée plus haut)

Exemple de résolution des collisions par méthode indirecte : chaînage séparé

Illustration du fonctionnement de la méthode indirecte de hachage avec chaînage séparé

  • les clés sont les mots d'un texte,
  • la fonction de hachage est la longueur (nombre de caractères) de ces mots,
  • les mots sont placés au fur et à mesure de leur introduction dans la liste dont la tête est donnée par la valeur de hash-code : ici, l'indice de la tête de la liste collision est la valeur du hash-code modulo 7
  • le texte est toujours :v " longtemps je me suis couché de bonne heure"

4.3. Fonction de hachage

Son rôle est extrêmement important : c'est elle qui doit assurer la répartition uniforme des valeurs de clé rencontrées sur les valeurs possibles de hash-code ; elle est donc extrêmement dépendante du contexte.

N.B. il est judicieux, lors de la mise au point, d'essayer avec une fonction qui ne donne qu'une seule valeur, on peut ainsi tester les procédures de gestion des collisions...