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