Computed Chaining (Hesaplanabilen Zincirler)

Arkadaşlar bu yazımda sizlere computed chaining yani hesaplanabilen zincirlerden bahsedeceğim. Çakışmaları genel olarak 2 farklı yaklaşımla çözüyoruz.
1-Link alanı kullanan çözümleme yaklaşımları (colaesced hashing)
2-Link alanı kullanmayan çözümleme yaklaşımları (progressive overflow, linear quotient, brient’s method ve binary tree)

Link kullanan çözümleme yaklaşımlarında performans genel olarak daha iyi olurken, link için extradan yere ihtiyacımız vardır. Tam tersi link kullanmayanlarda ise yere ihtiyaç azken performans daha düşüktür.

Her iki yaklaşımıda bir çatı altında toplayarak hem performans artışı, hem de yerden tasarruf sağlayabiliriz. Bu yeni yaklaşım computed chainingdir. Bu metodda gerçek link adreslerini kaydetmek yerine, adresler hesaplanarak bulunur. Daha az sayıda bit kullanarak adreslere ulaşmak mümkündür. Link alanlarında zincir içindeki elemanların tam adresileri yerine offset değerleri saklanır. Bu offset değeri daha sonra hesaplamalarda kullanılarak zincir içinde bir sonraki kayda ulaşmak mümkündür.

i(A) bir sonraki konuma ulaşmak için kullanılacak olan artım fonksiyonudur.

Şimdi örnekle devam edelim. Kullanacağımız değerler 27, 18, 29, 28, 39, 13, 16, 38, 53

Hash(key) = key mod 11

Artım fonksiyonu ise:  i(key)=Quotient(Key/11) mod11

27 ve 18 herhangi bir çakışma olmadan doğrudan 5. ve 7. konumlara yerleştirilebilir.

29 kaydı 7  numaralı konuma yerleşmek istiyor fakat bu noktada daha önceki 18 anahtarı ile çakışma meydana gelmektedir. Bu anahtar için uygun konumun bulunmasında bazı işlemlerin yapılması gerekmektedir. Bunlar:
Öncelikle eklenecek olan konumdaki anahtar kendi home adresine mi yerleşmiş? (18 kendi home adresinde olduğundan problem yok)
Bu konumdaki anahtarın ardından gelen başka bir anahtar var mı? Bunu link alanına bakarak anlayabiliriz.( 18 için null)

28 kaydı6 numaralıkonuma herhangi bir çakışma olmadan yerleşebilir.

39 kaydıda 6 numaralı konuma yerleşmek isteyeceğinden bir çakışma olacaktır. Bu konumda önceden olan 28 anahtarı kendi home adresindedir ve ardından gelecek olan bir kayıt şu an için yoktur. (offset alanıboş)
39 anahtarının yerleşeceği bir sonraki konum için 28’in artım değeri hesaplanır. (28’in artım değeri 2)
Artım değeri dikkate alınarak 39 için uygun olan konum, 10 numaralı konumdur.
39 anahtarı için gerekli olan probe sayısı 3 değil 2 dir.

13 kaydı 2 numaralıkonuma herhangi bir çakışma olmadan yerleşebilir.

 16 kaydı 5 numaralı konuma yerleşmek isteyeceğinden bir çakışma olacaktır.
Bu konumda önceden olan 27 anahtarıkendi home adresindedir ve ardından gelecek olan bir kayıt şu an için yoktur. (offset alanıboş)
16 anahtarının yerleşeceği bir sonraki konum için 27’in artım değeri hesaplanır. (27’in artım değeri 2)
Artım değeri dikkate alınarak 16 için uygun olan konum, 9 numaralı konumdur.

Örneğe ekstra olarak eklenmişolan 38 ve 53 anahtarlarına geçmeden önce genel olarak bu yaklaşımda her bir kayıda erişmek için gerekli olan probe sayısıhesaplayalım. 1,42

Aynı işlem ;

Binary tree (Link alanlarıkullanılmıyor) ile gerekli olan probe sayısı=1,7’dır.

LISCH (Link alanlarıkullanılmakta) ile gerekli olan probe sayısı=1,4’dır.
Organizasyonu 12  Buradan da görüleceği gibi LISCH  ile Computed Chaining yaklaşımları kayıtları okurken aynı probe sayısına ihtiyaç duymaktadırlar. (1,4)

Peki, o zaman Computed Chaining Yöteminin avantajınedir?

Computed Chaining yaklaşımda, link bölümünde adreslerin tamamıyerine pseudolinkler yardımıyla bağlantılar yapıldığından link alanlarının genişliği daha azdır. Bu da yerden kazanım sağlar. Böylece fazladan yer kullanımının önüne geçilmişolur.

Örneğin, gerçek adres değerleri için 3-4 byte’lık alanlar kullanılırken; pseudo linkler yardımıyla 2 bitlik alanlar yeterli olmaktadır.

38 kaydı 5 numaralı konuma yerleşmek isteyeceğinden bir çakışma olacaktır.
Bu konumda önceden olan 27 anahtarıkendi home adresindedir ve ardından gelecek olan bulunmaktadır. (Offset değeri 2 olduğundan ardından gelen kayıt 9 numaralı konumdadır)
Bu konumda ise 16 bulunmaktadır ve ardından herhangi bir anahtar değeri gelmemektedir. (Offset alanınull)
16 anahtarının artım değeri olan 1 kullanılarak 38 kaydıiçin uygun konum belirlenir. (0. konum boştur ve buraya 2 artım değeri sonucunda varılabilir.)

53 kaydı9 numaralı konuma yerleşmek isteyeceğinden bir çakışma olacaktır. Fakat burada karşımıza farklıbir durum çıkmaktadır.
53 anahtarının konumu olan 9 numaralıkonumda bulunan 16 anahtarının home adresi farklıdır.
Bu durumda 16 anahtarıve onun ardından gelen diğer anahtarların ötelenmesi gerekecektir.
Bu işlem için öncelikle, 16 ve ardındaki anahtar değerleri sonra tekrar eklenmek üzere tablodan geçici olarak ayrılır
Böylelikle boşalan konuma 53 kaydı kolaylıkla yerleşebilir.

Tablodan çıkarılan 16 ve 38 anahtarları tabloya yeniden eklenir.
Bunun için 16’nın home adresi olan 27’nin artım değeri tekrar kullanılarak ilk boşkonum araştırılır. İlk boşkonum 0. konumdur ve 3 artım değerinden sonra bu konuma varılmıştır.
16’dan sonra 38 anahtar değeri yerleştirilecektir ve bu sefer 16’nın artım değeri olan 1 kullanılarak boşkonumlar araştırılır ve 1. konuma yerleştirilir.

Retrieval işleminde 16. Anahtarıötelemekle performans kaybıyaşanmışolabilir mi ?

Herhangi bir performans kaybısözkonusu değildir. Çünkü, 16. anahtarıötelemeden önce retrieval için 2 probe söz konusu iken öteledikten sonra da aynısayıda probe söz konusudur. Dolayısıyla herhangi bir performans kaybıyoktur. (Retrieval açısından)

Avantajları

Computed chaining yöntemi link kullanmayan yakşaımlara göre daha iyi performansa sahiptir.

Bir kayda ulaşmak için gerekli olan probe sayısı, halkadaki sırasına bağımlıdır.

Kayda ulaşmadaki performansıarttırmak için, anahtar değerlerini eşsiz olarak dağatan hash fonksiyonları tercih edilmelidir.

Bir anahtar değeri silindiğinde, silinen elemandan sonraki tüm kayıtların yeniden yerleştirilmesi gerekmektedir.

Bu yaklaşım kayıt ekleme ve silme işlemleri sırasında daha fazla hesaplamaya gereksinim duyduğundan, bu işlemler sırasında gereksinim duyulan zaman daha fazladır. Diğer taraftan ise okuma işlemini daha kısa sürede gerçekleştirirler.

Dezavantajları

Daha önceki link kullanan çakışma çözme yöntemlerinde link alanında adres bilgisi tutulduğundan link alanın adres bilgisini barındıracak genişlikte olmasıgerekiyordu.

Computed chaining yönteminde ise; pseudo link alanıoffset adresin en büyük değerini adresleyebilecek genişlikte seçilmelidir.

Eğer pseudolinklerin bulunduğu offset alanı yeterli genişlikte seçilmezse, seçilen genişliğe sığabilecek en büyük değer offset alanına yerleştirilir. Böyle bir durumda ise bir kayda ulaşmak için gerekli olacak probe sayısıartacaktır.

Sonuçolarak; offset alanıiçin yeterli miktarda bit ayrılmalıdır.

Computed chainig için birinci bölüm bu kadardır, bir sonraki yazımda Multiple Chaining ve Çakışma Çözümleme Tekniklerinin Karşılaştırılmasından bahsedeceğim.

Anlatımda hata varsa lütfen yazın, düzelteyim.

<<< Önceki: WordPress Otomatik Güncelleme Sorun ve Çözümü

Sonraki: Computed Chaining (Hesaplanabilen Zincirler) – 2 >>>