19 Nisan 2013 Cuma

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ıraAnahtar Değeri
0
1
2
3
4
527
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ıraAnahtar Değeri
0
1
2
3
4
527
6
718
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ıraAnahtar Değeri
0
1
2
3
4
527
6
718
8
929
10


Devam edelim.
hash(28)=6 mod11
6 numaralı adres boş olduğundan sorunsuzca yerleştiririz.

SıraAnahtar Değeri
0
1
2
3
4
527
628
718
8
929
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ıraAnahtar Değeri
0
139
2
3
4
527
628
718
8
929
10

Sırada 13 var.
hash(13)=2 mod11
2 numaralı alan boş, sorunsuzca yerleştiririz.


SıraAnahtar Değeri
0
139
213
3
4
527
628
718
8
929
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ıraAnahtar Değeri
0
139
213
3
4
527
628
718
816
929
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ıraAnahtar Değeri
0
139
213
3
442
527
628
718
816
929
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ıraAnahtar Değeri
0
139
213
3
442
527
628
718
816
929
1017

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.

1 yorum: