Niyə HashMap?
Array-də bir key-i tapmaq üçün element-ləri bir-bir yoxlamaq lazımdır. 1 milyon element varsa, 1 milyon yoxlama ola bilər: O(n).
HashMap key-dən birbaşa index hesablayır və həmin bucket-ə gedir. Element sayı artsa da, yoxlama sayı adətən dəyişmir: orta hesabla O(1).
Sağda get("Leyla")-nın yolunu görürsən: key, hashCode(), hash, index, bucket.
hashCode: key-dən number
String.hashCode() hər character-i bu formula ilə toplayır: h = 31 * h + c. Burada c character-in kodudur.
Eyni String həmişə eyni number verir. Nəticə int-dir, overflow olanda mənfi də ola bilər.
Solda başqa key yaz və sağda hesablamanın necə dəyişdiyinə bax.
spread: yuxarı bit-ləri qarışdırmaq
index yalnız aşağı bit-ləri işlədir: n = 16 üçün son 4 bit. Spread olmasa, yalnız yuxarı bit-ləri fərqli olan key-lər eyni bucket-ə düşərdi.
Ona görə HashMap hash = h ^ (h >>> 16) hesablayır: yuxarı 16 bit aşağı 16 bit-ə qarışır.
Aşağıdakı Integer key-lərdə fərqi görürsən:
index: bucket-in yeri
index = (n - 1) & hash. Burada n capacity-dir və həmişə 2-nin qüvvətidir: 16, 32, 64. new HashMap<>(20) yazsan da, capacity 32 olur.
Ona görə n - 1-in aşağı bit-lərinin hamısı 1-dir (15 = 1111) və & yalnız hash-in son bit-lərini saxlayır.
Nəticə həmişə 0 ilə n - 1 arasındadır, hash mənfi olsa belə.
Collision
Fərqli key-lər eyni bucket-ə düşə bilər. "Aa" və "BB"-nin hashCode-u eynidir: 2112.
Bucket-də artıq Node varsa, yeni Node zəncirin sonuna next ilə bağlanır. Heç nə silinmir, array də dəyişmir.
Solda AaAa və BBBB yaz: onların da hash-i eynidir.
get və equals
get eyni yolla bucket-i tapır, sonra zəncirdə gəzir. Hər Node üçün əvvəl hash, sonra == və ya equals yoxlanır.
Sağda hər Node-un yanında yoxlamanın nəticəsi yazılıb.
Ona görə öz class-ını key edəndə equals və hashCode-u birlikdə yazmalısan. Biri olmasa, eyni məzmunlu key tapılmaya bilər.
Eyni key-ə put
Key artıq varsa, yeni Node yaranmır: mövcud Node-un value-su dəyişir, size artmır.
put köhnə value-nu qaytarır. Key-in özü dəyişmir.
resize
Table ilk put-da yaranır. Default capacity 16, load factor 0.75-dir, ona görə threshold 12-dir.
size threshold-u keçəndə, yəni 13-cü element-də, capacity 2 dəfə artır. Yeni array yaranır, Node-lar ora köçürülür.
hash yenidən hesablanmır, Node-da saxlanır. Yeni bir bit yoxlanır: hash & oldCap 0-dırsa index qalır, deyilsə index + oldCap olur. Yerini dəyişən Node-lar sağda işarələnib.
Zəncir uzananda: tree
Bir bucket-də Node çoxalanda axtarış yavaşlayır. Zəncir 8 Node-u keçəndə capacity 64-dən kiçikdirsə, əvvəl resize olur. Capacity 64 və ya daha böyükdürsə, bucket red-black tree-yə çevrilir və axtarış O(log n) olur.
Burada 11 key-in hash-i eynidir: 9-cu key-də capacity 32, 10-cu key-də 64 oldu, 11-ci key-də bucket tree-yə çevrilir.
Resize zamanı Node sayı 6 və ya daha az qalan bucket yenidən list olur. Bu alət tree-ni list kimi çəkir və bucket-i TreeNode nişanı ilə göstərir.
Bilməli olduğun tələlər
Sıra zəmanət deyil: element-lər bucket sırası ilə gəzilir. Sağdakı çıxışa bax. Əlavə etmə sırası lazımdırsa, LinkedHashMap işlət.
null key olar: hash-i 0-dır və bucket 0-a düşür.
Thread-safe deyil: bir neçə thread üçün ConcurrentHashMap işlət.
Key-i dəyişmə: map-ə girəndən sonra hashCode-u dəyişsə, Node köhnə bucket-də qalır və key tapılmır. Ona görə String kimi immutable key-lər yaxşıdır.