Hash Tablosu — Hashleme Nasıl Çalışır ve Çakışmalar Nasıl Çözülür?

Bir hash tablosu, her anahtarı bir dizi indeksine hashleyerek anahtar-değer çiftlerini saklar. Bu sayede tablo, saklanan her öğeyi tek tek taramak yerine doğru konuma yakın bir yere doğrudan gidebilir.

Bu yüzden hash tabloları, arama, ekleme ve silme işlemlerinde ortalama olarak çoğu zaman $O(1)$'e yakındır. Ancak bunun bir koşulu vardır: hash fonksiyonunun anahtarları yeterince dengeli dağıtması gerekir ve tablonun çakışmalar için de bir kuralı olmalıdır.

Hash Tablosu Ne Yapar?

Bir hash tablosu, "name" -> "Ada" veya 42 -> "blue" gibi anahtar-değer çiftlerini saklar. İki ana bileşeni vardır:

• yuvalardan veya kovalarından oluşan bir dizi
• her anahtarı bu yuvalardan birine eşleyen bir hash fonksiyonu

Dizide $m$ tane yuva varsa, hash fonksiyonunu $0$ ile $m-1$ arasında bir indeks üretiyor gibi düşünebilirsiniz.

Küçük tamsayılar için basit bir örnek olarak kural şu olabilir:

$$h(k) = k \bmod 8$$

Bu durumda $10$ anahtarı $2$ numaralı yuvaya gider, çünkü $10 \bmod 8 = 2$.

Gerçek hash fonksiyonları, özellikle metinler ve daha büyük veri kümeleri için daha dikkatli tasarlanır. Ama temel fikir aynıdır: hızlıca bir indeks hesapla, sonra orada saklanan öğeyi kontrol et.

Hash Çakışmaları Neden Kaçınılmazdır?

Bir çakışma, iki farklı anahtar aynı yuvaya eşlendiğinde oluşur.

Bu normaldir, çünkü tablodaki yuva sayısı genellikle olası anahtar sayısından daha azdır. Şu durumda:

$$h(k) = k \bmod 8$$

$10$, $18$ ve $26$ anahtarlarının hepsi $2$ numaralı yuvaya gider. Yani fonksiyon tanımlandığı gibi tamamen doğru çalışsa bile, tablonun yine de çözmesi gereken bir çakışma vardır.

Dolayısıyla bir hash tablosu, her anahtar için benzersiz bir yuva vaat etmez. Çakışmalar iyi yönetildiği sürece, aramayı hızlıca daraltmanın bir yolunu sunar.

Çözümlü Örnek: Bir Tablo, Bir Çakışma

Bir tablonun $8$ yuvası olduğunu ve şu fonksiyonu kullandığını varsayalım:

$$h(k) = k \bmod 8$$

$10$, $18$ ve $7$ anahtarlarını ekleyin.

Önce $10$, $10 \bmod 8 = 2$ olduğu için $2$ numaralı yuvaya gider.

Sonra $18$ de $2$ numaralı yuvaya hashlenir, yani bir çakışma oluşur.

Ardından $7$, $7$ numaralı yuvaya gider; dolayısıyla bu eklemede çakışma olmaz.

İşe yarayan temel desen her zaman aynıdır:

1. Anahtarı hashle.
2. Önerilen yuvaya git.
3. Orada zaten farklı bir anahtar varsa, çakışma kuralını uygula.

Bu desen netleştiğinde, iki ana çakışma stratejisini anlamak daha kolay olur.

Zincirleme ve Açık Adresleme

Zincirleme, her yuvada bir kova tutar

Zincirlemede her yuva, yalnızca tek bir giriş yerine küçük bir giriş koleksiyonu saklar.

Eğer $10$ ve $18$ anahtarlarının ikisi de $2$ numaralı yuvaya hashlenirse, $2$ numaralı kova şunları tutabilir:

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

$18$ anahtarını bulmak için tablo doğrudan $2$ numaralı kovaya gider ve yalnızca o kovadaki girişleri karşılaştırır.

Zincirleme kavramsal olarak basittir ve silme işlemi genellikle açık adreslemeye göre daha kolaydır. Bunun karşılığında, kovalar uzadıkça işlemler yavaşlar.

Açık adresleme dizi içinde kalır

Açık adreslemede, dizideki her yuva en fazla bir giriş tutar. Asıl yuva doluysa tablo, sabit bir kurala göre başka yuvaları yoklar.

Yaygın kurallardan biri doğrusal yoklamadır: eğer $2$ numaralı yuva doluysa, $3$, sonra $4$, sonra $5$ denenir; gerekirse başa sarılır.

Bu yöntem ayrı kova listelerine ihtiyaç duymaz, ancak dolu olan yakın yuvalar kümeler oluşturabilir. Bir diğer önemli nokta da, arama ve silme işlemlerinin ekleme sırasında kullanılan aynı yoklama kuralına uyması gerektiğidir.

$O(1)$ Demek Ne Zaman Makuldür?

Hash tabloları genellikle arama, ekleme ve silme için ortalama durumda $O(1)$ olarak tanımlanır. Bu ortalama durum ifadesi bazı koşullara bağlıdır:

• hash fonksiyonu anahtarları yeterince dengeli dağıtmalıdır
• yük faktörü kontrol altında tutulmalıdır
• çakışma stratejisi doğru uygulanmalıdır

Yük faktörü şu orandır:

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Tablo fazla dolarsa çakışmalar daha sık olur ve performans kötüleşir. Bu yüzden birçok uygulama, tablo doldukça diziyi yeniden boyutlandırır.

En kötü durumda performans yine de $O(n)$'e doğru düşebilir; özellikle çok fazla anahtar aynı bölgede birikirse.

Hash Tablolarında Sık Yapılan Hatalar

Çakışmaların hash fonksiyonunun başarısız olduğu anlamına geldiğini sanmak

Hayır. Çakışmalar beklenen bir durumdur. Asıl soru, tablonun bunları verimli biçimde yönetip yönetmediğidir.

$O(1)$ ifadesini koşulsuz sanmak

$O(1)$ genellikle ortalama durum ifadesidir; her girdi ve her an için verilmiş bir garanti değildir.

Buradaki hashlemeyi şifrelemeyle karıştırmak

Temel veri yapıları bağlamında bir hash fonksiyonu esas olarak hızlı indeksleme içindir, gizlilik için değil. Bunlar farklı amaçlardır.

Gerçek anahtarı karşılaştırmayı unutmak

İki anahtar aynı hash sonucunu paylaşabilir. Doğru kovaya veya yoklama konumuna ulaştıktan sonra, tablonun anahtarın gerçekten eşleşip eşleşmediğini yine de kontrol etmesi gerekir.

Hash Tabloları Ne Zaman Kullanılır?

Hash tabloları, anahtara göre hızlı erişimin önemli olduğu her yerde kullanılır. Yaygın örnekler arasında sözlükler, sembol tabloları, önbellekler, indeksleme ve verilerde frekans sayımı bulunur.

Öğeleri sıralı tutmaktan çok, anahtara göre tam eşleşmeli arama önemliyse iyi bir seçimdir. Eğer sıralı dolaşma, aralık sorguları veya en yakın değerler gerekiyorsa, başka bir veri yapısı daha uygun olabilir.

Benzer Bir Çakışma Örneği Deneyin

$8$ yuvalı küçük bir dizi alın ve $h(k)=k \bmod 8$ kullanın. $3$, $11$, $19$ ve $27$ gibi birkaç anahtar ekleyin. Sonra çakışmaları bir kez zincirleme ile, bir kez de doğrusal yoklama ile çözün.

Bu tek alıştırma ana fikri çok hızlı biçimde somutlaştırır: çakışmalar kaçınılmazdır ve çakışma kuralı tablonun nasıl davrandığını değiştirir. Faydalı bir sonraki adım isterseniz, farklı bir tablo boyutuyla kendi örneğinizi deneyin ve çakışmaların nasıl değiştiğine bakın.