Hash Tabloları: Milyonlarca Veride Bir Şeyi Anında Bulmanın Matematiği

Aramanın Hızı Neden Önemli?

Telefonunuzda bir kişiyi ararken, uygulama rehberdeki binlerce kişiyi baştan sona taramaz. Bir web sitesi, milyonlarca kullanıcı arasından sizin hesabınızı milisaniyeler içinde bulur. Bu hız nereden geliyor? Cevabın büyük kısmı, bilgisayar biliminin en zarif fikirlerinden biridir: hash tablosu.

Önce alternatifin ne kadar yavaş olduğunu görelim. Sırasız bir listede bir öğeyi aramak, en kötü durumda tüm listeyi gezmek demektir. $n$ öğe varsa bu, ortalama $n/2$ karşılaştırma — yani liste büyüdükçe arama doğru orantılı yavaşlar. Buna $O(n)$ denir. Bir milyon kayıtta bu, milyonlarca adım olabilir.

Hash tablosunun vaadi çarpıcıdır: kayıt sayısı ne olursa olsun, arama ortalama olarak sabit sayıda adımda biter. Buna $O(1)$ denir. Bir milyon da olsa bir milyar da, ortalama hız değişmez. Peki bu nasıl mümkün?

Sihir: Anahtarı Adrese Çevirmek

Fikir aslında çok sezgiseldir. Diyelim ki adres bilgilerini saklayacaksınız. Verileri rastgele kutulara koyup sonra aramak yerine, her veriye, içeriğinden hesaplanan bir kutu numarası verirsiniz.

Bunu yapan şeye hash fonksiyonu denir. Hash fonksiyonu, herhangi bir veriyi (bir isim, bir kelime, bir numara) alıp onu bir sayıya — yani bir kutu adresine — dönüştürür. Örneğin çok basit bir hash, kelimedeki harflerin kodlarını toplayıp, kutu sayısına bölüp kalanını alabilir:

$h(\text{anahtar}) = (\text{harflerin toplamı}) \bmod m$

Burada $m$ kutu sayısıdır ve $\bmod$ "bölümünden kalan" demektir; bu, sonucu daima $0$ ile $m-1$ arasında tutar — yani geçerli bir kutu numarası verir.

Artık bir veriyi saklamak için: hash'ini hesaplayın, çıkan kutuya koyun. Aramak için: aynı hash'i hesaplayın, doğrudan o kutuya bakın. Tüm tabloyu gezmek yok; tek bir hesap ve tek bir bakış. İşte sabit zamanın sırrı bu.

Çakışma: İki Veri Aynı Kutuya Düşerse?

Burada kaçınılmaz bir sorun var. Farklı iki veri, aynı kutu numarasını üretebilir — buna çakışma denir. Aslında çakışmalar şaşırtıcı derecede sık olur. Ünlü doğum günü paradoksu, bunun ne kadar yaygın olduğunu gösterir: bir odada sadece $23$ kişi varsa, ikisinin aynı doğum gününe sahip olma ihtimali $\%50$'yi geçer. Aynı mantıkla, çok sayıda veriyi sınırlı sayıda kutuya dağıtırken çakışma neredeyse kaçınılmazdır.

Çözümler vardır. En yaygını zincirlemedir: her kutuya tek bir veri değil, aynı kutuya düşenlerden oluşan küçük bir liste konur. O kutuya bakıp kısacık listeyi tararsınız. Liste kısa kaldığı sürece hız korunur. Bir diğer yöntem açık adreslemedir: kutu doluysa, belirli bir kurala göre bir sonraki boş kutuya geçilir.

Hızı Koruyan İki Şey

Hash tablosunun gerçekten hızlı kalması iki koşula bağlıdır:

1. İyi bir hash fonksiyonu: Verileri kutulara mümkün olduğunca eşit dağıtmalı. Eğer tüm veriler aynı birkaç kutuya yığılırsa, tablo dev bir listeye dönüşür ve hız $O(n)$'e geriler. İyi bir hash, çıktıları rastgele gibi serper.
2. Yeterli boş alan (yük faktörü): Kutu sayısı, veri sayısına göre makul tutulmalıdır. Tablo dolmaya başlayınca çakışmalar artar; bu yüzden hash tabloları, dolduklarında otomatik olarak büyüyüp tüm verileri daha çok kutuya yeniden dağıtır.

Bu iki koşul sağlandığında, ortalama arama süresi sabit kalır. (Çok kötü şartlarda en kötü durum hâlâ yavaş olabilir; ama iyi tasarımda bu neredeyse hiç yaşanmaz.)

Her Yerdeler

Hash tabloları görünmez ama her yerdeler. Programlama dillerindeki "sözlük" veya "harita" yapıları, veritabanı indeksleri, önbellekler, parola doğrulama sistemleri ve hatta blok zinciri teknolojisi — hepsi bu fikrin üstüne kurulu. Bir web sayfasını saniyeler içinde açan altyapının büyük kısmı, sessizce çalışan hash tablolarıdır.

Hash tablosu, matematiksel bir fikrin (bir anahtarı bir adrese dönüştürmek) nasıl koca bir teknolojiyi mümkün kıldığının harika bir örneğidir. Aradığınız her şeyi "anında" bulmanızı sağlayan o görünmez hız, aslında basit bir bölme işleminin ($\bmod$) ve akıllı bir dağıtımın eseridir.