HashMap采用Entry數(shù)組來存儲key-value對，每一個鍵值對組成了一個Entry實體鹿响，Entry類實際上是一個單向的鏈表結(jié)構(gòu)羡微，它具有Next指針，可以連接下一個Entry實體惶我，依次來解決Hash沖突的問題妈倔，因為HashMap是按照Key的hash值來計算Entry在HashMap中存儲的位置的，如果hash值相同绸贡，而key內(nèi)容不相等盯蝴，那么就用鏈表來解決這種hash沖突毅哗。
put方法簡單解析
public V put(K key, V value) {
//調(diào)用putVal()方法完成
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷table是否初始化，否則初始化操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//計算存儲的索引位置捧挺，如果沒有元素虑绵，直接賦值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//節(jié)點(diǎn)若已經(jīng)存在，執(zhí)行賦值操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷鏈表是否是紅黑樹
else if (p instanceof TreeNode)
//紅黑樹對象操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//為鏈表闽烙，
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長度8翅睛，將鏈表轉(zhuǎn)化為紅黑樹存儲
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key存在，直接覆蓋
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//記錄修改次數(shù)
++modCount;
//判斷是否需要擴(kuò)容
if (++size > threshold)
resize();
//空操作
afterNodeInsertion(evict);
return null;
}
下面將這個過程總結(jié)一下：
如果當(dāng)前map中沒有數(shù)據(jù)黑竞，執(zhí)行resize方法
如果要插入的鍵值對要存放的位置上剛好沒有元素捕发，那么就把它封裝成Node對象，并放在這個位置上很魂。
如果發(fā)生碰撞爬骤，判斷node的類型是紅黑樹還是鏈表：
3.1 如果為紅黑樹，則將K-V對插在紅黑樹對應(yīng)的位置莫换。
3.2 如果為鏈表霞玄，遍歷鏈表：
a.如果為鏈表最后一個node ,則將新的node節(jié)點(diǎn)插入到鏈表尾
b.插入完，如果鏈表的node數(shù)量大于8拉岁，則將鏈表轉(zhuǎn)為紅黑樹的操作坷剧；如果當(dāng)前哈希表為空或數(shù)組長度小于64，會擴(kuò)容喊暖，否則轉(zhuǎn)化為紅黑樹惫企。轉(zhuǎn)化的過程：先遍歷鏈表 ，將鏈表的節(jié)點(diǎn)轉(zhuǎn)化為紅黑樹的節(jié)點(diǎn)陵叽；然后將鏈表轉(zhuǎn)化為紅黑樹狞尔。
c.遍歷鏈表時，如果key已存在巩掺，則直接bredk循環(huán)偏序。
判斷是否要擴(kuò)容
返回
總結(jié)
HashMap采用hash算法來決定Map中key的存儲，并通過hash算法來增加集合的大小胖替。hash表里可以存儲元素的位置稱為桶研儒，如果通過key計算hash值發(fā)生沖突時，那么將采用鏈表的形式独令，來存儲元素端朵。HashMap的擴(kuò)容操作是一項很耗時的任務(wù)，所以如果能估算Map的容量燃箭，最好給它一個默認(rèn)初始值冲呢，避免進(jìn)行多次擴(kuò)容。HashMap的線程是不安全的招狸，多線程環(huán)境中推薦是ConcurrentHashMap敬拓。
