Hash Table Nasıl Çalışır?
Map ve Set yapılarını mümkün kılan hash fonksiyonu, bucket, collision ve load factor kavramlarını öğrenin.
Milyonlarca kullanıcı içinde e-posta adresine göre hızlı arama yapmak istiyoruz. Listeyi her seferinde dolaşmak O(n) sürer. Hash table, anahtarı doğrudan küçük bir saklama bölgesine eşleyerek ortalama O(1) erişim hedefler.
Parçalar ne işe yarar?
Hash function, anahtarı bir sayıya dönüştürür. Bu sayı kapasiteye göre bir bucket indeksine indirgenir. Aynı indekse düşen farklı anahtarlar collision oluşturur. Load factor, eleman sayısının bucket sayısına oranıdır; yükseldiğinde collision ihtimali artar.
const usersByEmail = new Map<string, User>();
usersByEmail.set(user.email, user);
const found = usersByEmail.get('onur@example.com');set, anahtar-değer ilişkisini ekler veya aynı anahtarın değerini günceller. get, anahtara karşılık gelen değeri bulur; yoksa undefined döner. has, değerle undefined arasındaki belirsizliği yaşamadan üyeliği kontrol eder. Set yalnızca benzersiz anahtarları tutar.
Collision nasıl çözülür?
Separate chaining, aynı bucket’taki kayıtları küçük bir koleksiyonda tutar. Open addressing, dolu konumda başka bir boş konum arar. İyi hash dağılımı ve kapasite yönetimi ortalama sabit zamanı korur. En kötü durumda çok sayıda anahtar aynı yere düşerse erişim O(n) olabilir.
Hash table ne zaman yanlış seçimdir?
Anahtarların sıralı gezilmesi veya aralık sorgusu gerekiyorsa yüksekliği kontrollü tutulan dengeli arama ağacı daha uygundur. En küçük öğeyi sürekli almak için kökünde en küçük değeri tutan min-heap, kelimeleri ortak başlangıç harflerine göre dallandıran trie ise prefix (ön ek) araması için düşünülebilir. Hash table hızlı eşitlik araması sağlar; doğal sıralama sağlamaz.
Hash fonksiyonuyla kriptografik hash aynı hedefe sahip değildir. Veri yapısındaki hash hızlı dağılım ister; parola saklama algoritması ise özellikle yavaş, salt destekli ve saldırıya dayanıklı olmalıdır.
Alıştırma
Bir metindeki kelime sıklıklarını Map<string, number> ile hesaplayın. get(word) ?? 0 ifadesinin olmayan kelime için başlangıç sayısını nasıl verdiğini açıklayın.