Hash tabloları, collision ve load factor

Hash fonksiyonu anahtarı bir tamsayıya, tablo indeksi bunu bir bucket'a eşler. Eşit hash eşit anahtar demek değildir; anahtar eşitliği ayrıca kontrol edilir. Hashing, şifreleme değildir. Doğru map, collision olduğunda veriyi kaybetmez.

Chaining bucket'ta bir liste/tampon tutar. Open addressing elemanları tablo içinde probe dizisiyle arar: linear probing, quadratic probing ve double hashing farklı kümelenme davranışları gösterir. Silinmiş slotu tamamen boş yapmak probe zincirini koparır; tombstone veya uygun backshift gerekir. Load factor α=n/m arttıkça özellikle open addressing araması pahalılaşır; yeniden boyutlandırma tüm öğeleri tekrar yerleştirir.

İyi dağılım, sınırlı yük ve uygun hash varsayımlarıyla beklenen O(1) erişim elde edilir; en kötü durumda O(n) mümkündür. Uzun metnin hash'ini ilk kez hesaplamak anahtar uzunluğuna bağlıdır. Untrusted girdide hash-flooding tehdidini hesaba kat. Mutable anahtarın eşitlik/hash değerini yerleştirdikten sonra değiştirmek erişimi bozabilir.

Collision çözümünü elle izle

m=5 bucket için h(k)=k mod 5 olsun. 2,7,12 anahtarları aynı 2 bucket'ına düşer. Chaining listesinde arama üç karşılaştırmaya kadar çıkar. Open addressing'de linear probing bunları 2,3,4 slotlarına yerleştirebilir. Anahtar 7 silinince slot 3'ü sıradan EMPTY yapmak, 12 aramasını erken durdurur; DELETED tombstone ile arama sürmelidir.

Load factor α=n/m chaining'de 1'i aşabilir; open addressing'de boş slot gereklidir. Resize/re-hash mevcut elemanların yeni kapasitedeki konumunu yeniden hesaplar. Düzgün dağılım varsayımında expected O(1) ile saldırgan çakışmada O(n) worst-case aynı tabloda mümkündür. Hash randomization veya balanced-tree buckets gibi önlemler modele bağlıdır.

Equality ve hash tutarlı olmalıdır: eşit anahtarlar aynı hash üretmeli. Anahtarın equality'de kullanılan alanı tablodayken değişirse erişim bozulabilir. Hash değeri benzersiz kimlik değildir; collision equality kontrolüyle çözülür. Kriptografik hash farklı hedeflere sahiptir; dictionary hash'inden imza veya güvenli şifre saklama beklenmez.

Temel: 2,7,12 için insertion/search/delete trace çıkar. Orta: Tombstone doluluğunu da izleyen resize ölçütü kur. İleri: Key dağılımı ve adversarial input altında p95 latency ölç; “ortalama hızlı” iddiasının hangi rastgeleliğe dayandığını yaz.

def chain_insert(table, key, value):
    bucket = table[key % len(table)]
    for i, (k, _) in enumerate(bucket):
        if k == key:
            bucket[i] = (key, value)
            return
    bucket.append((key, value))
table = [[] for _ in range(5)]
chain_insert(table, 7, "A")
chain_insert(table, 12, "B")
assert len(table[2]) == 2