LICH (Last Insertion Coalesced Hashing)

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:

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:

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:

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ıradaki sayımı 28 mod 7 = 0. Sıraya problemsiz bir şekilde yerleşir:

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ı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ıradaki sayımı 16 mod 7 = 2. Sıraya problemsiz bir şekilde yerleşir:

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ıradaki sayımı 17 mod 7 = 3. Sıraya problemsiz bir şekilde yerleşir:

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.