Qu'est-ce qu'une table de hachage et comment réalise-t-elle une recherche en O(1) ?

Question

Accepted Answer

Une **table de hachage** (hash map) stocke des paires **clé → valeur** et offre un insert, une recherche et une suppression en **O(1) en moyenne**. Elle fonctionne en exécutant chaque clé à travers une **fonction de hachage** qui la mappe vers un index dans un tableau sous-jacent (un « bucket »).

## Fonctionnement

```text
key "cat" --hash()--> 3   buckets:
key "dog" --hash()--> 0     [0] -> ("dog", 5)
                            [1]
                            [2]
                            [3] -> ("cat", 9)
```

## Exemple

```python
phone = {}
phone['alice'] = 555_1234   # insert -> hash 'alice' to a bucket
num = phone['alice']        # lookup -> hash again, jump to bucket
del phone['alice']          # delete
'bob' in phone              # membership -> O(1) average
```

## Complexité

| Opération | Moyenne | Pire cas |
|---|---|---|
| insert | O(1) | O(n) |
| lookup | O(1) | O(n) |
| delete | O(1) | O(n) |

Le **pire cas** O(n) se produit quand de nombreuses clés entrent en collision dans le même bucket.

## Compromis

- **Points forts :** accès extrêmement rapide par clé ; clés flexibles.
- **Points faibles :** pas d'ordre des clés ; mémoire supplémentaire ; pire cas O(n) ; nécessite une bonne fonction de hachage.

## Pourquoi c'est important

Les tables de hachage sont probablement la structure la plus utilisée en pratique — derrière les dictionnaires, les ensembles, les caches, les index de base de données et la déduplication.

Remplacer un scan linéaire par une recherche par hachage est l'une des façons les plus courantes de transformer un algorithme O(n²) en O(n).