Bölüm 12 · Simülasyon

Hash Tablosu Simülatörü

← Bölüm 12

Hash hesabı

hash(anahtar) = FNV-1a hash mod kapasite

İşlem adımları

  1. Henüz işlem yok.

Geçmiş

  1. Henüz işlem yok.

Hash Tablosu Simülatörü

Ayrı zincirleme kullanan hash tablosu: anahtar hash'lenerek bir kova indisine dönüştürülür ve her kova oraya düşen girdilerin zincirini (listesini) tutar.

Kullanım

  • Bir Anahtar ve Değer yazın. Ekle / Güncelle girdiyi ekler ya da var olan anahtarın değerini değiştirir; Ara ve Sil yalnızca anahtarı kullanır; Rastgele Ekle rastgele bir girdi ekler. En fazla 12 girdi sığar.
  • Kapasite başlangıç kova sayısını belirler; değiştirilince tablo boşaltılır (Temizle ve Örneği Yükle de bu değeri kullanır). Otomatik büyütme, yük faktörü 0,75'i aştığında kapasiteyi iki katına çıkarır.
  • Örneği Yükle örnek tabloyu geri getirir; İptal çalışan animasyonu durdurur; değişiklik henüz yapılmadıysa tablo olduğu gibi kalır, bekleyen bir büyütme varsa tamamlanır.

Hash fonksiyonu

FNV-1a tarzı hash: 2.166.136.261'den başlanır; her karakterin kodu XOR'lanır ve sonuç 16.777.619 ile çarpılır (32 bit). Kova indisi hash mod kapasite olur.

Notlar

  • İki anahtar aynı kovaya düştüğünde çakışma olur; yeni girdi, anahtarı zincirde bulunmadığı anlaşıldıktan sonra zincirin sonuna eklenir.
  • Yük faktörü λ = öğe sayısı / kapasite, ortalama zincir uzunluğudur.
  • Büyütme her girdiyi yeniden hash'ler (rehashing), çünkü indis kapasiteye bağlıdır.

Karmaşıklık

Ekleme, arama ve silme ortalama O(1 + λ) sürer; tüm anahtarlar tek kovaya düşerse O(n)'ye kötüleşir. Büyütme O(n) tutar ama seyrek olur; bu yüzden ekleme amortize O(1) kalır.