Hash Table Collision: Çakışma Nasıl Çözülür?

Hash table collision, iki farklı anahtarın hash tablosunda aynı indeks ya da bucket konumuna yönelmesiyle oluşur. Bu durumda veri silinmez; tablo, çakışmayı çözmek için aynı bucket içinde birden fazla kayıt tutabilir veya başka bir boş konum arayabilir. Hangi yöntemin kullanılacağı, hash tablosunun tasarımına bağlıdır.

Bu konuyu anlamanın en önemli noktası, hash değeri ile tablo indeksinin aynı şey olmadığını bilmektir. Hash fonksiyonu anahtarı sayısal bir değere dönüştürür; tablo boyutu kullanılarak bu değer bir indekse çevrilir. Hash değerlerinin benzersiz olması gerekmez ve farklı anahtarlar aynı konuma düşebilir.

Hash Table Collision Nedir? Hash Değeri, İndeks ve Bucket Farkı

Bir hash tablosunda anahtar ile değer arasındaki ilişkiyi hızlı kurmak için üç aşamalı bir süreç düşünebilirsiniz: anahtardan hash değeri üretmek, bu hash değerini tablo içinde kullanılacak indekse dönüştürmek ve ilgili bucket üzerinde işlemi gerçekleştirmek. Başlangıç seviyesinde bu üç kavram birbirine karıştırılsa da çakışmanın mantığını çözmek için aralarındaki farkı netleştirmek gerekir.

Hash fonksiyonu anahtarı sayıya dönüştürür

Hash fonksiyonu, bir anahtarı alıp sayısal bir hash değerine dönüştüren fonksiyondur. Örneğin “kitap” kelimesi bir hash fonksiyonundan geçirildiğinde 4821 gibi bir sonuç üretebilir. “kalem” anahtarı ise 9176 değerini üretebilir. Bu sayılar doğrudan tablo konumu olmak zorunda değildir; çoğu tasarımda tablo boyutuna göre tekrar işlenir.

İyi bir hash fonksiyonundan beklenen temel özellikler şunlardır:

• Aynı anahtar için aynı çalışma koşullarında tutarlı bir sonuç üretmesi,
• Farklı anahtarları mümkün olduğunca tabloya dengeli dağıtması,
• Hesaplanmasının gereksiz yere pahalı olmaması,
• Anahtarlar farklı olduğu hâlde aynı hash değerinin oluşabileceğini hesaba katması.

Burada “mümkün olduğunca” ifadesi önemlidir. Hash değeri alanı çok büyük olsa bile tablo içindeki indeks sayısı sınırlıdır. Bu nedenle bazı farklı anahtarların aynı indekse yönelmesi kaçınılmaz olabilir. Bir sınıfta öğrencileri soyadlarının ilk harfine göre raflara yerleştirdiğinizi düşünün. Aynı harfle başlayan öğrenciler aynı rafa gider; bu, öğrencilerin aynı kişi olduğu anlamına gelmez. Sadece ilk yerleştirme kuralı aynı rafı göstermiştir.

Hash değeri, tablo indeksi ve bucket aynı değildir

Hash değeri, anahtarın hash fonksiyonundan çıkan sayısal sonucudur. Tablo indeksi, bu sonucun tablo boyutuna uyarlanmasıyla elde edilen konumdur. Örneğin tablo boyutu 5 ise basitleştirilmiş bir hesaplama olarak hash_degeri % 5 kullanılabilir. Bu işlem sonucunda yalnızca 0, 1, 2, 3 veya 4 indekslerinden biri elde edilir.

Bucket ise bu indeksin işaret ettiği kayıt alanıdır. Bir tasarımda bucket tek bir hücre gibi düşünülebilir; başka bir tasarımda ise bağlı liste, dizi veya benzeri bir kayıt koleksiyonuna açılan giriş olabilir. Yani “indeks” konumu gösterirken, “bucket” o konumda kayıtların tutulduğu yapıyı ifade eder.

Python’daki dict, Java’daki HashMap ve C#’taki Dictionary yapıları bu fikre kavramsal olarak bağlanabilir: anahtarın hash bilgisi kullanılır, uygun bir tablo konumu hesaplanır ve olası çakışmalar iç yapı tarafından yönetilir. Ancak hash değeri üretme, tabloyu büyütme ve çakışmaları temsil etme ayrıntıları kullanılan dilin ve çalışma ortamının uygulamasına göre değişebilir. Bu nedenle ders çalışırken belirli bir kütüphanenin iç ayrıntısını tüm hash tablolarının genel kuralı gibi kabul etmeyin. Temel kavramları pekiştirmek isteyenler, algoritma bilgi testi üzerinden hash tablolarının dayandığı indeksleme ve veri yapısı mantığını ölçebilir.

Hash table collision ile kriptografik hash çakışması aynı amaçta değildir

Hash table collision ile MD5 gibi kriptografik hash fonksiyonlarındaki çakışma kavramı, yalnızca “iki girdinin aynı hash sonucuna ulaşması” bakımından benzer görünür. Fakat kullanım amacı farklıdır. Hash tablolarında amaç, anahtar-değer erişimini pratik biçimde hızlandırmaktır. Çakışma beklenen bir tasarım durumudur ve separate chaining veya linear probing gibi yöntemlerle yönetilir.

Kriptografik hash fonksiyonlarında ise amaç; dosya, mesaj veya başka bir girdiyi güvenlik bağlamında temsil eden bir özet üretmektir. Buradaki çakışma, güvenlik özellikleri açısından değerlendirilir. Bu nedenle hash table için kullanılan hash değeri ile MD5 gibi kriptografik hash çıktısını eş anlamlı kabul etmek doğru değildir. Birinin çakışması tablo yerleştirme problemi, diğerinin çakışması ise güvenlik ve bütünlük değerlendirmesi bağlamında ele alınır.

Çakışma Küçük Bir Hash Tablosunda Nasıl Görünür?

Çakışmayı görmek için tablo boyutu 5 olan basitleştirilmiş bir hash tablosu kullanalım. Hash fonksiyonumuz h(k) = k mod 5 olsun. Bu örnekte anahtarlar 10, 15, 7 ve 12’dir.

Bu tabloya bakıldığında 10 ile 15’in, 7 ile 12’nin farklı anahtarlar olduğu hâlde aynı indeksleri paylaştığı görülür. Bu durum veri kaybı anlamına gelmez. Yalnızca tabloya “aynı hücreye birden fazla kayıt yerleştirmek gerekiyor” mesajı verir. Hash tablosu, seçilen çakışma çözme yöntemine göre ilgili bucket içinde kayıtları birlikte tutar veya ilk konum doluysa başka bir boş konuma ilerler.

Separate Chaining: Aynı Bucket İçinde Birden Fazla Kayıt Tutmak

Separate chaining, çakışmayı çözmenin en anlaşılır yöntemlerinden biridir. Bu yöntemde her indeks yalnızca tek bir değer hücresini göstermek zorunda değildir. İndeks, bir bağlı listeye, diziye veya benzer bir kayıt koleksiyonuna işaret edebilir.

Önceki örneği kullandığımızda yapı kavramsal olarak şöyle görünür:

• İndeks 0 bucket’ı: 10 ve 15 kayıtları
• İndeks 1 bucket’ı: boş
• İndeks 2 bucket’ı: 7 ve 12 kayıtları
• İndeks 3 bucket’ı: boş
• İndeks 4 bucket’ı: boş

Ekleme sırasında anahtarın hash değeri hesaplanır ve ilgili indeks bulunur. Bucket boşsa kayıt oraya eklenir. Bucket doluysa yeni kayıt, o bucket içindeki koleksiyona eklenir. Arama işleminde bütün tabloyu dolaşmak yerine önce anahtarın hash değerinden ilgili bucket bulunur; ardından yalnızca o bucket içindeki aday kayıtların anahtarları karşılaştırılır.

Örneğin 12 aranırken önce 12 mod 5 = 2 hesaplanır. Bu nedenle 0, 1, 3 ve 4 indeksleri incelenmez; yalnızca 2 numaralı bucket içindeki 7 ve 12 adayları kontrol edilir. 12 bulunduğunda karşılık gelen değer döndürülür.

Silme işlemi de benzer biçimde ilerler. Önce ilgili bucket bulunur, ardından bucket içindeki kayıtlar arasında gerçek anahtar karşılaştırması yapılır ve eşleşen kayıt koleksiyondan çıkarılır. Hash değerlerinin eşit olması, anahtarların kesinlikle eşit olduğu anlamına gelmediği için yalnızca hash sonucuna bakarak kayıt silmek doğru değildir.

Separate chaining ek bir koleksiyon yapısı ve bu yapının kayıtlarını yönetmek için ek alan kullanabilir. Ayrıca aynı bucket içinde kayıt sayısı arttıkça arama sırasında daha fazla karşılaştırma gerekebilir. Bu yüzden ortalama erişim maliyeti çoğu durumda düşük olsa da bunu her giriş için kesin ve değişmez bir performans garantisi olarak yorumlamamak gerekir. Kullanılan hash fonksiyonunun dağılımı, tablo yoğunluğu ve bucket’ların iç yapısı gerçek davranışı etkiler.

Open Addressing ve Linear Probing Boş Konumu Nasıl Bulur?

Open addressing yaklaşımında kayıtlar, ayrı listelerde değil doğrudan hash tablosunun kendi hücrelerinde tutulur. Hash fonksiyonu bir indeks üretir; ancak bu indeks doluysa algoritma, önceden belirlenmiş bir sıraya göre başka hücreleri kontrol eder. Bu yaklaşımın en kolay anlaşılabilen türü linear probing yöntemidir.

Örneğin tablo boyutunun 5 olduğunu ve basitçe anahtar % 5 formülünü kullandığımızı düşünelim:

• 10: 10 % 5 = 0. 0. hücre boş olduğu için 10 buraya yerleşir.
• 15: 15 % 5 = 0. 0. hücrede 10 bulunduğundan algoritma bir sonraki hücre olan 1'i dener. Hücre boşsa 15, 1. indekse yerleşir.
• 7: 7 % 5 = 2. 2. hücre boş olduğu için 7 doğrudan buraya eklenir.
• 12: 12 % 5 = 2. 2. hücrede 7 bulunduğundan önce 3. hücre kontrol edilir. 3 boşsa 12, 3. indekse yerleşir.

Bu yerleşimde çakışma sonrasında aranan hücreler doğrusal bir sıra izler. Örneğin 12 aranırken önce 2. indeks kontrol edilir; burada 7 olduğu görülürse 3. indekse geçilir ve 12 bulunur. Aynı sıra, tabloda ilgili anahtarın bulunmadığına karar vermek için de kullanılır. Boş bir hücreye ulaşmak çoğu tasarımda aramanın sonlandırılması için önemli bir işarettir.

Silme işlemi linear probing içinde ayrıca dikkat ister. Bir hücre doğrudan “boş” yapılırsa, o hücrenin arkasına yerleşmiş başka bir anahtarı arayan algoritma boş hücreyi görünce aramayı erken bitirebilir. Bu nedenle silinen hücre için özel bir “silindi” işareti tutulabilir veya ilgili bölüm yeniden düzenlenebilir. Buradaki ayrıntı, kullanılan veri yapısının tasarımına ve kütüphaneye göre değişebilir; bu yüzden Python dictionary, Java HashMap ya da C# Dictionary için aynı iç uygulama varsayılmamalıdır.

Chaining ve Linear Probing Hangi Durumlarda Farklı Davranır?

İki yöntemde de aynı anahtarlar kullanılabilir; fark, çakışma gerçekleştiğinde kaydın nereye yerleştirildiğidir. Örneğin 10 ve 15 aynı başlangıç indeksini, 7 ve 12 ise başka bir başlangıç indeksini üretiyorsa chaining, aynı bucket içinde birden fazla kayıt tutar. Linear probing ise kayıtları boş olan ardışık hücrelere dağıtır.

Load factor yükseldikçe tablodaki boş alan azalır. Bu durum linear probing'de ardışık dolu hücre kümelerinin büyümesine, chaining'de ise bazı bucket'ların daha kalabalık hâle gelmesine yol açabilir. Sonuç olarak işlem, ideal dağılımdaki kadar az adayla sınırlı kalmayabilir. Ancak ortalama maliyet ifadeleri kesin bir performans garantisi değil, uygun hash fonksiyonu ve makul doluluk varsayımlarına dayanan analizlerdir.

Bucket içinde esnek biçimde birden fazla kayıt tutma fikrini anlamak isteyen öğrenciler için chaining daha sezgiseldir. Tablo hücrelerini doğrudan kullanmak, boş konum aramak ve yerleşim düzenini takip etmek isteyenler için linear probing daha açıklayıcı bir model sunar. Hangisinin her durumda üstün olduğunu söylemek yerine, veri dağılımı, silme ihtiyacı ve bellek düzeni birlikte değerlendirilmelidir. Bu ayrımı pekiştirmek için Python bilgi testi içinde sözlük ve veri yapılarıyla ilgili temel sorular üzerinden pratik yapılabilir.

Yeniden Boyutlandırma, Rehashing ve Gerçek Programlama Dilleriyle Bağlantı

Hash tablosu doldukça aynı hash fonksiyonu, daha az boş konum arasında seçim yapmak zorunda kalır. Bu nedenle çakışmaların ve arama sırasında kontrol edilen adayların artma ihtimali yükselir. Çözüm olarak tablo daha büyük bir alana taşınabilir. Bu işlem yalnızca eski diziyi büyütmek değildir; kayıtların yeni tablo boyutuna göre indeksleri yeniden hesaplanır. Buna rehashing denir.

Rehashing sırasında birçok kayıt yeniden yerleştirildiği için işlem maliyeti tek bir ekleme gibi düşünülemez. Bazı eklemeler normal biçimde hızlı ilerlerken yeniden boyutlandırma anında toplu bir çalışma oluşabilir. Pratik davranış; anahtarların dağılımına, kullanılan hash fonksiyonuna, tablo tasarımına ve ilgili uygulamanın kapasite politikasına bağlıdır.

Günlük kodda karşılaşılan Python dictionary, Java HashMap ve C# Dictionary yapıları, anahtar-değer eşleştirmesi fikrini hash tablosu kavramıyla ilişkilendirmek için iyi örneklerdir. Ancak bu yapıların güncel iç implementasyonları, çakışma yönetimi ve yeniden boyutlandırma ayrıntıları aynı kabul edilmemelidir. Örneğin Java dokümantasyonu HashMap için kapasite ve load factor kavramlarının yeniden boyutlandırma davranışıyla ilişkili olduğunu belirtirken, Microsoft dokümantasyonu C# Dictionary kapasitesi aşıldığında iç depolamanın yeniden tahsis edilebildiğini açıklar. ([docs.oracle.com](https://docs.oracle.com/en/java/javase/26/docs/api/java.base/java/util/HashMap.html?utm_source=openai))

Bu kavramları yalnızca tanım olarak değil, tablo çizerek, küçük algoritmalar yazarak ve farklı girdilerle deneyerek öğrenmek daha kalıcıdır. Hash table gibi veri yapılarının kod içindeki davranışını düzenli uygulamalarla incelemek isteyenler, canlı sınıflı yazılım eğitimleri üzerinden algoritmik düşünme çalışmalarını gerçek kodlama pratiğiyle ilişkilendirebilir.

Kısa Python Örneği: İki Çakışma Stratejisinin Beklenen Çıktısı

Aşağıdaki örnekte h(k) = k % 5 hash fonksiyonu ve aynı anahtar kümesi kullanılır: 10, 15, 7 ve 12. İlk olarak separate chaining, ardından linear probing mantığı uygulanır.

keys = [10, 15, 7, 12]

chaining = [[] for _ in range(5)]
for key in keys:
    chaining[key % 5].append(key)

probing = [None] * 5
for key in keys:
    index = key % 5
    while probing[index] is not None:
        index = (index + 1) % 5
    probing[index] = key

print("Chaining:", chaining)
print("Linear probing:", probing)

Beklenen çıktı şöyledir:

Chaining: [[10, 15], [], [7, 12], [], []]
Linear probing: [10, 15, 7, 12, None]

Chaining yönteminde aynı bucket içinde birden fazla anahtar tutulur. Bu nedenle 10 ve 15, hash değerleri aynı olduğu için 0 indeksindeki listede yer alır. Benzer şekilde 7 ve 12 için başlangıç indeksi 2’dir.

Linear probing ise dolu hücreyi görünce sonraki uygun konumu arar. Böylece 10 0’a, 15 1’e, 7 2’ye ve 12 3’e yerleşir. Bu eğitim kodu çakışma mantığını göstermek içindir; üretim ortamındaki Python dictionary davranışı, yalnızca bu basitleştirilmiş örnekle açıklanamaz.

• Önce hash değerini hesapla: 10 % 5 = 0.
• İlk indeksi bul ve hücrenin boş olup olmadığını kontrol et.
• Hücre doluysa kullanılan yöntemi belirle.
• Chaining için aynı bucket’a ekle; probing için sonraki boş hücreyi ara.
• Arama sırasında aynı yöntemin izlediği yolu yeniden takip et.

Sık Sorulan Sorular

Hash table collision olduğunda mevcut veri silinir mi?

Doğru tasarlanmış bir çakışma çözümünde mevcut veri doğrudan silinmez. Separate chaining yeni kaydı aynı bucket içindeki yapıya ekler; linear probing ise boş bir hücre bulana kadar ilerler. Ancak hatalı bir uygulama, dolu hücreyi kontrol etmeden üzerine yazarsa veri kaybı oluşabilir.

Hash değeri neden farklı anahtarlar için aynı olabilir?

Hash tablosundaki indeks sayısı sınırlıdır, anahtarların olası değerleri ise çok daha geniş olabilir. Bu nedenle farklı anahtarlar aynı indeks aralığına indirgenebilir. Örneğin 10 % 5 ve 15 % 5 işlemlerinin sonucu aynıdır. Bu durum çakışma olarak adlandırılır.

Separate chaining ile linear probing arasındaki temel fark nedir?

Separate chaining, aynı indekse gelen kayıtları bucket içindeki bağlı bir yapı veya listeyle birlikte tutar. Linear probing ise tablo içinde başka boş hücre arar. Birinde bucket içi yapı büyür, diğerinde kayıtlar komşu hücrelere doğru yayılır.

Load factor yükseldiğinde hash tablosunda ne değişir?

Load factor yükseldikçe tabloda boş hücre sayısı azalır ve çakışma çözümü için daha fazla adım gerekebilir. Özellikle linear probing’de uzun dolu kümeler oluşabilir. Bu nedenle uygulamalar belirli bir doluluk seviyesine ulaşıldığında tabloyu büyütüp kayıtları yeni indekslere göre yeniden yerleştirebilir.

Bir hash tablosunu elle analiz ederken yalnızca hash değerine değil, çakışma çözüm yöntemine ve arama sırasında izlenen yola da bakmak gerekir.