Hashing (Hesaba Dayalı Adresleme)?
Bilgiye
tekrardan erişmek için iki genel teknik vardır: Sıralı erişim ve Doğrudan
erişim.Sıralı erişime örnek teyp kasetleri verilebilirken doğrudan erişime
müzik Cd leri verilebilir.Örneğin 100 tane ismi tutan bir listemiz olduğunu
düşünelim. Bu liste içinde bir isim arayacak olursak listenin başından sonuna
kadar bu ismi aramamız gerekecek. Eğer aradığımız elemanı bulursak arama
sonlandırılacak aksi halde arama başarısız olacaktır. Bu işlem sıralı erişim
olarak adlandırılmaktadır. Bu tür bir aramada en kötü durum liste boyutunun n olduğu
bir durum için O(n) arama zamanı olacaktır. Eğer liste sıralı bir
liste olsaydı, ikili arama kullanacaktık ve arama zamanı O(log n) olacaktı.
Anahtar karşılaştırmalı bir
aramada,
n
elemanlı bir liste için aramanın ”log n” den daha az karşılaştırma
sonucu tamamlanması mümkün değildir. Sıralı ve ikili arama metotları anahtar
karşılaştırma tekniğini kullanırlar. Verilen elamanı doğrudan ve daha hızlı
konumlayabilmek için verileri düzenleyebileceğimiz başka teknikler
geliştirebiliriz.
Elimizde 1000 öğrencinin
kayıtları var diyelim, her birine 0 ile 999 arasında indis numaraları verilmiş
olsun bu durumda herhangi bir kaydı bulmak için sıralı veya ikili arama
tekniklerini kullanmayı düşünmeyiz. Kayıtlarımızı basitçe 1000 boyutlu bir
diziye kaydedeceğiz. Şekil 15.1 de gösterildiği gibi k elemanı için k.
indis numarasının atanması ile oluşan dizi basit bir başvuru çizelgesidir (Table lookup). Tabloyu kayit[1000]
olarak isimlendirdik. Bu bir kayıt dizisidir. Her bir kayıt öğrenci kayıt
numarası, isim v.b. şeklinde alanlar içermektedir. Öğrenci numarası anahtar
olarak seçilmiştir ve aynı zamanda kayit dizisi için indis görevi de görmektedir.
Örneğin kayit[659]
ile Ahmet ERCAN kaydına doğrudan erişebiliriz.
Kayıt Numarası
|
Öğrenci İsmi
|
Diğer Detaylar…
|
||
000
|
Zeynep UĞUR
|
|||
001
|
Ali TÜRK
|
|||
002
|
Hakan MERT
|
|||
 003 |
Deniz KELEK
|
|||
…
|
…
|
|||
659
|
Ahmet ERCAN
|
|||
660
|
Ramazan DURAN
|
|||
…
|
…
|
|||
998
|
Gülcan TEMİZGİL
|
|||
999
|
Alparslan Bilge DÜRÜST
|
Şekil 15.1:Başvuru Çizelgesi (Table
Lookup)
Başvuru çizelgesi ve arama
işleminin temel amacı verilere yeniden erişimi sağlamaktır. Hem başvuru
çizelgeleri hem de arama algoritmaları bir grup anahtardan liste veya dizinin
belli bir yerini bulan işlevler (fonksiyonlar) sunar. Fonksiyonlar bir grup anahtardan
hesaplanan belli yerlere birebir ilişki kurar. Her bir kayıt için bir anahtar
olduğunu düşünürsek, bu anahtar için sadece bir kayıt bulunabilir. Bu tür
başvuru çizelgelerinde herhangi bir kayda ulaşmak için gereken süre O(1) dir ve
sabittir. Yani erişim süresi tablo boyutundan bağımsızdır. Bu yüzden başvuru
çizelgesi herhangi bir arama algoritmasından daha verimlidir.
Veri ekleme ve yer belirleme
işlemlerini sabit bir zaman dilimi içinde yapabilmek için bu işlemlerin
herhangi bir arama işlemi yapmadan gerçekleşmesi gerekir. Yani verilen bir x
elemanı için, x in kaydedileceği dizi veya liste yerini doğrudan x
in kendisini kullanarak belirlememiz gerekmektedir.
Eğer kayıt anahtarları sayısal
bir değer ise bunlar dizinin indisleri olarak kullanılabilir. Öğrenci örneğini düşünürsek
birbirinden farklı olan kayıt numaraları buna örnek olabilir. Burada eğer 5
haneli bir sayı kullanacak olsaydık, 100000 elemanlı bir dizimizin olması gerekirdi.
Böylece çok büyük bir alan israfı yapmış olurduk.
Öğrenci kayıt tablosunu göz önüne
alırsak;
Her bir öğrenci için sadece bir kayıt
bulunmaktadır. Dolaysıyla 1000 elemanlı bir dizi bize yeterli olacaktır. Bu
dizi 0-999 arasında sayısal değerlerle indislenmiştir. Öğrenci kayıt
numarasının son 3 hanesi öğrenci kaydının dizideki yerini bulmak için indis
olarak kullanılmıştır.74361 ve 75961 birbirlerine çok benziyor gibi gözükse de
kayıt tablosunda çok farklıdırlar (361-961). Çünkü kayıt numaralarının son 3
hanesi kullanılmıştır.
Hash tablosu ;herhangi bir
elemanın indis bilgisine gereksinim duymadan elamana doğrudan ulaşmayı sağlayan
kayıtlar dizisidir. Bu elemanın anahtarından indis bilgisini hesaplayan bir
hash fonksiyonu tarafından gerçekleştirilir.
“hash”
kelimesi elemanların herhangi bir sıralama olmadan karıştırılmış olduğunu
gösterir. Bir kayıt bir veya birden fazla alanı barındıran birleşik bir veri
yapısıdır. Her bir alan kendi tipi ve adı vardır.COBOL gibi bazı programlama dillerinde
kayıtlar standart tiplerdedir. JAVA da ise kayıtlar bir nesne olabilir.
Bu bölümde java.util paketinde
bulunanlar gibi , farklı tipte hash
tablolarını açıklamaktadır.
Hash tabloları?
Anahtarları değiştirerek yada
eşleştirme yaparak tablo indislerine dönüştüren fonksiyona hash fonksiyonları
denir. Eğer h bir hash fonksiyonu , k bir anahtar ise h(k)
ye k
nin hashi denir ve
anahtarı k olan kadın tablo indisidir.Yani k anahtarlı kayıt h(k)
ye kaydedilir. Öğrenci örneğimizde h(k)=key%1000 dir. h
fonksiyonunun ürettiği tüm değerler tablodaki tüm indisleri kapsar. Örneğin x%1000
fonksiyonu x
in değerine göre 0 ile 999 arasında tamsayılar üretir. Hash tablosunun
üretilmesi işlemine hashing denir.
Genelde hash fonksiyonu
tarafından tanımlanan değişiklikler çoktan-teke eşleşmiş
olabilmektedir.Yani fonksiyon çıktısı
birbirine eşit olan birden fazla x , y, z anahtarları olabilir h(x)=h(y)=h(z). Başka bir ifadeyle iki yada daha fazla kayıt
anahtarı aynı dizi indisi ile eşleşebilir. Bu
durum çakışma (collision) olarak adlandırılır. Bu tür çakışmalarla başa çıkmak için
geliştirilmiş birkaç yaklaşım sonraki bölümlerde incelenecektir.
İyi bir hash fonksiyonunun karakteristikleri:
§ İyi bir hash fonksiyonu çakışmalardan
uzak olmalıdır. Gerçek hayatta eğer seçilen anahtarlar hakkında bir bilgimiz
yok ise çakışmaların olmayacağı garantisini veremeyiz. Ancak bazı uygulamalarda
anahtarlar hakkında bazı önbilgilere sahip oluruz ve bu anahtarları çakışmaları
engellemek için kullanırız.
§ İyi bir hash fonksiyonu dizi indislerini eşit bir şekilde
dağıtmalıdır. Yani hash fonksiyonunun ürettiği değerler eşit oranda dağıtık
olmalıdır. Eşit anahtar numaraları aynı
dizi posizyonuna eşleştirilmelidir.
§ İyi bir hash fonksiyonu kolaylıkla
hesaplanmalıdır. Bu hash fonksiyonunun gerçekleştirme zamanının O(1)
olması gerektiğini göstermektedir.
