Gestion des collisions dans les Tables de Hachage

Introduction aux Collisions

Dans une table de hachage, une collision se produit lorsque deux clés différentes, après application de la fonction de hachage, produisent la même adresse (indice) dans le tableau sous-jacent. Imaginez un cas simple : vous avez une table de hachage de taille 10. La fonction de hachage, pour simplifier, retourne la dernière décimale de la clé. Ainsi, les clés 12, 22, 32 vont toutes à la même position (2) dans la table. C'est une collision.

La performance d'une table de hachage est grandement affectée par le nombre de collisions. Un grand nombre de collisions peut transformer une recherche en O(1) (temps constant) en une recherche en O(n) (temps linéaire), où n est le nombre d'éléments dans la table. Il est donc crucial de bien gérer les collisions pour maintenir l'efficacité de la table.

Méthode 1 : Chaînage Séparé (Separate Chaining)

Le chaînage séparé est une méthode de gestion des collisions où chaque case du tableau de la table de hachage pointe vers une liste chaînée (ou une autre structure de données, comme un arbre binaire de recherche équilibré). Lorsque deux clés entrent en collision, le nouvel élément est simplement ajouté à la liste chaînée de la case correspondante.

Fonctionnement :

1. Insertion : Calculer l'indice avec la fonction de hachage. Insérer le nouvel élément en tête (ou en queue) de la liste chaînée à cet indice.
2. Recherche : Calculer l'indice avec la fonction de hachage. Parcourir la liste chaînée à cet indice pour trouver la clé recherchée.
3. Suppression : Calculer l'indice avec la fonction de hachage. Parcourir la liste chaînée à cet indice et supprimer l'élément si trouvé.

Avantages :

• Simple à implémenter.
• Peut gérer un grand nombre de collisions (si les listes chaînées sont raisonnablement courtes).
• La table de hachage peut contenir plus d'éléments que sa taille sans problème immédiat.

Inconvénients :

• Utilise de la mémoire supplémentaire pour les listes chaînées.
• La performance se dégrade si certaines listes chaînées deviennent trop longues (tendance vers O(n)).

Exemple : Supposons une table de hachage de taille 5 et une fonction de hachage simple : h(clé) = clé % 5. Nous voulons insérer les clés 12, 22, 32, 17, 5, 15.

Voici comment la table évoluerait avec le chaînage séparé :

• Indice 2 : 32 -> 22 -> 12
• Indice 2 : 17 -> 2
• Indice 0 : 15 -> 5

Les autres indices (0, 1, 3, 4) seraient vides ou contiendraient d'autres listes chainées selon les autres insertions.

Méthode 2 : Adressage Ouvert (Open Addressing)

L'adressage ouvert est une autre méthode de gestion des collisions où tous les éléments sont stockés directement dans le tableau de la table de hachage. En cas de collision, on cherche une autre case vide dans le tableau en utilisant une technique de sondage.

Techniques de sondage courantes :

1. Sondage Linéaire (Linear Probing) : En cas de collision à l'indice i, on vérifie les indices i+1, i+2, i+3, ... jusqu'à trouver une case vide.
2. Sondage Quadratique (Quadratic Probing) : En cas de collision à l'indice i, on vérifie les indices i+1², i+2², i+3², ... jusqu'à trouver une case vide.
3. Double Hachage (Double Hashing) : On utilise une deuxième fonction de hachage h₂(clé) pour déterminer l'intervalle de sondage. En cas de collision à l'indice i, on vérifie les indices i + h₂(clé), i + 2 * h₂(clé), i + 3 * h₂(clé), ... jusqu'à trouver une case vide.

Fonctionnement :

1. Insertion : Calculer l'indice avec la fonction de hachage. Si la case est vide, insérer l'élément. Sinon, utiliser la technique de sondage pour trouver une case vide et y insérer l'élément.
2. Recherche : Calculer l'indice avec la fonction de hachage. Si la clé est présente, on l'a trouvée. Sinon, utiliser la même technique de sondage que lors de l'insertion pour parcourir les cases et trouver la clé (ou arriver à une case vide, signifiant que la clé n'est pas présente).
3. Suppression : La suppression est plus complexe. On ne peut pas simplement vider la case, car cela pourrait interrompre les chaînes de sondage pour d'autres clés. On utilise souvent une valeur spéciale (par exemple, SUPPRIMÉ) pour marquer une case comme supprimée. Lors de la recherche, on continue le sondage même si on rencontre une case marquée SUPPRIMÉ.

Avantages :

• Utilise moins de mémoire que le chaînage séparé (pas besoin de listes chaînées).

Inconvénients :

• Plus complexe à implémenter que le chaînage séparé.
• Peut souffrir de clustering (regroupement) : si beaucoup de clés ont des indices de hachage proches, les sondages peuvent créer de longues séquences de cases occupées, ralentissant les recherches et les insertions. Le sondage linéaire est particulièrement sensible au clustering.
• La performance se dégrade fortement lorsque la table devient presque pleine. Il est important de redimensionner la table (rehashing) lorsque le facteur de charge (nombre d'éléments / taille de la table) devient trop élevé.
• La suppression est plus complexe.

Exemple : Sondage Linéaire

Table de hachage de taille 5, fonction de hachage h(clé) = clé % 5. Insérer les clés 12, 22, 32, 17.

1. 12 : h(12) = 2. Table[2] = 12.
2. 22 : h(22) = 2. Collision. On regarde Table[3]. Elle est vide. Table[3] = 22.
3. 32 : h(32) = 2. Collision. On regarde Table[3]. Occupée. On regarde Table[4]. Elle est vide. Table[4] = 32.
4. 17 : h(17) = 2. Collision. On regarde Table[3]. Occupée. On regarde Table[4]. Occupée. On regarde Table[0]. Elle est vide. Table[0] = 17.

La table résultante :

• Table[0] = 17
• Table[1] = (vide)
• Table[2] = 12
• Table[3] = 22
• Table[4] = 32

Choisir la Bonne Méthode

Le choix entre le chaînage séparé et l'adressage ouvert dépend de plusieurs facteurs :

• Utilisation de la mémoire : L'adressage ouvert utilise généralement moins de mémoire si l'on est certain que le nombre d'éléments à stocker ne dépassera pas de beaucoup la taille de la table. Si le nombre d'éléments peut être imprévisible, le chaînage séparé est plus sûr.
• Complexité de l'implémentation : Le chaînage séparé est plus simple à implémenter.
• Performance : Si les collisions sont rares et que la table n'est pas trop pleine, l'adressage ouvert peut être plus rapide car il n'y a pas de surcharge liée aux listes chaînées. Si les collisions sont fréquentes, le chaînage séparé peut être plus performant si les listes chaînées restent courtes.

En pratique, le chaînage séparé est souvent préféré pour sa simplicité et sa robustesse, tandis que l'adressage ouvert peut être utilisé lorsque la mémoire est une contrainte importante et que l'on peut estimer raisonnablement le nombre d'éléments.

Ce qu'il faut retenir

• Collision : Se produit lorsque deux clés différentes produisent le même indice dans une table de hachage.
• Chaînage Séparé : Chaque case de la table pointe vers une liste chaînée contenant les éléments ayant le même indice. Simple à implémenter, mais utilise plus de mémoire.
• Adressage Ouvert : Tous les éléments sont stockés directement dans la table. Utilise des techniques de sondage (linéaire, quadratique, double hachage) pour trouver une case vide en cas de collision. Plus complexe, peut souffrir de clustering.
• Choisir la Méthode : Chaînage séparé pour la simplicité et la robustesse, adressage ouvert pour économiser la mémoire si le nombre d'éléments est prévisible.