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. Dictionary, HashMap ve HashSet uygulamalarının önemli bir bölümü bu fikri kullanır; ancak performans collision dağılımına, doluluk oranına ve yeniden boyutlandırma politikasına bağlıdır.
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 probing yapısına göre maliyet O(n)‘e kadar çıkabilir.
Hash Function Nedir?
Hash function, herhangi bir input’u (key) sabit boyutlu bir sayıya (hash value) dönüştüren matematiksel fonksiyon. Amaç, bu sayıyı array index’i olarak kullanmak.
Mesela “John” ismini 5’e, “Alice” ismini 12’ye dönüştüren bir fonksiyon düşünün. Artık John’un bilgilerini array[5]‘te, Alice’in bilgilerini array[12]‘de saklayabilirsiniz. Aramak için? Direkt array[hash(“John”)]!
İyi Bir Hash Function’ın Özellikleri
Deterministic olmalı: Aynı input her zaman aynı output’u vermeli. “Ali” her seferinde aynı hash’i üretmeli.
Uniform distribution: Hash değerleri mümkün olduğunca eşit dağılmalı. Herkes aynı index’e düşerse, performans kaybolur.
Hızlı hesaplanmalı: Hash hesaplamak, arama yapmaktan hızlı olmalı. Yoksa ne anlamı var?
Avalanche effect: Küçük input değişikliği, büyük output değişikliği yaratmalı. “Ali” ve “Ali1” çok farklı hash’ler üretmeli.
Hash Table Nasıl Çalışır?
Hash table, aslında gelişmiş bir array. Ama index’leri sıralı değil, hash function’dan geliyor:
- Insert: Key’i hash’le, çıkan değeri index olarak kullan, value’yu o index’e koy
- Search: Key’i hash’le, o index’teki değeri getir
- Delete: Key’i hash’le, o index’i temizle
Basit görünüyor değil mi? Ama şeytan detayda…
Collision (Çarpışma) Problemi
İki farklı anahtar aynı tablo konumuna eşlenirse collision oluşur. Olası anahtar uzayı tablo boyutundan büyük olduğunda bu durum kaçınılmazdır; uygulama zincirleme veya açık adresleme gibi bir çözüm stratejisi kullanır.
Collision Resolution Teknikleri
Chaining (Zincirleme): Her index’te linked list tut. Collision olursa, listeye ekle. Basit ama extra memory.
Open Addressing: Collision olursa, başka boş index bul:
- Linear Probing: Sırayla bak (i+1, i+2, i+3…)
- Quadratic Probing: Kare kare atla (i+1², i+2², i+3²…)
- Double Hashing: İkinci bir hash function kullan
Robin Hood Hashing: Arama mesafeleri arasındaki farkı azaltmak için daha uzun probe mesafesine sahip girdiye öncelik verir.
Load Factor ve Rehashing
Load factor = Dolu slot sayısı / Toplam slot sayısı
Load factor için eşik uygulamaya bağlıdır; Java HashMap varsayılan olarak 0,75 kullanır. Eşik aşıldığında tablo genellikle büyütülür ve girdiler yeni kapasiteye göre yeniden yerleştirilir.
Bu işlem O(n) ama amortized O(1) - yani nadiren olduğu için ortalama performansı etkilemiyor.
Basit Örnekler
# Simple hash function for strings
def simple_hash(key, table_size):
hash_value = 0
for char in key:
hash_value += ord(char)
return hash_value % table_size
# Better hash function (polynomial rolling)
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
# Basic hash table with chaining
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)] # List of lists for chaining
def insert(self, key, value):
index = hash(key) % self.size
# Check if key exists, update if found
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
# Add new key-value pair
self.table[index].append((key, value))
def get(self, key):
index = hash(key) % self.size
for k, v in self.table[index]:
if k == key:
return v
return None # Key not found
Gerçek Dünyada Hash Table
Database Indexing: Primary key index’leri hash table kullanır. Milyonlarca kayıt içinden O(1)‘de bulur.
Caching Systems: Redis, Memcached gibi cache’ler temelde glorified hash table.
Compiler Symbol Tables: Değişken isimleri ve memory adresleri hash table’da tutulur.
Password Storage: Password’ler hash’lenip saklanır (ama cryptographic hash - farklı konu).
Routing Tables: Network router’ları IP adresleri için hash table kullanır.
Hash Table vs Diğer Veri Yapıları
vs Array: Hash table daha hızlı arama (O(1) vs O(n)), ama daha fazla memory.
vs Binary Search Tree: Hash table average case’de daha hızlı (O(1) vs O(log n)), ama sorted değil.
vs Linked List: Hash table çok daha hızlı arama, ama insertion order korunmaz.
Perfect Hashing
Eğer key set’iniz sabit ve önceden biliniyorsa (mesela programlama dilinin keyword’leri), perfect hash function oluşturabilirsiniz - hiç collision olmaz! Compiler’lar bunu kullanır.
Modern Hash Function’lar
MurmurHash: Hızlı, non-cryptographic. Redis kullanıyor.
CityHash: Google’ın hash’i. Çok hızlı, özellikle kısa string’ler için.
xxHash: Extremely fast. Game engine’lerde popüler.
SipHash: DoS attack’lara karşı korumalı. Python 3.4+ kullanıyor.
Sonuç
Hash table, computer science’ın en güzel buluşlarından biri. O(1) lookup time’ı sayesinde modern yazılımın temel taşı. Database’lerden cache’lere, compiler’lardan router’lara her yerde var.
Ama sihirli değnek değil! Collision handling, load factor, rehashing… Bunları anlamadan kullanırsanız, performans facialara yol açabilir.
“Premature optimization is the root of all evil” ama “Using the right data structure is not premature optimization”! Hash table çoğu zaman o “right data structure”.
Bir sonraki yazıda görüşmek üzere.