EISCH (Early Insertion Standart Coalesced Hashing)

Yazan : Şadi Evren ŞEKER

Türkçeye, erken ekleme standart birleştirme özetlemesi olarak çevrilebilir. Bilgisayar bilimlerinde, özellikle dosya yönetimi konusunun (file organization) kullandığı bir özetleme (hashing) çakışması (collision) çözüm algoritmasıdır. Basitçe bir özetleme fonksiyonu (hashing function) sonucunda, çalışma olması durumunda (collision), dizinin sonundan başa doğru boş bulunan ilk yere yerleştirmeyi söyler.

Bu durumu bir örnek üzerinden anlamaya çalışalım.

Eklenecek olan sayılarımız 27, 18, 29, 28, 39, 13, 16, 42, 17 olsun. Kullanacağımız özetleme fonksiyonu ise H : K mod 11 olarak verilsin.

Bu duruma mod 11 için 11 farklı alandan oluşan boş bir dizimiz bulunacaktır:

Yukarıdaki boş tabloda, sıra sütunu, verilerin ekleneceği yeri, anahtar sütunu örnekte verilen sayıların nereye eklendiğini, bağlantı sütunu ise, arama ve ekleme işlemleri sırasında bir sayının beklenen yerde bulunamadığında nerede aranacağı bilgisini tutmaktadır.

Ayrıca yukarıda görülmeyen bir gösterici (Biz buna R diyelim), tablonun boş olan en alt elemanını göstermektedir. Yani şu anda R = 10 olarak başlayabiliriz.

Bu anlamda eisch algoritması bağlantılı çakışma çözümü (collision with links) yapmaktadır. Yani bir çakışma durumunda, konulması gereken sıraya değil farklı bir sıraya, bir sayı konulduğunda, bu yer bağlantı bilgisinde durmaktadır.

Yukarıdaki örnekte bulunan sayıları sırasıyla ekleyelim. İlk sayımız 27 için sıra hesaplanır ve 27 mod 11 = 5 olarak bulunur ve çakışma olmadan sorunsuz bir şekilde eklenir:

Ardından eklenen sayımız 18 için sıra hesaplanır ve 18 mod 11 = 7 olarak bulunur ve çakışma olmadan sorunsuz bir şekilde eklenir:

Ardından eklenen sayımız 29 için sıra hesaplanır ve 29 mod 11 = 7 olarak bulunur. Yukarıdaki görüldüğü üzere 7. Sıra doludur ve dolayısıyla bir çakışma durumu söz konusudur. Çakışma durumunda R ile gösterilen adrese bu çakışan yeni sayı yerleştirilir. Bu durumda R ile gösterilen ve boş hücrelerin en alttaki olan 10. Sıraya yerleştirme yapıyoruz. Ayrıca normalde 7. Sıraya yerleşmesi gereken 29 sayısını, farklı bir yere yerleştirdiğimiz için 7. Sırada bir bağlantı kurup, 7. Sırada bulunamayan sayılar için 10. Sıraya bakmasını söylüyoruz:

Sıradaki sayımı 28 mod 11 = 6. Sıraya problemsiz bir şekilde yerleşir:

Bir sonraki sayı olan 39 mod 11 = 6, yerleştirilirken çakışma olur ve şu anda R değeri olan, boş hücrelerin en altındaki 9. Sıraya yerleştirilir. Ayrıca 6. Sıraya yerleşmesi gerekirken, 9. Sıray a yerleşen bu sayı için 6’dan 9’a bir bağlantı kurulur:

13 sayısı sorunsuz bir şekilde 13 mod 11 = 2. Sıraya yerleştirilir:

16 sayısı ise 16mod11= 5. Sıra dolu olduğu için çakışır. Bu durumda R değeri olan en alttaki boş hücreye yani 8. Sıraya 16 sayısı yerleştirilip 5. Sıradan 8. Sıraya bağlantı kurulur:

42 sayısı da benzer şekilde problemli bir sayıdır. 42 mod 11 = 9. Sıra doludur ve şu anda en alttaki boş hücre 4’tür. Bu durumda sayı 4. Sıraya yerleştirilerek 9. Sıradan buraya bir bağlantı oluşturulur:

Son olarak gelen 17 sayısı, yerleşmesi gereken 17 mod 11 = 6. Sıra dolu olduğu için en alttaki boş hücre olan 3. Sıraya yerleştirilir. Ardından 6. Sıradan buraya bağlantı oluşturulması gerekir. Ancak yukarıda görüldüğü üzere 6. Sırada zaten bir bağlantı vardır ve bu bağlantı 9. Sıraya işaret etmektedir. Bu durumda çözüm olarak yeni yerleştirilen sıra ile 6. Sıradaki bağlantı değiştirilir ve 6. Sırada zaten var olan bağlantı yeni yerleştirilen sayıya konulur:

Yukarıdaki bu problemli durumda görüldüğü üzere 17 sayısı 3. Sıraya yerleştirilmiş dolayısıyla 6’da bulunan eski bağlantı değeri olan 9, 3. Sıradaki bağlantı olarak taşınmış bunun yerine de yeni sayıyı yerleştirdiğimiz sıra olan 3 yazılmıştır.

Yukarıdaki bu durumu, bağlantı seviyesinin 2’den fazla olmaması olarak da yorumlamak mümkündür. Yani eski durumda şayet 28 → 39 → 42 → 17 bağlantısı kurulacak olsaydı, bu durumda 3 atlama yapılması gerekecekti. Bunu engellemek için yukarıdaki çözüm kullanılmıştır.

Yukarıdaki örnekte sayıların nasıl yerleştirildiğini gördük. Bu yöntemi özetleyecek olursak:

1. Yerleşecek sayının (anahtarın) özetleme fonksiyonu değerini (hashing function) hesapla ve buraya yerleştir.
2. Şayet burası doluysa, dizideki boş en alt hücreye yerleştir ve bu yerleştirdiğin yere, normalde yerleşmesi gereken yerden bir bağlantı kur
3. Sayının, normalde yerleşmesi gereken yerde bir bağlantı varsa, bu bağlantıyı yeni yerleşen sayının yanına taşı.

Yukarıdaki bu 3 basit adım takip edilerek EISCH algoritmasına göre yerleştirme işlemi yapılabilir.

Yerleşen bu sayıların aranması ise oldukça basittir.

Örneğin aranan sayının 17 olduğunu düşünelim. 17 mod 11 = 6 olarak bulunur ve 6. Sırada bu sayı aranır. Sayı burada olmadığı için buradaki bağlantı olan 3. Sıraya gidilip bakılır ve 17 sayısı bulunmuş olunur.

Benzer şekilde, dizide hiç bulunmayan bir sayı aranırsa, bağlantısı olmayan bir sıraya gelindiğinde bu sayının dizide olmadığına kanaat getirip durulabilir. Örneğin dizimizde olmayan 34 sayısını aramak istediğimizi düşünelim.

34 mod 11 = 3 bulunup bu sıraya bakılacak, bu sırada 34 olmadığı görülünce bağlantının gösterdiği 9. Sıraya oradan da 4. Sıraya bakılacak ve nihayet herhangi bir bağlantı olmadığı ve bu bakılan sayılardan hiçbiri 34 olmadığı için bu sayının dizide olmadığı neticesine varılacaktır.

Dolayısıyla arama algoritmasını aşağıdaki şekilde yazabiliriz:

1. Sayının özetleme fonksiyonu (hashing function) değerini hesapla ve sayıyı bu bulduğun sırada ara
2. Sayı burada ise sayıyı buldun. Aramayı bitir.
3. Sayı yoksa ve bağlantı varsa bağlantıyı takip edip 2. Adıma git.
4. Bağlantı yoksa sayı dizide yok demektir.

Yukarıda anlatılan EISCH yöntemine göre aranan sayıların dizide, alttan yukarı doğru doldurulması gerekmektedir. Ayrıca EISCH yönteminin bir dezavantajı çakışan ve çakışmayan bütün sayıların karışık bir şekilde iç içe durmasıdır. Bu problem LICH yönteminde veya CCI yönteminde çözülmüştür.

EISCH yöntemi yine sınıflandırma bakımından sabit metot (static method) olarak kabul edilebilir. Bundan kasıt, bir sayı bir sıraya yerleştikten sonra buradan hareket edemez, ilk defa yerleştiği yerde kalır.