LISCH(Last Insertion Standart Coalesced Hashing)

Merhaba arkadaşlar,

Collision kavramından daha önce bu blogda bahsetmiştim. Dileyenler arattırıp bakabilir. Collision Resolution dediğimiz, çarpışmaları engelleme yöntemleri mevcuttur. Bunlar:

• Bağlantı ile(With Links)
• Bağlantı Olmadan(Without Links)
• Yalancı Link ile(With PseudoLinks)

Bağlantı(Link) ile çözüm yöntemlerinden olan LISCH, bugünkü konumuz arkadaşlar... Yani isimden de anlaşıldığı üzere, coalesced olduğunda, gelen kaydı en sona atıyoruz. Coalesced'in de ne olduğuna değineceğim, biraz sabır. :) Konuyu en iyi örnek üzerinde anlatabilirim. O yüzden direkt örneğe geçiyorum.

SORU:
27-18-29-28-39-13-16-42-17 şeklinde bir dizi sayı gelmiş ve
hash(key)=key mod 11

ÇÖZÜM:
İlk önce yerleştireceğimiz tablo boyutunu ayarlamalıyız. Soruda mod 11 dediği için tablomuz 0 ile 10 arasında olacaktır. Ayrıca R diye bir değer de tutalım. Bu da bize tabloyu sondan tarasın ve boş yeri söylesin. İlk başta R=10. Çünkü collision yok ve en son gözü gösteriyor. (Eğer sona bir eleman eklenseydi, R=9 derdik. Yani en sondan bir önceki eleman müsait anlamında...)

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

Tablomuz yukarıdaki gibidir. 27'yi yerleştirerek işe başlayalım.
hash(27)=5 mod 11
27'nin mod 11'e göre hash'i 5 değerini verdi.(27/11=2 kalan=5. Kalan değer, bize hash değerini veriyor.)
Bu yüzden 27'yi 5 numaralı alana yazıyoruz. Collision yok. R=10 hala. Tablonun yeni hali aşağıdadır.

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

 Şimdi ise 18'i yerleştirelim.
hash(18)=7 mod 11 (18/11=1 Kalan=7)
 18 değerini de 7 numaralı göze yerleştirelim o halde. Collision yok. R=10 hala. Tablomuz şöyle oldu:

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

Sıradaki kaydımız 29.
hash(29)=7 mod 11. İşte burada bir collision oluştu! Çünkü 7 numaralı gözde 18 var şu anda. 29 da aynı yeri gösteriyor. O yüzden LISCH mantığı gereği, 29'u en sondaki müsait yere atıyoruz. Çünkü hatırlarsanız algoritma gereği collision olduğunda, collision'a sebep olan değer en sona atılıyordu. Bu müsait yeri R ile tutmuştuk hatırlarsanız. R=10 idi. Yani 10 numaralı göze, collision'a neden olan 29 değerini atıyoruz. Artık 10 numaralı göz dolu. R=9 oldu (Alttan taramaya başlayınca, en sondaki müsait değer).
Ancak şu var! 29'u tabloda bulmak istersek, 7 numaralı göze bakarız. Çünkü hash değeri 7 çıkıyor. Ama 7 numaralı gözde 18 var. 29 değeri kaybolmasın diye 7 numaralı gözden, 29'u yerleştirdiğimiz 10 numaralı göze link atarız(şimdi neden bu yöntemin "with links" diye adlandırıldığını anlamışsınızdır). Tablo şu şekle gelir.

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

Üstteki tabloya dikkat buyurun şimdi. 7 numaralı hücreye baktığınızda link alanında 10 yazdığını görürsünüz. Yani hash değeri 7 olan bir diğer değer, 10 numaralı gözde imiş.

Sıradaki değerimiz 28.
hash(28)=6 mod 11
28 değerini sorunsuz bir şekilde 6 numaralı göze yerleştirelim. R=9 hala...
 Tablonun son hali şöyle:

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

Yeni değerimiz 39.
hash(39)=6 mod 11. 39 değerini 6 numaralı göze yerleştiremiyoruz çünkü orada 28 değeri var. Az önceki gibi collision oldu. Yapılacak işlem tamamen aynı. Collision'a sebep olan 39'u R değerine yerleştiriyoruz. R değeri en son 9 idi. O yüzden 39'u 9 numaralı göze yerleştiriyoruz. R=8 oldu(sondan başlayınca boş/müsait olan göz 8 çünkü). 28'in bulunduğu 6 numaları gözden, 39'un bulunduğu 9 numaralı göze de link atarız ki 39 değeri kaybolmasın.. Tablo şu şekle gelir.

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

13 değerine geçelim.
hash(13)=2 mod 11.    2 numaralı göz boş olduğundan, 13 değerini sorunsuzca yerleştiriyoruz. R=8 hala... Tablo şu hale geldi:

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

 16 değeri var sırada.
hash(16)=5 mod 11.
16 değerini 5 numaralı göze yerleştiremiyoruz zira orada 27 değeri var. Yine bir collision vakası. :P :) Hafıza-i beşerin nisyan ile malul olmasından mütevellit bir kez daha anlatıyorum. :) Bu cümleyi yazdığım sırada Mein Herz Brennt çalıyordu. Yan etkileri diyeyim artık. :D
Collision'a sebep olan 16 değerini, R ile tuttuğumuz sondaki müsait göze yerleştiririz. R=8 idi en son. Bu yüzden 16'yı 8 numaralı göze yerleştiriyoruz. 27'den de 16'ya link atıyoruz. Yani 27'nin durduğu 5 numaralı gözün link değerine 8 yazıyoruz ki 16 değeri kaybolmasın... R değeri en son 8 idi. Şu an 7 olamaz, orası boş değil,18 değeri var. R değeri 6 da olamaz, orada da 28 değeri var. R değeri 5'i de gösteremez çünkü orada da 27 var. O halde R=4 oldu. Tablonun son hali şöyle:

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

Sıradaki değerimiz 42.
hash(42)=9 mod 11.
42 değerini 9 numaralı göze yazamıyoruz çünkü orada 39 var. 39 da orada aslında misafirdi hatırlarsanız çünkü 39'un çıkan hash değeri 6 idi(hash39= 6 mod 11). İşte buna coalescing denir!!.. Yani dönen hash değerleri fark olanlar aynı zincirde buluşuyor. 42'yi bulmak için, 9 numaralı göze gidiyorsunuz ve orada aslında dönen değeri 6 olan başka bir değer var ama link'i yine de 39'dan atıyoruz. Buna coalescing deniyor işte. :) Daha nasıl anlatayım bilemiyorum ama anladınız siz onu. :)
42'yi R'nin tuttuğu göze, yani 4 numaralı göze, yerleştiriyoruz. 9 numaralı gözden de 42'ye link atıyoruz. R=3 oldu artık. Tablonun son hali şöyledir:

Sıra	Anahtar Değeri	Link
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 17 değeri kaldı.
hash(17)=6 mod 11
6 numaralı gözde 28 değeri var. O yüzden 17'yi R'nin gösterdiği yere, yani 3 numaralı göze, koyuyoruz. Link atma olayı ise şöyle:Link'i 28'den atamayız çünkü 28'in olduğu gözden, 9 numaralı göze link atılmış. 9 numaralı gözden de, 4 numaralı göze link atılmış. Bu yüzden biz de 17'ye 4 numaralı gözden link atarız. R=2 oldu en son... Tablonun nihai hali şöyledir:

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

 Böylelikle tabloya yerleştirmiş olduk. Bir iki şey daha söyleyeyim. Hash'ten dönen değere home address denir. Kısa ismi varken, tüm yazı boyunca nedense uzun uzun kastım. :) Yani bir yerde home address gibi bir şey okursanız, artık anlarsınız. :)
Son şey: average probe. Yani ortalama kaç adımda verilere ulaştığımız...
27 değerine 1 adımda ulaşıyoruz.
18 değerine 1 adımda ulaşıyoruz.
29 değerine 2 adımda ulaşıyoruz.(7 numaralı göze gidiyoruz, ordan link ile 29'a atlıyoruz)
28 değerine 1 adımda ulaşıyoruz.
39 değerine 2 adımda ulaşıyoruz.(6 numaralı göze gidiyoruz, ordan link ile 39'a atlıyoruz)
13 değerine 1 adımda ulaşıyoruz.
16 değerine 2 adımda ulaşıyoruz.
42 değerine 2 adımda ulaşıyoruz.
17 değerine 4 adımda ulaşıyoruz.
 Toplamda 16 adımda tüm değerlere ulaşıyoruz. 9 tane de değer olduğuna göre=> 16/9=1,78 de average probe olur.
LISCH metodu bu kadar arkadaşlar. İnşallah bu konser ortamından doğru düzgün bir anlatım çıkmıştır. :D
Korn yorumuyla One ile sizlere veda ediyorum. :)

Sonra görüşürüz..