LICH(Last Insertion Coalesced Hashing)

Tekrar merhaba arkadaşlar,

Dün yazmış olduğum LISCH metoduna, Link Atarak çarpışmaları(collision) önleme yöntemlerimize, bugün LICH ile devam ediyoruz. Önceki yazı için bkz. http://gurkanalkan.blogspot.com/2010/11/lischlast-insertion-standart-colesced.html

LICH yönteminde iki parçalı yapı mevcut. Biri Primary Area dediğimiz, gelen kayıtları yerleştirdiğimiz alan; diğeri ise Overflow Area dediğimiz, collision'a sebep olan kayıtları yerleştirdiğimiz alan.

Primary Area

Overflow Area

LISCH konusunda o kadar detaylı yazdım ki bazı kavramları, burada daha yüzeysel geçeceğim. Diğer makaleye bağımlı kalın diye yapıyorum. :P :)

Dilerseniz Alan Tharp'ın kitabındaki soruyu burada beraber yapalım..

SORU:
27-18-29-28-39-13-16-42-17
hash(key)=key mod 7

ÇÖZÜM:
Tablo boyutunu ayarlayarak işe başlayalım yine. mod 7 dediği için 0-6 arası bir tablo kullanacağız ama burada LISCH'ten farklı olarak, bu tablo sadece Primary Area dediğimiz bölgedir. Bir de küçük bir kısım Overflow Area için kullanırız. Overflow Area için de, tabloyu 10'a tamamlamak için, 4 satır kullanalım.

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5
6
///////////	/////////////////////	///////////////
7
8
9
10

Tablomuz yukarıdaki gibi 2'ye bölünmüştür. 27'yi yerleştirerek işe başlayalım.hash(27)=6 mod 7
27'yi 6 numaralı göze sorunsuz bir şekilde yerleştiririz. Tablo şu hale gelir.

Sıra	Anahtar Değeri	Link
0
1
2
3
4
5
6	27
///////////	/////////////////////	///////////////
7
8
9
10

18'i yerleştirelim şimdi de.
hash(18)=4 mod 7
18 değeri de 4 numaralı göze sorunsuzca yerleştirilir.

Sıra	Anahtar Değeri	Link
0
1
2
3
4	18
5
6	27
///////////	/////////////////////	///////////////
7
8
9
10

Sıra geldi 29'u ve 28'i yerleştirmeye.
hash(29)=1 mod 7
hash(28)=0 mod 7
29 değerini 1 numaralı göze, 28 değerini de 0 numaralı göze sorunsuzca yerleştirdik. Tablo şu hale geldi:

Sıra	Anahtar Değeri	Link
0	28
1	29
2
3
4	18
5
6	27
///////////	/////////////////////	///////////////
7
8
9
10

 39'u yerleştirelim şimdi de.
hash(39)=4 mod 7.
39'u 4 numaralı göze yerleştiremiyoruz, orası dolu, 18 var. Collision(çarpışma) oldu! Collision'a sebep olan 39 değerini overflow area'nın en sonundaki müsait/boş olan alanına yerleştiririz. Yani 10 numaralı göze... 4 numaralı gözden de, 10 numaralı göze link atarız. Sebebini diğer başlıkta yazmıştım. son kez burada bir daha yazmış olayım. 39 değerini kaybetmemek için link atıyoruz. 39'u bu tabloda aradığımızda 4 numaralı göze gideriz ama orada başka değer var. O yüzden 4 numaralı gözden 39'un olduğu yere link atarız ki bulabilelim. Tablo şu hale gelir. 

Sıra	Anahtar Değeri	Link
0	28
1	29
2
3
4	18	10
5
6	27
///////////	/////////////////////	///////////////
7
8
9
10	39

13'ü yerleştirelim şimdi de.
hash(13)=6 mod 7
13'ü de yerleştiremiyoruz çünkü 6 numaralı göz dolu. 13'ü de overflow area'da 9 numaralı göze yerleştiriyoruz çünkü en alttan baktığımızda, orası müsait(10 numaralı göz demin dolmuştu). 6 numaralı gözden de, 9 numaralı göze link atıyoruz. Tablo şu hale geldi:

Sıra	Anahtar Değeri	Link
0	28
1	29
2
3
4	18	10
5
6	27	9
///////////	/////////////////////	///////////////
7
8
9	13
10	39

16'ya geldi sıra.
hash(16)=2 mod 7
2 numaralı göz zaten boş olduğundan sorunsuzca yerleştirdik. Tablonun son hali:

Sıra	Anahtar Değeri	Link
0	28
1	29
2	16
3
4	18	10
5
6	27	9
///////////	/////////////////////	///////////////
7
8
9	13
10	39

42'ye geçelim.
hash(42)=0 mod 7
0 numaralı göz dolu olduğundan, 42'yi overflow area'ya, müsait olan göze[8 numaralı göz], yerleştiririz. 0 numaralı gözden de link atarız. Tablo şu hale gelir:

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

Son olarak 17 kaldı.
hash(17)=3 mod 7
3 numaralı göz boş olduğundan, 17 değeri sorunsuzca yerleştirilir. Tablo şu hale gelir nihai olarak:

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

Böylelikle tabloya yerleştirmiş olduk. Şimdi bir iki husustan bahsedeceğim ki LISCH'ten farkını daha net görebilelim. Bunda da sona eleman attığımızdan, farkını tam kavrayamayanlar vardır muhtemelen. Eğer overflow area dolarsa ne yaparız? Doldurmayacak bir değer seçeriz genelde. :) Dikkat ettiyseniz, 4 gözlük bir overflow area'yı ben kendim uydurdum. O açıdan bu çok sıkıntı yaratamaz. Asıl soruna gelelim. Örneğin home address'i(hash'ten dönen değeri) 4 olan bir sayı daha olsaydı ne yapacaktık? 4 dolu malum. 4 numaralı gözden zaten link atılmış. Peki o zaman overflow area'dan link mi atacaktık? HAYIIIIR. :) Sıkı durun şimdi. :) Primary Area'yı 1 göz azaltacaktık(örneğimize göre 0-5 arası olurdu), overflow area'yı da 1 göz arttıracaktık(örneğimize göre 6-10 arası olurdu). Mod'u da haliyle 7 değil, 6 yapacaktık. Ve herşeyi sil baştan hesaplayacak, ona göre tekrar tabloyu dolduracaktık. :)

Son olarak average probe değerini(verilere ortalama kaç adımda ulaşılacağı) hesaplayalım. LISCH konusunda detaylı anlattığım için buraları hızlı geçiyorum.

27 değerine 1 adımda ulaşıyoruz.
18 değerine 1 adımda ulaşıyoruz.
29 değerine 1 adımda ulaşıyoruz.
28 değerine 1 adımda ulaşıyoruz.
39 değerine 2 adımda ulaşıyoruz.
13 değerine 2 adımda ulaşıyoruz.
16 değerine 1 adımda ulaşıyoruz.
42 değerine 2 adımda ulaşıyoruz.
17 değerine 1 adımda ulaşıyoruz.
Toplamda 12 adımda tüm değerlere ulaşıyoruz. 9 tane de değer olduğuna göre=> 12/9=1,33 de average probe olur. LISCH'de de aynı değerleri kullanmış ve average probe'u 1,78 bulmuştuk. Görüldüğü üzere LICH yöntemi, LISCH yöntemine göre daha etkili...
Son olarak Address Factor diye bir kavram var. O da şudur: Primary Area/Total Table Size.
Yani verileri yerleştirdiğimiz alan, toplam tablo boyutunun kaçta kaçı olduğunu bize veriyor. Bu oranı yaklaşık %85lerde tutmamız gerekiyor.

Bir yöntemin daha sonuna geldik. Ben de fenerin yenilişini keyifle izlemeye gideyim artık. :)
Sonra görüşürüz.