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