Două chei distincte pot face hash în același bucket — o coliziune. Tabelele hash rămân O(1) în medie prin rezolvarea coliziunilor și redimensionarea înainte ca bucket-urile să se umple, controlate de factorul de încărcare.
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
| Operație | Medie | Cel mai rău |
|---|---|---|
| căutare / inserție / ștergere | O(1) | O(n) |
| redimensionare unică | — | O(n) |
| inserție (amortizată, cu redimensionare) | O(1) | — |
O redimensionare este O(n) dar se întâmplă rar, deci se amortizează la O(1) per inserție.
Aceste detalii interne explică de ce harta hash-urilor sunt rapide în medie, dar pot crește la O(n) — crucial pentru cod sensibil la performanță și apărări împotriva intrării adversare (hash-flooding).
Înțelegerea factorului de încărcare explică, de asemenea, butoanele de reglare memorie/viteză expuse de biblioteci reale.