Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde dosya yönetiminde özetleme (hashing) için kullanılan bir yöntemdir. Bu yönteme göre ekleme sırasında bazı değişiklikler ile yerleştirilen kayıtların arama hızını arttırmak ön plandadır. Özet tabloya (hash table) yerleştirilen bir kayıdın çeşitli durumlarda yeri değiştirilerek okuma zamanının arttırılması hedeflenir. İki ayrı zincir tutmaktadır.

  • Birincil sonda zincirinde (primary probe chain) sayının aranması ve yerleştirilmesi için gereken sıra tutulur.
  • İkincil sonda zincirinde (secondary probe chain) ise sayının yer değiştirmesi için gereken sıra tutulur.

Çalışmasını daha iyi anlamak için aşağıdaki örnek üzerinden yöntemi anlamaya çalışalım:

Eklenmek istenen sayılar : 27, 18, 29, 28, 39, 13, 16 olsun.

Ekleme sırasında kullanılacak olan öze fonksiyonlarımız ( hashing function):

H1(anahtar) = anahtar mod 11 (anahtarın 11’e bölümünden kalan değer)

H2(anahtar) = bölüm ( anahtar/11 ) mod 11 (anahtarın 11’e bölüm değerinin tekrar 11’e bölümünden kalan değer)

İlk 3 sayı herhangi bir çakışma olmadan özet tablomuza koyulabilirler. Bu sayılardan sonra tablomuz:

Yukarıdaki şekilde olur. Burada koyu renkle gösterilen anahtarlar değiştirilmiştir.

Örneğin ilk durumda 27, 18 ve 29 sayıları problemsiz bir şekilde koyulur. Ardından gelen 28 ve 39 sayısı çakışır (collision). İkisi de 6 adresine konulmalıyken sırasıyla önce 28 daha sonra da 39 bu adrese konulur. En son durumda 6. adreste 39 bulunur. 28 değeri ise ikinci özetleme fonksiyonuna (hashing function sokulur. H2(28) = 2 olduğu için 6+2 = 8. adrese 28 değeri taşınır.

Ardından gelen 13 problemsiz bir şekilde 2. adrese koyulurken, 16 sayısı için yine çakışma söz konusudur.

16 sayısı 5. adree koyulduktan sonra bu adreste bulunan 27 sayısı taşınmaya başlanır. H2(27) = 2 olduğu için 2şer atlanarak uygun yer aranır. Önce 5+2 = 7 kontrol edilir, dolu olduğu için 5+2+2 = 9 kontrol edilir dolu olduğu için 5+2+2+2 = 11 mod 11 = 0 kontrol edilir ve boş bulunduğu için bu adrese sayı yerleştirilir.

Görüldüğü üzere brent metodunda (brents method) her zaman son gelen değer adreste tutulmakta ve adreste bulunan eski değer hareket ettirilmektedir. Bu anlamda dinamik metot olarak sınıflandırılabilecek brent yönteminde, EISCH yöntemi, LISCH yöntemi veya doğrusal sondalama (linear probing) yöntemlerinden farklı olarak  sayılar ilk konuldukları yerden farklı yerlere taşınabilirler.

Yorumlar

  1. huseyin

    burada anlattığınız yöntem doğru ama asıl yapılması gereken i+j< s koşulunu sürekli kontrol etmenizdir.5 için P1,1
    p1,2……şeklinde..

  2. gurcan

    evet anlatım doğru olmakla birlikte, brent’s methodun asıl yapması gerekn i+j < s olayı anlatılmamış. Daha karmaşık sayılarda sadece sizin söylediğiniz “En son gelen konur, diğeri ilerletilir” mantığı çalışmayacaktır.

  3. halo

    “En son gelen konur diğeri ilerletilir mantığı” hepsi için geçerli değil önemli olan az sayıda probea ulaşmak

  4. Mehmet

    derse gidemediğim için kaçırdığım bu brent’s konusu için verilen ödevi buradaki anlatımdan dolayı neredeyse yanlış yapıyordum. Arkadaş s değerinden bahsetmese buraya göre yapacaktım. Emeğiniz için teşekkür ederim ama lütfen bir şeyi anlatıyorsanız eksik anlatıp insanları mağdur etmeyiniz. iyi çalışmalar…

  5. Okan

    İlk üç sayı çakışmadan eklenebiliyor demişsiniz ama 18 sayısı 29 ile çakışıyor.Keşke (i+j)<s kuralını da anlatsaymışsınız.

  6. davut beytekin

    bende acaba beni mi yanlış yaptım diyordum..galiba biraz hatalı bir anlatım olmuş..bende bu yöntemi çok sevmiştim halbuki…:)

davut beytekin için bir cevap yazın Cevabı iptal et

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