Hash table, anahtarı bir hash function ile dizi konumuna eşleyerek ortalama durumda O(1) ekleme ve arama sağlayan veri yapısıdır. Python’un dict ve set tipleri, Java’nın HashMap ve HashSet sınıfları bu fikri kullanır; performans ise çarpışmaların (collision) dağılımına, doluluk oranına ve yeniden boyutlandırma politikasına bağlıdır.
Aşağıda iyi bir hash function’ın özellikleri, çarpışma çözüm yöntemleri, load factor ve amortize maliyet, gerçek sistemlerdeki kullanım alanları ve hash table’ın uygun olmadığı durumlar ele alınıyor.
Problem: Hızlı Arama İhtiyacı
Bir milyon kullanıcıyı kimliğine göre aradığınızı düşünün. Sırasız dizide doğrusal arama O(n), sıralı dizide ikili arama O(log n) maliyetindedir. İyi dağılan bir hash ve kontrollü load factor ile hash table ortalama O(1) erişim sunabilir; kötü durumda ise zincir veya yoklama yapısına göre maliyet O(n)‘e kadar çıkabilir.
Hash Function Nedir?
Hash function, bir anahtarı (key) sabit boyutlu bir sayıya (hash değeri) dönüştüren fonksiyondur. Hash table bu sayıyı tablo boyutuna göre küçültüp (genellikle mod alarak) dizi indeksi olarak kullanır.
Örneğin “John” anahtarı 5’e, “Alice” anahtarı 12’ye eşlenirse John’un kaydı table[5], Alice’inki table[12] konumunda saklanır. Arama için hash("John") % size yeniden hesaplanır; diziyi baştan sona taramak gerekmez.
İyi Bir Hash Function’ın Özellikleri
Belirlenimci (deterministic): Aynı girdi aynı süreç içinde her zaman aynı çıktıyı vermelidir. Python, str ve bytes hash’lerini her süreçte rastgele seçilen bir tohumla (seed) hesaplar; aynı metnin hash’i iki ayrı çalıştırmada farklı olabilir, ama tek bir süreç içinde sabittir.
Düzgün dağılım (uniform distribution): Hash değerleri tablo konumlarına mümkün olduğunca eşit dağılmalıdır. Bütün anahtarlar aynı konuma düşerse tablo fiilen bir bağlı listeye dönüşür.
Hızlı hesaplanma: Hash hesaplamak, karşılaştırmalı aramadan ucuz olmalıdır; aksi hâlde kazanç kaybolur.
Çığ etkisi (avalanche effect): Girdideki küçük bir değişikliğin çıktının birçok bitini değiştirmesi istenen bir özelliktir, ama her uygulama bunu şart koşmaz. CPython’da küçük tamsayıların hash’i sayının kendisidir (hash(5) == 5); dict uygulaması bunu yoklama sırasında hash’in üst bitlerini de kullanarak dengeler. Vector database’lerde kullanılan LSH (locality-sensitive hashing) ise bilerek tersini yapar: benzer girdileri aynı bucket’a düşürmeye çalışır.
Hash Table Nasıl Çalışır?
Hash table, indeksi hash function’dan gelen bir dizidir:
- Ekleme: Anahtarın hash’i hesaplanır, tablo boyutuna göre indekse çevrilir ve değer o konuma (bucket) yazılır.
- Arama: Aynı indeks hesaplanır ve o konumdaki girdinin anahtarı aranan anahtarla karşılaştırılır.
- Silme: Aynı indeks hesaplanır ve girdi kaldırılır. Zincirlemede eleman o konumun listesinden çıkarılır. Açık adreslemede ise slotu doğrudan boşaltmak, o slotun üzerinden geçerek yerleştirilmiş diğer anahtarların yoklama zincirini kırar; bu yüzden silinen yere bir mezar taşı (tombstone) işareti konur. Arama bu işaretin üzerinden devam eder, ekleme ise o slotu yeniden kullanabilir.
Bu akışın asıl zorluğu, farklı anahtarların aynı konuma düşmesidir.
Çarpışma (Collision)
İki farklı anahtar aynı tablo konumuna eşlenirse çarpışma oluşur. Olası anahtar uzayı tablo boyutundan büyük olduğunda bu kaçınılmazdır; uygulama zincirleme veya açık adresleme gibi bir çözüm stratejisi kullanır.
Çarpışma Çözüm Yöntemleri
Zincirleme (chaining): Her konumda bir liste tutulur; çarpışan girdiler bu listeye eklenir. Uygulaması basittir, ama her eleman için ek bellek gerekir. Java’nın HashMap sınıfı, çok sayıda anahtar aynı konuma düştüğünde anahtarlar Comparable ise karşılaştırma sırasından yararlanarak kötü durumun etkisini azaltabilir.
Açık adresleme (open addressing): Çarpışmada tablonun içinde başka bir boş konum aranır:
- Doğrusal yoklama (linear probing): Sırayla sonraki konumlara bakılır (i+1, i+2, i+3…).
- Karesel yoklama (quadratic probing): Kare artışlarla atlanır (i+1², i+2², i+3²…).
- Çift hash’leme (double hashing): Adım boyu ikinci bir hash function ile belirlenir.
Robin Hood hashing: Açık adreslemenin bir çeşididir; ekleme sırasında yoklama mesafesi daha uzun olan girdiye öncelik verir ve arama mesafeleri arasındaki farkı azaltır.
Load Factor ve Yeniden Boyutlandırma
Load factor (doluluk oranı), saklanan eleman sayısının bucket sayısına oranıdır: α = n / m. Açık adreslemede her konumda en fazla bir eleman bulunduğu için α 1’i aşamaz. Zincirlemede bir konumda birden çok eleman olabildiği için α 1’den büyük olabilir.
Eşik değer uygulamaya bağlıdır; Java HashMap varsayılan olarak 0,75 kullanır. Eşik aşıldığında tablo büyütülür ve bütün girdiler yeni kapasiteye göre yeniden yerleştirilir (rehashing).
Yeniden yerleştirme O(n) sürer. Kapasite her büyütmede sabit bir çarpanla (örneğin iki katına) artırılırsa, n ekleme boyunca yapılan toplam yeniden yerleştirme işi O(n) olur ve ekleme başına amortize maliyet O(1) kalır. Kapasite sabit bir miktarla (örneğin her seferinde 100 konum) artırılsaydı bu garanti olmazdı. Amortize O(1), her eklemenin hızlı olduğu anlamına da gelmez: büyütmeyi tetikleyen ekleme O(n) sürer ve gecikme ölçümlerinde sıçrama olarak görünür. Eleman sayısı önceden biliniyorsa tabloyu baştan uygun kapasiteyle oluşturmak bu sıçramaları önler.
Basit Örnekler
# Basit hash function: karakter kodlarını toplar
# Aynı harflerden oluşan "abc" ve "cba" aynı değeri verir; dağılımı zayıftır
def simple_hash(key, table_size):
hash_value = 0
for char in key:
hash_value += ord(char)
return hash_value % table_size
# Polinom hash: karakterin konumunu da hesaba katar
def better_hash(key, table_size):
hash_value = 0
prime = 31
for char in key:
hash_value = (hash_value * prime + ord(char)) % table_size
return hash_value
print(simple_hash("abc", 101), simple_hash("cba", 101)) # 92 92
print(better_hash("abc", 101), better_hash("cba", 101)) # 0 1
Aşağıdaki sınıf zincirleme kullanan basitleştirilmiş bir hash table’dır; yeniden boyutlandırma yapmaz. Python’un yerleşik hash() fonksiyonunu kullandığı için anahtarın hashable olması gerekir; örneğin bir tuple ancak bütün öğeleri hashable ise anahtar olabilir.
# Zincirleme kullanan basitleştirilmiş hash table (yeniden boyutlandırma yok)
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)] # her konum bir liste
def _bucket(self, key):
return self.table[hash(key) % self.size]
def insert(self, key, value):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # anahtar varsa değeri güncelle
return
bucket.append((key, value))
def get(self, key):
for k, v in self._bucket(key):
if k == key:
return v
return None # anahtar yok
def delete(self, key):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
del bucket[i] # zincirlemede silme: girdiyi listeden çıkar
return True
return False
table = HashTable()
table.insert("ali", 1)
table.insert("ayse", 2)
print(table.get("ayse")) # 2
table.delete("ayse")
print(table.get("ayse")) # None
Gerçek Dünyada Hash Table
Veritabanı indeksleri: Hash table, veritabanı indekslerinin varsayılanı değildir. InnoDB (MySQL) indeksleri, uzamsal indeksler dışında B-tree yapısındadır; PostgreSQL de birincil anahtar için otomatik olarak benzersiz bir B-tree indeksi oluşturur. B-tree’de arama O(log n) sürer, ama eşitliğin yanında aralık sorgularını (<, BETWEEN) ve sıralamayı da destekler. Hash index ayrı bir seçenektir: PostgreSQL’de CREATE INDEX ... USING HASH ile oluşturulur, MySQL’de MEMORY motoru tarafından sunulur. Hash index yalnız eşitlik karşılaştırmasında kullanılır; aralık sorgusu ve ORDER BY için işe yaramaz.
Önbellekler: Redis gibi bellek içi anahtar-değer depoları anahtarları hash table yapısında tutar. Redis’in sözlük yapısı (dict.c) 4.0 sürümünden beri anahtarları SipHash’in 1-2 varyantıyla hash’ler.
Derleyici sembol tabloları: Derleyiciler değişken ve fonksiyon adlarını tür ve kapsam bilgileriyle birlikte sembol tablolarında tutar; bu tablolar sık sık hash table olarak uygulanır.
Bağlantı izleme (connection tracking): Linux çekirdeğinin netfilter conntrack modülü, NAT ve durum bilgili güvenlik duvarı (firewall) kuralları için izlediği bağlantıları bir hash table’da tutar; bucket sayısı nf_conntrack_buckets ayarıyla belirlenir. IP yönlendirme ise farklı bir problemdir: hedef adres için en uzun önek eşleşmesi (longest prefix match) gerekir. Tam eşleşme arayan bir hash table bunu doğrudan çözmez; Linux IPv4 yönlendirme tablosunu bir trie (fib_trie) ile tutar, yönlendirici donanımları ise genellikle TCAM kullanır.
Hash Table ve Diğer Veri Yapıları
Dizi: İndeksle erişim dizide de O(1)‘dir. Fark, anahtara veya değere göre aramadadır: sırasız dizide O(n), hash table’da ortalama O(1). Karşılığında hash table daha fazla bellek kullanır.
İkili arama ağacı: Hash table ortalama durumda daha hızlıdır (O(1) ve O(log n)), ama anahtarları sıralı tutmaz. Aralık sorgusu ve sıralı dolaşma için dengeli ağaç ya da B-tree daha uygundur.
Bağlı liste: Hash table aramada çok daha hızlıdır. Klasik bir hash table ekleme sırasını korumaz; Python 3.7 ve sonrasında dict ile Java’da LinkedHashMap ise ekleme sırasını korur.
Perfect Hashing
Anahtar kümesi sabit ve önceden biliniyorsa (örneğin bir programlama dilinin anahtar kelimeleri), bu küme için hiç çarpışma üretmeyen bir perfect hash function kurulabilir. Kümeye yeni bir anahtar eklenirse fonksiyonun yeniden üretilmesi gerekir.
Yaygın Hash Function’lar
SipHash: Gizli bir anahtarla çalışan ve hash flooding (bilerek çarpışma üreterek hizmeti yavaşlatma) saldırılarına karşı tasarlanmış bir fonksiyondur. Python 3.4’ten beri str ve bytes için kullanılır (PEP 456); Python 3.11’den beri varsayılan varyant SipHash-1-3’tür. Redis de 4.0’dan beri sözlük anahtarlarında SipHash 1-2 kullanır.
MurmurHash: Hızlı, kriptografik olmayan bir hash ailesidir. Redis, HyperLogLog veri yapısında MurmurHash2’nin 64 bit sürümünü kullanır.
CityHash ve FarmHash: Google’ın metinler için geliştirdiği hızlı, kriptografik olmayan hash aileleridir. Google 2014’te FarmHash’i CityHash’in halefi olarak duyurdu.
xxHash: Kriptografik olmayan, hız odaklı bir hash ailesidir (XXH32, XXH64 ve XXH3).
Sonuç
Hash table, anahtara göre arama ve eklemeyi ortalama O(1) sürede yapan temel bir veri yapısıdır; dil sözlüklerinden önbelleklere, bağlantı izlemeden sembol tablolarına kadar birçok yerde kullanılır. Bu ortalama; iyi dağılan bir hash function’a, kontrol altındaki bir load factor’e ve kapasitenin geometrik büyümesine bağlıdır. Aralık sorgusu, sıralı dolaşma veya önek eşleşmesi gerekiyorsa B-tree ya da trie gibi yapılar daha uygundur. Donald Knuth’un 1974 tarihli “Structured Programming with go to Statements” makalesindeki “premature optimization is the root of all evil” cümlesi sık alıntılanır; ancak probleme uygun veri yapısını seçmek erken optimizasyon değil, tasarımın parçasıdır.