Ufunguo mbili tofauti zinaweza hash kwenye ndoo sawa — mgongano. Jedwali la hash linabaki O(1) kwa wastani kwa kutatua miingiliano na kubadilisha ukubwa kabla ndoo zijae, iliyodhibitiwa na kipengele cha kupakia.
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
| Operesheni | Wastani | Kesi mbaya zaidi |
|---|---|---|
| kutafuta / kuingiza / kufuta | O(1) | O(n) |
| kubadilisha ukubwa mara moja | — | O(n) |
| kuingiza (iliyocezeshwa, na kubadilisha ukubwa) | O(1) | — |
Kubadilisha ukubwa ni O(n) lakini kinatokea mara chache, kwa hiyo inacezeshwa hadi O(1) kwa kuingiza.
Maelezo ya ndani haya yanafafanua kwa nini ramani za hash ni haraka kwa wastani lakini zinaweza kuruka hadi O(n) — muhimu kwa msimbo unaohisi utendaji na ulinzi dhidi ya ingizo la adui (kumwaga hash).
Kuelewa kipengele cha kupakia pia kunafafanua vitufe vya urekebishaji wa kumbukumbu/kasi vinavyowaziwa na maktaba halisi.