Yazan : Şadi Evren ŞEKER

Türkçeye, son ekleme 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 alanını iki parçaya ayıran bu algoritmada amaç çakışma sonucu oluşan alanlar ile doğru adreste indekslenen verilerin ayrılmasıdır.

Kabaca aşağıdaki şekil gibi düşünebiliriz:

Yukarıdaki şekilde görüldüğü üzere, indeksleme alanı ana alan (primary) ve çakışma alanı (overflow) olarak ikiye bölünmüş ve dolayısıyla çakışmadan dolayı farklı bir sıraya yerleşen sayılar ile olması gereken yerde bulunan sayılar birbirinden ayrılmıştır.

Yöntemimiz, 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 7 olarak verilsin.

Bu duruma mod 7 için 7 farklı alandan oluşan boş bir dizimiz bulunacaktır. Bu 7 sıra içeren ana indeksleme alanının yanında bir de çakışma alanımız (overflow) bulunmalıdır. Bu alanı da problemimizde 4 olarak tanımlayalım:

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 dikkat edilirse 6. Ve 7. Sıralar arasında da bir çizgi ile ana indeksleme ve çakışma indeksleme alanları ayrılmıştır. Amacımız çakışarak farklı yere yerleştirilen sayılar ile doğal indeksleme sırasında bulunan sayıları ayırmaktı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 7 = 6 olarak bulunur ve çakışma olmadan sorunsuz bir şekilde eklenir:

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

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

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

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

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

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

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

Sıradaki sayımı 39 mod 7 = 4. Sıraya yerleşmesi gerekir. Ancak 4. Sırada daha önceden yerleştirilen 18 sayısı bulunmaktadır. Bu durumda sayı çakışma durumunda olduğu üzere çakışma alanındaki sondan boş olan ilk yere yerleştirilir. Çakışma alanımız 7 ile 10. Sıralar arasıdır ve şu anda bütün sıralar boştur. Bu sıralardan en altta olan 10. Sıraya çakışan sayımızı yerleştiriyoruz. Sayımızın normalde olması gereken 4. Sıraya da 10. Sıraya bir çakışan sayı yerleştirdiğimiz için bağlantı ekliyoruz ve 4’ten 10. Sıraya aşağıda görüldüğü üzere ilerideki aramalar için bir bağlantı kuruluyor:

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

Sıradaki sayımı 13 mod 7 = 6. Sıraya yerleşmesi gerekirken yine bir çakışma ile karşılaşıyoruz. Çakışan sayılar için ayrılan alt alanımızdaki en alttaki en boş sıra 9 ve çakışan sayı buraya yerleştiriliyor, ilave olarak bir bağlantı ile sayının 6. Sırada olması gerekirken yerleştirildiği bu çakışma sırası bağlanıyor:

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

Sıradaki sayımı 16 mod 7 = 2. Sıraya problemsiz bir şekilde yerleşir:

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

Sıradaki sayımı 42 mod 7 = 0. Sıraya yerleşmesi gerekirken yine bir çakışma ile karşılaşıyoruz. Çakışan sayılar için ayrılan alt alanımızdaki en alttaki en boş sıra 8 ve çakışan sayı buraya yerleştiriliyor, ilave olarak bir bağlantı ile sayının 0. Sırada olması gerekirken yerleştirildiği bu çakışma sırası bağlanıyor:

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

Sıradaki sayımı 17 mod 7 = 3. Sıraya problemsiz bir şekilde yerleşir:

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

Yukarıdaki örnekte görüldüğü üzere özetleme fonksiyonu sonucunda çakışan sayılar, çakışma alanına (overflow) yerleşirken 0 ile 6. Sıralar arasında belirlenen ana alanda sadece özetleme fonksiyonundan gelen asil sayılar durmaktadır. Bu durumu EISCH yöntemi ile karşılaşırsak, sayıları düzenli bir şekilde yerleştirmesi LICH yönteminin bir avantajıdır. Ancak Ayrılan çakışma alanı veya ana alanın dolması durumunda diğer alanı kullanamıyor olması LICH yönteminin yer israfı yapmasına sebep olur. Bu ise bir dezavantaj olarak görülebilir. Yani yukarıdaki örnekte, 2 adet çakışma daha olsaydı, çakışma alanında tek yer olduğu için 2. Çakışmayı yerleştiremeyecek özetleme alanımız dolu hatasını verecektik. Oysaki EISCH yöntemi burada boş olan herhangi bir yeri kullanabilmektedir.

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 çakışma alanında (overflow) bulunan boş en alt hücreye yerleştir ve bu yerleştirdiğin yere, normalde yerleşmesi gereken yerden bir bağlantı kur

Yukarıdaki bu 2 basit adım takip edilerek LICH 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 13 olduğunu düşünelim. 13 mod 7 = 6 olarak bulunur ve 6. Sırada bu sayı aranır. Sayı burada olmadığı için buradaki bağlantı olan 9. Sıraya gidilip bakılır ve 13 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 7 = 6 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 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.

LICH 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.

LICH algoritmasının farklı uygulamalarına göre çeşitli isimlendirmelerin kullanılması da mümkündür. Örneğin, 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.

Yorumlar

  1. tuğba aksu

    Alan L. Tharp, File Organization and Processing kitabında lisch için the standart in the name refers to lack of o cellar ve genel olarak lisch in bir overflow area kullanmadığından bahsediyor ancak siz lisch yi çakışma alanı ile kullanmışsınız acaba benim kacırdığım bir şey mi var yoksa lisch derken aslında lich mi demek istediniz

  2. Şadi Evren ŞEKER Article Author

    Doğrusu LICH olacaktır. Yazıda yanlışlıkla lisch olarak yazılmış. Alan Tharp’ın yazdığı doğrudur, yazıdan da bu hatayı düzeltiyorum. ilginiz ve uyarınız için teşekkürler

  3. nakruta

    Yazılarınız için teşekkür ederim, packing factor ve average probe için de hesaplama ve açıklama yapmanız mümkün mü?

  4. Şadi Evren ŞEKER Article Author

    Hemen ekleyelim. Average probe (ortalama sondalama) sayısı için her veriye ne kadar sondalama ile erişildiğini hesaplamamız gerekir. Bu değerin hesaplanması gayet basittir.
    Yukarıdaki örneğe özel olarak
    Ana indeksleme alanındaki anahtarlara tek erişimde
    Çakışma indeksleme alanındaki anahtarlara ise iki erişimde ulaşılır.

    Yukarıdaki örneğin son halinde ana indekseleme alanında 6 adet anahtar bulunurken, çakışma indeksleme alanında 3 anahtar bulunmaktadır. Bu durumda 6 x 1 + 3 x 2 = 12 bu değer toplam sondalama değeridir, ortalama sondalama için bu değeri anahtar sayısına bölüyoruz 12 / 8 = 1.5 olarak ortalama sondalama sayısını bulabiliriz. Yani diğer bir değişle bu anahtarlardan birisi arandığında ortalama 1.5 sondalama yapılması gerekecektir.

    Gelelim paket yoğunluğunu (packing factor, packet density, load factor) değerini hesaplamaya. Bu değeri hesaplamak için toplam kapasitenin ne kadarını kullandığımıza bakıyoruz.

    Yukarıdaki örneğin son durumunda 10 kapasiteli bir tablonun 8 adresinde anahtar bulunuyor. Bu durumda paket yoğunluğumuz 8/10 = %80’dir denilebilir.

  5. Şadi Evren ŞEKER Article Author

    Sorunuzu anlayamadım. Overflow zaten taşma alanı. Yani çakışma (collision) anında kullanılacak alana verilen isim. LISCH yönteminde bu alan zaten tanımlı, verilmemesi gibi birşey söz konusu değil. Farklı hashing algoritmalarında çakışma alanı kullanmadan da hashing yapılabiliyor. Örneğin linear hashing konusunu okursanız, burada ilave bir overflow alanı olmadığını görürsünüz.

  6. Şadi Evren ŞEKER Article Author

    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.

    başarılar

  7. Anonim

    Hocam yazılarınız için teşekkür ederim, lich ve eisch c kodlarını sitenizde bulamadım yayınladığınız başka bölüm varmı?

  8. Orhan

    Hocam teşekkürler bilgileriniz için fakat bir sorum olacak.Hash fonksiyonu key mod 11 olsa nasıl olacaktı bu yerleşim ?

ezgi için bir cevap yazın Cevabı iptal et

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