Comment les tables de hachage optimisent-elles les algorithmes ?

Question

Accepted Answer

Une **table de hachage** (dictionnaire) offre des recherches, insertions et suppressions en **O(1) en moyenne**. Échanger O(n) de mémoire pour de la vitesse transforme de nombreux algorithmes O(n²) en O(n) en remplaçant les analyses répétées par des recherches instantanées.

## L'idée

Au lieu de chercher dans une liste à chaque fois, stockez les valeurs vues dans une table de hachage et vérifiez l'appartenance en temps constant.

## Exemple : two-sum en O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Sans la table, c'est O(n²) ; avec elle, un seul passage.

## Utilisations courantes

- **Déduplication / appartenance** avec un ensemble.
- **Comptage de fréquences** (`Counter`).
- **Regroupement / indexation** par clé.
- **Mise en cache / mémoïsation** des résultats.

## Complexité

- **Moyenne :** O(1) par opération. **Pire cas :** O(n) en cas de collisions massives. **Espace :** O(n).

## Pièges

Les clés doivent être **hachables** et immuables. Les collisions dans le pire cas dégradent les performances. Les tables de hachage sont non ordonnées (utilisez des variantes ordonnées si l'ordre importe).

## Pourquoi c'est important

Le hachage est l'optimisation unique la plus courante dans les entretiens de codage et les systèmes réels — il transforme « chercher encore et encore » en « chercher une fois ».

L'échange espace-pour-temps est un levier d'ingénierie récurrent.

Le comptage de fréquences, la mise en cache et l'indexation reposent tous sur cette unique idée.