Progressive Overflow (Linear Probing)

Herkese tekrar merhaba,

Çarpışmayı engelleyen(collusion resolution) yöntemlerimize devam ediyoruz. En son EISCH algoritmasından bahsetmiştik. Tıpkı LISCH-LICH gibi, EISCH'in de EICH adında farklı bir versiyonu var. Ama benzer mantık olduğu için onu anlatmadan geçtim. BLISCH gibi konulara değineceğim bir ara da. Şimdiye kadar hep bağlantı yoluyla çarpışma engelleme algoritmalarından bahsettik(with links). Şu anda ise bağlantı olmadan, without links, çarpışmayı engelleme algoritmasına geçiyoruz.

Link'ler ile olan yöntemde, hatırlarsınız, bir anahtar değerini tutan alanımız, bir de bağlantıyı koparmamak için Link değerini tutan alanımız vardı. Without Links kategorisinde, adından da anlaşılacağı üzere, Link değerini tutan bir alanımız yok. Bu anlamda, Link ile çalışan algoritmalara göre daha avantajlı.

Progressive Overflow, bağlantısız (without links) çalışan algoritmalar içerisinde en basit olanı. Mantık şu: herhangi bir anda collision(çarpışma) olursa, takip eden ilk boş/müsait yere yerleştirilir.(Tablonun sonuna kadar gittiniz ve boş yer bulamadıysanız, tablonun en başından itibaren yerleştirmeye çalışınız). Basit olduğu için tercih edilebilse de, başarısız aramalarda performansı oldukça düşüktür.

Her zaman olduğu gibi Alan Tharp amcamızın kitabındaki soruyu çözelim.

SORU: 27-18-29-28-39-13-16-42-17       mod 11


ÇÖZÜM: Her zaman olduğu gibi hash'ini alarak home address'lerini buluruz.
hash(27)=5 mod11
Hash bulmayı unutanlar için bir kez daha hatırlatayım. 27 değeri verilmiş bize. mod da 11 imiş. 27'yi 11'e bölüyoruz. Kalan değer bizim hash değerimiz veya bir başka deyişle home address'imiz oluyor. 27 için home address'i 5 çıktı. O halde 27 değerini tablomuzun 5 numaralı gözüne yazıyoruz.

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

Şimdi de 18'i yerleştirelim.
hash(18)=7 mod 11
7 numaralı göz de boş olduğundan sorunsuzca yerleştiririz.

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

29'a geldi sıra. Şimdi bu yöntemi anlamaya başlayacaksınız.
hash(29)=7 mod 11
7 numaralı göz dolu, az önce oraya 18 yerleşmişti. Link kullandığımız önceki algoritmalarda R değeri tutuyor, bu değerin gösterdiği gözlere sayımızı yerleştiriyorduk. Progressive Overflow'da ise bir sonraki göze yazıyoruz, gayet basit. :) 7 numaralı göz dolu olduğundan, bir sonraki göze bakıyoruz. 8 numaralı göz dolu mu boş mu diye kontrol ediyoruz. Boş olduğunu görüyoruz(yukarıdaki tabloya bakın). Bu yüzden kaydımızı 8 numaralı göze yazıyoruz. Eğer 8 numaralı göz de dolu olsaydı, bu sefer 9 numaralı göze bakardık. Tablonun son hali şöyledir:

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

28'i yerleştirelim.
hash(28)=6 mod 11
6 numaralı göz boş olduğundan, 28'i sorunsuzca yerleştiriyoruz.

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

39'a geldi sıra.
hash(39)=6 mod11
6 numaralı göz dolu. Oraya az önce 28'i yerleştirmiştik. O yüzden bir sonraki göze bakıyoruz:7 numaralı göz. Ancak 7 nuaralı göz de dolu, orda da 18 var. Yine bir sonraki göze bakıyoruz:8 numaralı göz. Maalesef orası da dolu, orda da 29 var. Yine bir sonrasına bakarız:9 numaralı göz. Nihayet boş bir göze denk geldik. :) 39 değerini 9 numaralı göze yerleştiriyoruz. Tablo şu hale gelir:

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

13'ü yerleştiriyoruz şimdi.
hash(13)=2 mod11
2 numaralı göz boş olduğundan, 13 değerini sorunsuzca yerleştiririz.

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

16'da sıra.
hash(16)=5 mod11
5 numaralı göz dolu. 6, 7, 8 ve 9 numaralı gözlere de sırayla bakacak olursak, onların da dolu olduğunu göreceğiz. O yüzden yine bir sonraki göze bakıyoruz:10 numaralı göz. Orası boş!! :) 16 değerini de 10 numaralı göze yerleştiriyoruz o halde. Tablo şu hale gelir:

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

42'ye geldi sıra.
hash(42)=9 mod11
9 numaralı göz dolu olduğundan, oraya yerleştiremiyoruz. Bir sonraki göze bakarız:10 numaralı göz. Ancak orası da dolu. Yazının en başında, böyle bir durumla karşılaşırsak, ne yapacağımızı belirtmiştim. Tablonun sonuna ulaştık. O yüzden tablonun en başından başlayarak, boş yer aramaya devam ederiz. 10 numaralı göz doluydu. Bir sonraki göze bakalım:0(sıfır) numaralı göz. Orası boş. Bu yüzden 42 değerini 0 numaralı göze yerleştiririz. Tablo şu hale gelir.

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

Son olarak 17'yi de yerleştirelim.
hash(17)=6 mod 11
6 numaralı göz dolu. Ondan sonra gelen, sırasıyla 7, 8, 9, 10 ve 0 numaralı gözler de dolu. 1 numaralı göz ise boş. 17 değerini de buraya yerleştiririz. Tablonun nihai hali şöyledir:

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

Bu algoritma için de average probe'u(bir değere ortalama kaç adımda ulaşabildiğimiz) hesaplarsanız(daha önce yapmıştık), oldukça yüksek bir değer elde edeceksiniz. Bunun sebebi secondary clustering(ikincil kümeler)'dir. Bu da farklı home address'ine sahip kayıtlardan kaynaklanmaktadır. Daha farklı açıklamak gerekirse, artış sayısının 1 olmasından ötürü, ikincil kümeler ortaya çıkmaktadır. Pratikte pek de kullanılmaz bu algoritma.
Son bir not, bu algoritmada da kayıt direkt silinmez. Aksi takdirde arama işlemi sırasında boşluklar oluşabilir. Arama işlemi de boşluğu gördüğünde, aramayı durdurur; aranan kayıt tabloda bile olsa ulaşılamaz olur. Bu yüzden silinecek kaydın başına tombstone konur(işaretleme yapıyorsunuz yani). Bu göze yeni bir kayıt ekleyince de o tombstone'u kaldırırsınız.

Bu algoritma da bu kadar. Sonra görüşürüz..

EISCH (Early Insertion Standart Coalesced Hashing)

Merhaba arkadaşlar,

Daha önce başlamış olduğumuz "collusion resolution" yöntemlerinden "bağlantı yöntemi ile çarpışma önleme" tekniğinin bir diğer konusundan devam ediyoruz. Şimdiki konumuz EISCH. Diğer anlattığım konuları okuduysanız şayet, bu isimden yanlışbir anlam çıkarmayın sakın. EISCH, collision olduğunda, kaydı başa ATMAZ!! Daha farklı bir durum söz konusu. Örnek üzerinde anlatayım.

Yine Alan Tharp'ın North Carolina State Üniversitesi için hazırladığı kitabındaki örneği yapalım:

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

ÇÖZÜM: Mod 11 dediği için tablomuzu yine 0-10 arasında çiziyoruz.

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

Ardından ilk elemanımızı yerleştirmeye başlıyoruz.
hash(27)=5 mod11
Artık bu işlemleri biliyorsunuz farz ediyorum çünkü diğer başlıklarımda bayağı anlatmıştım. O yüzden 27'yi direkt 5 numaralı göze yerleştirdim. 5 numaralı göz boş olduğundan sorunsuzca yerleştiririz.

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

Şimdi ikinci elemanımızı yerleştirelim.
hash(18)=7 mod 11
7 numaralı göz de boş olduğundan, 18'i de oraya sorunsuzca yerleştiririz.

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

Sıra geldi 29'u yerleştirmeye.
hash(29)=7 mod 11
7 numaralı göz dolu! Orada 18 var. Bu yöntemde tıpkı LISCH yönteminde gösterdiğim gibi kaydı en sondaki müsait alana atıyoruz. Yani 10 numaralı göze... Yine R diye bir değer tutalım isterseniz, diğer tekniklerde yaptığımız gibi... R bize en alttaki müsait değeri versin. 10 numaralı göze 29'u koyuyoruz, artık 9 numaralı göz müsait. O yüzden R=9 oldu. 7 numaralı gözden de, 10 numaralı göze bir link attık. Sebebini bir kez daha açıklamış olayım: 29'u aramak isteyenler, doğal olarak 7 numaralı göze bakacaklar. Ancak orada 29 yok, 18 var. Dolayısıyla 29'un izini kaybetmememiz lazım. O yüzden de 7 numaralı gözden, bir link atmak zorundayız.

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

Şimdi de 28 var sırada.
hash(28)=6 mod11
6 numaralı göz boş olduğundan, 28'i sorunsuzca yerleştiririz. R=9 hala...

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

39'a geldi sıra.
hash(39)=6 mod11
6 numaralı göze az önce 28'i yerleştirmiştik; yani orası dolu. O halde R değerinin işaret ettiği göze yerleştireceğiz. R=9 idi. Dolayısıyla 39'u 9 numaralı göze yerleştiriyoruz. R=8 oldu. 6 numaralı gözden, 9 numaralı göze link atarız. Çünkü 39 değerini aradıklarında önce 6 numaralı göze bakarlar... Tablo şu hale 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

Şimdi bunun LISCH'ten farkı ne, diye soranlar vardır mutlaka. :) Az sabredin, farkı fark etmeye ramak kaldı. :)

13'ü yerleştiriyoruz şimdi de.
hash(13)=2 mod11
13 numaralı göz boş olduğundan, sorunsuzca yerleştiriyoruz. R=8 hala...

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'yı yerleştirelim hemen.
hash(16)=5 mod11
5 numaralı gözde 27 var. Dolayısıyla R değerinin işaret ettiği göze koyacağız 16'yı. R=8 olduğundan, 16'yı 8 numaralı göze yerleştiririz. 5 numaralı gözden de link atarız.. R=4 oldu artık. 7-6 ve 5 numaralı gözler dolu çünkü. En alttaki boş olan göz 4 olduğundan, R değeri de 4 oldu. :) Doğru dürüst anlatayım diye saçma sapan cümleler kuracağım yakında. :D Neyse. :)

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

42 değeri var sırada.
hash(42)=9 mod11
9 numaralı gözde39 var. (Eski bilgileri tazelemek isterseniz, şunu da belirtelim. 9 numaralı gözde home address'i[hashten dönen değeri] 6 olan 39 değeri var. Yani 39'un home addressi değil zaten orası. Dolayısıyla burada bir coalescing var)
R=4 idi en son. Dolayısıyla 42'yi 4 numaralı göze yerleştiriyoruz. R=3 oldu... 9 numaralı gözden de, 4 numaralı göze bir link atarız yine..

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

Veee.. :) Gelelim EISCH'in ne olduğunu anlayacağınız, 17'nin yerleştirilmesine. Aynı home address'ten en az 3 kere gelmesi lazımdı ki konuyu anlatabileyim. :) Benim suçum yok yani. :)

hash(17)=6 mod 11
6 numaralı gözde 28 var. Dolayısyla 17'yi R değerinin gösterdiği 3 numaralı göze yerleştireceğiz. Ancaaak.. Ancak 6 numaralı gözden zaten 9 numaralı göze link atılmış. LISCH olsaydı sorumuz, 6 numaralı göze giderdik. Ordan 9 numaralı göze link atılmış, 9'a giderdik; ordan da 4 numaralı göze link atılmış. 4 numaralı göze giderdik ve ordan da 17'nin bulunduğu 3 numaralı göze link atardık. Fakat EISCH böyle değil.. :)

EISCH yönteminde, yeni eklediğiniz elemanı, home address'inizdeki, yani hashten dönen değerdeki gözde bulunan elemandan sonraki ilk göze atarsınız. Örnekten devam edecek olursak: 17'nin home address'i 6 çıkmıştı. 6 numaralı gözde 28 var. İşte 17'yi hemen 28'ten sonraki eleman yapıyoruz. Bu EISCH yöntemindeki E(Early) harfinin esprisi de burada zaten. :) Yani 28'ten link direkt 17'nin bulunduğu göze atılır. Ordan da linkler eskisi gibi devam eder. Tablonun son hali şöyle olur:

Sıra	Anahtar Değeri	Link
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

Şimdi elemanlara kaçar adımda ulaştığımıza bakalım ve daha önceki yöntemlerde yaptığımız gibi average probe'u(ortalama olarak hedefe ulaşmadaki adım sayısı) hesaplayalım.
27 değerine 1 adımda ulaşıyoruz.
18 değerine 1 adımda ulaşıyoruz.
29 değerine 2 adımda ulaşıyoruz.
28 değerine 1 adımda ulaşıyoruz.
39 değerine 3 adımda ulaşı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 2 adımda ulaşıyoruz.
Toplamda 15 adımda 9 değere de ulaşabiliyoruz. 15/9=1.67 çıkıyor. LISCH'te bu değer 1.78 idi. Daha etkili bir yöntem imiş demek ki. :)


Bu yöntemin esprisi coalescing'i daha sonraki sıralara ötelemesidir. Yeni gelen değeri, home address'inden sonraki eleman yaptığınızda, bu yöntemi uygulamış oluyorsunuz.


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

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.

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