Két különböző kulcs ugyanabba az emmerbe hashelődhet — ez egy ütközés. A hash táblák az ütközések feloldásával és az átméretezéssel az **emmerek megduzzadása előtt O(1) maradnak átlagosan, amelyet a terhelési tényező szabályoz.
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
| Művelet | Átlag | Legrosszabb eset |
|---|---|---|
| lookup / insert / delete | O(1) | O(n) |
| egyetlen átméretezés | — | O(n) |
| insert (amortizált, átméretezéssel) | O(1) | — |
Az átméretezés O(n), de ritkán történik meg, így O(1) amortizálódik insertönként.
Ezek a belső részletek magyarázzák, miért olyan gyorsak az átlagban a hash térképek, mégis O(n)-re tudnak ugrani — döntő fontosságú a teljesítményre érzékeny kódhoz és az ellentétes bemenet (hash-flooding) elleni védelemhez.
A terhelési tényező megértése azt is elmagyarázza, milyen memória/sebesség hangolási gombokat mutatnak be az igazi könyvtárak.