Çift Özetleme (Double Hashing)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde kullanılan özetleme fonksiyonları, genellikle büyük bir verinin daha küçük bir hale getirilmesine yarar. Bu anlamda özetleme fonksiyonları veri doğrulama (data verification) , veri bütünlüğü (data integrity), veri güvenliği (security) ve şifreleme (encryption) gibi pek çok alanda kullanılırlar.

Özetleme fonksiyonlarının bir problemi, büyük bir veriyi özetledikten sonra, çakışma olması durumudur. Çalışma (collision) kısaca aynı özet değerine sahip iki farklı verinin olmasıdır.

Örneğin en basit özetleme fonksiyonlarından birisi olan kalan ( mod ) işlemini ele alalım. 0 ile 100 arasındaki sayıları, 0 ile 10 arasındaki sayılarla özetlemek istersek, mod 10 kullanmamız mümkündür. Bu durumda her sayının 0 – 10 aralığında bir karşılığı bulunacaktır.

Ancak 41 mod 10 ile 51 mod 10 aynı sonucu verir. Bu durumda bir çakışma olmuş denilebilir.

Çakışmayı engellemek için veri yapılar üzerinde sondalama yöntemleri kullanılabilir. En meşhurları olan doğrusal sondalama (linear probing) ve ikinci dereceden sondalama (quadratic probign) yöntemleri bu problemin çözümü için geliştirilmiş yöntemlerdir.

Bu yazının konusu olan çift özetleme (double hashing) yöntemi de işte tam bu noktada devreye girer. Yani bir şekilde özetleme fonksiyonundan çıkan sonuçların, çakışması (collision) durumunda, ikinci ve farklı bir özetleme fonksiyonu kullanılarak veri yapısı üzerinde farklı bir noktada arama veya veri ekleme işlemine devam edilebilir.

Örneğin veri yapısına ekleme işlemini ele alalım. Verinin hangi adrese ekleneceğini bulmak için öncelikle anahtar (key) bir özetleme fonksiyonuna sokulur. Bu ilk özetleme fonksiyonuna Ö₁ ismini verelim.

Adres = Ö1 (anahtar) formülü ile adresi buluruz. Diyelim ki bu adres dolu ve buraya yeni verimizi ekleyemiyoruz. Bu durumda ikinci bir adres aranmalıdır. İşte bu noktada ikinci özetleme fonksiyonu Ö₂ devreye girer ve verinin yerleştirilebileceği boş bir adres bulunana kadar bu fonksiyon kullanılmaya devam edilir.

Bu durumu 10 adet hücresi bulunan boş bir veri yapısı üzerinden sırasıyla 21,31,41,51 sayılarının eklenmesi şeklinde görelim. Ö1 fonksiyonu olarak

Adres = anahtar mod 10

Ve ikinci özetleme fonksiyonu olarak Ö2 :

Adres = (( anahatar mod 7 ) x 3 ) mod 10

Fonksiyonlarını alalım. Bu fonksiyonlar örnek olarak alınmıştır ve farklı fonksiyonlar üzerinden de çift özetleme (double hashing) yapılabilir.

Sırasıyla sayılarımızın üzerinden geçiyoruz. İlk sayımız 21 mo 10 = 1 olarak bulunur.

0
1	21
2
3
4
5
6
7
8
9

İlk özetleme fonksiyonu sonucu olarak 1 numaralı adrese yerleştirilir. Ardından ikinci sayıya geçilir:

31 mod 10 = 1 bulunur ve bu adres dolu olduğu için çakışma olur. Çözüm olarak ikinci özetleme fonksiyonu kullanılır.

( ( 31 mod 7 ) x 3 ) mod 10 = 9 olarak bulunur ve bu adrese yerleştirilir:

0
1	21
2
3
4
5
6
7
8
9	31

Ardından 41 sayısı için 1. özetleme fonksiyonu çalıştırılır ve 1 numaralı adres dolu olduğu için çakışma oluşur. Çözüm olarak ikinci özetleme fonksiyonu çalıştırılır:

( ( 41 mod 7 ) x 3 ) mod 10 = 8

0
1	21
2
3
4
5
6
7
8	41
9	31

Benzer şekilde 51 için çakışma olur ve ikinci özet fonksiyonu çalıştırılır.

( ( 51 mod 7 ) x 3 ) mod 10 = 6

0
1	21
2
3
4
5
6	51
7
8	41
9	31

Görüldüğü üzere ikinci özetleme fonksiyonu, ilkinde bir çakışma olması halinde kullanılmaktadır. Peki acaba ikinci özetleme fonksiyonunda da çakışma olursa ne yapılır?

Bu durumu örneğimize devam edip 61 sayısını eklemek istediğimizde görebiliriz.

( ( 61 mod 7 ) x 3 ) mod 10 = 8

Bulunacaktır ve 8 numaralı adres doludur. Bu durumda ikinci özetleme fonksiyonuna ikinci kere sokularak farklı bir adres aranır:

(( 8 mod 7 ) x 3 ) mod 10 = 3 olarak bulunur ve bu adrese yerleştirilir.

0
1	21
2
3	61
4
5
6	51
7
8	41
9	31

Görüldüğü üzere ikinci özetleme fonksiyonunun ilk özetleme fonksiyonu ile aralarında asal olması, belirli bir adres dizilimine girilmesine engellemekte bu sayede veri yapısı üzerinde boş yer bulunuyorsa mutlaka belirli bir denemeden sonra bu adrese erişilmesi garanti edilmiş olmaktadır.

« İkinci Dereceden Sondalama (Quadratic Probing) | Çok Seviyeli Sıralar (Multi Level Queues) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Çift Özetleme (Double Hashing)' isimli yazı 18 Jan 2010 tarihinde, saat: 15:01 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 202 defa okunmuştur.

Benzer yazıları Dosya Organizasyonu (File Organisation), Veri Güvenliği(Cryptography), Veri Sıkıştırma (Data Compression), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar