• Bağış

    • Doğrusal Sondalama (Linear Probing, Progressive Overflow)

    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.

    Benzer Yazılar:

    Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Doğrusal Sondalama (Linear Probing, Progressive Overflow)' isimli yazı 01 Nov 2008 tarihinde, saat: 17:21 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 816 defa okunmuştur.

    Benzer yazıları Veri Tabanı (Database), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


    Category: Veri Tabanı (Database), veri yapıları
    2 responses to “Doğrusal Sondalama (Linear Probing, Progressive Overflow)”
    1. Burak says:
      14/03/2009 at 2:08 pm

      35 mod 11 = 3 değil de 2 olmalı sanki.
      Güzel çalışma. Kolay gelsin

    2. Şadi Evren ŞEKER says:
      14/03/2009 at 2:14 pm

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

    Leave a Reply