Linear Quotient

Merhaba arkadaşlar,

Bugün, daha önce başlamış olduğumuz, collision resolution algorithms without links(bağlantı olmadan çakışmaları çözme algoritmaları)'e devam edeceğiz. Bugünkü konumuz Linear Quotient. Bu algoritma, Progressive Overflow yöntemine çok benzer. O yöntemde, collision olduğunda, kaydı bir sonraki boş adrese yerleştiriyorduk. Yani artım sayımız 1 idi(1 sonraki adres doluysa, yine 1 sonrasına gidiyorduk. Hatırlayamayanlar için: http://gurkanalkan.blogspot.com/2010/12/progressive-overflow-linear-probing.html). Linear Quotient'te ise artım sayısı değişkendir. Yani collision(çarpışma) olduğunda, 1 sonraki kayda bakmak zorunda değiliz. Artım sayısı kaç ise, o kadar ötedeki adrese yerleştiririz. Bu sayede probe(adım) sayısı azaltılarak, average probe(bir kayda ulaşmak için gereken ortalama adım sayısı) düşürülmüş; başka bir deyişle progressive overflow'a göre performans artışı sağlanmış olur.

Peki bunca şeyi nasıl yapıyoruz? 2 adımda yaparız. Önce her zaman olduğu gibi, değerin home adress'ini bulan hash fonksiyonuna tabi tutarız. Ardından collision yaratan kayıt varsa şayet, o kayıt için artım miktarını belirleyen ikinci bir hash fonksiyonunu uygularız.

hash₁=key modP

hash₂=Quotient(key/P) modP

Yine Alan Tharp ve yine klasik örneğimiz diyorum. :)

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

ÇÖZÜM:
hash(27)=5 mod11
Tablomuza ilk elemanımızı sorunsuzca yerleştiriyoruz.

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

İkinci elemanımıza geçelim. hash(18)=7 mod11
7 numaralı adres(göz) de boş olduğundan, 18'i de sorunsuzca yerleştiririz.

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

Sıradaki kayda geçelim.
hash(29)=7 mod11
Evet arkadaşlar, konuyu anlama vakti. :) Collision oldu şimdi. 7 numaralı adrese az önce 18'i yerleştirmiştik, 29'u yazamayız artık. Linear Quotient'te şöyle yapıyoruz: Collision'ı yaratan kaydı buluruz. Örneğimizde collicion'a sebep olan değer 29. O halde collision'a sebep olan kaydın(29) artım miktarını bulmalıyız. Yani ikinci kez hash fonksiyonuna tabi tutarız. O da şöyledir: 29/11=2. Yani 29'u, mod 11'e göre yaptığımızdan dolayı, 11'e böldük. Bölen 2 çıktı. Bizi bölen değer ilgilendirir, kalan ilgilendirmez. Bölen değer bizim artım miktarımız oluyor aynı zamanda.
Şimdi... 29 değerinin home adress'i 7 çıkmıştı. Artım miktarını(bölen değer) 2 bulmuştuk.. Yani 7 numaralı adresten 2 birim ötesine bakarız. 7+2=9 numaralı adrese bakarız. Orası boş ise şayet, 29'u yerleştiririz. Boş olduğunu gördüğümüze göre, yerleştirelim.

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

Herhalde neden Quotient isminin kullanıldığını anlamışsınızdır. Quotient, bölen demektir. Biz de artım miktarını bulurken, değerimizi, mod değerine bölüyoruz ve böleni alıyoruz...

Sırada 28 var.
hash(28)=6 mod11
6 numaralı adres boş olduğundan sorunsuzca yerleştiririz.

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

Sırada 39 var.
hash(39)=6 mod 11
Yine collision oluştu. 6 numaralı adrese az önce 28'i yerleştirmiştik. O zaman collision'ı yaratan kayıt olan 39'u ikinci kez hash'leyeceğiz.
39/11=3. Bölen 3, kalan 6. Ancak bizi sadece bölen ilgilendirir. (Bu arada hep 11'e bölmemizin sebebi, soruda mod 11 olarak verilmesindendir. mod7 denseydi, 7'ye bölerdik)
6 numaralı adrese yerleştirememiştik. Artım miktarı 3 çıktığından, 3 birim sonrasına gideriz: 6+3=9 numaralı adres. Ancak 9 numaralı adreste de 29 değeri var, yani yine dolu... O zaman bir 3 birim daha gitmeliyiz. Ta ki boş alan bulana dek gideriz. (Ancak sonsuza kadar gidilmez tabi. Tekrardan 6 numaralı adrese geldiğimizde, bu işlemi sonlandırırız.). 9 numaralı adresten, 3 birim daha gidersek, 1 numaralı adrese gideriz. Orası boş, o halde 39'u yerleştirebiliriz.

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

Sırada 13 var.
hash(13)=2 mod11
2 numaralı göz boş olduğundan sorunsuzca yerleştiririz.

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

Sıra geldi 16'yı yerleştirmeye.
hash(16)=5 mod11
5 numaralı göz dolu.
16/11=1.(Bölen 1, kalan 5; bizi sadece bölenin ilgilendirdiğini hatırlayın)
Yani 1 birim öteleyerek uygun/boş adresi bulacağız. 5 numaralı adres dolu idi. 1 birim sonrası:6 numara da dolu. 1 birim daha ötelersek:7 numaralı göz de dolu. 1 birim daha ötelersek:8 numaralı göz boş. 16 değerini 8 numaralı göze yerleştirebiliriz.

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

Sırada 42 var.
hash(42)=9 mod11
9 numaralı göz dolu maalesef.
42/11=3 (Bölen 3, kalan9. Bizi yalnızca bölen ilgilendiriyor)
9 numaralı gözden 3 birim öteye gideriz:1 numaralı göz de dolu. Yine 3 birim öeteye gideriz:4 numaralı göz boş. O halde 42'yi oraya yerleştiririz.

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

Son olarak 17'yi yerleştirelim.
hash(17)=6 mod11
6 numaralı adres dolu olduğundan, yeni collision'ımız hayırlı uğurlu olsun. Hemen ikinci hash fonksiyonumuza geçelim.
17/11=1 (Bölen 1, kalan 6. Biz sadece bölene bakarız)
6 numaralı göz doluydu. 1 birimötelersek:7 numaralı göz de dolu. Yine 1 birim ötelersek, 8 numaralı göz de dolu. Yine öteleyelim:9 numaralı göz de dolu. Durmak yok, yola devam, öteleyelim efendim:10 numaralı göz boş. O halde hemen 17'yi yerleştiriyoruz.

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

Böylece bir kayda erişmek istediğimizde, bunu daha az adımda başarabileceğiz. Average probe da yaklaşık 1.9 çıkmakta. Bu yöntemde de kayıt silmek istediğinizde tombstone kullanmalısınız. Sebebini diğer kayıtta açıklamıştım gerçi: arama yaparken, arada boşluk olur. Arama işlemi de boşluğu görünce sonlanır. O yüzden kayıt silerken, yerine bir işaret koyarız. Böylece orda kayıt olmasa da, ordan bir yol geçtiğini biliriz. Yerine yeni bir kayıt geldiğinde de tombstone'u kaldırırız.

Eğer arada anlamadığınız terimler var ise, sormaktan çekinmeyin. Çünkü bugün bazı yerleri anlamayan arkadaşlarım olduğunu öğrendim. Konu bütünlüğü için tüm hash konularımı okumanızı öneririm, eğer vaktiniz varsa.

İyi akşamlar.