Två olika nycklar kan hasha till samma hink — en kollision. Hashtabeller förblir O(1) i genomsnitt genom att lösa kollisioner och ändra storlek innan hinkar blir överfulla, kontrollerat av lastfaktorn.
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
| Operation | Genomsnitt | Värsta fall |
|---|---|---|
| slå upp / infoga / ta bort | O(1) | O(n) |
| enstaka storleksförändring | — | O(n) |
| infoga (amorterad, med storleksförändring) | O(1) | — |
En storleksförändring är O(n) men inträffar sällan, så den amorteras till O(1) per infogning.
Dessa interna mekanismer förklarar varför hashkartor är snabba i genomsnitt men kan hoppa till O(n) — avgörande för prestandakänslig kod och försvar mot fientlig inmatning (hash-flood).
Att förstå lastfaktor förklarar också minne/hastighets-justeringsknappar som exponeras av riktiga bibliotek.