Une façon de ranger une donnée dans un tableau est de lui affecter un emplacement calculé par une fonction f. f(K) est alors l'emplacement dans le tableau o� sera rangée la donnée K. Dans ce type de rangement, que ce soit pour insérer ou rechercher une donnée, on procédera toujours aussi rapidement. Cette classe d'algorithmes est appelée hachage ou technique de rangement dispersé.

Le problème avec ce nouveau type de rangement est la détermination d'une fonction bijective, c'est à dire une fonction qui attribue pour chaque donnée à insérer un nouvel emplacement dans le tableau. Le fameux paradoxe de l'anniversaire, cité dans Knuth, nous laisse entendre qu'il est impossible d'essayer de chercher une fonction qui soit bijective. En d'autres termes, il existe toujours des données distinctes K1 et K2 pour lesquelles f(K1) = f(K2). Une telle situation est appelée collision. Pour utiliser une table à rangement dispersé ou, d'une façon générale les méthodes de hachage, l'utilisateur doit définir :

- la fonction de hachage

- une méthode dite méthode de résolution des collisions.

Fonction de hachage

Il s'agit de trouver une fonction f telle que :

0 <= f(K) < M

qui réduit au maximum le nombre de collisions.

Exemple de fonction de hachage

h(K)= K MOD M

M premier constitue généralement un bon choix.

Méthodes de résolution des collisions

Il existe plusieurs façons de résoudre les collisions. Les méthodes suivantes sont les plus classiques :

Essai linéaire

S'il se produit une collision sur la case k du tableau T[0..M-1], on insère la donnée, si elle n'existe pas, dans la première case libre fournie par la séquence cyclique

h(k)-1, ......, 0, M-1, M-2, ......h(k)+1

En d'autres termes, on essaie de chercher linéairement une case libre dans la séquence ci-dessous. D'ou l’appellation de la méthode.

Double hachage

Cette méthode est presque analogue à la précédente mais au lieu que la séquence soit linéaire, elle est construite par une autre fonction de hachage. D'o� l’appellation de la méthode.

Autrement dit, s'il y a collision sur une case k, on calcule un pas p par une autre fonction de hachage et la séquence cyclique à consulter serait

h(k)-p, h(k)-2p, ....

Les valeurs sont calculées modulo M, la taille de la table.

Deux fonctions de hachage sont alors utilisées h(K) et h'(K).

Le choix de M est très important. Un mauvais choix peut entraîner une non-couverture de l'ensemble des adresses possibles.

On démontre que lorsque M est un nombre premier et la fonction de hachage est aléatoire, il y a couverture de l'ensemble des adresses.

Chaînage interne

Afin de réduire le temps de recherche on ajoute au niveau de chaque élément du tableau un champ LIEN. Ce champ contient la prochaine position de la table à examiner pour la recherche d'un élément donné.

Les synonymes sont ainsi rangés dans une liste linéaire chaînée représentée dans un tableau. D'ou l’appellation de la méthode.

Une liste contient des groupes de synonymes.

Quand une collision se produit sur une case k, on parcourt la liste des débordements commençant en k. Si la donnée n'est pas trouvée, on cherche un emplacement vide dans le tableau.

Une bonne façon de rechercher une position vide c'est de parcourir le tableau à partir de la position R (initialisée à N+1). On décrémente R une ou plusieurs fois jusqu'à ce que l'on trouve une position vide. Ainsi, à un moment donné, toutes les positions p telles que p > R sont occupées.

Chaînage séparé

Les synonymes sont rangés dans une liste linéaire chaînée séparée. D'ou l’appellation de la méthode.

Performance des méthodes de hachage

Les méthodes qui utilisent le chaînage semblent les meilleurs. Cependant, leurs inconvénients résident dans le champ additionnel représentant les liens. En général, les méthodes de hachage ont de très bonnes performances. Pour l'essai linéaire par exemple, même quand la table est remplie à 90 �/�, le nombre de tests est au voisinage de 5. Pour avoir un temps rapide ( de l'ordre de 1) , on convient de ne pas dépasser un chargement de 70�/�.

Réduction des débordements

Le résultat de l'étude probabilistique développée ci-après permet de montrer que si la fonction de hachage est aléatoire, alors on peut prévoir le nombre de collisions, et par conséquent comment les réduire.

Supposons N adresses possibles et considérons les 2 événements :

A : une adresse donnée n'est pas choisie

B : une adresse donnée est choisie.

Quand une donnée est hachée, l'un des événements (A ou B) se produit pour une adresse donnée.

Soit P(A) = a = 1/N et P(B) = b = 1 - 1/N.

P(A) désigne la probabilité qu'une adresse donnée ne soit pas choisie.

P(B) désigne la probabilité qu'une adresse donnée soit choisie.

Si x données parmi r hachent la même adresse on a x fois B et (r-x) fois A. La probabilité pour que x données parmi r hachent la même adresse est

Crx . ar-x bx

avec Crx = x! / (x! (r-x)!)

Ce qui veut aussi dire :

Probabilité qu'une adresse donnée soit choisie x fois et ne soit pas choisie r-x fois.

L'inconvénient de la formule est qu'elle est difficile à calculer pour N et r grands. La fonction de POISSON est une bonne approximation.

P(x) =/ f(x) = ( (r/N) x . e - (r/N) ) / x!

P(x) donne aussi la probabilité que x données hachent la même adresse parmi r données insérées.

En général, s'il existe N adresses, N.P(x) est le nombre de données qui hachent x fois la même adresse. P(x) est aussi la proportion d'adresses ayant x données qui lui sont attribuées par hachage.

Ceci nous permet donc de prévoir le nombre D de collisions.

D = N*( P(2) + 2*P(3) + 3*P(4) + 4* P(5) ......)

Le pourcentage des articles en débordement est : D/N

En guise de conclusion Il existe plusieurs façons de réduire les collisions :

- trouver une fonction qui distribue bien les données c'est a dire de façon aléatoire.

- augmenter l'espace des adresses possibles.

- mettre plus d'une donnée par adresse possible.