Les tables de hachage

Introduction du cours

Bonjour à tous et bienvenue dans ce modeste tutoriel ! Aujourd'hui nous allons explorer et décortiquer une structure de donnée particulière : les tables de hachage ! Au programme : à quoi cela sert, comment cela fonctionne, une rapide analyse sur les temps d'exécutions et en prime une implémentation en Java (que le monde est bien fait :p ).

Pour aborder ce tutoriel, il n'est pas nécessaire d'avoir des connaissances particulières sur les structures de données, nous allons reprendre tout depuis zéro. En soit, le concept est facile...

... néanmoins je ne détaillerai pas les mécanismes de Java et de la POO utilisés pour l'implémentation (ce qui explique le niveau intermédiaire), le tutoriel de cysboy le fera mieux de toute façon ;) . Sachez juste que j'utiliserai des exceptions et des interfaces.

Bonne lecture !

Note : j'ai choisi Java comme langage par facilité et afin de donner des pistes simples d'accès vers un autre langage comme le C ou le C++. Il faut savoir que Java intègre déjà du code pour les tables de symbole (notamment une interface), et même une implémentation. Nous n'allons pas aborder ces objets existants, vu que le but est de comprendre et recréer les mécanismes internes en partant de rien ;) .

Les tables de symboles : maps et dictionnaires

Avant de commencer, un petit rappel sur le type de donnée abstrait que sont les tables de symboles. Le but du jeu est en fait de stocker des paires "clé-valeur" et de pouvoir y accéder efficacement, en utilisant seulement la clé. Un exemple sera plus parlant :) .

Imaginez un répertoire dans un téléphone portable : la clé serait le nom du contact tandis que la valeur serait le numéro de téléphone. Ou encore un dictionnaire, où vous associez un mot à une définition. Dans les deux cas, vous cherchez une clé (un nom/mot) pour retrouver une information (le numéro de téléphone/la définition).

(Avouez-le, vous êtes jaloux de ne pas avoir Chuck Norris dans vos contacts :p .)

Autre exemple, qui parlera plus aux webmasters et programmeurs PHP : les news des sites web. Chacune possède un numéro d'identification unique qui permet de les distinguer, c'est la clé (le fameux champ 'id' du tutoriel de M@teo21), le reste de la news (titre, contenu, etc) étant la valeur associée. Pour les autres qui ne voient pas trop de quoi je parle, vous pouvez également penser au PID que les systèmes d'exploitation assignent aux programmes chargés en mémoire.

(Extrait de phpMyAdmin.)

Les plus curieux d'entre vous auront peut être remarqué le tableau ci-dessous, dans l'onglet "Structure" d'une table SQL dans phpMyAdmin (pour le voir, il est possible que vous deviez cliquer sur un lien "Détails").

En fait, c'est la configuration de la structure de table de symbole de la table ! On peut voir que la clé est le champ 'id', qu'il y a 6 éléments (c'est la cardinalité), que la clé est unique et que le type de structure de donnée est un B-tree.

Map ou dictionnaire ?

C'est ici que parmi les tables de symboles on distingue deux types : les tables associatives (maps en anglais) et les dictionnaires. Ce sont exactement les mêmes structures avec une légère différence (mais de taille !) : les clés des maps sont uniques tandis que celles d'un dictionnaire ne le sont pas nécessairement. Cela peut paraître anodin, mais dans nos exemples c'est hyper important !

Ainsi, le répertoire téléphonique est un dictionnaire : vous pourriez très bien avoir deux contacts qui portent le même nom, mais qui ont des numéros différents. Ou bien vous pourriez associer à une même personne plusieurs numéros, par exemple son téléphone fixe et son téléphone portable. Un dictionnaire est également un... dictionnaire ( :D ) puisque certains mots peuvent avoir plusieurs significations.

A l'opposé, l'unicité des id des news d'un site et des PIDs est primordiale ; imaginez que deux news possèdent le même id, comment savoir laquelle consulter ? Cela serait pire avec les PIDs ; si vous voulez terminer un programme avec un PID qui n'est pas unique, comment faire la différence ?

Cette distinction est très importante lorsqu'on programmera les tables de hachage, pensez y car le comportement est radicalement différent !

Mode d'emploi

Définissons à présent l'interface d'une table de symbole, autrement dit ce que l'on peut faire avec ; on a les méthodes suivantes :

• put(clé, valeur) : permet d'ajouter une paire "clé-valeur" ;

• get(clé) : comme son nom l'indique, retourne la valeur associée à une clé ;

• remove(clé) : je ne vous le cache pas plus longtemps, supprime une paire ;

• contains(clé) : retourne vrai si la clé se trouve dans la table, faux sinon ;

• size() : retourne le nombre de paires entrées dans la table.

Il existe d'autres opérations sur les clés, comme min qui retourne la plus petite clé, mais vu que les tables de hachage ne sont pas efficaces ni pratiques pour les réaliser, nous n'en discuterons pas.

Voici l'interface Java que nous nous amuserons à implémenter par la suite :

public interface SymbolTable { public void put(int key, Object value) throws HashTableException; public Object get(int key) throws HashTableException; public void remove(int key) throws HashTableException; public boolean contains(int key); public int size(); }

Les exceptions sont là "pour faire propre", si vous reprenez cette interface vous n'êtes pas obligé de les utiliser (même si cela reste plus élégant que des valeurs particulières ;) ). Pour ceux que cela intéresse, voici le code Java de cette exception.

public class HashTableException extends Exception { public HashTableException() { super() ; } public HashTableException(String s) { super(s); } } Implémentations

Il existe plusieurs manières d'implémenter ces méthodes : on peut citer un tableau, une liste liée, un arbre, ou encore... une table de hachage :) .

Pour maintenir le suspens, nous n'allons parler des temps d'exécution qu'à la fin de ce tutoriel, car les tables de hachage ont des performances extrêmement variables selon les situations, notamment à cause du mécanisme interne utilisé. Quand nous aurons vu les manières de concevoir une table de hachage, vous comprendrez tout de suite ;) .

Le principe des tables de hachage

Rentrons enfin dans le vif du sujet : que sont ces fameux tables de hachage ? Derrière ce nom un peu barbare se cache un mécanisme très simple : les paires "clé-valeur" sont placées dans un tableau de manière efficace. En fait, au lieu de les ajouter l'une après l'autre comme on aurait tendance à faire dans un tableau, on va les éparpiller le plus uniformément possible.

Un peu de vocabulaire : le tableau porte généralement le nom de bucket array tandis que les cases, vides ou occupées, sont les buckets.

Bien évidemment, on ne va pas les mettre n'importe comment, sinon on ne saura plus les retrouver :p . Les indices de chaque paire sont déterminés par le hach code de la clé, qui est donné par une fonction de hachage. Oui, je sais, ces mots font peur, mais vous verrez que ce n'est pas si terrible que ça !

Une histoire de hach code

Pour faire simple, le hach code d'un objet ou d'une variable est un entier qui lui est associé et qui est idéalement propre à chaque élément. C'est le résultat d'une fonction de hachage, on dit qu'elle hache l'élément.

On pourrait faire tout un cours sur les fonctions de hachage (Artefact2 en a même fait un tutoriel), mais pour rester simple une bonne fonction de hachage (que l'on va appeler

dans le reste de ce tutoriel) doit respecter les deux conditions suivantes :

• si deux clés sont identiques, leur hachage l'est aussi ; si

  , alors

  ;

• les hach codes doivent être tous uniques ; si

  , alors

La première condition est obligatoire, mais est assez facile à faire respecter, tandis que la seconde est beaucoup plus difficile à mettre en pratique (surtout dans le cas des tables de hachage).

En effet, les tables de hachage utilisent le hach code pour placer une paire dans un tableau, mais ce code peut potentiellement prendre n'importe quelle valeur (généralement de

à

). Il va donc falloir le compresser, c'est-à-dire le borner aux indices du tableau. On utilise pour cela une fonction de compression (que l'on va ici noter

). Ainsi, l'indice d'un élément i, qui sera donné par la fonction

, est défini ainsi :

Par exemple, imaginons que j'ajoute le numéro de téléphone Jean-Paul Belmondo (pourquoi pas ^^ ). L'ajout se déroulera selon le schéma ci-dessous.

Exemple avec des chiffres

Illustrons le mécanisme que nous allons implémenter avec un petit exemple numérique, cela ne sera pas de trop ;) . Imaginons que l'on dispose des fonctions suivantes :

Pour ceux qui sont allergiques aux maths et/ou qui ne connaissent pas la fonction modulo (mod ou %), il s'agit du reste d'une division entière. Ici, par exemple, on a

,

et

On aimerait insérer les clés suivantes dans un tableau de 10 cases (les valeurs associées n'ont ici pas beaucoup d'importance, on va les laisser de côté) : 0, 4, 7 et 42(soyons fous :p ). En sortant la calculette, on obtient les résultats ci-dessous :

Clé

0

14

4

4

26

6

7

35

5

42

140

0

Par convention, pour ne pas confondre les clés et les indices dans du texte, les clés seront écrites en bleu gras.

Et si on place les clés dans un tableau, on a

Diablement simple, n'est-il pas ? ^^

Vous avez ici un exemple de mauvaise fonction de hachage. En effet, les clés sont regroupées en une grappe (que l'on appelle cluster en anglais) ; idéalement il devrait y avoir des cases vides entre 0, 4 et 7. Ce manque d'uniformité dans la répartition peut engendrer de sérieux problèmes, dont nous discuterons juste après. En attendant, ne reprenez pas cette fonction de hachage, elle n'est là que pour l'exemple :) .

Gestions des collisions

Tout paraît si beau, et pourtant un problème de taille peut survenir. Reprenons notre exemple, et imaginons que l'on veut insérer la clé 22. On a

et

, et c'est la cata : l'indice 0 est déjà occupé par 42 !

Lorsque deux clés différentes sont envoyées sur la même case, on dit qu'il y a collision, et il va falloir les gérer car plus le tableau sera rempli plus il y aura de chances d'en avoir une !

Plusieurs manières existent ; nous n'allons en voir que trois, très différentes mais faciles à implémenter :

• le sondage ;

• le double hachage ;

• le chaînage linéaire.

Des noms qui font peur, mais vous verrez ce n'est pas si difficile ;) .

Le sondage linéaireLe principe

Appelé probing en anglais, cette méthode est la plus intuitive : si on a une collision, à partir de l'indice, on parcourt le tableau jusqu'à trouver une case libre ! Les indices parcourus peuvent être écrits sous la forme suivante, avec M la taille du tableau,

la fonction de hachage-compression, et i un indice qui varie de 0 à M :

Ainsi, pour placer 22, vu que la case à l'indice 0 est occupée, on va vérifier en 1. C'est vide, on l'y insère !

Ajoutons la clé 30 ; on a

et

. La case 4 est occupée, on parcourt alors les indices jusqu'à trouver une case libre. La première case libre est en 7, on y met 30 !

Pour rechercher une clé, c'est le même principe : on va calculer son indice, puis on va descendre dans le tableau jusqu'à trouver la clé. Si on tombe sur une case vide, c'est que la clé n'existe pas (sinon on l'aurait rencontrée en chemin), idem si on revient au point de départ.

Une petite subtilité : la suppression

L'insertion de clés est relativement simple, mais c'est la suppression qui est délicate et qui peut rendre inefficace la recherche. Comme dit plus haut, on va descendre dans le tableau jusqu'à trouver la clé ou une case vide... Si la suppression rend une case vide sur le "chemin" à parcourir, alors on perdra l'accès à certaines clés !

Par exemple, imaginons qu'on supprime purement et...