Hash fonksiyonu, belirli uzunluktaki bir veri setini bir diziye yerleştirmek için kullanılan yöntemdir. Hash fonksiyonu her bir veri için bir index değeri üretir ve veri dizide üretilen index değerine yerleşir. İndex değeri üretmek için farklı algoritmalar kullanılabilir. En yaygın kullanılan yöntemlerden biri; elemanın dizinin büyüklüğüne bölümünden kalanı index olarak almaktır. Eğer dolu olan bir index değeri üretilirse collision (çakışma) durumu oluşur. Bu durumda çakışmayı önlemek için farklı yöntemler kullanılarak eleman yeni bir index’e yerleştirilir.
[8, 6, 7, 21, 35, 22] elemanlarını, hash fonksiyonu h(x) = x % 10 olmak üzere “10” büyüklüğünde bir diziye yerleştirelim.
Öncelikle elemanlar için hash fonksiyonunu kullanarak index değerlerini üretelim.
h(8) = 8 % 10 = 8
h(6) = 6 % 10 = 6
h(7) = 7 % 10 = 7
h(21) = 21 % 10 = 1
h(35) = 35 % 10 = 5
h(22) = 22 % 10 = 2
Şimdi, elemanları hash fonksiyonu ile oluşturduğumuz index’lerine yerleştirelim.
Tüm elemanlar diziye collision durumu olmadan yerleşebildi. Peki ya collision olsaydı? Bu durumda; separate chaining (Ayrık zincirleme), linear probing (doğrusal ölçüm) veya quadratic probing (karesel ölçüm) yöntemlerinden birini kullanmamız gerekecekti.
Separete Chaining
Bu yöntemde dizinin elemanları birer linked list tutar. Boş bir index’e eleman, linked list’in ilk node’u olarak yerleşir. Eğer index boş değilse; eleman, index’deki linked list’in son node’u olarak yerleşir.
Aşağıda; [10, 20, 25, 1, 2, 5, 16] elemanları, hash fonksiyonu h(x) = x % 10 olmak üzere “10” büyüklüğünde bir diziye collision durumunda separete chaining uygulanarak yerleştirilmiştir.
Linear Probing
Bu yöntemde eğer elemanın yerleşeceği index doluysa bir sonrakine yerleşir. Eğer bir sonraki de doluysa boş olan index bulana kadar sırayla bakmaya devam eder.Boş index bulduğunda o index’e yerleşir.
Aşağıda; [10, 20, 25, 1, 2, 5, 16] elemanları, hash fonksiyonu h(x) = x % 10 olmak üzere “10” büyüklüğünde bir diziye collision durumunda linear probing uygulanarak yerleştirilmiştir.
Quadratic Probing
Bu yöntemde eğer elemanın yerleşeceği index doluysa; sırasıyla kendinden 1, 4, 9, 16… sonraki indexlere bakılarak boş olana yerleştirilir.
Aşağıda; [10, 20, 25, 1, 2, 5, 16] elemanları, hash fonksiyonu h(x) = x % 10 olmak üzere “10” büyüklüğünde bir diziye collision durumunda quadratic probing uygulanarak yerleştirilmiştir.
