COALESCED HASHING

Coalesced hashing , diğer bir ismiyle Coalesced chaining karmaşık yapıda olan zincirleri düzenlemek için oluşturulan bir stratejidir.

Örneğin bir sınıfta 40 kişi olsun ve bu kişilerin numaraları 6 haneli olsun. Bu kişilerin bilgilerine arama yapmadan, direk ulaşabilmek için bir array oluşturmak istersek nasıl yapabiliriz? İlk düşünce 999999’luk bir array oluşturur ve her kişiyi kendi numarasına göre yerine yerleştirmektir. Böyle yaptığımız zaman kullanılmayan numaraların yerleri boşa tutulmuş olacaktır.

Peki kişi sayısı kadar oluşan bir array içerisine bu kişileri nasıl yerleştirmeliyiz ki arama süresini kısaltarak ulaşabilelim. İşte coalesced hash tablosu ile bu soruya cevap bulabilmemiz mümkündür.

Öğrencileri belli bir sayının moduna göre o listeye yerleştirelim. Sayımız 59 olsun. Asal olması her zaman daha iyi sonuç verecektir. Asal sayı seçilmesi durumunda aynı yere yerleşmek isteyen öğrencilerin sayısı azalacaktır. Sayının aşırı küçük seçilmesi aynı şekilde birçok öğrenciyi aynı yere atamak isteyecektir. Sayının çok büyük seçilmesi işlem süresini uzatacaktır.

Öğrenci Numarası % 59' a göre öğrencileri yerleştirelim. Çıkan sonuçun arraydeki yeri boş ise öğrenci oraya yerleşsin. Sonucun aynı gelmesi durumunda arraydeki yer dolu olacaktır. Bu durumda örneğin 1 ilersine bakalım. Orası boş ise oraya yerleştirelim. Orasıda dolu ise gene 1 ilerisine bakalım ve oraya yerleştirelim. Bu şekilde doldurduğumuzda güzel bir sonuç ortaya çıkacaktır.

Örneğin bir öğrenciye ulaşmak istediğimizde öğrenci numarası % 59 = 43 olsun. Direk array üzerinde 43 numaralı indexe bakılır. Öğrenci ya direk burdadır ya da bu aynı indexe yerleşmiş başka bir öğrencidir. Eğer öğrenci numaraları eşleşiyorsa işlem tamamdır. Öğrenci numaraları eşleşmiyor ise eşleşene kadar bir sonraki array indexine bakılır.

Sonuç olarak toplam probe ( erişim ) sayısında düşme söz konusudur ve erişilmek istenen bilgiye daha hızlı erişilir. Aşağıda 58 kişilik bir sınıf için hash tablosu oluşturan ve toplam probe sayısını hesaplayan bir C kodu bulunmaktadır.

KODLAR