Hash table nasıl çalışır? Çakışmalar (collision) nasıl çözülür?

Hash table, anahtarı bir hash fonksiyonu ile sayıya çevirip dizide bir indekse (hash(key) % kapasite) eşler. Bu sayede ortalama O(1) ekleme, arama ve silme sağlar.

Çakışma, iki farklı anahtarın aynı indekse düşmesidir. Kapasite sınırlı olduğu için kaçınılmazdır.

1. Separate chaining (zincirleme)

Her kova (bucket) bir liste tutar; aynı indekse düşenler listeye eklenir.

class HashMap:
    def __init__(self, cap=8):
        self.buckets = [[] for _ in range(cap)]

    def put(self, key, val):
        b = self.buckets[hash(key) % len(self.buckets)]
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, val); return
        b.append((key, val))

    def get(self, key):
        b = self.buckets[hash(key) % len(self.buckets)]
        for k, v in b:
            if k == key: return v
        raise KeyError(key)

Java'nın HashMap'i bir kovada eleman sayısı çok artınca listeyi dengeli ağaca çevirir.

2. Open addressing (açık adresleme)

Tüm elemanlar dizide durur; dolu indekse denk gelinirse başka bir boş yer aranır:

• Linear probing: i+1, i+2, ... (önbellek dostu ama kümelenme olur)
• Quadratic probing, double hashing

Silmede "tombstone" işareti gerekir, yoksa arama zinciri kopar. Python dict açık adresleme kullanır.

Load factor ve yeniden boyutlandırma

load factor = eleman sayısı / kapasite. Eşik aşılınca (ör. 0.75) kapasite genelde iki katına çıkarılır ve tüm elemanlar yeniden hash'lenir: tek seferde O(n), ama amortize O(1).

En kötü durumda (her şey aynı kovaya düşerse) işlemler O(n) olur; iyi hash fonksiyonu anahtarları düzgün dağıtmalıdır.