Du skirtingi raktai gali būti maišyti į tą patį indą — tai susidūrimas. Maišos lentelės išlaiko O(1) vidurkiu, išsprendę susidūrimus ir iš naujo nustatydami dydį prieš kol indai tampa per daug užpildyti. Šiuo procesu vadovauja apkrovos koeficientas.
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
| Operacija | Vidurkis | Blogiausias atvejis |
|---|---|---|
| paieška / įterpimas / trynimas | O(1) | O(n) |
| vienas dydžio pakeitimas | — | O(n) |
| įterpimas (amortizuotas, su dydžio pakeitimu) | O(1) | — |
Dydžio pakeitimas yra O(n), bet įvyksta retai, todėl jis amortizuojasi į O(1) per įterpimą.
Šie vidiniai mechanizmai paaiškina, kodėl maišos žemėlapiai yra greit vidutiniškai, tačiau gali staigiai padidėti iki O(n) — tai svarbiausia veiklos jautriam kodui ir apsaugai nuo priešiško įvesties (maišų potvynio).
Supratimas apie apkrovos koeficientą taip pat paaiškina atminties ir greičio reguliavimo nustatymus, kuriuos eksponuoja tikros bibliotekos.