Neden HashMap?
Array'de bir key'i bulmak için element'leri tek tek kontrol etmek gerekir. 1 milyon element varsa 1 milyon kontrol olabilir: O(n).
HashMap, key'den doğrudan index hesaplar ve o bucket'a gider. Element sayısı artsa da kontrol sayısı genellikle değişmez: ortalama O(1).
Sağda get("Leyla") çağrısının yolunu görüyorsun: key, hashCode(), hash, index, bucket.
hashCode: key'den number
String.hashCode() her character'i şu formülle toplar: h = 31 * h + c. Burada c, character'in kodudur.
Aynı String her zaman aynı number'ı verir. Sonuç int'tir, overflow olunca negatif de olabilir.
Solda başka bir key yaz ve sağda hesaplamanın nasıl değiştiğine bak.
spread: üst bit'leri karıştırmak
index yalnızca alt bit'leri kullanır: n = 16 için son 4 bit. Spread olmasa, yalnızca üst bit'leri farklı olan key'ler aynı bucket'a düşerdi.
Bu yüzden HashMap hash = h ^ (h >>> 16) hesaplar: üst 16 bit, alt 16 bit'e karışır.
Aşağıdaki Integer key'lerde farkı görüyorsun:
index: bucket'ın yeri
index = (n - 1) & hash. Burada n capacity'dir ve her zaman 2'nin kuvvetidir: 16, 32, 64. new HashMap<>(20) yazsan bile capacity 32 olur.
Bu yüzden n - 1 değerinin alt bit'lerinin hepsi 1'dir (15 = 1111) ve & yalnızca hash'in son bit'lerini tutar.
Sonuç her zaman 0 ile n - 1 arasındadır, hash negatif olsa bile.
Collision
Farklı key'ler aynı bucket'a düşebilir. "Aa" ve "BB" için hashCode aynıdır: 2112.
Bucket'ta zaten Node varsa, yeni Node zincirin sonuna next ile bağlanır. Hiçbir şey silinmez, array de değişmez.
Solda AaAa ve BBBB yaz: onların da hash'i aynıdır.
get ve equals
get aynı yolla bucket'ı bulur, sonra zincirde gezer. Her Node için önce hash, sonra == veya equals kontrol edilir.
Sağda her Node'un yanında kontrolün sonucu yazıyor.
Bu yüzden kendi class'ını key yaparken equals ve hashCode metotlarını birlikte yazmalısın. Biri olmazsa, aynı içerikli key bulunamayabilir.
Aynı key'e put
Key zaten varsa yeni Node oluşmaz: mevcut Node'un value alanı değişir, size artmaz.
put eski value'yu döndürür. Key'in kendisi değişmez.
resize
Table ilk put çağrısında oluşur. Default capacity 16, load factor 0.75'tir, bu yüzden threshold 12'dir.
size threshold'u aşınca, yani 13. element'te, capacity 2 katına çıkar. Yeni array oluşur, Node'lar oraya taşınır.
hash yeniden hesaplanmaz, Node'da saklanır. Yeni bir bit kontrol edilir: hash & oldCap 0 ise index kalır, değilse index + oldCap olur. Yer değiştiren Node'lar sağda işaretli.
Zincir uzayınca: tree
Bir bucket'ta Node çoğalınca arama yavaşlar. Zincir 8 Node'u geçince capacity 64'ten küçükse önce resize olur. Capacity 64 veya daha büyükse bucket red-black tree'ye çevrilir ve arama O(log n) olur.
Burada 11 key'in hash'i aynı: 9. key'de capacity 32, 10. key'de 64 oldu, 11. key'de bucket tree'ye çevrilir.
Resize sırasında Node sayısı 6 veya daha az kalan bucket yeniden list olur. Bu araç tree'yi list olarak çizer ve bucket'ı TreeNode etiketiyle gösterir.
Bilmen gereken tuzaklar
Sıra garanti değildir: element'ler bucket sırasıyla gezilir. Sağdaki çıktıya bak. Ekleme sırası gerekiyorsa LinkedHashMap kullan.
null key olabilir: hash'i 0'dır ve bucket 0'a düşer.
Thread-safe değildir: birden fazla thread için ConcurrentHashMap kullan.
Key'i değiştirme: map'e girdikten sonra hashCode değişirse Node eski bucket'ta kalır ve key bulunamaz. Bu yüzden String gibi immutable key'ler iyidir.