Doğrusal Karım (Linear Hashing)

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 h_x fonksiyonu x seviyesindeki fonksiyon ise, h_x+1 seviyesindeki fonksiyonun h_x fonksiyonunun etki alanının iki misline sahip olması gerekir.

Şekilde görüldüğü gibi, şayet h_x fonksiyonu, B-1 elemana kadar kodlayabiliyorsa, h_x+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:

h_x(key) = H(k) mod (2^x B )

Bu fonksiyonda, h_x 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, 2^x 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.

h₀(k) = k mod 2⁰

h₁(k) = k mod 2¹

h₂(k) = k mod 2²

h₃(k) = k mod 2³

…

Ö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:

h₀(45) = 45 mod 2⁰ = 0

 

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.

h₀(33) = 33 mod 2⁰ = 0

h₁(33) = 33 mod 2¹ = 1

 

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 h₁ 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.

h₀(78) = 78 mod 2⁰ = 0

h₁(78) = 78 mod 2¹ = 0

 

Sıradaki sayımız 22:

h₀(22) = 22 mod 2⁰ = 0

h₁(22) = 22 mod 2¹ = 0

 

Sıradaki sayımız 21

h₀(21) = 21 mod 2⁰ = 0

h₁(21) = 21 mod 2¹ = 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.

h₀(21) = 21 mod 2⁰ = 0

h₁(21) = 21 mod 2¹ = 1

h₂(21) = 21 mod 2² = 1

 

 

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ı:

h₀(78) = 78 mod 2⁰ = 0

h₁(78) = 78 mod 2¹ = 0

h₂(78) = 78 mod 2² = 2

h₀(22) = 22 mod 2⁰ = 0

h₁(22) = 22 mod 2¹ = 0

h₂(22) = 22 mod 2² = 2

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

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

h₀(76) = 76 mod 2⁰ = 0

h₁(76) = 76 mod 2¹ = 0

h₂(76) = 76 mod 2² = 0

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

h₀(23) = 23 mod 2⁰ = 0

h₁(23) = 23 mod 2¹ = 1

h₂(23) = 23 mod 2² = 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:

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.

h₀(45) = 45 mod 2⁰ = 0

h₁(45) = 45 mod 2¹ = 1

h₂(45) = 45 mod 2² = 1

h₀(33) = 33 mod 2⁰ = 0

h₁(33) = 33 mod 2¹ = 1

h₂(33) = 33 mod 2² = 1

h₀(21) = 21 mod 2⁰ = 0

h₁(21) = 21 mod 2¹ = 1

h₂(21) = 21 mod 2² = 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:

h₀(65) = 65 mod 2⁰ = 0

h₁(65) = 65 mod 2¹ = 1

h₂(65) = 65 mod 2² = 1

 

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)₂ , 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ı 2⁵ = 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.