Merhaba arkadaşlar! Bugün computer science’ın en temel ve bir o kadar da büyüleyici konularından birini konuşacağız: Hash Table ve Hash Function. Dictionary, HashMap, HashSet… Hepsi aynı temel prensiple çalışıyor. O(1) time complexity’nin sırrı burada yatıyor!
Problem: Hızlı Arama İhtiyacı
Diyelim ki 1 milyon kullanıcınız var ve kullanıcı ID’sine göre bilgilerini getirmeniz gerekiyor. Array’de linear search yaparsanız O(n), sorted array’de binary search yaparsanız O(log n). Ama hash table? O(1)! Nasıl mı? İşte büyü başlıyor…
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ı key aynı hash değerini üretirse ne olur? “John” da 5, “Mary” de 5 verirse? İşte buna collision deniyor ve kaçınılmaz! (Pigeonhole principle)
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: “Zengin” elemanları yerinden edip “fakir” elemanlara yer aç. Load balance için harika!
Load Factor ve Rehashing
Load factor = Dolu slot sayısı / Toplam slot sayısı
Load factor 0.75’i geçerse (Java’nın default’u), performans düşmeye başlar. Çözüm? Rehashing! Table size’ı büyüt (genelde 2 katına), tüm elemanları yeni hash’lerle yerleştir.
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.