Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde, özellikle dosya yönetimi konusunun (file organization) kullandığı bir özetleme (hashing) çakışması (collision) çözüm algoritmasıdır. Basitçe bir çakışma durumu olduğunda, eklenecek olan anahtarı kaç sıra sonraya yerleştireceğimizi bulan ikinci bir özetleme fonksiyonu kullanılır. Kullanılan ikinci özetleme fonksiyonu ise sayının bölümüdür:
H1 : K mod n
H2 : K / n
Olarak düşünülebilir. Bu anlamda çift özetleme fonksiyonlarına (double hashing) benzetilebilir.
Yöntemimizin çalışmasını bir örnek üzerinden anlamaya çalışalım.
Eklenecek olan sayılarımız 27, 18, 29, 28, 39, 13, 16, 42, 17 olsun. Kullanacağımız özetleme fonksiyonu ise H1 : K mod 11 ve H2 : K / 11 olarak verilsin.
Bu duruma mod 11 için 11 farklı alandan oluşan boş bir dizimiz bulunacaktır:
| Sıra | Anahtar |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 |
Yukarıdaki boş tabloda, sıra sütunu, verilerin ekleneceği yeri, anahtar sütunu örnekte verilen sayıların nereye eklendiğini tutmaktadır. Diğer çakışma çözüm yöntemleri olan LISCH yönteminin veya EISCH yönteminin tersine bu yöntemde bir bağlantı sütunu bulunmaz. Bunun sebebi çakışma durumunda sayının konulacağı veya aranacağı adresin ikinci bir özetleme fonksiyonu (hashing function) ile hesaplanabiliyor olmasıdır.
Bu anlamda doğrusal bölüm (linear quotient) algoritması bir doğrusal sondalama (linear progbing veya progressive overflow) olarak düşünülebilir ve bağlantısız çakışma çözümü (collision without links) olarak sınıflandırılabilir.
Yukarıdaki örnekte bulunan sayıları sırasıyla ekleyelim. İlk sayımız 27 için sıra hesaplanır ve 27 mod 11 = 5 olarak bulunur ve çakışma olmadan sorunsuz bir şekilde eklenir:
| Sıra | Anahtar |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 27 |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 |
Ardından eklenen sayımız 18 için sıra hesaplanır ve 18 mod 11 = 7 olarak bulunur ve çakışma olmadan sorunsuz bir şekilde eklenir:
| Sıra | Anahtar |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 27 |
| 6 | |
| 7 | 18 |
| 8 | |
| 9 | |
| 10 |
Ardından eklenen sayımız 29 için sıra hesaplanır ve 29 mod 11 = 7 olarak bulunur. Yukarıdaki görüldüğü üzere 7. Sıra doludur ve dolayısıyla bir çakışma durumu söz konusudur. Çakışma durumunda ikinci özetleme fonksiyonumuz devreye girer ve 29 / 11 = 2 bulunur. Bu durumda sayının konulması gereken yerden 2 sonraki adrese koymayı denememiz gerekir. Örneğimizde 7. Sıraya konması gereken sayımızın ikinci özetleme fonksiyonu sonucu 2’dir ve dolayısıyla 9. Sıraya koymaya çalışırız. Henüz boş olan bu sıraya sayı başarı ile yerleştirilir.
| Sıra | Anahtar |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 27 |
| 6 | |
| 7 | 18 |
| 8 | |
| 9 | 29 |
| 10 |
Sıradaki sayımı 28 mod 11 = 6. Sıraya problemsiz bir şekilde yerleşir:
| Sıra | Anahtar |
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 27 |
| 6 | 28 |
| 7 | 18 |
| 8 | |
| 9 | 29 |
| 10 |
Bir sonraki sayı olan 39 mod 11 = 6, yerleştirilirken çakışma olur, dolayısıyla sayının ikinci özetleme fonksiyonu değeri hesaplanır. Bu değer 39 / 11 = 3 olarak bulunur ve normalde konulması gereken 6. Sıradan 3 sıra sonraya yani 9. Sıraya yerleştirilmeye çalışılır. Ancak bu adres de doludur. Çözüm olarak 3 sıra daha ilerlenir ve 12. Sıraya (mod 11’de çalıştığımız için 1. Sıra oluyor, okuyucu bunu sona ulaşıldığında baştan devam edilir şeklinde de düşünebilir) yerleştirilir:
| Sıra | Anahtar |
| 0 | |
| 1 | 39 |
| 2 | |
| 3 | |
| 4 | |
| 5 | 27 |
| 6 | 28 |
| 7 | 18 |
| 8 | |
| 9 | 29 |
| 10 |
13 sayısı sorunsuz bir şekilde 13 mod 11 = 2. Sıraya yerleştirilir:
| Sıra | Anahtar |
| 0 | |
| 1 | 39 |
| 2 | 13 |
| 3 | |
| 4 | |
| 5 | 27 |
| 6 | 28 |
| 7 | 18 |
| 8 | |
| 9 | 29 |
| 10 |
16 sayısı ise 16mod11= 5. Sıra dolu olduğu için çakışır. 16/11 = 1 olduğu için birer eklenerek ilk boş yer bulunana kadar arama yapılır. Sırasıyla 6. 7. Ve 8. Sıralara bakılır. Nihayet 8. Sırada boşluk bulunduğu için sayı buraya yerleştirilir:
| Sıra | Anahtar |
| 0 | |
| 1 | 39 |
| 2 | 13 |
| 3 | |
| 4 | |
| 5 | 27 |
| 6 | 28 |
| 7 | 18 |
| 8 | 16 |
| 9 | 29 |
| 10 |
42 sayısı da benzer şekilde problemli bir sayıdır. 42 mod 11 = 9. Sıra doludur. İkinci özetleme fonksiyonumuza göre 42 / 11 = 3’tür ve yerleştirme 9 + 3 = 12 mod 11 = 1 sırasına yapılmaya çalışılır mamafih bu alanda dolu olduğu için bir kere daha 3 eklenerek 1 + 3 mod 11 = 4. Sıraya yerleştirilir:
| Sıra | Anahtar |
| 0 | |
| 1 | 39 |
| 2 | 13 |
| 3 | |
| 4 | 42 |
| 5 | 27 |
| 6 | 28 |
| 7 | 18 |
| 8 | 16 |
| 9 | 29 |
| 10 |
Son olarak gelen 17 sayısı, yerleşmesi gereken 17 mod 11 = 6. Sıra dolu olduğu için 17/11 = 1 değerine göre birer arttırılarak boş bir yer aranır. Sırasıyla 7. 8. 9. Ve 10. Sıralara bakılır. Boş sıra bulununca 17 sayısı buraya yerleştirilir:
| Sıra | Anahtar |
| 0 | |
| 1 | 39 |
| 2 | 13 |
| 3 | |
| 4 | 42 |
| 5 | 27 |
| 6 | 28 |
| 7 | 18 |
| 8 | 16 |
| 9 | 29 |
| 10 | 17 |
Yukarıdaki örnekte sayıların nasıl yerleştirildiğini gördük. Bu yöntemi özetleyecek olursak:
- Yerleşecek sayının (anahtarın) özetleme fonksiyonu değerini (hashing function) hesapla ve buraya yerleştir.
- Şayet burası doluysa, ikinci özetleme fonksiyonuna, yani bölme işlemine tabi tutup bulunan değer kadar sonrasına bak.
- Boş alan bulunana kadar bölme işlemi sonucunu ekleyerek arama yap.
Yukarıdaki bu 3 basit adım takip edilerek doğrusal bölüm (linear quotient) yöntemine göre yerleştirme işlemi yapılabilir.
Yerleşen bu sayıların aranması ise oldukça basittir.
Örneğin aranan sayının 42 olduğunu düşünelim. 42 mod 11 = 9 olarak bulunur ve 9. Sırada bu sayı aranır. Sayı burada olmadığı için aranan sayının ikinci özetleme fonksiyonu hesaplanır. 42 / 11 = 3’tür ve dolayısıyla 9. Sıradan başlanarak 3’er arttırılarak bu sayı aranır. 9 + 3 = 12 mod 11 = 1. Sıraya bakılır ancak sayı yoktur, tekrar 3 arttırılır ve 4. Sırada sayı bulunur.
Benzer şekilde, dizide hiç bulunmayan bir sayı aranırsa, arama işlemine başladığımız sıraya gelinmesi veya bütün diziye bakılması durumunda işlem iptal edilir. Örneğin dizimizde olmayan 34 sayısını aramak istediğimizi düşünelim.
34 mod 11 = 3 bulunup bu sıraya bakılacak, bu sırada hiç sayı olmadığı için arama işlemi sayının dizide olmadığını rahatlıkla söyleyebilecektir.
Aranan sayımız 48 olsaydı. 48 mod 11 = 4 bulunacak ve 4. Sırada sayı aranacaktır. 4. Sırada sayı olmadığı için 48 / 11 = 4 arttırılarak arama işlemi devam edecektir.
Sırasıyla 8, 1,5,9,2,6,10,3,7,0 sıralarına bakılacak ve en sonunda bakılacak değer 4 olarak hesaplanınca arama işlemi nihayete erdirilecektir.
Bu durumda da görüldüğü üzere, olmayan bir sayının aranması bazı durumlarda bütün indeksleme alanına bakılmasını gerektirebilir. Bu performans açısından kötü bir durumdur.
Arama algoritmasını aşağıdaki şekilde yazabiliriz:
- Sayının özetleme fonksiyonu (hashing function) değerini hesapla ve sayıyı bu bulduğun sırada ara
- Sayı burada ise sayıyı buldun. Aramayı bitir.
- Sayı yoksa 2. Özetleme değeri olan bölümü hesapla.
- Baktığın adresi bölüm değeri kadar arttırarak tekrar bak.
- Sayıyı bulduysan bitir.
- Başladığın adrese döndüysen aramayı bitir ve sayının bulunmadığını söyle.
- 4. Adıma geri git.
Yukarıda anlatılan doğrusal bölüm yöntemi, doğrusal sondalama (linear probing) çatısı altında kabul edilebilir. Bu tip yöntemlerde, EISCH yöntemi veya LISCH yönteminde bulunan bağlantı sütunları (links) kullanılmaz. Bunun bir neticesi olarak arama sırasında bulunmayan bir sayı için bütün arama alanına bakılması gerekebilir. Bu durum bir dezavantajdır ancak bir avantajı, bağlantı sütunu tutulmadığı için yer kazanılmış olunur.
Doğrusal bölüm (linear quotient) yöntemi yine sınıflandırma bakımından sabit metot (static method) olarak kabul edilebilir. Bundan kasıt, bir sayı bir sıraya yerleştikten sonra buradan hareket edemez, ilk defa yerleştiği yerde kalır.
hocam bir şey sormak istiyorum. Statik bir metot biliyorum ama 42 anahtarını eklemek istediğimizde gerçek adresi 9′ dur. Fakat 9 da 29 bulunmaktadır ve gerçek adresi değildir. 9’u 0.anahtara kaydırarak 42′ yi 9′ a yerleştirebilir miyiz? diyelim ki probe sayısında azalma da oluo bu şekilde yer değiştirebilirler mi ?
Sorunuz, bu şekilde yer değiştirmenin, doğrusal bölüm (linear quotient) yöntemi ile olup olmadığı ise, yöntem yukarıda anlatıldığı gibi olup bu şekilde bir işlem yapılmaz.
Ancak bahsettiğiniz yöntemler kullanılarak algoritmada iyileştirme yapılabilir. Bu konulara bakarken benzer iyileştirmeler görmüştüm. Arama, silme veya veri ekleme zamanlarını iyileştirmek için çeşitli yöntemler kullanılıyordu ancak tam olarak sizin bahsettiğiniz yöntem var mı bilmiyorum. Literatüre bir bakabilirsiniz.
Başarılar