İki farklı anahtar aynı bucket'a hash olabilir — bir çakışma. Hash tabloları çakışmaları çözerek ve bucket'lar kalabalık olmadan önce yeniden boyutlandırarak O(1) ortalama performansını korur, bunu yük faktörü kontrol eder.
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
| İşlem | Ortalama | En Kötü Durum |
|---|---|---|
| arama / ekleme / silme | O(1) | O(n) |
| tek yeniden boyutlandırma | — | O(n) |
| ekleme (amortize, yeniden boyutlandırma ile) | O(1) | — |
Yeniden boyutlandırma O(n) olsa da nadiren gerçekleşir, bu nedenle her ekleme için O(1) olarak amortize edilir.
Bu iç detaylar hash haritalarının neden ortalamada hızlı olduğunu ancak O(n)'ye sıçrayabileceğini açıklar — performansa duyarlı kod ve hasla taşma (hash-flooding) savunması için çok önemlidir.
Yük faktörünü anlamak, gerçek kütüphaneler tarafından sunulan bellek/hız ayarlama düğmelerini de açıklar.