Comment est structurée une table de hachage dans le conteneur unordered_map?

unordered_map en C++ est implémenté comme une table de hachage.

Principe de fonctionnement:

1. Hachage: La clé est transformée en un entier — code de hachage — à l'aide d'une fonction de hachage.
2. Indexation: Le code de hachage est utilisé pour déterminer l'indice (seau ou bucket) dans un tableau de pointeurs ou de listes.
3. Stockage: Dans chaque seau, on stocke des paires clé-valeur.

Caractéristiques:

• Seaux: La table de hachage consiste en un tableau de seaux. Le nombre de seaux peut changer dynamiquement (re-hachage) lorsqu'un certain facteur de charge est atteint.
• Collisions: Différentes clés peuvent donner le même code de hachage. Cela s'appelle une collision. Pour résoudre les collisions, unordered_map utilise la méthode chaînage: les éléments avec le même hash sont ajoutés à une liste chaînée (ou autre structure de données) dans le seau correspondant.
• Fonction de hachage et fonction de comparaison: Pour un fonctionnement correct, deux choses sont nécessaires:
  • Une bonne fonction de hachage, qui répartit uniformément les clés dans les seaux, minimisant les collisions.
  • Une fonction d'égalité (l'opérateur ==), pour distinguer les clés avec le même code de hachage dans un même seau.
• Performance: En moyenne, les opérations d'insertion, de suppression et de recherche ont une complexité temporelle O(1). Dans le pire cas (par exemple, beaucoup de collisions ou une mauvaise fonction de hachage), la performance peut se dégrader à O(n), où n est le nombre d'éléments.

Exemple de structure (simplifié):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Pour liste chaînée dans le seau
};

struct Bucket {
  Node* head; // Pointeur au début de la liste
};

Bucket* buckets; // Tableau de seaux
size_t num_buckets;

Processus d'ajout d'un élément:

1. Le code de hachage de la clé est calculé.
2. L'indice du seau est déterminé: bucket_index = hash(key) % num_buckets.
3. Le couple clé-valeur est ajouté à la liste d'éléments dans ce seau. Si la clé existe déjà, la valeur est mise à jour.

Processus de recherche d'un élément:

1. Le code de hachage de la clé est calculé.
2. L'indice du seau est déterminé.
3. La liste d'éléments dans ce seau est parcourue, en comparant les clés avec la clé recherchée à l'aide de l'opérateur ==.

Le re-hachage se produit lorsque le nombre d'éléments par rapport au nombre de seaux dépasse un seuil (facteur de charge). Lors du re-hachage, un nouveau tableau de seaux plus grand est créé, et tous les éléments des anciens seaux sont re-hachés et déplacés vers les nouveaux.