Dva odlišné klíče se mohou hashovat na stejný bucket — kolizi. Tabulky hash zůstávají v průměru O(1) řešením kolizí a změnou velikosti před tím, než se buckety přeplní, kontrolováno faktorem zatížení.
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
| Operace | Průměr | Nejhorší |
|---|---|---|
| vyhledávání / vložení / smazání | O(1) | O(n) |
| jednorázová změna velikosti | — | O(n) |
| vložení (amortizované, se změnou velikosti) | O(1) | — |
Změna velikosti je O(n), ale děje se zřídka, takže se amortizuje na O(1) na vložení.
Tyto interní detaily vysvětlují proč jsou mapy hash v průměru rychlé, ale mohou skočit na O(n) — zásadní pro kód citlivý na výkon a obrany před nepřátelskými vstupy (hash-flooding).
Chápání faktoru zatížení také vysvětluje knoflíky pro ladění paměti/rychlosti vystavené skutečnými knihovnami.