如果 HashMap 的 table 長度為 M荒叶，全部存儲的鍵值對數(shù)量為 N瘦穆，如果哈希函數(shù)滿足均勻性的要求闪湾，那么每條鏈表的長度大約為 N/M早处，因此平均查找次數(shù)的復雜度為 O(N/M)。
為了讓提高查找效率椒丧，需要降低每條鏈表的長度壹甥，也就是說 table 要盡可能大。HashMap 采用動態(tài)擴容來根據(jù)當前的 N 值來調(diào)整 M 值壶熏，使得空間效率和時間效率都能得到保證句柠。
關于JAVA7中的擴容機制不了解的 大家可以先參考這篇文章# 博客園java容器03--HashMap源碼分析
JAVA7擴容后的rehash過程使用了單鏈表的頭插法方式，同一位置上新元素總會被放在鏈表的頭部位置棒假；這樣如果發(fā)生了hash沖突的話先放在一個索引上的元素終會被放到Entry鏈的尾部溯职，這一點和JAVA8有區(qū)別。
JAVA8在rehash算法利用了下面的一個特性：
HashMap的擴容使用的是2次冪的擴展(指長度擴為原來2倍)帽哑，所以谜酒，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置妻枕。什么意思呢僻族？ 我們舉個例子說明。
假設原數(shù)組長度 capacity 為 16屡谐，擴容之后 new capacity 為 32：
old capacity : 00010000
new capacity : 00100000
根據(jù)HashMap如何計算Entry在桶中的下標述么？一文中，
下標的計算方法愕掏，對于一個 Key度秘，如原Hash值 key1 = 0001 1001 key2 = 0000 1001
擴容前 hash & (length - 1) :
key1 : 0001 1001 & 0000 1111 -> 0000 1001
key2 : 0000 1001 & 0000 1111 -> 0000 1001
擴容后 hash & (length - 1) :
key1 : 0001 1001 & 0001 1111 -> 0001 1001
key2 : 0000 1001 & 0001 1111 -> 0000 1001
因此，我們在擴充HashMap的時候饵撑，不需要像JDK1.7的實現(xiàn)那樣重新計算hash剑梳，
**只需要看原來的hash值在擴容后新增的那一位是1還是0唆貌，如果是0的話索引沒變，是1的話索引變成“原索引+oldCap” 阻荒。
在JAVA8代碼中挠锥，抽象為一行if判斷代碼 ：
if ((e.hash & oldCap) == 0）
即如果位與原來的capacity結(jié)果為0 則代表hash值新增的高位為0。
這種算法既省去了重新計算hash值的時間侨赡，而且新增的1位是0還是1機會是隨機的蓖租，因此resize的過程，均勻的把之前的沖突的節(jié)點分散到新的bucket了羊壹。
這就是JAVA8新增的優(yōu)化點：
在JAVA7中rehash舊鏈表遷移新鏈表的時候蓖宦，如果在新表的數(shù)組索引位置相同，則鏈表元素會倒置油猫，但是從上圖可以看出稠茂，而在JAVA8中不會倒置。
參考：
http://www.importnew.com/20386.html
https://www.cnblogs.com/csslcww/p/9611568.html
