Deux clés distinctes peuvent être hachées vers le même bucket — une collision. Les tables de hachage restent O(1) en moyenne en résolvant les collisions et en se redimensionnant avant que les buckets ne deviennent trop remplis, contrôlé par le facteur de charge.
Separate chaining: each bucket holds a list
[3] -> ("cat",9) -> ("rat",2) # both hashed to 3
Open addressing: probe to the next free slot
hash=3 taken -> try 4 -> try 5 ... (linear probing)
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
-> allocate a bigger array (usually 2x)
-> REHASH every existing key into new buckets
# Conceptual resize
def _resize(self):
old = self.buckets
self.buckets = [None] * (len(old) * 2)
for entry in all_entries(old):
self._insert(entry.key, entry.value) # rehash into new array
| Opération | Moyenne | Pire cas |
|---|---|---|
| recherche / insertion / suppression | O(1) | O(n) |
| redimensionnement unique | — | O(n) |
| insertion (amortie, avec redimensionnement) | O(1) | — |
Un redimensionnement est O(n) mais se produit rarement, donc il s'amortit à O(1) par insertion.
Ces détails internes expliquent pourquoi les tables de hachage sont rapides en moyenne mais peuvent monter en flèche à O(n) — crucial pour le code sensible aux performances et les défenses contre les entrées adversariales (hash-flooding).
Comprendre le facteur de charge explique aussi les boutons de réglage mémoire/vitesse exposés par les vraies bibliothèques.