Yazan : Şadi Evren ŞEKER
Özellikle özetleme fonksiyonları ve tablolarında (hashing function and tables) kullanılan ve tabloya girdi yapılması (insertion) okuma ve veriye ulaşmaya göre daha basit olan bir yöntemdir.
Basitçe tek bir özetleme fonksiyonu (hashing function) kullanır ve çakışma (conflict) olması durumunda boş adres bulana kadar sırasıyla adresin altına bakar. Aşağıdaki örnek üzerinden anlamaya çalışalım:
H(anahtar) = anahtar mod 11
Olarak verilmiş olsun (yani verilen anahtarın 11’e bölümünden kalan bizim adresimiz olacak)
Sırasıyla yerleştirilmek istenen anahtarlar:
36,28,44,90,57,68,25,14,36,47,92 olsunlar. Bu sayıların nasıl yerleştiğini adım adım inceleyelim:
36 mod 11 = 3
| Adres | Anahtar |
| 0 | |
| 1 | |
| 2 | |
| 3 | 36 |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 |
28 mod 11 = 6
| Adres | Anahtar |
| 0 | |
| 1 | |
| 2 | |
| 3 | 36 |
| 4 | |
| 5 | |
| 6 | 28 |
| 7 | |
| 8 | |
| 9 | |
| 10 |
44 mod 11 = 0
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | |
| 3 | 36 |
| 4 | |
| 5 | |
| 6 | 28 |
| 7 | |
| 8 | |
| 9 | |
| 10 |
90 mod 11 = 2
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 |
| 3 | 36 |
| 4 | |
| 5 | |
| 6 | 28 |
| 7 | |
| 8 | |
| 9 | |
| 10 |
57 mod 11 = 2
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 | 57 X |
| 3 | 36 |
| 4 | |
| 5 | |
| 6 | 28 |
| 7 | |
| 8 | |
| 9 | |
| 10 |
Yukarıda bir çakışma (conflict) olmuştur. Aynı adreste iki anahtar bulunmasından dolayı çakışmayı engellemek için doğrusal sonda (linear probing) kullanılır. Bu doğrultuda bir alttaki adrese bakılır. Yani adresimiz 2’dir bir altındaki boş adres aranır. 3 numaralı adres ne yazık ki doludur buraya da konulamaz. Dolayısıyla bir sonraki adrese tekrar bakılır. 4 numaralı adres boş olduğu için buraya 57 anahtarı konulabilir.
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 |
| 3 | 36 |
| 4 | 57 |
| 5 | |
| 6 | 28 |
| 7 | |
| 8 | |
| 9 | |
| 10 |
68 mod 11 = 2
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 |
| 3 | 36 |
| 4 | 57 |
| 5 | 68 |
| 6 | 28 |
| 7 | |
| 8 | |
| 9 | |
| 10 |
Yukarıda yine 2 numaralı adreste çakışma olmuş ve çözüm olarak boş yer bulunana kadar altına bakılmış en son 5 numaralı adreste boş yer bulunmuştur.
25 mod 11 = 3
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 |
| 3 | 36 |
| 4 | 57 |
| 5 | 68 |
| 6 | 28 |
| 7 | 25 |
| 8 | |
| 9 | |
| 10 |
14 mod 11 = 3
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 |
| 3 | 36 |
| 4 | 57 |
| 5 | 68 |
| 6 | 28 |
| 7 | 25 |
| 8 | 14 |
| 9 | |
| 10 |
36 mod 11 = 3
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 |
| 3 | 36 |
| 4 | 57 |
| 5 | 68 |
| 6 | 28 |
| 7 | 25 |
| 8 | 14 |
| 9 | 36 |
| 10 |
47 mod 11 = 3
| Adres | Anahtar |
| 0 | 44 |
| 1 | |
| 2 | 90 |
| 3 | 36 |
| 4 | 57 |
| 5 | 68 |
| 6 | 28 |
| 7 | 25 |
| 8 | 14 |
| 9 | 36 |
| 10 | 47 |
92 mod 11 = 4
| Adres | Anahtar |
| 0 | 44 |
| 1 | 92 |
| 2 | 90 |
| 3 | 36 |
| 4 | 57 |
| 5 | 68 |
| 6 | 28 |
| 7 | 25 |
| 8 | 14 |
| 9 | 36 |
| 10 | 47 |
Yukarıdaki son durumda yine çakışma olmuş ve bir alttaki adres aranarak son hücreye kadar ilerlenmiştir. Son hücre dolu olduğu için tablonun başına dönülerek tekrar boş yer aranmıştır. İlk bulunan boş yer olan 1. Adrese anahtar değeri konulmuştur.
35 mod 11 = 3 değil de 2 olmalı sanki.
Güzel çalışma. Kolay gelsin
evet haklısınız işlem hatası yapılmış, sayıyı 36 olarak düzeltiyorum. Teşekkürler.
merhaba hocam
Uzunluğu 13 olan bir karım(hash) tablosuna, aşagıda gösterildiği gibi bazı anahtar(key)
değerleri yüklenmekte; karım fonksiyonu olarak mod işlemi kullanılmakta ve çakışma çözme
amacıyla sıradan yoklama (linear probing) tekniği kullanılmaktadır.
Buna göre, her bir anahtarın aranma olasılığının eşit olduğu varsayılırsa,
başarılı aramalar için ortalama yoklama sayısı kaç olur?
a – 0,8 b- 1,4 c – 1,6 d – 1,8 e – 2,0
bu soruda linear probing tekniği demiş. Ben linear probing tekniği hakkında bildiğim tek şey
mesela 26 değeri mod 13 göre 0 dir. 26 değerini 0. kayıta yerleştirmek. Eğer 0.ıncı kayıt doluysa
1.inci oda dolu ise 2.inci v.s diye gider.
Bu soruda herhangi bir çözüm yolu bulamadım.
Ayrıca böyle soruları çözebilmek için ne tür bir kaynak önerirsiniz veya neye çalışayım.
Yukarıdaki yazıda anlatıldığı üzere her anahtar için sondalama (arama) işlemi yapıp, her arama için kaç değerin sondalandığına bakacaksınız ve ortalama değeri bu şekilde bulacaksınız.
hocam tabloda 26 anahtarı 0. ıncı kayıtta oldugundan 1. aramada bulunur. 17–>5 , 31–>6,
30–>7 , 32 –>8 bu aramaların hepsini toplayıp ortalamasını mı bulmalıyım. Yazınızı okudum. Yazıda anahtar değerlerin mod 11 e göre tabloya yerleştirilmesi ve eger kayıt yeri doluysa bir sonraki kayıta yerleştirilmesi gerektiği anlatılıyor.
Yine de ben sorumu çözemedim. Ayrıca soruda her bir anahtarın aranma olasılığı eşit olduğu varsayılırsa derken , “her anahtar değeri ararken tablonun başından sonuna kadar arama yapmalıyım” bunu mu anlamalıyım.
Tamam sorunuzu çözelim. Sizin durumunuzda 13 kayıt bulunduğu için mod 13 kullanılacak.
26 mod 13 = 0, ilk aramada bulunur (sayı zaten 0. sırada ve ilave sondalama gerekmez)
17 mod 13 = 4, ilk aramada bulunur (sayı zaten 4. sırada ve ilave sondalama gerekmez)
31 mod 13 = 5, ilk aramada bulunur (sayı zaten 5. sırada ve ilave sondalama gerekmez)
30 mod 13 = 4, sayıyı bulmak için 4. sıraya bakıyoruz ancak sayı yok. Dolayısıyla sayı bulunana kadar sonraki sıralara bakılıyor ve sırasıyla 5. ve 6. sıradaki anahtarlara bakarak 6. sırada buluyor. Dolayısıyla sayının orjinal yeri dahil 3 sondalama yapılmıştır.
32 mod 13 = 6, sayıyı bulmak için 6. sıraya bakılıyor. Sayı bulunamadığı için sonraki sıralara bakılarak sayı bulunana kadar devam edilir ve sayı 7. sırada bulunur.
Şimdi her sayıyı bulmak için ne kadar sondalama yapıldığına bakalım:
26 – 1
17 – 1
31 – 1
30 – 3
32 – 2
toplam sondalama sayımız = 8
bakılan anahtar sayısı = 5
ortalama = 8 / 5 = 1.6 olarak bulunur
Hocam chaining,linear,quadraric ve double hashing ‘in zaman karmaşıklığıyla ilgili de bilgilerndirme yapar mısınız?