Hash Fonksiyonları

Merhaba tekrar,

Bu saatlerde normalde blogda yazmazdım ancak sanırım boşluğa düştüm bir anda ve boşluğu düşünmemenin en iyi yolu sevdiğin konular hakkında yazmak olsa gerek.

Ben de Hash Fonksiyonlarını anlatacağım. 8 tür Hash fonksiyonunu ele alacağım. İstediğiniz gibi gruplandırın siz bunu ama ben üniversitede Alan Tharp'ın kitabından öğrendim, dolayısıyla temelim ordan geliyor.

1. hash(key)=key mod N
Bu ilk hash fonksiyonudur. N dediğim şey, tablo boyutudur veyahut mod operatörü diyelim de lügatına uygun olsun. Yani bildiğiniz mod alma işlemini uyguluyorsunuz.

2. hash(key)=key mod P
Aslında bunu ilk maddede de belirtebilirdik. Buradaki P'yi de şöyle açıklayayım: tablonun boyutundan(N) büyük veya eşit en küçük asal sayı. Yine mod alma işlemi yaptığınız zaten aşikar.

3. Truncate etmek.
Bir sayı dizisi düşünün. 123456789 mesela. Siz mesela 4'ten öncesini truncate edersiniz: 456789 arasından istediğiniz haneleri alarak adres üretebilirsiniz.

4. Folding
İki türdür bu yöntem.
a-Folding by boundary: 1 2 3 4 5 6 7 8 9
sayı dizisini düşünün. 9 hane var, 3'erli gruplara ayıralım bunu.
1 2 3 | 4 5 6 | 7 8 9
Araya çizdiğim çizgilerden, kağıdı katlar gibi bir hareket çekeceğiz şimdi. :) Düz bir kağıda yazıldığını düşünün üstteki sayı dizisinin. Aradaki çizgilerden, bu kağıdı katladığınızı hayal edin şimdi.
3 2 1
4 5 6
9 8 7
şekline gelir. Bu alt alta yazdığım üçerli sayı dizilerini toplayın. Eğer 4 haneli bir sayı dizisi oluşursa, soldaki taşan haneyi atın.

b-Folding by shifting: 1 2 3 4 5 6 7 8 9
sayı dizisini düşünün. 9 hane var, 3'erli gruplara ayıralım bunu.
1 2 3 | 4 5 6 | 7 8 9
Araya çizdiğim çizgilerle ayırdığımız bu sayı dizisine herhangi bir hareket çekmeyeceğiz bu sefer. :) Direkt bu sayı dizilerini alt alta yazıp topluyoruz yine.
1 2 3
4 5 6
7 8 9
şeklinde topluyoruz yani. Toplama işleminin sonucunda ortaya çıkan sayının en soldaki hanesi(oluşursa, örneğimizde tabi ki oluşacak) atılır.

5. Squaring
Bu yöntemde de önce değerin karesini alıyorsunuz ve taşma olursa(bir sütteki gibi taşan hane varsa), taşan haneyi atıyorsunuz.

6. Radix Conversion
Bu yöntemde de sayılık sisteminizi değiştiriyorsunuz. Atıyorum, 10luk sistemde bir değeriniz var diyelim ki. Siz bunu 16lık sisteme(hex) çeviriyorsunuz.

7. Polynomial Hashing
Bilgisayar Ağları dersi aldıysanız, bu yöntemi CRC başlığında işlemişsinizdir zaten.
Bir tane sabit polinom tanımlarsınız, örneğin: x³+x
Bir tane de polinom key tanımlayın, örneğin: x⁶+2x⁵+....+6x¹+7x⁰
Bu son yazdığım polinomu, sabit polinomunuza bölün. Kalan sonuç adresi verecektir.

8. Alphabetic Keys
Sevmediğim bir yöntemdir bu. Elinizdeki key'i alfanümerik hale getiriyorsunuz. Normalde key değerlerimiz hep sayısal idi dikkat ettiyseniz. Daha sonra da, alfanümerik hale getirdiğiniz key'i truncate ediyorsunuz. Elinizde de adres kalmış oluyor. Yalnız Türkçe'yi katlettim orijinal terimleri kullanacağım diye. Kendimden utanıyorum ama Türkçe'deki bilimsel anlamlarını henüz bilmiyorum bazılarının.

Fonksiyonlar bu kadar. Zaman geçmek bilmiyor, ben yazmaya devam edeceğim sanırım. Birazdan görüşürüz.