Tables de hachage : fonction de hachage et collisions

Informatique de gestion · Bachelor 2

Fonctionnement des tables de hachage, gestion des collisions, facteur de charge et coûts.

Introduction

Une table de hachage associe des clés à des valeurs en visant un accès en temps constant en moyenne. Une fonction de hachage transforme la clé (numéro de client, code article) en un entier, puis en un indice dans un tableau de compartiments. C'est la structure sous-jacente des dictionnaires et des ensembles dans la plupart des langages : HashMap en Java, dict en Python.

Deux clés différentes peuvent donner le même indice : c'est une collision, inévitable puisque l'espace des clés est bien plus grand que celui des indices. On les traite par chaînage (chaque compartiment contient une liste) ou par adressage ouvert (on cherche un autre emplacement libre par sondage). La performance dépend du facteur de charge, rapport entre le nombre d'éléments et le nombre de compartiments : quand il dépasse un seuil, la table est agrandie et réorganisée.

En informatique de gestion, les tables de hachage servent aux index en mémoire, aux caches, à la détection de doublons dans des fichiers de clients ou aux jointures par hachage des moteurs de bases de données.

Objectifs d'apprentissage

Expliquer le principe de la fonction de hachage et ses propriétés souhaitables
Comparer le chaînage et l'adressage ouvert pour traiter les collisions
Définir le facteur de charge et expliquer le redimensionnement
Donner la complexité moyenne et le pire cas des opérations
Choisir entre table de hachage et structure ordonnée selon le besoin

Concepts clés

Fonction de hachage: Fonction déterministe qui répartit les clés de façon uniforme sur les indices du tableau ; deux clés égales doivent donner le même hachage.
Chaînage: Chaque compartiment contient une liste des éléments dont la clé donne cet indice ; simple, mais coûteux en mémoire.
Adressage ouvert: En cas de collision, on teste d'autres cases (sondage linéaire, quadratique, double hachage) dans le tableau lui-même.
Facteur de charge: Nombre d'éléments divisé par le nombre de compartiments ; au-delà d'un seuil, on double la taille et on réinsère tous les éléments.

Conclusion

La table de hachage est le compromis classique entre rapidité et simplicité : accès en temps constant moyen, au prix de la perte d'ordre et d'une dépendance à la qualité du hachage.

Savoir expliquer collisions, facteur de charge et pire cas permet de choisir à bon escient entre dictionnaire, ensemble ou structure ordonnée dans les applications de gestion.

Cartes

Quel est l'objectif d'une table de hachage ?: Retrouver, insérer et supprimer une valeur à partir de sa clé en temps constant en moyenne.
Qu'est-ce qu'une collision ?: Deux clés distinctes qui produisent le même indice dans le tableau.
Comment fonctionne le chaînage ?: Chaque case du tableau pointe vers une liste d'éléments partageant le même indice ; on parcourt cette liste pour retrouver la clé.
Comment fonctionne l'adressage ouvert ?: On stocke l'élément dans le tableau lui-même et, en cas de collision, on teste d'autres cases selon une séquence de sondage.
Qu'est-ce que le facteur de charge ?: Le rapport entre le nombre d'éléments stockés et le nombre de compartiments.
Pourquoi redimensionner la table ?: Un facteur de charge élevé augmente les collisions ; on agrandit le tableau et on recalcule les indices (rehachage) pour garder des accès rapides.
Quel est le coût moyen d'une recherche ?: O(1) en moyenne avec une bonne fonction de hachage et un facteur de charge maîtrisé.
Quel est le coût dans le pire cas ?: O(n) si toutes les clés tombent dans le même compartiment (mauvaise fonction ou attaque par collisions).
Pourquoi les clés doivent-elles être immuables ?: Si la clé change, son hachage change et l'élément devient introuvable dans le compartiment où il avait été placé.
Quel inconvénient par rapport à un arbre équilibré ?: Aucun ordre sur les clés : pas de parcours trié ni de recherche par intervalle efficace.

Glossaire

Fonction de hachage: Fonction qui transforme une clé en entier utilisé pour calculer un indice.
Compartiment (bucket): Case de la table qui accueille les éléments d'un même indice.
Collision: Situation où deux clés différentes ont le même indice.
Sondage: Séquence de cases testées en adressage ouvert après une collision.
Facteur de charge: Rapport éléments / compartiments qui conditionne le taux de collisions.
Rehachage: Recalcul de tous les indices après agrandissement de la table.