Gömülü Proje - HashMap Yazmak

Giriş
Gömülü bir projede hashmap yazmamız gerekti. Hashmap yazmak için gerekli bazı bilgiler şöyle.

Buradaki bilgiler concurrent (eş zamanlılık) olmayan bir HashMap için

Çakışma Collision
Mükemmel hash fonksiyonu olmadığı için anahtarların çakışması durumundan kaçınmak mümkün değildir. Aşağıda çakışma durumunda kullanılabilecek iki yöntemin açıklaması var.

1. Çakışma Durumunda Chaining Yöntemi
Chaining aynı zamanda closed addressing olarak ta anılır. Bucket adresi bir kere bulunduktan sonra tekrar hesaplanmaz. Chain işlemi için farklı veriyapıları tercih edilebilir.

1.1 Separate Chaining With Linked Lists Yöntemi
Bu yöntemde hash veri yapısındaki her eleman içinde liste bulunduran bir array yapısına işaret eder. Çakışma olması durumunda array'deki listeye yeni bir ekleme yapılır.

1.2 Java 8 ve HashMap
Java 8'e kadar olan HashMap çakışmadan kurtulmak için Separate chaining with linked lists yöntemini kullanıyor. Bu yöntemde aynı hash değerine sahip sınıflar liste şeklinde sıralanıyorlar.

Java 8'den sonra ise ise Separate Chaining With Other Data Structures yöntemi benimsenmiş. Linked List'in boyu 8'i geçerse, binary tree veriyapısına geçiyor.

1.3 Guava
Performance of Guava's ImmutableSet.contains sorusunda sürekli çakışmaların yaşanması yüzünden ImmutableSet'in performansının bazı durumlar için çok iyi olmadığını anlatılıyor

2. Çakışma Durumunda Open Addressing Yöntemi
Bu yöntemde hash veri yapısındaki her eleman tek bir array yapısına işaret eder.

Separate Chaining yönteminin aksine array'deki her bir eleman liste değildir. Çakışma durumunda ya array büyütmek ya da array'de yeni bir boşluk bulmak gerekir.

2.1 Open Addressing With Linear Probing Yöntemi
Yeni bir boşluk bulmak için kullanılabilen yöntemlerden birisi ise Linear probing. Yani hash değerini bir sabit değer kullanarak artırmak. Java'daki IdentityHashMap sınıfı bu yöntemi kullanıyor. Açıklaması şöyle

Open addressing means that the key-value pairs are stored in a single array. The index to store a key-value pair is given by the hash code modulo the array size.

Linear probing means that if this array element is already occupied, we use the next array element. And so on, until we have found an empty slot.

3. Çakışma Varsa HashMap Neden O(1) Kabul Edilir?
Çakışmalar yüzünden her hash kullanan veri yapısında bir miktar O(1)'den fazla işlem yapar ancak Amortized Analysis yöntemince zamana yayılan kullanımda limiti alınan denklem sonsuzda O(1)' yakınsar. Bu yüzden O(1) kabul edilir.

Şu şekilde unordered_map ile map arasındaki farkı görmek mümkün. Amortized algortimaları anlamak için buradaki cümle önemli:

Amortized algorithms and data structures usually perform additional house keeping tasks which "amortize" for the performance costs of other operations.

4. Bucket Boyunun Dizisinin Değişmesi - ReHashing
Eğer bucket boyutunu değiştirirsek elemanların hash değerinin tekrar hesaplanarak yeni yerlerine yerleştirmek gerekir, dolayısıyla O(n) bir işlem yapılır.

Büyüme durumunda yeni boyutun (eski boyut * 2) 'nin üstteki en yakın asal sayıya yuvarlanması kullanılabilir.