1.資料結構
一般地，我們讨論的JDK版本為JDK1.7和JDK1.8。
（1）jdk1.7
數組+連結清單。
（2）jdk1.8
數組+連結清單+紅黑樹。
2.HashMap中的雜湊演算法
（1）什麼是哈希：
Hash，一般翻譯做散列、雜湊，或音譯為哈希，是把任意長度的輸入（又叫做預映射pre-image）通過雜湊演算法變換成固定長度的輸出，該輸出就是散列值。
（2）雜湊演算法：
簡單來說，通過哈希表（HASH-TABLE），對散列進行映射，根據鍵（Key）而直接通路在記憶體存儲位置。
（3）HashMap中的雜湊演算法：
在jdk1.8中，HashMap中主要是通過
index=hash&(n-1)
以此來确定元素在數組中的索引。（此處n為容器長度，且長度必須為2的n次幂，原因可以點選檢視這篇文章）
注:“無符号”右移位運算符（>>>），它使用了“零擴充”：無論正負，都在高位插入0。
3.HashMap中的哈希沖突
一般地，我們把不同的key映射到同一個hash值，叫做哈希碰撞，也就是哈希沖突。
HashMap中如何解決哈希沖突：
這裡我們僅讨論jdk1.8
首先通過鍊位址法（使用HASH-TABLE）來連結擁有相同hash值的資料，計算出
hashcode
,然後使得
hash=hashcode^hashcode>>>16
（這樣可以大大減少哈希沖突？請看==>HashMap的擾動函數），将
hash
與和
（數組長度n-1）
相與，轉化為公式
index=(n - 1) & hash
計算出索引值
index
，此時能夠過濾大部分哈希沖突，如果仍然存在哈希沖突則将新的元素插入對應數組索引處的連結清單尾部（尾插法）。
4.源碼分析
（1）put方法
我們來逐漸分析：
- 定義容器
tab[node]
-
初始化
當放入第一個元素時，會建立一個預設長度16的連結清單數組，并設定預設門檻值12。
1.第一次放入元素會進行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
2.進入resize()方法中,如果沒有指定容器長度，容器大小預設值為16
容器門檻值，達到門檻值會擴容，預設12
-
定位索引index
通過
index=(n - 1) & hash
index
index
tab[index]
if ((p = tab[i = (n - 1) & hash]) == null)
//tab[index]為空，則此時建立一個連結清單，并放入value值，key值，hash值。
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//該元素為已存在的key，此時進行替換key映射的value。
e = p;
//如果tab[index]為紅黑樹，進行紅黑樹相關的插入方法，
//此處較為複雜暫時不展開進行讨論。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果tab[index]為連結清單，則周遊此連結清單
for (int binCount = 0; ; ++binCount) {
//判斷p.next來确認是否到達連結清單尾部
if ((e = p.next) == null) {
//尾部插入新的資料節點
p.next = newNode(hash, key, value, null);
//當連結清單長度達到8後，轉換為紅黑樹
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))))
//找到後e不為空，該元素為已存在的key，此時進行替換key映射的value。
break;
//因為要循環周遊，是以需要不斷指派找到下一個節點
p = e;
}
}
//該元素為已存在的key，此時進行替換key映射的value。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
-
連結清單紅黑樹互相轉化條件
(1) 當連結清單長度大于等于8時，此時會将連結清單轉化為紅黑樹。
(2) 當紅黑樹長度小于等于6時，又轉化為連結清單結構
(3) 作為緩沖，當連結清單（紅黑樹）長度為7時保持目前資料結構不變
- 擴容
if (++size > threshold)
resize();
如果tab長度達到門檻值，将擴容，具體如何擴容還要繼續進行分類讨論。
如果能夠大緻确定tab的長度，則盡量初始化設定相近的長度，因為擴容很消耗性能。
==>詳細請看這篇文章【HashMap的擴容機制—resize()】