Çırpılama (hashing), hash tablosu ve hash arama

• Hashing mevcut veriyi kullanarak benzersiz bir değer elde etme işlemidir.
• Hashing ile farklı büyüklükte girdilerden sabit büyüklükte çıktı elde edilir.
• Hashing bilgisayar ağlarında parola, kredi kartı numarası gibi birçok verinin güvenli bir şekilde iletilmesini sağlar.
• Hash algoritmaları deterministiktir. Yani girdi değişmediği sürece her zaman aynı hash çıktısı alınır.
• Hash girdisinin yalnızca bir karakteri bile değişse çıktı büyük ölçüde değişmelidir.

Bazı popüler hash algoritmaları

1. MD-5: 1991’de tasarlandı ve o günün şartları ile oldukça güvenliydi. Ancak bugün kolayca kırılabilen bir algoritmadır.
2. RIPEMD-160: 1990’ların ortalarında Belçika’da geliştirildi. Henüz kırılmadığı için aktif kullanılıyor.
3. SHA: İlk sürümler ABD hükümeti tarafından geliştirildi. Programcılar tarafından sonraki varyasyonları geliştirilerek kırılması daha zor hale getirildi. Genel olarak, “SHA” harflerinden sonraki sayı ne kadar büyükse, sürüm o kadar yeni ve karmaşıktır. Örneğin, SHA-3 rastgelelik içerir, bu da onu kırılması çok daha zor hale getirir. Bu nedenle 2015 yılında standart bir hash algoritması haline geldi.
4. Whirlpool: 2000 yılında AES’e (Advanced Encryption Standard) dayanarak geliştirilen çok güvenli Hash algoritmasıdır.

Bu algoritmaları denemek için “Hash Calculator” web sitelerini kullanılabilirsiniz. (Ör: https://md5calc.com/hash).

Veri ekleme, silme ve arama işlemi için hashing kullanımı

Burada Hashing’in temel bileşenleri girdi, hash fonksiyonu ve hash tablosudur.

Hash tablosu ile veri uygun bir satıra yerleştirilir. Hash tablosunun en önemli fonksiyonu bir anahtar ile tabloda arama yapıldığında anahtarın bulunduğu satırın çok hızlı biçimde bulunmasıdır. Veri eklemenin veya aramanın yapılacağı satır, yani indeks numarası aşağıda gösterilen hash fonksiyonu ile bulunur.

Hash fonksiyonunun algoritma karmaşıklığı en iyi durum için O(1), en kötü durum için O(n)’dir. Bellek karmaşıklığı ise O(1)’dir.

Örneğin 10 elemanlı boş bir diziye {12, 34, 48} elemanları sırasıyla aşağıdaki gibi yerleştirilir.

Bir karakter dizisine hash uygulamak için alfabedeki harflerin her birine bir sayısal değer verilir. Örneğin;

a = 1, b = 2, c = 3, d = 4, e = 5, f = 6…

Hash tablosunun boyutunun 12 olsun (s = 12).

Sırasıyla {ada, feda, baba} kelimelerini bu tabloya yerleştirmek istenirse,

ada = a + d + a = 1 + 4 + 1 = 6

feda = f + e + d + a = 6 + 5 + 4 + 1 = 16

bebe = b + e + b + e = 2 + 5 + 2 + 5 = 14

Hash fonksiyonu iki farklı girdi için aynı çıktıyı üretiyorsa bu duruma çatışma (collision) denir. Örneğin, 12 elemanlı bir hash tablosuna sırasıyla {12, 36} verileri girilmek istenirse,

Çatışma problemini çözmek (collision resolving) için bazı yöntemler kullanılır:

Ayrık zincirleme

Bu teknikte çatışma gerçekleştiğinde, yeni gelen veri ilgili indekse bağlı liste mantığı ile bağlanır.

Örneğin boyutu 6 olan hash tablosuna {12, 41, 8, 24} verileri yazılmak istenirse,

Bu hash tablosunda 24 verisi aranmak istenirse 0.indekse bakılır. Bu indekste farklı veri olduğu görüldüğünde bu verinin gösterdiği 2.adrese bakılır. Yine farklı veri bulunursa 3.adrese bakılır. Aranan veri bulunana kadar bu işlem devam eder.

Açık adresleme

Bu yaklaşımda Hash fonksiyonu ek bir sayısal girdi (i) alır. Hash fonksiyonunun sonucunda gösterilen indekse veri yazılır veya veri burada aranır.

1. Doğrusal araştırma

Hash fonksiyonu: H(x) = (x + i) % s

i çatışma sayısını gösterir. Yani, çatışma gerçekleşmediği sürece i = 0’dır. Her çatışma gerçekleştiğinde i = i+1 olarak hesaplanır.

Örneğin, boyutu 6 olan hash tablosuna {12, 41, 8, 24} verileri yazılmak istenirse,

2.İkinci dereceden araştırma

Çatışma gerçekleşmediği sürece i = 0’dır. Her çatışma gerçekleştiğinde i = (i+1)² olarak hesaplanır.

Örneğin, boyutu 6 olan hash tablosuna {24, 29, 41} verileri yazılmak istenirse,

3.Çift çırpılama

Bu yöntemde kullanıcı tarafından tanımlanmış iki farklı hash fonksiyonu (H₁(x) ve H₂(x)) kullanılır. Çift çırpılama, bu iki hash fonksiyonunun kombinasyonu şeklinde çalışır (i: çatışma sayısı).

H(x) = ( H₁(x) + ( i * H₂(x) ) ) % s

Örneğin,

H₁(x) = x % 5

H₂(x) = |5 – x|

Fonksiyonları için 6 elemanlı diziye {21, 33, 51} verilerini eklenirse,