Comment fonctionne une table de hachage?

Une table de hachage (hash table) est une structure de données qui implémente un tableau associatif.

Principe de fonctionnement :

1. Hachage. Pour chaque clé (key), on calcule un code de hachage (hash code) à l'aide d'une fonction de hachage (hash function). Le code de hachage est un entier.
2. Indexation. Le code de hachage est utilisé pour déterminer un indice (index) dans le tableau (ou vecteur) de la structure interne de la table de hachage. Généralement, l'indice est calculé comme hash_code % taille_du_tableau, où taille_du_tableau est la taille du tableau.
3. Stockage. À l'indice trouvé, la valeur (value) associée à la clé est stockée.

Problèmes et solutions :

• Collisions. Différentes clés peuvent donner le même code de hachage et, par conséquent, le même indice dans le tableau. Cela s'appelle une collision.
  • Méthodes pour résoudre les collisions :
    • Méthode de chaînage (Separate Chaining) : Dans chaque cellule du tableau, on stocke une liste (liste, vecteur, etc.) de paires "clé-valeur". En cas de collision, la nouvelle paire est ajoutée à cette liste. Lors de la recherche par indice, on parcourt la liste correspondante pour trouver la clé désirée.
    • Méthode d'adressage ouvert (Open Addressing) : En cas de collision, on cherche une autre cellule libre dans le tableau selon une règle déterminée (sondage).
      • Sondage linéaire (Linear Probing) : On vérifie séquentiellement les cellules index + 1, index + 2, etc., modulo la taille du tableau.
      • Sondage quadratique (Quadratic Probing) : On vérifie les cellules index + 1^2, index + 2^2, etc., modulo la taille du tableau.
      • Double hachage (Double Hashing) : On utilise une seconde fonction de hachage pour déterminer le pas du sondage.

Avantages :

• En moyenne, les opérations d'insertion, de suppression et de recherche s'effectuent avec une complexité O(1).

Inconvénients :

• En pire cas (par exemple, beaucoup de collisions ou mauvaise fonction de hachage), la complexité peut atteindre O(n), où n est le nombre d'éléments.
• Nécessite de la mémoire supplémentaire (par exemple, pour les listes en méthode de chaînage ou pour le sondage en adressage ouvert).

Exemple d'utilisation en C++ (std::unordered_map) :

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Création de la table de hachage (unordered_map)
    std::unordered_map<std::string, int> ages;

    // Insertion d'éléments
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    // Récupération de la valeur par clé
    std::cout << "Âge de Alice : " << ages["Alice"] << std::endl;

    // Recherche d'un élément
    if (ages.count("Bob")) {
        std::cout << "Bob est dans la map." << std::endl;
    }

    // Suppression d'un élément
    ages.erase("Charlie");

    return 0;
}