Linear Quotient

Bugün bağlantı olmadan çakışmaları çözme algoritmaları (collision resolution algorithms without links) üstünde duralım hadi. Uğraştıracak bir lab'ımız var bilmeden olmaz dedim, öğrendim sonra blogum vardı lan oraya da yazıyım dedim. :)
Klasik örneğimiz 27-18-29-28-39-13-16-42-17 sayıları.Her tarafta bunlar var diye şikayet etmiyoruz bu sayılar biraz özel çünkü. Kendimiz belirlesek sayılar bazı durumları test etmeyi atlarız o yüzden bu sayılar iyi neyse çok uzattım :)
Linear Quotient de ilk seferde sayılarımızın modunu alıyoruz yerleştirmeye çalısıyoruz. Peki yerleştireceğimiz yer doluysa?
İşte o zaman ikinci fonksiyonumuz devreye giriyor. O da şu işi görüyor: kayıt doluysa az uzağına bi yere yerleştiriyor kaydımızı. Bu uzaklık rastgele değil tabi.Fonksiyonlar geliyoorr.

hash1=key modP
hash2=Quotient(key/P) modP

Burada P gireceğimiz kayıt sayısından büyük ilk asal sayı.Asal sayı olması çakışmayı azaltması açısından çok mantıklı.
Hadi sayıları link olmadan tablomuza yerleştirelim. ÇÖZÜM:
hash(27)=5 mod11
Tablomuz boş, sorunsuz yerleştiriyoruz.

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

İkinci kayıt için hash(18)=7 mod11
7 numaralı alan 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

hash(29)=7 mod11
Biz masum masum ilerlerken ahan da collision oldu. Ne yapcaz şimdi? Linear Quotient'te şöyle yapıyoruz: Sonradan geleni istediğimiz yere yazamayacaksak nereye yazacağımızı ikinci fonksiyona danışıyoruz.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ı. Bu bizim arttırım miktarımız.Yani home adress'ini 7 bulduk e dolu o zaman 7+2=9 a bak boşsa yaz.Baktık boş hemen yazalıım :)

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

Devam edelim.
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 ikinci fonksiyonumuza danışalım ne diyor?
39/11=3. 6 numaralı home adress e yerleştiremedik. 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."Aha o zaman ne yapcaz? Bize denmedi, kimse dolu olur demedi?" :) O zaman bir 3 birim daha gitmeliyiz. Ta ki boş alan bulana dek gideriz. (Ancak sonsuza kadar gidilmez değil mi? Baktık ki 6 numaralı adrese geldik tekrar, bu işlemi sonlandırmalıyız,patladı.). 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ı alan boş, 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ırada 16 var.
hash(16)=5 mod11
5 numaralı alan dolu.
16/11=1.
Yani 1 birim öteleyerek uygun/boş adresi bulacağız. 5 numaralı adres dolu idi. 1 birim sonrası:6 numara e burası da dolu. 1 birim daha ötelersek:7 numaralı yuhh bura da dolu. 1 birim daha ötelersek:8 numaralı alan boş heh:). 16 değerini 8 numaralı alana 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 dolu!
42/11=3 Arttırım miktarı.
9 numaralı alandan 3 birim öteye gittik:1 numaralı göz de dolu. Yine 3 birim öeteye gittik:4 numaralı göz boş. O halde 42'yi buraya 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.
hash(17)=6 mod11
6 numaralı adres dolu olduğundan, hemen ikinci hash fonksiyonumuza danışıyoruz.
17/11=1 arttırım miktarını verdi.
6 numaralı göz doluydu. 1 birim gittik:7 numaralı alan da dolu. Yine 1 birim ötelersek, 8 numaralı alan da dolu. Hadi birkez daha öteleyelim:9 numaralı alan da dolu. Pes etmek yookk.. 10 numaralı göz boş. O halde hemen 17'yi hemen 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

Average probe yaklaşık 1.9 çıkmakta imiş.Bundan önceki lab da EISCH ile uğraşmıştık.EISCH de average probe 1.3 - 1.4 civarlaradında ama onun da problemi link verdiği için fazladan hafıza işte.Zaten bir şey bi yerden iyiyse bir yerden kötü hep. Karamsar oldu o cümle ama öyle hep bi kulp buluyolar yesin hafızayı kurban olsun nedir :D He bu arada bi anlatımında tablo yapısı hoşuma gittiği için tablolar alıntıdır.