Perfect Hashing

Merhaba herkese. Dün dediğim gibi yine bir algoritma başlığı ile birlikteyiz. :) Bugün de perfect hashing'in nasıl olabileceğine değineceğiz.

Malumunuz, hashing işleminde her key'e karşılık bir adres hedefi vardı. Ancak farklı 2 key aynı adresi ya da başka deyişle elemanı üretirse, burada çatışma, çarpışma(collision) oluşuyordu. Collision'ı önlemek için de 3 yöntem vardı: Linkli, Linksiz, Yalancı Linkli. bunlara zaten girmiyorum şimdi, ana konuya döneyim tekrar.

Perfect Hashing'de unique adresleme var. Key sayısı ile adreslerin(yani üretilecek elemanlar) sayısı aynı olması ideal bir durum yaratmaktadır. Örnek olarak programlama dilindeki "keyword"ler verilebilir. Yani sabit ve az elemanlı olmasına özen göstermeliyiz. Aksi taktirde avantajdan ziyade dezavantajı var.

Gösterimi de şu şekilde:
p.hash(key)=(h₀(key)+g[h₁(key)]+g[h₂(key)])

Bu formüle, mesela: g[h₂(key)] ifadesinde, key'i hashliyorsunuz, g tablosundaki ilgili yerde bulunan değeri alıyorsunuz.(g tablosunu oluşturmak için farklı yöntemler vardır, muhtemelen bunun hakkında yazı sonra yazarım ama, siz şimdilik size verildiğini kabul edin bu tablonun.)

En yaygın algoritmayla basit bir örnek yapacağım. Ayrıntılı bir yazıyı da yakında yazarım ama gitmem lazım şu an. O yüzden girizgah mahiyetinde olacak bu yazı.

Cichelli Algoritması, en bilinen algoritmadır bu konu için. Bir programlama dilinin(yanılmıyorsam Pascal) keywordlerinin frekanslarına göre bir tablo oluşturulmuş ve işlemler ona gre yapılmış. Mesela B=15 N=13 vs. gibi her harfe bir değer atanmış tablo tasvir ediniz.

Hazır B ve N demişken, bu harfleri örnekte kullanayım. :) Cichelli'ye göre

h₀=uzunluk(key)
h₁=ilk karakter(key)
h₂=son karakter(key)

Örnek de şu olsun: begin.
Formül şuydu:
p.hash(key)=(h₀(key)+g[h₁(key)]+g[h₂(key)])

p.hash(begin)=5(h₀, begin'in uzunluğu,5 harfli bir kelime çünkü)+15(h₁'in g tablosundaki değeri.h₁ de ilk karaktere göre hesaplanıyordu, formüle bakarsanız.İlk karakter B. B=15)+13(Son karakter de n. N=13)=33


Başka bir key'den 33 değeri üretilmemeli. Başka bir deyişle b ile başlayıp, n ile biten ve 5 karakteri olan key olmamalı. Farklı durumları da başka zaman yazarım.

Görüşmek üzere..