上篇我們介紹了JDK1.7版的HashMap，今天我們來講解下JDK1.8版的HashMap。
JDK1.7的實作大家看出有沒有需要優化的地方？
其實一個很明顯的地方就是：當 Hash 沖突嚴重時，在桶上形成的連結清單會變的越來越長，這樣在查詢時的效率就會越來越低；時間複雜度為 O(N)。
是以JDK1.8 中重點優化了這個查詢效率。
1、JDK1.8 HashMap 資料結構圖
我們會發現優化的部分就是把連結清單結構變成了紅黑樹。原來jdk1.7的優點是增删效率高，于是在jdk1.8的時候，不僅僅增删效率高，而且查找效率也提升了。
注意：不是說變成了紅黑樹效率就一定提高了，隻有在連結清單的長度不小于8，而且數組的長度不小于64的時候才會将連結清單轉化為紅黑樹。
問題一：什麼是紅黑樹呢？
紅黑樹是一個自平衡的二叉查找樹，也就是說紅黑樹的查找效率是非常的高，查找效率會從連結清單的o(n)降低為o(logn)。如果之前沒有了解過紅黑樹的話，也沒關系，你就記住紅黑樹的查找效率很高就OK了。
問題二：為什麼不一下子把整個連結清單變為紅黑樹呢？
這個問題的意思是這樣的，就是說我們為什麼非要等到連結清單的長度大于等于8的時候，才轉變成紅黑樹？在這裡可以從兩方面來解釋
（1）構造紅黑樹要比構造連結清單複雜，在連結清單的節點不多的時候，從整體的性能看來， 數組+連結清單+紅黑樹的結構可能不一定比數組+連結清單的結構性能高。就好比殺雞焉用牛刀的意思。
（2）HashMap頻繁的擴容，會造成底部紅黑樹不斷的進行拆分和重組，這是非常耗時的。是以，也就是連結清單長度比較長的時候轉變成紅黑樹才會顯著提高效率。
2、HashMap構造方法
構造方法一共有四個：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
這四個構造方法很明顯第四個最麻煩，我們就來分析一下第四個構造方法，其他三個自然而然也就明白了。上面出現了兩個新的名詞：loadFactor和initialCapacity。我們一個一個來分析：
（1）initialCapacity初始容量
官方要求我們要輸入一個2的N次幂的值，比如說2、4、8、16等等這些，但是我們忽然一個不小心，輸入了一個20怎麼辦？沒關系，虛拟機會根據你輸入的值，找一個離20最近的2的N次幂的值，比如說16離他最近，就取16為初始容量。
（2）loadFactor負載因子
負載因子，預設值是0.75。負載因子表示一個散清單的空間的使用程度，有這樣一個公式：initailCapacity*loadFactor=HashMap的容量。 是以負載因子越大則散清單的裝填程度越高，也就是能容納更多的元素，元素多了，連結清單大了，是以此時索引效率就會降低。反之，負載因子越小則連結清單中的資料量就越稀疏，此時會對空間造成爛費，但是此時索引效率高。
3、put方法
我們在存儲一個元素的時候，大多是使用下面的這種方式。
public class Test {
public static void main(String[] args) {
HashMap<String, Integer> map= new HashMap<>();
//存儲一個元素
map.put("張三", 20);
}
}
在這裡HashMap<String, Integer>，第一個參數是鍵，第二個參數是值，合起來叫做鍵值對。存儲的時候隻需要調用put方法即可。那底層的實作原理是怎麼樣的呢？這裡還是先給出一個流程圖：
上面這個流程，不知道你能否看到，紅色字迹的是三個判斷框，也是轉折點，我們使用文字來梳理一下這個流程：
（1）第一步：調用put方法傳入鍵值對
（2）第二步：使用hash算法計算hash值
（3）第三步：根據hash值确定存放的位置，判斷是否和其他鍵值對位置發生了沖突
（4）第四步：若沒有發生沖突，直接存放在數組中即可
（5）第五步：若發生了沖突，還要判斷此時的資料結構是什麼？
（6）第六步：若此時的資料結構是紅黑樹，那就直接插入紅黑樹中
（7）第七步：若此時的資料結構是連結清單，判斷插入之後是否大于等于8
（8）第八步：插入之後大于8了，就要先調整為紅黑樹，在插入
（9）第九步：插入之後不大于8，那麼就直接插入到連結清單尾部即可。
上面就是插入資料的整個流程，光看流程還不行，我們還需要深入到源碼中去看看底部是如何按照這個流程寫代碼的。
滑鼠聚焦在put方法上面，按一下F3，我們就能進入put的源碼。來看一下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
也就是說，put方法其實調用的是putVal方法。putVal方法有5個參數：
（1）第一個參數hash：調用了hash方法計算hash值
（2）第二個參數key：就是我們傳入的key值，也就是例子中的張三
（3）第三個參數value：就是我們傳入的value值，也就是例子中的20
（4）第四個參數onlyIfAbsent：也就是當鍵相同時，不修改已存在的值
（5）第五個參數evict ：如果為false，那麼數組就處于建立模式中，是以一般為true。
知道了這5個參數的含義，我們就進入到這個putVal方法中。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//第一部分
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;
//第三部分第一小節
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//第三小節第一段
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;
}
}
++modCount;
//第四部分
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
乍一看，這代碼完全沒有讀下去的欲望，第一次看的時候真實惡心到想吐，但是結合上一開始畫的流程圖再來分析，相信就會好很多。我們把代碼進行拆分（整體分了四大部分）：
（1）Node<K,V>[] tab中tab表示的就是數組。Node<K,V> p中p表示的就是目前插入的節點
（2）第一部分：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
這一部分表示的意思是如果數組是空的，那麼就通過resize方法來建立一個新的數組。在這裡resize方法先不說明，在下一小節擴容的時候會提到。
（3）第二部分：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
i表示在數組中插入的位置，計算的方式為(n - 1) & hash。在這裡需要判斷插入的位置是否是沖突的，如果不沖突就直接newNode，插入到數組中即可，這就和流程圖中第一個判斷框對應了。
如果插入的hash值沖突了，那就轉到第三部分，處理沖突
（4）第三部分：
else {
Node<K,V> e; K k;
//第三部分a
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//第三部分b
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//第三部分c
else {
for (int binCount = 0; ; ++binCount) {
//第三小節第一段
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//第三小節第一段
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//第三小節第三段
p = e;
}
}
//第三部分d
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
我們會看到，處理沖突還真是麻煩，好在我們對這一部分又進行了劃分
a）第三部分第一小節：
if (p.hash == hash
&&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
在這裡判斷table[i]中的元素是否與插入的key一樣，若相同那就直接使用插入的值p替換掉舊的值e。
b）第三部分第二小節：
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
判斷插入的資料結構是紅黑樹還是連結清單，在這裡表示如果是紅黑樹，那就直接putTreeVal到紅黑樹中。這就和流程圖裡面的第二個判斷框對應了。
c）第三部分第三小節：
//第三部分c
else {
for (int binCount = 0; ; ++binCount) {
//第三小節第一段
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//第三小節第一段
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//第三小節第三段
p = e;
}
}
如果資料結構是連結清單，首先要周遊table數組是否存在，如果不存在直接newNode(hash, key, value, null)。如果存在了直接使用新的value替換掉舊的。
注意一點：不存在并且在連結清單末尾插入元素的時候，會判斷binCount >= TREEIFY_THRESHOLD - 1。也就是判斷目前連結清單的長度是否大于門檻值8，如果大于那就會把目前連結清單轉變成紅黑樹，方法是treeifyBin。這也就和流程圖中第三個判斷框對應了。
（5）第四部分：
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
插入成功之後，還要判斷一下實際存在的鍵值對數量size是否大于門檻值threshold。如果大于那就開始擴容了。
4、resize方法
為什麼擴容呢？很明顯就是目前容量不夠，也就是put了太多的元素。為此我們還是先給出一個流程圖，再來進行分析。
這個擴容就比較簡單了，HaspMap擴容就是就是先計算 新的hash表容量和新的容量閥值，然後初始化一個新的hash表，将舊的鍵值對重新映射在新的hash表裡。如果在舊的hash表裡涉及到紅黑樹，那麼在映射到新的hash表中還涉及到紅黑樹的拆分。整個流程也符合我們正常擴容一個容量的過程，我們根據流程圖結合代碼來分析：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//第一部分：擴容
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//第二部分：設定門檻值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//第三部分：舊資料儲存在新數組裡面
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//隻有一個節點，通過索引位置直接映射
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是紅黑樹，需要進行樹拆分然後映射
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//如果是多個節點的連結清單，将原連結清單拆分為兩個連結清單
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//連結清單1存于原索引
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//連結清單2存于原索引加上原hash桶長度的偏移量
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
這代碼量同樣讓人惡心，不過我們還是分段來分析：
（1）第一部分：
//第一部分：擴容
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
根據代碼也能看明白：首先如果超過了數組的最大容量，那麼就直接将門檻值設定為整數最大值，然後如果沒有超過，那就擴容為原來的2倍，這裡要注意是oldThr << 1，移位操作來實作的。
（2）第二部分：
//第二部分：設定門檻值
else if (oldThr > 0) //門檻值已經初始化了，就直接使用
newCap = oldThr;
else { // 沒有初始化門檻值那就初始化一個預設的容量和門檻值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//為目前的容量門檻值指派
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
首先第一個else if表示如果門檻值已經初始化過了，那就直接使用舊的門檻值。然後第二個else表示如果沒有初始化，那就初始化一個新的數組容量和新的門檻值。
（3）第三部分
第三部分同樣也很複雜，就是把舊資料複制到新數組裡面。這裡面需要注意的有下面幾種情況：
A：擴容後，若hash值新增參與運算的位=0，那麼元素在擴容後的位置=原始位置
B：擴容後，若hash值新增參與運算的位!=0，那麼元素在擴容後的位置=原始位置+擴容後的舊位置。
這裡面有一個非常好的設計理念，擴容後長度為原hash表的2倍，于是把hash表分為兩半，分為低位和高位，如果能把原連結清單的鍵值對， 一半放在低位，一半放在高位，而且是通過e.hash & oldCap == 0來判斷，這個判斷有什麼優點呢？
舉個例子：n = 16，二進制為10000，第5位為1，e.hash & oldCap 是否等于0就取決于e.hash第5 位是0還是1，這就相當于有50%的機率放在新hash表低位，50%的機率放在新hash表高位。
5、hash方法
Java 8中的散列值優化函數：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
源碼中模運算就是把散列值和數組長度做一個"與"操作：
這也正好解釋了為什麼HashMap的數組長度要取2的整次幂，因為這樣（數組長度-1）正好相當于一個“低位掩碼”，“與”操作的結果就是散列值的高位全部歸零，隻保留低位值，用來做數組下标通路。
以初始長度16為例，16-1=15，2進制表示是00000000 00000000 00001111，和某散列值做“與”操作如下，結果就是截取了最低的四位值：
但這時候問題就來了：這樣就算我的散列值分布再松散，要是隻取最後幾位的話，碰撞也會很嚴重，這時候“擾動函數”的價值就展現出來了：
右位移16位，正好是32位一半，自己的高半區和低半區做異或，就是為了混合原始hashCode的高位和低位，以此來加大低位的随機性，而且混合後的低位摻雜了高位的部分特征，這樣高位的資訊也被變相保留下來，即降低了哈希沖突的風險又不會帶來太大的性能問題。這個設計很巧妙！
6、hash沖突
通過異或運算能夠是的計算出來的hash比較均勻，不容易出現沖突。但是偏偏出現了沖突現象，這時候該如何去解決呢？
在資料結構中，我們處理hash沖突常使用的方法有：開發定址法、再哈希法、鍊位址法、建立公共溢出區。而hashMap中處理hash沖突的方法就是鍊位址法。
這種方法的基本思想是将所有哈希位址為i的元素構成一個稱為同義詞鍊的單連結清單，并将單連結清單的頭指針存在哈希表的第i個單元中，因而查找、插入和删除主要在同義詞鍊中進行。鍊位址法适用于經常進行插入和删除的情況。
7、table數組用transient修飾
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
從HashMap 的源碼，會發現桶數組 table 被申明為 transient。transient 表示易變的意思，在 Java 中，被該關鍵字修飾的變量不會被預設的序列化機制序列化。我們再回到源碼中，考慮一個問題：桶數組 table 是 HashMap 底層重要的資料結構，不序列化的話，别人還怎麼還原呢？
這裡簡單說明一下吧，HashMap 并沒有使用預設的序列化機制，而是通過實作readObject/writeObject兩個方法自定義了序列化的内容。這樣做是有原因的，試問一句，HashMap 中存儲的内容是什麼？不用說，大家也知道是鍵值對。是以隻要我們把鍵值對序列化了，我們就可以根據鍵值對資料重建 HashMap。有的朋友可能會想，序列化 table 不是可以一步到位，後面直接還原不就行了嗎？這樣一想，倒也是合理。但序列化 talbe 存在着兩個問題：
1）table 多數情況下是無法被存滿的，序列化未使用的部分，浪費空間。
2）同一個鍵值對在不同 JVM 下，所處的桶位置可能是不同的，在不同的 JVM 下反序列化 table 可能會發生錯誤。
以上兩個問題中，第一個問題比較好了解，第二個問題解釋一下。HashMap 的get/put/remove等方法第一步就是根據 hash 找到鍵所在的桶位置，但如果鍵沒有覆寫 hashCode 方法，計算 hash 時最終調用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的，不同的 JVM 下，可能會有不同的實作，産生的 hash 可能也是不一樣的。也就是說同一個鍵在不同平台下可能會産生不同的 hash，此時再對在同一個 table 繼續操作，就會出現問題。
綜上所述，大家應該能明白 HashMap 不序列化 table 的原因了，下面是HashMap自定義的序列化代碼：
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
// 寫入一些屬性值，待反序列化時用到
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);
internalWriteEntries(s);
}
// Called only from writeObject, to ensure compatible ordering.
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
//寫入鍵值對
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
reinitialize();
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
s.readInt(); // Read and ignore number of buckets
int mappings = s.readInt(); // Read number of mappings (size)
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
else if (mappings > 0) { // (if zero, use defaults)
// Size the table using given load factor only if within
// range of 0.25...4.0
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
float fc = (float)mappings / lf + 1.0f;
int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
DEFAULT_INITIAL_CAPACITY :
(fc >= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
table = tab;
// Read the keys and values, and put the mappings in the HashMap
// 讀出鍵值對，放入hashMap
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}
8、HashMap非線程安全
HashMap源碼裡面方法是沒有synchronized或lock處理的，無法保證線程安全。于是出現了線程安全的ConcurrentHashMap，這個我們後續講解。
歡迎小夥伴們留言交流~~
浏覽更多文章可關注微信公衆号：diggkr