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:

Sıra Anahtar Bağlantı
0
1
2
3
4
5
6
7
8
9
10

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:

Sıra Anahtar Bağlantı
0
1
2
3
4
5 27
6
7
8
9
10

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:

Sıra Anahtar Bağlantı
0
1
2
3
4
5 27
6
7 18
8
9
10

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ıra Anahtar Bağlantı
0
1
2
3
4
5 27
6
7 18 10
8
9
10 29

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

Sıra Anahtar Bağlantı
0
1
2
3
4
5 27
6 28
7 18 10
8
9
10 29

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:

Sıra Anahtar Bağlantı
0
1
2
3
4
5 27
6 28 9
7 18 10
8
9 39
10 29

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

Sıra Anahtar Bağlantı
0
1
2 13
3
4
5 27
6 28 9
7 18 10
8
9 39
10 29

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:

Sıra Anahtar Bağlantı
0
1
2 13
3
4
5 27 8
6 28 9
7 18 10
8 16
9 39
10 29

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:

Sıra Anahtar Bağlantı
0
1
2 13
3
4 42
5 27 8
6 28 9
7 18 10
8 16
9 39 4
10 29

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:

Sıra Anahtar Bağlantı
0
1
2 13
3 17 9
4 42
5 27 8
6 28 3
7 18 10
8 16
9 39 4
10 29

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.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Evet, daha önce de bir arkadaş aşağıdaki yazıda benzer bir soru sormuştu:
    http://www.bilgisayarkavramlari.com/2010/03/25/lisch-last-insertion-standard-coalesced-hashing/
    Cevaben açıklamayı aşağıdaki şekilde yapmıştım:
    Bunlar LISCH algoritmasının çeşitleridir. BLISCH algoritmasındaki B harfi, ingilizce bidirectional (iki yönlü) kelimesinden gelmektedir ve hashte olan taşmaların (overflow) iki yönde de olabileceğini (yani klasik lisch algoritmasındaki gibi her zaman sona değil de hashin başına da yönlendirilebileceğini) ifade eder.
    Örneğin RLISCH çeşidinde ise R harfi Random (rastgele) kelimesinden gelmektedir ve ekleme yapılacak yer rast gele olarak seçilir.

    Aynı durum REISCH ve BEISCH olarak da geçebilir. Yani sorunuzdaki reisch, random olarak yukarıdaki eisch algoritmasının uyarlanmış halidir.

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir