HashMap nedir ve HashMap nasıl çalışır?

Bu yazıda, neden Hashmap kullandığımızdan ve Hashmap’in çalışma mantığını açıklamaya çalışacağım. Biraz uzun bir yazı olabilir.

Hashmap Map Interface’ni gerçekleştiren, AbstractMap’i ise extend eden bir sınıftır.

Hashmap’in en öne çıkan özelliği Key-Value(anahtar-değer) mantığıyla çalışıyor olması. Tuttuğu her anahtara karşılık, yine bir değer tutuyor. Key-Value ikilisinin birleşimineyse “Entry” diyoruz.

Hashmap yapısı not-sychronized’dır. Yani asenkron yapıdadır. Çoklu thread kullanımı olursa aynı anda bir elemana birden fazla thread erişebilir. Bu yüzden harici olarak senkronize edilmelidir. HashMap yapısını kullanırken dikkat etmemiz gereken birkaç nokta var . Örneğin HashMap entryleri eklenme sırasına göre veya belirli bir sıralamaya göre tutmaz. Sadece Key(anahtar)’ lerin -özellikle belirteyim sadece keylerin hashcode’u oluşturulur, valuelerin hashcode’u oluşturulmaz - Hash değerlerine göre sıralar belirli bir algoritmadan geçirir ve bir indexe atama yapar. Hashmap dışında Key-Value mantığına göre çalışan iki sınıfımız daha var. Bunlarsa LinkedHashmap ve TreeMap. Kısaca onlara da değinmek istiyorum. Aralarında küçük ancak önemli farklar bulunmakta.

LinkedHashMap ve TreeMap ikisi de aynı şekilde Not-Sychronized yapıdadır. LinkedHashMap entryleri ekleme sırasına göre tutarken, TreeMap ise Comparator Interface’nin yardımıyla istediğimiz şekilde sıralamalar yapabiliyoruz. Bu sıralama olayının elbette bir maliyeti var. Aralarında en hızlı çalışan HashMap oluyor böylelikle.

Öncelikle bir HashMap oluşturan kod yazalım, sonra eklemeler yapalım ve en son olarak nasıl çalıştığını anlatmaya çalışalım.

Çıktısını ise şöyle alıyoruz.

Öncelikle tanımlamamızla başlayalım. Main metodunun içine girdik ve HashMap<Integer,String> yazdık. Bu kullanıma Generic HashMap diyoruz. Bu tanımda dikkat edilmesi gereken şey şu : Eğer Primitive bir tip kullanmak istiyorsanız mutlaka Wrapper sınıflarıyla kullanmalısınız . Ardından referansımızı belirtiyoruz “plakaMap” şeklinde. Sonra kurucumuzu (constructor) çağırıyoruz.

Şimdi kurucumuzun içine bir şey yazmadan da varsayılan değerlerle Hashmapimizi oluşturabilirdik. Ancak kurucumuz overload edilmiş. Kurucularımızı inceleyelim o halde.

HashMapin dört farklı parametre alabilen kurucusu vardır.

1. HashMap()

2. HashMap(int initialCapacity)

3. HashMap(int initialCapacity, float loadFactor)

4. HashMap(Map map)

İlk kurucumuz herhangi bir parametre almıyor. Parametre almadığında kendisi varsayılan değerler atıyor. Hangi elemanlara varsayılan değerler atanır derseniz initialCapacity ve loadFactor ikilisine atanır. Initialcapacity Hashmapin oluşturulduğu zaman, boyutunun ne kadar büyüklükte olacağını belirten değerdir. Hiçbir parametre girmediğimizde Hashmap’in boyutu yani initialcapacity değeri varsayılan olarak 16'dır. Yani bir HashMap oluşturduğumuzda HashMap 16 eleman boyutundadır. loadFactor’ın default parametresi 0.75f’dır. loadFactor bize bellek tasarrufunda büyük katkı sağlar. Peki nasıl ?

Şimdi şöyle düşünelim, elimizde bir HashMap var. Bu HashMap’ın değer girildikçe büyümesini bekleriz. Ancak bunun oranı ne olacak ? Yani kaç eleman girdiğimizde HashMap kendi boyutunu arttıracak? İşte bu parametreyi loadFactor ile veriyoruz. 0.75 = 3/4 olduğu için 16*3/4 işlemi bize 12 sonucunu verecektir. Hashmap’e 12 eleman girildiği anda HashMap default olarak kendi boyutunu 2 katına çıkaracaktır. Yani 32. Biz parametreyi 0.50f girersek, 8.eleman girildiği zamana HashMap boyutunu 2 katına çıkaracaktır.

Ve Son olarak HashMap parametre olarak Map Interface’ini implemente eden başka bir sınıfı parametre olarak alabilir. Alırsa ne olur dersek kodlayalım ve sonucuna bakalım.

İlk Hashmapimize benzer bir kod amacıyla plakaMap2 ve plakaMap3 Hashmaplerini oluşturdum. plakaMap2 Hashmapine iki adet entry ekledim. Ardından plakaMap3 Hashmapini oluşturdum ve parametre olarak plakaMap2'yi geçtim. Ancak dikkat ettiyseniz plakaMap3 Hashmapine hiçbir entry girmedim.

Iterator ile plakaMap3'ün içindeki entryleri dolaşmak istedik ve çıktımız aşağıdaki gibi oldu.

Peki buradan çıkarmamız gerekense şudur : Eğer bir Hashmap kurucusuna başka bir Hashmapi parametre geçersek onun elemanlarını kendisine ekler. Iterator ile değil foreach ile okumak isteseydik şöyle yapacaktık. Ve çıktımız yine aynı olacaktı.

Aslında bu yazının asıl amacı, HashMaplerin çalışma mantığını anlatmaktı. Şimdi ona geçelim.

Öncelikle şunu bilelim Hashcode nedir ? Hashcode ile ilgili bilinmesi gereken ilk şey şudur, Hashcode bellek adresi değildir. Java da bellek adreslerine erişim gibi bir şey mümkün değildir. Hashcode sizin verdiğiniz nesnenin, integer tipinde karşılığı aslında. Hatta şöyle gösterebilirim.

Şimdi birkaç nesne oluşturalım ve bu nesnelerin hashcodelarını gözlemleyelim.

Primitive nesnelerde object sınıfından gelen hashcode herhangi bir problem çıkarmıyor. Ancak kendi oluşturduğumuz sınıflarda bu olay maalesef böyle olmuyor. HashMap yapısına bağlı olarak hashcode ile çalıştığı için bu durum bizim için kritik önem arzediyor. Yazının başında da söylemiştim. Key değerlerimizin Hashcode’u alınıyor, belirli bir algoritmadan geçiriliyor ve algoritma sonucunda çıkan indexe entrylerimiz(<K,V>) atanıyor.

Eğer kendi oluşturduğumuz sınıfları <K,V> olarak kullanacaksak, oluşturduğumuz sınıflarda equals ve hashcode metotlarını override etmeliyiz. Peki neden?

Öncelikle bir sınıf oluşturalım, bu sınıf kurucusuna iki değişken alsın, boy ve yaş. Ve bizim yaşı key olarak kullandığımızı düşünün

Yukarıdaki kodun çıktısı, şöyle oluyor:

Halbuki bizim girdiğimiz nesnelerin tüm değerleri birbirine eşit. Bu yüzden equals metodunu sınıfımızda override etmezsek, bu tip sorunlar yaşayabiliriz. Biz bu iki nesnenin aynı olduğunu düşünürken, program öyle düşünmüyor. HashMap oluşturduğumuzda, eğer ki kendi oluşturduğumuz bir sınıfı kullanacaksak herhangi bir sıkıntı yaşamamak için equals ve hashcode ikilisini sınıfımızda override etmeliyiz.

Şimdi HashMapin nasıl çalıştığına geçelim.

Bir Hashmap nesnesini tanımlayalım ve içine entryler koyalım. Hashmapi ilk tanımladığımız an bellekte,

16 elemanlı bir dizi oluşturuluyor. Bu yapının tamamına “Table” diyoruz.

Hashmap kurucusuna herhangi bir parametre vermeden çalıştırırsak bellekte oluşturulacak alan budur

Bir alt çizim de “put” metodunu kullandığımızda neler olduğunu anlatmaya çalışacağım.

kisiListesi Hashmapinin tamamına “table” dediğimizi söylemiştik. Table’da her satıra ise “basket”(sepet) diyoruz .Hashmapimize “put()” metoduyla, Key değerleri sırasıyla Yahya, Levent olan valueleriyse (değerleri) sıralı olarak 1,2 olan iki entry ekledik. Yahya keyinin(anahtarının)nasıl işlemlerden geçtiğini anlatalım, zaten hepsi aynı mantıkla çalışıyor. Öncelikle sadece key değerlerinin hashcodenun alındığını söylemiştik. Yahya keyinin hashcode değeri : 85186888 çıkıyor. Bu key değeri direkt hashmape atanmıyor. Zira bu inanılmaz bir bellek masrafına sebep olurdu. Burada 85186888 değeri bir algoritmadan geçirilip [0,16] arasında bir yere atanıyor. Bu algoritmadan burada bahsetmeye şimdilik gerek yok böyle olduğunu bilelim yeter.

Atadığımız varlığa ise “node” diyoruz. Node 4 parçadan oluşur. İlk kısım key değerini, ikinci kısım keyin karşılığı olan değeri, üçüncü kısım hashcodeu ve 4.kısım ise bir sonraki nodeun bilgisini tutar. Bir sonraki nodeun bilgisi derken neyi kastediyoruz? Açıklayalım.

Hashmapimize put() metoduyla bir eleman daha ekleyelim.

kisiListesi.put(“Mert”,3) olsun. Mert Keyinin hashcodenun Yahya Key değerinin hashcodeu ile aynı olduğunu düşünelim. Tekrardan hatırlarsak, hashcodeun bir algoritmadan geçirildiğini ve bu algoritma sonucunda çıkan sayının değeri olan indexe atandığını söylemiştik. Hashcodelar aynıysa atanacağı index numarası da aynı çıkacak. Peki böyle olursa beşinci indexteki veri silinip(Yahya Keyinin değeri) yerine Mert Keyinin değeri mi yazılacak?

Hayır böyle olmuyor. Şimdi çizimlere biraz daha mercek tutalım.

Gördüğümüz gibi iki entry de aynı indexe bağlı. Eğer aynı index numarası dolu diye silip yerine sadece Mert keyinin nodeunu tutsaydı, Yahya keyinin nodeunu kaybedecektik. Bu sebeple önce yeni node oluşturuluyor, ve bu yeni node tıpkı diğer node gibi dolduruluyor. Ancak şöyle bir fark var aralarında. Yahya keyinin next bölümü artık null bir yere işaret etmiyor. Mert Keyinin nodeuna işaret ediyor(onun bilgisini tutuyor). Next kısmı bu işe yarıyor. Böylelikle aynı indexte birçok node tutabiliyoruz. Herhangi bir veri kaybı olmuyor.

HashMap yapısının key değerleri benzersizdir(unique). Yani aynı key değerinden iki tane olamaz. İki tane key değerinin alt alta yazarsanız, HashMap bunu güncelleme olarak algılayacaktır. Ve değerleri değiştirecektir. HashMapte son yazdığınız <Key, Value> değeri kayıtlıdır.

Örneğin ben kisiListesi.put(“Mert,5) yaparsam daha önce tuttuğu 3 değeri silinecek, yerine 5 değeri yazılacaktır. Null değerlerin de key olabildiğini bilmeliyiz. Null Key değerleri varsayılan olarak direkt sıfırıncı indexe atanırlar.

Peki, bir başka konuya değinelim, put metodu nasıl değerleri nasıl güncelleme yapıyor?

kisiListesi.put(“Yahya,5) diyelim.

Öncelikle key değerinin null olup olmadığı kontrol ediliyor. Eğer null bir değerse index 0'a atanıyor ve geçiliyor. Ancak null değilse key değerinin hashcodeu hesaplanıyor. Örneğimizde key değeri yukarıdaki çizimde olan “Yahya” değeri olsun. Null kontrolü yapıldıktan sonra “Yahya” değerinin hashcodeu hesaplanır. Belirli algoritmadan tekrar geçirilir. Ve index bulunur. Biz 6 numaralı index olduğunu varsayıyoruz. 6 numaralı indexe geldiğinde, baskette(her satıra bir basket dediğimizi söylemiştik)node var mı diye bakıyor. Node varsa hashcode kontrolü yapıyor.(Aynı nodeda farklı hashmap değerleri olabilir.)Hashcode değeri eğer doğruysa, bu sefer key değerlerinin kontrolünü yapıyor(Key değerleri benzersizdir.)eğer key değerleri de tutuyorsa, bu key değerleri güncellenmek istiyor diyerek, yeni valueyi oraya yazıyor. Böylelikle güncelleme yapılmış oluyor.

Güncellenmiş hali.

Peki get() metodu nasıl çalışıyor?

kisiListesi.get("Mert");

Not: Bu kısma gelmeden önce Yahya ve Mert Key değerlerinin aynı indexe(6 numaralı) karşılık geldiğini unutmayalım. Yukarıdaki çizimde belli oluyor aynı zamanda.

Yukarıda kodda görüldüğü gibi “Mert” keyine karşılık gelen değerini çağırdık. Peki arka planda neler oldu ?

Öncelikle “Mert” Key değerinin hashcodeu hesaplanıyor. Aynı şekilde algoritmadan geçip hashcodeu buluyor. Hashcodeun hangi indexe karşılık geldiğini bulduktan sonra, daha sonra içeride olan nodeları kontrol etmeye başladı. Öncelikle hashcodeları kontrol etmeye başlıyor.(farklı hashcode sayısı da bu indexte bulunabilir.)İlk olarak Yahya keyinin bulunduğu node’a geldi. Hashcodeları aynı olduğu için, hemen Key değerinin kontrolü yapılıyor. Key değeri “Yahya” olduğunu görünce eşleşme sağlanamıyor ve Yahya keyinin next kısmına gelip diğer nodea atlıyor.

Aynı şekilde önce hashcode ve sonra key değeri kontrolü yapıldıktan sonra

eşleşmeleri sağlayınca, demek ki aranan değer bu diyerek “3” değerini döndürüyor. Çalışan yapı aşağı yukarı böyle. Elbette daha detayına inilebilir ancak bu yazıda gerek görmedim.

Kısaca Hashmap metotlarına da değinelim. Çok kısaca değineceğim çünkü yazının amacı bu değil.

1. put() metodu : Hashmapin içine entry yerleştirir.
2. get() metodu : Verdiğimiz keyin hashmapte karşılığı olan değeri döner.
3. size() metodu : Hashmapin içinde kaç entry olduğunun değerini döner.
4. entrySet() metodu : Hashmap içindeki entryleri set yapısına çevirip, döndürür.
5. putAll() metodu : Parametre olarak gelen hashmapinn içindeki tüm değerleri çağıran hashmape aktarır.
6. clear() metodu : Tüm entryleri hashmapten siler.

Özet olarak;

• Java Collections Framework’unun bir öğesidir.
• Hashmap Map interfaceni gerçekleştiren üç sınıftan biridir.
• <Key,Value> mantığıyla, bir nevi sözlük yapısıyla çalışır.
• Bu üç sınıf arasında en hızlı çalışan veri yapısı HashMaptir.
• Elemanları listelerken herhangi bir sıralamayla yapmaz.
• Key değerleri benzersizdir. Bir Key değerinden sadece bir tane olabilir. Buna mukabil valuelerde böyle bir şart yoktur. Benzersizliği söz konusu değildir. Farklı key değerleri aynı valueleri tutabilir.
• Asenkron yapıdadır.
• Null key değeri ve Null value alabilir.

Elimden geldiğince anlatmaya çalıştım, yanlış bir bilgi verdiysem düzeltmem için bana ulaşırsanız çok sevinirim. Okuyan herkese şimdiden teşekkür ederim.