RUST : HashMap ve Hashing Anlamak

Hashing yapısı bilgisayar bilimlerinin özünde bulunan taa “data structer” konularından itibaren karşımıza çıkan hafıza yönetimi konusunda bizleri ilgilendiren bir konu.
Rust dilinde kullandığımız “HashMap” yapısı, verileri saklamak için kullanılan harika bir yapıdır. Anahtarlarınız için hazırladığınız hash değerlerine göre dizi içinde yerleştirir. Hash değerleri oluşturulduğunda, anahtarınızın yerleştirileceği dizi indisi belirlenir. Ayrıca, verileri hızlı ve verimli bir şekilde aramak, eklemek ve silmek için harika bir seçenektir.
Hashing işleminde basit mantık (öğretilen kadarıyla ) elimizde bulunan verilerin adedini, elimizde bulunan verilerin özelliğine göre “mod” alınarak yapılan işlemlerdir.
Az tanım çok örnek:
Elimizde bulunan Ates, Vitalik ve Elon Musk’ın adresleri mevcut. Bu adresleri ve kişileri listeye nasıl yerleştiririm?
(adres değeri temsili)
1-Veri adedini belirle ve buna göre adresin modunu al:
Ateş.eth 57 mod 3 = 0
Elon Musk -> 25 mod 3 = 1
Satoshi -> 29 mod 3 = 2
2- Bu mod verilerine göre kimin öncelikli olduğunu ve sıralamanın nasıl olacağını belirle:
Ates.eth 100 numaralı adrese adreslenecekse;
Elon Musk 101,
Satoshi 102 nolu adreste adreslenecek.
Bu kadar basit 😊 Peki aklınıza o önemli soru geldi mi? Bence geldi…
Mod işlemi sonucu bir adress için birden fazla değer gelirse ne olacak?
Bu örnekte Vitalik Bey ve Ates.Eth(Ben 😊) mod değerlerimiz aynı oluyor:
Buradaki duruma “Collision” deniyor. Collision nedeni ile ortaya çıkan sorunu çözme için birden fazla metod mevcut bunlar:

1-Separate Chaining
2-Open Addressing

Separate Chaining

Separate chaining metodu, bir hash tablosunda oluşabilecek çakışmaları çözmek için kullanılan bir yöntemdir. Bu yöntemde, her bir dizi indisi için bir bağlantılı liste oluşturulur. Eğer bir çakışma oluştuğunda, anahtar-değer çifti o bağlantılı listenin uygun indisine eklenir.
Bu sayede, aynı hash değerine sahip anahtar-değer çiftleri ayrı bağlantılı listelerde saklanır. Bu yöntem ile arama, ekleme ve silme işlemleri hızlı ve verimli bir şekilde gerçekleştirilebilir. Ayrıca, bellek kullanımını optimize etmek için dinamik bir boyutlandırma mekanizması kullanılabilir.

Az tanım çok örnek:
Sonradan eklediğimiz Vitalik Buterin’i dizi üzerinde nasıl göstereceğiz?
Vitalik ile Ates.eth aynı adreste adreslenirler. Bu adreslemede olay birbirlerine bağlı tek bir liste gibi görünmeleridir. Aşağıdaki gibi:

Open Addressing

Bu metodda çakışan değerler bir liste içinde tutulmaz. İlk değer atandıktan sonra gelecek olan değer şayet ilk değerin adreslendiği bölgeye denk geliyorsa, bu değer başka bir adrese atanır. Bu atama işleminde minicik bir matematik kullanarak anlamak mümkündür.
Bu adresleme yönteminin birkaç varyasyonu mevcuttur.

1-linear Probing
2-Quadratic Probing
3-Double Probing

Az tanım çok örnek:
“Vitalik Buterin”i chaining metodu ile değil, linear probing metodu ile yerleştirmek istersek,ne yapmamız gerekir?

Bu formülde anlatılmak istenen aslında çok basit. Veri değerini adres adedine göre modla ve yerleştir. Şayet yerleştirme sonucu çakışan bir durum olursa veri değerini bir artır ve tekrar adreslemeye çalış. Ta ki boş yer bulana kadar:


Vakit ayırdığınız için teşekkür ederim. İyi çalışmalar. İşiniz Rust gitsin 😊
(Dipnot:Rust Hashmap’de collision’u engelllemek için “Open Addressing” metodunu kullanır)