Hash (Hesaba dayalı adresleme) ve Hashing nedir ?(java)

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
kayit[659]   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.