İki Anahtar Aynı Yere Düşerse Ne Olur?
Çakışma (Collision), farklı iki anahtarın hash fonksiyonu sonucunda aynı indekse düşmesi durumudur.
Hash tablosu boyutu: 10
hash("elma") % 10 = 3 ✅hash("armut") % 10 = 7 ✅hash("muz") % 10 = 3 ❌ ÇAKIŞMA!"elma" ve "muz" aynı indekse (3) düşüyor!
Okulda sınıflara öğrenci yerleştiriliyor:
Problem: "Ahmet" ve "Ali" ikisi de "A" ile başlıyor - ikisi de 1. Sınıfa gitmeli ama sınıfta tek kişilik yer var!
Çözüm: Ya ikisini yan yana oturtmalıyız (chaining) ya da Ali için başka boş sınıf bulmalıyız (probing)!
100 anahtar var, tablo boyutu sadece 10 → Kesin çakışma olur!
Hash fonksiyonu anahtarları eşit dağıtmıyor - hep aynı yere düşüyor!
Rastgele bile olsa, yeterli anahtar eklenirse çakışma kaçınılmaz!
10 güvercin var ve 9 delik var → En az 2 güvercin aynı deliğe girmek zorunda!
Hash Table: Anahtarlar > Tablo boyutu → Çakışma kaçınılmaz!
İki ana yöntem vardır:
Her indekste bir liste tut
Çakışan anahtarlar aynı indekste bir liste olarak saklanır.
Başka boş yer bul
Çakışma olursa, tabloda başka boş indeks aranır.
Her indekste bir linked list tutarız. Çakışan anahtarlar bu listeye eklenir.
Tablo boyutu: 5, Hash: key % 5
class HashTableChaining:
"""Chaining yöntemi ile Hash Table"""
def __init__(self, size=10):
self.size = size
# Her indekste boş liste
self.table = [[] for _ in range(size)]
def hash_function(self, key):
"""Basit hash fonksiyonu"""
return key % self.size
def insert(self, key, value):
"""Anahtar-değer ekle"""
index = self.hash_function(key)
# Bu indekste zaten var mı kontrol et
for i, (k, v) in enumerate(self.table[index]):
if k == key:
# Varsa güncelle
self.table[index][i] = (key, value)
print(f"Güncellendi: {key} → indeks {index}")
return
# Yoksa ekle
self.table[index].append((key, value))
print(f"Eklendi: {key} → indeks {index}")
def search(self, key):
"""Anahtar ara"""
index = self.hash_function(key)
# Bu indeksteki listeyi dolaş
for k, v in self.table[index]:
if k == key:
return v
return None # Bulunamadı
def display(self):
"""Tabloyu göster"""
print("\n=== Hash Table (Chaining) ===")
for i in range(self.size):
print(f"[{i}]: ", end="")
if self.table[i]:
print(" → ".join([f"{k}" for k, v in self.table[i]]))
else:
print("boş")
# Örnek kullanım
ht = HashTableChaining(size=5)
# Anahtar ekle
keys = [10, 6, 3, 8, 20, 9, 13]
print("=== Ekleme İşlemleri ===")
for key in keys:
ht.insert(key, f"değer_{key}")
# Tabloyu göster
ht.display()
# Çakışma analizi
print("\n=== Çakışma Analizi ===")
collisions = sum(1 for bucket in ht.table if len(bucket) > 1)
print(f"Çakışma olan indeks sayısı: {collisions}")
print(f"En uzun zincir: {max(len(bucket) for bucket in ht.table)} eleman")
# Arama
print("\n=== Arama ===")
search_keys = [3, 8, 100]
for key in search_keys:
result = ht.search(key)
if result:
print(f"Anahtar {key} bulundu: {result}")
else:
print(f"Anahtar {key} bulunamadı")Çakışma olduğunda, tabloda sıradaki boş yeri ararız.
new_index = (hash_value + i) % table_size
i: 0, 1, 2, 3, ... (deneme sayısı)
Sırayla: indeks, indeks+1, indeks+2, ... boş yer bulunana kadar
13 eklenirken ne olur? (hash(13) = 13 % 5 = 3)
class HashTableProbing:
"""Linear Probing ile Hash Table"""
def __init__(self, size=10):
self.size = size
self.table = [None] * size # Tek dizi
self.count = 0 # Eleman sayısı
def hash_function(self, key):
"""Basit hash fonksiyonu"""
return key % self.size
def insert(self, key, value):
"""Anahtar-değer ekle"""
if self.count >= self.size:
print("❌ Tablo dolu!")
return False
index = self.hash_function(key)
start_index = index
i = 0
print(f"\n{key} ekleniyor (hash: {index})...")
while True:
current_index = (index + i) % self.size
print(f" Deneme {i+1}: İndeks {current_index}", end=" ")
if self.table[current_index] is None:
# Boş yer bulundu
self.table[current_index] = (key, value)
self.count += 1
print("→ BOŞ, eklendi! ✅")
return True
# Aynı anahtar mı?
if self.table[current_index][0] == key:
self.table[current_index] = (key, value)
print("→ Aynı anahtar, güncellendi! 🔄")
return True
print("→ DOLU, devam et...")
i += 1
# Tüm tablo dolaşıldı
if i >= self.size:
print("❌ Tablo dolu!")
return False
def search(self, key):
"""Anahtar ara"""
index = self.hash_function(key)
i = 0
while i < self.size:
current_index = (index + i) % self.size
if self.table[current_index] is None:
return None # Boş yer → bulunamadı
if self.table[current_index][0] == key:
return self.table[current_index][1] # Bulundu!
i += 1
return None # Bulunamadı
def display(self):
"""Tabloyu göster"""
print("\n=== Hash Table (Linear Probing) ===")
for i in range(self.size):
if self.table[i] is None:
print(f"[{i}]: boş")
else:
key, val = self.table[i]
original_index = self.hash_function(key)
if original_index != i:
print(f"[{i}]: {key} (orijinal: {original_index}, kayma: {i - original_index})")
else:
print(f"[{i}]: {key}")
# Örnek kullanım
ht = HashTableProbing(size=7)
# Anahtar ekle
keys = [10, 3, 8, 17, 24] # 10%7=3, 3%7=3, 8%7=1, 17%7=3, 24%7=3
for key in keys:
ht.insert(key, f"değer_{key}")
# Tabloyu göster
ht.display()
# Load factor
print(f"\nLoad Factor: {ht.count}/{ht.size} = {ht.count/ht.size:.2f}")
# Arama
print("\n=== Arama ===")
for key in [3, 17, 100]:
result = ht.search(key)
if result:
print(f"✅ {key} bulundu: {result}")
else:
print(f"❌ {key} bulunamadı")| Özellik | Chaining | Open Addressing |
|---|---|---|
| Veri Yapısı | Dizi + Linked List | Sadece Dizi |
| Bellek | Ekstra (pointer'lar) | Verimli (tek dizi) |
| Tablo Dolduğunda | Sorun yok (liste uzar) | Eklenemez! |
| Cache | Kötü (pointer takibi) | İyi (ardışık bellek) |
| Silme | Kolay | Karmaşık ("deleted" işareti) |
| En Kötü Durum | Tüm elemanlar tek zincirde | Tablo tamamen dolu |
| Kullanım | Python dict, Java HashMap | Cache, Embedded sistemler |
Hash table'ın performansını etkileyen en önemli faktör: Load Factor (Doluluk Oranı). Ne kadar doluysa o kadar yavaş!