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.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    evet haklısınız işlem hatası yapılmış, sayıyı 36 olarak düzeltiyorum. Teşekkürler.

  2. freelancer03

    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.

  3. Şadi Evren ŞEKER Article Author

    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.

  4. freelancer03

    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.

  5. Şadi Evren ŞEKER Article Author

    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

  6. Orhan

    Hocam chaining,linear,quadraric ve double hashing ‘in zaman karmaşıklığıyla ilgili de bilgilerndirme yapar mısınız?

Orhan için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir