Tables de Hachage (Hash Maps) : Comment ça marche et quand les utiliser ?

Introduction aux tables de hachage

Une table de hachage (ou hash map, dictionnaire) est une structure de données qui associe des clés à des valeurs. Elle permet d'effectuer des opérations d'insertion, de recherche et de suppression en temps O(1) en moyenne — ce qui en fait l'une des structures les plus utilisées en programmation compétitive.

Comment fonctionne une table de hachage ?

Le principe est simple : une fonction de hachage transforme une clé (par exemple une chaîne de caractères ou un entier) en un indice dans un tableau interne.

On calcule indice = hash(clé) % taille_tableau.
On stocke la valeur à cet indice.
Pour retrouver une valeur, on recalcule le même indice.

Le problème des collisions

Deux clés différentes peuvent produire le même indice — c'est une collision. Les stratégies courantes pour les gérer :

Chaînage (chaining) : chaque case du tableau contient une liste chaînée de paires clé/valeur.
Adressage ouvert (open addressing) : en cas de collision, on cherche la prochaine case libre.

Complexité

Opération	Cas moyen	Pire cas
Insertion	O(1)	O(n)
Recherche	O(1)	O(n)
Suppression	O(1)	O(n)

Le pire cas se produit quand de nombreuses collisions ont lieu, ce qui est rare avec une bonne fonction de hachage.

Utilisation en Python : les dictionnaires

En Python, les tables de hachage sont nativement disponibles via le type dict :


# Compter les occurrences de chaque lettre
texte = "programmation"
compteur = {}

for lettre in texte:
    if lettre in compteur:
        compteur[lettre] += 1
    else:
        compteur[lettre] = 1

print(compteur)

# Encore plus simple avec defaultdict
from collections import defaultdict
compteur2 = defaultdict(int)
for lettre in texte:
    compteur2[lettre] += 1

Utilisation en C++ : unordered_map


#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;

    // Recherche
    if (scores.count("Alice")) {
        cout << "Score d'Alice : " << scores["Alice"] << endl;
    }

    // Parcours
    for (auto& pair : scores) {
        cout << pair.first << " : " << pair.second << endl;
    }
    return 0;
}

Cas d'utilisation typiques en compétition

Compter des occurrences (fréquence de lettres, de mots, d'éléments).
Vérifier l'existence d'un élément rapidement (appartenance à un ensemble).
Mémoïsation pour les algorithmes de programmation dynamique.
Détection de doublons dans un tableau.
Two-sum : trouver deux éléments dont la somme vaut une cible.

Différence entre map et unordered_map en C++

Critère	map	unordered_map
Structure interne	Arbre rouge-noir	Table de hachage
Complexité recherche	O(log n)	O(1) moyen
Ordre des clés	Trié	Non trié
À utiliser quand	Ordre nécessaire	Vitesse maximale

Conclusion

Les tables de hachage sont incontournables en programmation compétitive. Dès que vous avez besoin de retrouver ou compter des éléments rapidement, pensez-y en premier. Maîtrisez les dict Python et unordered_map C++ et vous résoudrez de nombreux problèmes bien plus efficacement.