Hash Tablosu

#Nasıl çalışır?

Hash tablosu (hash table), anahtarları bir hash fonksiyonuyla bir dizi indeksine dönüştürerek saklar. Bir anahtarı aramak için bütün veriyi gezmek gerekmez: hash hesaplanır ve doğrudan ilgili kovaya (bucket) gidilir.

Farklı anahtarlar aynı kovaya düşebilir; buna çakışma (collision) denir. Bu derste kullanılan ayrı zincirleme (separate chaining) yönteminde her kova, kendisine düşen anahtarların küçük bir listesini tutar.

İyi bir hash fonksiyonu anahtarları kovalara eşit dağıtır. Böylece zincirler kısa kalır ve ekleme, arama, silme ortalamada sabit sürede yapılır.

#Kendin dene

#Temel işlemler

insert(key)

hash(key) ile kovayı bulur; anahtar orada yoksa zincirin sonuna ekler.

search(key)

Yalnızca hash(key) kovasındaki zinciri tarar.

remove(key)

Anahtarı kovasının zincirinde bulup çıkarır.

yük faktörü (load factor)

Eleman sayısı / kova sayısı. Belirli bir sınırı (ör. 0,75) geçince tablo büyütülür ve tüm anahtarlar yeniden hash'lenir.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

class HashSet:
    """Separate chaining: each bucket is a list of the keys that hash to it."""

    def __init__(self, bucket_count: int) -> None:
        self.buckets: list[list[int]] = [[] for _ in range(bucket_count)]

    def _hash(self, key: int) -> int:
        return key % len(self.buckets)

    def contains(self, key: int) -> bool:
        return key in self.buckets[self._hash(key)]

    def add(self, key: int) -> None:
        if not self.contains(key):
            self.buckets[self._hash(key)].append(key)

    def remove(self, key: int) -> None:
        chain = self.buckets[self._hash(key)]
        if key in chain:
            chain.remove(key)


s = HashSet(7)
for key in (15, 8, 22, 31):  # 15, 8 and 22 all hash to bucket 1
    s.add(key)

print(str(s.contains(22)).lower())
s.remove(8)
print(str(s.contains(8)).lower())
print(*s.buckets[1])

#Karmaşıklık

Ortalama O(1), yük faktörü düşük tutulduğu ve hash fonksiyonu iyi dağıttığı sürece geçerlidir. Bütün anahtarlar aynı kovaya düşerse tablo bir bağlı listeye dönüşür ve işlemler O(n) olur. Büyütme işlemi tek seferde O(n) sürse de seyrek yapıldığı için eleman başına maliyeti sabittir (amortize O(1)).

#Ne zaman kullanılır?

Anahtarla hızlı erişim gereken her yerde: sözlükler ve kümeler (Python dict/set, Java HashMap, JavaScript Map/Set), önbellekler, sayaçlar, tekrar kontrolü. Elemanların sıralı gezilmesi ya da aralık sorguları gerekiyorsa dengeli ağaçlar daha uygundur.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Rabin-Karp Algoritması