Yazan : Şadi Evren ŞEKER

Bu yazının amacı, doğrusal karım ve doğrusal karım tablosu (linear hash table) konularını anlatmaktır. Bilgisayar bilimlerinde veri depolamak veya veriye hızlı ulaşmak için kullanılan yöntemlerdir.

Doğrusal karım yönteminde temel olarak özetleme fonksiyonları kullanılır (karım fonksiyonu, hash function). Bu fonksiyonlar sıralıdır ve sayısı, özetleme fonksiyonunun seviyesini belirtir. (h1, h2, h3, … şeklinde istenilen seviyede istenildiği kadar fonksiyon olabilir).

Doğrusal karım’ın en önemli özelliği yük çarpanını (load factor) sabit tutmasıdır. Yük faktörü aşağıdaki formül ile hesaplanabilir:

LF = R / (B * c)

Buradaki R değeri bir kayıtta tutulan anahtar sayısı (Record),

B değeri, kovaların (Bucket) sayısı

c değeri ise bir bloktaki kayıt sayısıdır.

Doğrusal karım için bir anahtar değerine (key value) erişim aşağıdaki algoritma ile olur.

  • Verilen seviye için özetleme fonksiyonuna sokulup özetleme değeri hesaplanır h = H(key) , key anahtar değeri, H() fonksiyonu özet fonksiyonu ve h değeri ise özetleme fonksiyonu sonucudur.
  • Sınır değeri hesaplanır (Boundary value, kısaca bv) bv = c * LF , buradaki c değeri blok başınsa tutulan kayıt değeridir. LF ise yük çarpanı (load factor) değeridir.
  • Sonucun son k hanesi için bir yerleştirme işlemi yapılır. (örneğin k değeri 3 ise, sonuçta bulunan değerin son 3 hanesine bakılarak yerleştirme işlemi yapılır)
  • Genişleme gerekmesi durumunda, ilgili kova (bucket, buket) k+1 hane kullanarak bölünür.

Yukarıdaki algoritmadan anlaşılacağı üzere, k değeri o andaki saklanan bilgiler için tutulan değerdir. Karım’a ekleme yapıldıkça k değeri artar (her ekleme ile birlikte artması gerekmez ama belirli değerlere ulaşıldığında artar).

Ayrıca doğrusal karım ile ilgili bilinmesi gereken bir nokta da özetleme fonksiyonlarının özelliğidir.

Özetleme fonksiyonları arasında kesişim olmamalıdır. Örneğin hx fonksiyonu x seviyesindeki fonksiyon ise, hx+1 seviyesindeki fonksiyonun hx fonksiyonunun etki alanının iki misline sahip olması gerekir.

Şekilde görüldüğü gibi, şayet hx fonksiyonu, B-1 elemana kadar kodlayabiliyorsa, hx+1 fonksiyonunun 2B-1’e kadar kodlayabilmesi beklenir.

Yukarıdaki bu özelliği sağlayan en temel özetleme fonksiyonu aşağıdaki şekilde yazılabilir:

hx(key) = H(k) mod (2x B )

Bu fonksiyonda, hx ilgili seviyedeki özetleme fonksiyonu (karım fonksiyonu, hash function) olmak üzere, H(k) ise sistemimizde kullandığımız bir özetleme fonksiyonu olmak şartıyla (ve ayrıca sistemin ihtiyacı olan en büyük B değerinden daha büyük bir sonuç üretebilecek entropiye (Entropy) sahip olmalıdır ). Sistemimiz, 2x değerini B ile çarparak kalan işlemine tabi tutmaktadır (modulo). Sonuçta çıkan değerler ilgili seviyeden B değerinin içerisine sığdırılmaktadır. Diğer bir deyişle yukarıdaki fonksiyonumuz B, 2B, 4B, 8B … şeklinde bir öncekinin iki misli olan kodlama aralığı üretmektedir.

Yukarıda anlatılan konuyu bir örnek üzerinden anlamaya çalışalım.

Örnek

Öncelikle özetleme fonksiyonlarımızı aşağıdaki şekilde tanımlayalım.

h0(k) = k mod 20

h1(k) = k mod 21

h2(k) = k mod 22

h3(k) = k mod 23

Örneği kolay tutmak için sadece ilgili değerin gerekli olan özetleme fonksiyonu seviyesinden 2 üzeri şeklinde modulo’su hesaplanmaktadır. Örneğin 0. seviyedeki bir özetleme işlemi her zaman 0 üretmekte , 1. Seviyeden bir özetleme fonksiyonu ise 0 veya 1 üretmektedir…

Doğrusal karım içerisine eklemek istediğimiz sayılar aşağıdaki şekilde verilmiş olsun :

45, 33, 78, 22, 21, 76, 23, 65

Bu sayıları, yukarıda tanımı yapılan fonksiyonlar ile doğrusal karım tablomuza eklemeye çalışalım.

Ekleme işlemi sırasında bize eşlik edecek önemli bir değişkenimiz bulunuyor. n = 0 olarak başlıyoruz. Buradaki n, bölmek için sıranın kaçıncı bukette (kova, bucket) olduğudur.

İlk gelen sayımız 45 ve biz bu sayının 0. seviyedeki özetleme fonksiyonu sonucunu alıyoruz ve doğal olarak 0 çıkıyor:

h0(45) = 45 mod 20 = 0

Sıra Değer
0 45

 

Yukarıda görüldüğü şekilde gelen yeni değeri tablonun 0. sırasına ekliyoruz. Sıradaki sayımız 33. Yukarıdaki doğrusal karım tablomuzda tek eleman koymak için yer bulunuyor ve bizim ise iki elemanımız bulunuyor. Bu durumda k değerini arttırıyoruz ve 2 eleman sığabilecek şekilde tablomuzu genişletiyoruz.

h0(33) = 33 mod 20 = 0

h1(33) = 33 mod 21 = 1

Buket No Sıra Değer
0 0
1
1 2 45
3 33

 

Yukarıdaki şekilde görüldüğü üzere 2 ayrı kova (bucket) oluşturulmuş ve anahtarların, bu kovalardan hangisine yerleştirileceğini belirlemek için h1 fonksiyonu kullanılmıştır. Elimizdeki değerlerin ikisi de (45 ve 33) tek sayı olduğu için ikisi birden ikinci bukete yerleştirilmiştir.

Şimdilik herhangi bir çakışma olmadan sayılarımızı ekliyoruz. Sıradaki sayımız 78.

h0(78) = 78 mod 20 = 0

h1(78) = 78 mod 21 = 0

Buket No Sıra Değer
0 0 78
1
1 2 45
3 33

 

Sıradaki sayımız 22:

h0(22) = 22 mod 20 = 0

h1(22) = 22 mod 21 = 0

Buket No Sıra Değer
0 0 78
1 22
1 2 45
3 33

 

Sıradaki sayımız 21

h0(21) = 21 mod 20 = 0

h1(21) = 21 mod 21 = 1

Ne yazık ki, burada bir çakışma oluyor. Bunun sebebi şu anda sayıyı yerleştirmek istediğimiz buketin dolu oluşudur. Hemen k değerini arttırarak yeni bir buket oluşturuyoruz ve özetleme fonksiyonunu bir seviye ilerletiyoruz.

Şu anda n değerimiz 0 (örneğin başında atamıştık). Bunun anlamı bölme işleminin uygulanacağı buketin 0. buket olduğu. O halde yeni yer açmak için bu buketi parçalıyoruz ve aşağıdaki şekilde bir doğrusal karım tablosu elde ediyoruz. Ayrıca n değerini artık 1 olarak arttırıyoruz. Yani sıradaki parçalama işlemi 1. bukete yapılacak.

h0(21) = 21 mod 20 = 0

h1(21) = 21 mod 21 = 1

h2(21) = 21 mod 22 = 1

 

Buket No Sıra Değer Genişleme
00 0 78
1 22
1 2 45
3 33 21
10 4
5

 

Yukarıda bir genişleme işlemi yapılmıştır. Genişletilen buket ise 00 numaralı bukettir. Bu durumda 00 numaralı bukete bulunan değerlerin durumu yeniden kontrol edilip bölünmeden sonra yerlerinde mi kalacakları yoksa yeni bukete mi gidecekleri sorgulanmalı:

h0(78) = 78 mod 20 = 0

h1(78) = 78 mod 21 = 0

h2(78) = 78 mod 22 = 2

h0(22) = 22 mod 20 = 0

h1(22) = 22 mod 21 = 0

h2(22) = 22 mod 22 = 2

Yukarıdaki işlemlerden sonra tablomuz aşağıdaki hale gelir:

Buket No Sıra Değer Genişleme
00 0
1
1 2 45
3 33 21
10 4 78
5 22

Sıradaki sayımız 76. Bu sayı için de özetleme fonksiyonlarımızı kullanıyoruz:

h0(76) = 76 mod 20 = 0

h1(76) = 76 mod 21 = 0

h2(76) = 76 mod 22 = 0

Buket No Sıra Değer Genişleme
00 0 76
1
1 2 45
3 33 21
10 4 78
5 22

Sıradaki sayımız 23. Bu sayı için özetleme fonksiyonları kullanıldığında yeni bir genişleme ihtiyacı doğacaktır:

h0(23) = 23 mod 20 = 0

h1(23) = 23 mod 21 = 1

h2(23) = 23 mod 22 = 3

Genişleme işleminin uygulanacağı buket ise n ile gösterilmekte olan 1 numaralı bukettir. Buket genişletildikten sonra, tablomuz aşağıdaki hale dönüşür:

Buket No Sıra Değer Genişleme
00 0 76
1
01 2 45
3 33 21
10 4 78
5 22
11 6 23
7

Yukarıdaki tabloda işlem henüz tamamlanmamıştır. Bunun sebebi genişleme yapılan buketin içerisinde bulunan değerlerin kontrol edilerek, mevcut yerlerinde mi kalacakları yoksa yeni bukete mi gideceklerine bakılmamış olmasıdır.

h0(45) = 45 mod 20 = 0

h1(45) = 45 mod 21 = 1

h2(45) = 45 mod 22 = 1

h0(33) = 33 mod 20 = 0

h1(33) = 33 mod 21 = 1

h2(33) = 33 mod 22 = 1

h0(21) = 21 mod 20 = 0

h1(21) = 21 mod 21 = 1

h2(21) = 21 mod 22 = 1

Yukarıdaki denklemlerden görüldüğü üzere sayılarımız mevcut yerlerinde kalacaklardır. Unutmamamız gereken değişim ise n değerini arttırarak artık 2 yapmaktır.

Sıradaki sayımız 65:

h0(65) = 65 mod 20 = 0

h1(65) = 65 mod 21 = 1

h2(65) = 65 mod 22 = 1

Buket No Sıra Değer Genişleme
00 0 76
1
01 2 45 65
3 33 21
10 4 78
5 22
11 6 23
7

 

Yukarıdaki tabloda görüldüğü üzere bütün değerler tabloya yerleştirilmiştir. Tablonun performansı ile ilgili olarak en kötü durumu düşünelim ve bundan sonraki gelecek sayıların sürekli olarak 01 buketine geldiğini hayal edelim. Bu durumda tablo bölünmeye devam edecek ve en kötü ihtimalle 3 dönüşten sonra 01 buketini parçalayacaktır. Dolayısıyla buketlerde taşma olması halinde (overflow) belirli bir sürede bu bukete dönülmekte ve bölme işlemi yapılarak tablodaki yük dengesi sağlanmaktadır.

Yukarıdaki bu yazıyı yazmama sebep olan, Hande hanımın sorusunu bu bilgilerden sonra cevaplayayım. Öncelikle soruyu alıntılayalım:

Sınır değerinin bv = (10110)2 , k değerinin 5 olduğu
bir doğrusal kırım tablosunda (linear hash
table), birincil bölgede kaç tane kova (bucket)
vardır?
A) 5 B) 22 C) 32 D) 54 E) 76

Sorudaki sınır değeri (boundary value , bv ) 10110 olarak verilmiş. Bu değerin 10’luk tabandaki karşılığı 22’dir. k değerinin 5 olmasından anlaşılacağı üzere, özetleme fonksiyonlarımız o anda son 5 haneye bakmaktadır. Son 5 haneye bakarak kodlayabileceğimiz kova sayısı 25 = 32 olarak bulunur. Ayrıca sınır değeri olarak verilen 22 kovaya da erişebildiğimizi düşünürsek, 22 + 32 = 54 olarak anlık erişilebilen kova sayısı (bucket) bulunmuş olur.

Yorumlar

  1. Gülşah Masat

    Merhaba hocam,
    21 i eklerken neden genişletilen bucket 00 oluyor? sonuçta biz onu 10 bucket ına ekledik onun genişlemesi gerekmez mi?

Bir cevap yazın

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