De quoi se compose une table de hachage?

Une table de hachage se compose d'un tableau de taille fixe (seau ou slot) et d'une fonction de hachage.

• Tableau (Seaux/Slots): Représente une séquence de cellules où sont stockées des paires "clé-valeur". La taille du tableau détermine le nombre d'emplacements possibles pour stocker des éléments.

• Fonction de hachage: Transforme la clé en une valeur entière (code de hachage), utilisée pour déterminer l'indice de la cellule dans le tableau (seau), où la valeur correspondante sera stockée ou extraite.

De plus, il peut y avoir:

• Stratégie de résolution des collisions: Mécanisme pour gérer les situations où différentes clés génèrent le même code de hachage et pointent vers la même cellule du tableau. Stratégies courantes:
  • Méthode de chaînage (Chaînage séparé): Chaque cellule du tableau stocke un pointeur vers une liste chaînée (ou une autre structure de données), contenant toutes les paires "clé-valeur" dont les codes de hachage pointent vers cette cellule.
  • Méthode d'adressage ouvert: En cas de collision, une recherche d'une cellule libre dans le tableau est effectuée selon une règle déterminée (par exemple, sondage linéaire ou quadratique).