參考：https://www.cnblogs.com/yeya/p/13247070.html
HashMap底層資料結構：數組+單連結清單+紅黑樹
HashMap底層資料結構設計的非常巧妙，充分利用了數組随機查詢快連結清單增删快的特點，大大提高了效率，而在JDK1.8引入紅黑樹的目的是為了解決當發生Hash沖突時元素查找效率随着連結清單長度的增加而降低的問題，這就是所謂的樹化，要想利用紅黑樹的查找優勢就需要付出代價，這個代價就是紅黑樹為了維持平衡需要的左旋右旋以及變色操作，這些操作同樣耗時，而連結清單為了查找元素周遊整個連結清單的操作也耗時，當連結清單中的元素個數少時，插入删除成本高，不宜用紅黑樹，應該用連結清單；當連結清單中的元素個數多時，查詢成本高，不宜用連結清單，應該用紅黑樹，是以我們需要結合自身需求平衡好兩種操作的耗時以此來提高效率，這個平衡點就是我們人為需要設定的。平衡點一：當連結清單長度大于等于8且底層數組長度大于等于64時才能進行樹化操作；平衡點二：當紅黑樹中的節點數小于等于6時進行紅黑樹轉為連結清單的退化操作
核心的成員變量
以下所帶預設的字樣的意思是如果在初始化的時候沒有指定該變量的值，那麼就按官方給定的值來
-
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
-
static final float DEFAULT_LOAD_FACTOR = 0.75f;
-
transient Set<Map.Entry<K,V>> entrySet;
-
static final int MIN_TREEIFY_CAPACITY = 64;
-
transient Node<K,V>[] table;
-
int threshold;
-
static final int TREEIFY_THRESHOLD = 8;
-
static final int UNTREEIFY_THRESHOLD = 6;
初始化
無參初始化
帶參初始化
下面的tableSizeFor(int cap)方法是為了得到一個與輸入參數接近的2次幂整數，比如輸入9，得到就是16，hashMap用的是懶初始化的方式，也就是說容量初始化是第一次添加元素進行的，檢視resize方法可以知道，這時的數組容量就是上面tableSizeFor方法的傳回值，這就有個問題了：為什麼要保證數組初始化容量是2的次幂？
答：索引的計算方式是
(n - 1) & hash
，也就是數組長度減一與上hash值，那麼2次幂整數減一之後二進制數低位都是1高位都是0，和hash進行與之後就能保證最後的索引值一定在[0,n-1]之内，是以tableSizeFor方法的作用就是為了保證計算出來的索引不越界
添加元素流程 put
下面的hash函數是為了讓高16位也參與下标索引的運算，目的是降低hash沖突的機率，見如下分析：
(n - 1) & hash
這個就是節點對應的下标值，如果兩個節點值下标相同也就發生了哈希碰撞了，我們現在讨論數組長度非常小且沒有使用hash()方法的情況（即簡單的用hashCode()的結果值作為hash，也就是hash=key.hashCode()），如果數組長度非常小，也就是n很小，那麼也就是說n在二進制中的高位大部分為0，或者說都是0，這時如果與hash進行&操作的話，hash的高16位就沒有參與運算了,最後的索引值其實隻用到了hash的低16位，這樣做計算出來的索引值顯然是沒有用hash的全位計算出的索引值豐富的，根據以上分析可知，這個hash()方法的目的是在數組長度很小的情況下，盡量使索引值更加散列（散布均勻），也就降低了hash沖突的機率
/**
* @param hash 鍵key的hash值
* @param key 要存儲的鍵
* @param value 要存儲的值
* @param onlyIfAbsent 這個值決定了是否替換已經存在的值 false是替換（預設） true不替換
* @param evict 是否在建立模式，預設為true表示不在建立模式
* @return previous value 如果插入的鍵在容器中存在就傳回舊的值 否則傳回null
*/
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;
//前面通過Key計算的Hash值并不就是存入數組中的實際位置 實際位置為(n - 1) & hash
//如果該位置上沒有節點 那麼就直接插入
if ((p = tab[i = (n - 1) & hash]) == null) //p被指派為數組中的元素 也就是一個連結清單的首節點
tab[i] = newNode(hash, key, value, null); //從最後一個參數為null就可以看出 這是尾插法
else {//之後的操作就是将目前位置節點的key與要插入的節點的key進行比較
// 如果該位置上有節點
Node<K,V> e;//從後面可以看出 這個e節點儲存的是已經存在的key 的鍵值對
K k; //儲存了目前位置節點的鍵
// 标注A：插入的節點的key與首節點的key相同 就将e指派 此時e不為null 而且e的key與插入的key相同
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果目前節點是樹節點的話 也就是說這時的連結清單已經轉為了紅黑樹 那麼就按紅黑樹的方式插入節點
else if (p instanceof TreeNode)
//标注B：此時的e不為null 而且e的key與插入的key相同
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//要插入的節點既不存在也不是紅黑樹類型的 那麼就是簡單的連結清單插入了
for (int binCount = 0; ; ++binCount) {//這個循環是為了找到連結清單中的最後一個節點
if ((e = p.next) == null) { //如果目前位置節點p是連結清單的最後一個節點 就直接插入到p的後面即可
p.next = newNode(hash, key, value, null);
//如果目前連結清單的長度超過了8（能否進行樹化條件之一） 這裡将門檻值-1 是因為binCount是從0開始的
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//将連結清單進行樹化 從treeifyBin這個方法中可以知道樹化的的條件之一是底層數組的長度大于MIN_TREEIFY_CAPACITY=64
treeifyBin(tab, hash);
break; //這時節點已經插入完畢 退出循環即可 标注C：注意這時的e是null
}
//如果插入的值已經存在就直接退出循環
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; //标注D：注意這時的e非null 而且e的key與插入的key相同
p = e;//節點後移 判斷下一個節點 p.next.next
}
}
//注意檢視上述注釋中的标注ABCD 就可以知道當插入的鍵值對中的鍵已經在容器中存在時 那麼e就是容器中鍵與插入鍵相同的鍵值對
//如果e 不為null 表示在該容器已經存在了要插入的鍵 而鍵不能重複 是以值就隻能被覆寫
//這裡就是在HashMap前後插入相同的鍵值對時 後插入的鍵值對的值會覆寫掉前面鍵值對值 并傳回舊的值的緣由
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; //傳回null表示插入的鍵值對在目前容器中不存在
}
經過上述源碼分析，HashMap添加元素的大概步驟：
- 檢查底層數組是否為空，如果為空就需要初始化
- 根據輸入的key結合目前數組的長度計算出該鍵值對在數組中的位置
(n - 1) & hash
- 判斷該位置上有沒有元素，如果沒有元素就直接插入鍵值對，此時程式跳到第8 步，否則下一步
- 判斷該位置的key與傳入的key是否相同 如果相同則進行7 步，否則下一步
- 判斷該節點是否是紅黑樹節點類型，如果是則用紅黑樹的方式插入資料并進行第7步，否則下一步
- 周遊連結清單尋找最後一個節點并在此節點後面插入鍵值對，周遊的過程中還需要判斷此時連結清單是否可以進行樹化
- 判斷在該容器是否存在相同的key，相同則覆寫value值并結束方法傳回舊值，否則下一步
- 操作數加一并判斷是否進行擴容，最後傳回null
擷取元素流程 get
/**
* @param hash 鍵的hash值
* @param key 鍵key
* @return 傳回值value
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e; //first儲存了目前hash值所對應的鍵值對 也就是首節點
int n; //底層數組的長度
K k;
//如果 目前數組存在且目前hash值所表示的數組下标存在
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//如果首節點的key等于要查詢的key 那麼這個首節點就是要查詢的節點 傳回即可
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
//當首節點的下一個節點不為空 就通過周遊查找
if ((e = first.next) != null) {
if (first instanceof TreeNode) //如果這個首節點是樹節點類型 表示連結清單已經變為了紅黑樹 那麼就按紅黑樹的方式去查找節點
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//否則就是簡單的周遊連結清單查找節點并傳回
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
//沒有找到就傳回null
return null;
}
大緻思路：在底層數組不為空且有資料的情況下根據傳入hash值确定位置，判斷該位置是否為空，為空立即傳回null，方法結束，否則判斷其key是否與傳入的key相等，相等就傳回此節點，否則判斷該節點是數節點還是連結清單節點，如果是樹節點的話就按照紅黑樹的查找方式查找，否則就周遊連結清單查找，并傳回結果
擴容或者初始化resize
擴容的流程：
整個擴容分為兩個部分：1、确定新容量和新門檻值；2、将舊數組中的所有元素包括連結清單複制到新數組中
第一部分：
主要根據舊數組容量來判斷：
- 正常擴容的情況（不是第一次添加元素的情況）：如果舊容量大于0且不超過最大值的情況下，就将舊容量擴容2倍大小（即新容量=舊容量*2），且在舊容量大于等于16的情況下将舊門檻值擴容2倍（即新門檻值=舊門檻值*2）
- 用有參構造初始化第一次添加元素的情況：如果舊容量等于0并且舊門檻值大于0，就将舊門檻值指派給新容量（即新容量=舊門檻值），
- 用無參構造初始化第一次添加元素的情況：如果舊容量等于0并且舊門檻值也等于0，也就是用無參構造初始化HashMap的情況下，這時的舊容量值被指派為預設數組長度16（即新容量=16），舊門檻值被指派為預設數組長度16*預設加載因子0.75為12（即新門檻值=12）
上述三個判斷結束後，一定能夠确定新容量的值，但是可能确定不了新門檻值的值，也就是新門檻值可能還是0，這個時候對新門檻值的處理是，新門檻值=新容量*加載因子
第二部分：
在經過第一部分後，新容量和新門檻值也就确定了，後續的操作就是數組元素複制了，周遊舊數組将其中的内容指派到新數組中，
在周遊指派的過程中，有如下判斷：
- 如果目前位置沒有連結清單，也就是沒有産生哈希沖突，就直接将該元素指派給新數組中對應的位置即可，這個新位置是
e.hash & (newCap - 1)
- 如果目前位置的節點為樹節點，就執行split方法通過對紅黑樹進行分割将舊數組轉移到新數組，注意該方法中的
untreeify
- 如果該位置上有連結清單 則将連結清單分為高位連結清單為低位連結清單，低位連結清單還是存放在原來的位置 ，高位連結清單存放的位置是在原數組位置的基礎上加上舊容量的位置
final Node<K,V>[] resize() {
//将原始數組指派到臨時數組oldTab
Node<K,V>[] oldTab = table;
//舊數組的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//決定是否進行擴容的門檻值 這個門檻值在初始化容量時已經确定了 this.threshold = tableSizeFor(initialCapacity);
int oldThr = threshold;
int newCap, newThr = 0;
//如果舊容量大于0
if (oldCap > 0) {
//如果舊容量 超過了最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
//門檻值就是Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
//傳回舊數組 因為數組的長度已經到達最大值了 不能再擴容了
return oldTab;
}
//新容量=舊容量<<1 即新容量是舊容量的2倍
//這裡還判斷了舊容量的值是否大于等于預設容量16 是因為有可能初始化HashMap的時候傳入的容量小于16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//新門檻值等于舊門檻值的兩倍
newThr = oldThr << 1; // double threshold
}
//在舊容量等于0時 如果舊門檻值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
//新容量容量設定為舊門檻值
newCap = oldThr;
//在舊容量等于0時 如果舊門檻值也等于0
//也就是用無參構造初始化HashMap的情況下 是以可以知道 在用無參構造初始化時 并不是立即建立長度為16的數組，而是要等到在加入第一個元素時執行這個resize方法才會建立
else {
//新容量為預設容量
newCap = DEFAULT_INITIAL_CAPACITY;
//新門檻值為預設容量*預設加載因子
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新門檻值等于0 那麼新門檻值就被重新指派為新容量*加載因子
//如果新容量大于最大容量 或者新門檻值超過了最大容量 那麼新門檻值就被重新指派為Integer.MAX_VALUE
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];//這裡就初始化了數組 這就是為什麼resize方法同時具備了初始化和擴容兩份功能的原因
//新舊數組更替
table = newTab; //這時候的table還是空的 沒有資料 隻有容量大小
//下面就是将舊數組中的資料複制到新數組中
if (oldTab != null) {
//周遊舊數組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//如果目前位置不為空
if ((e = oldTab[j]) != null) {
//将目前位置指派為null 目的是為了友善垃圾回收器及時回收 節約記憶體空間
oldTab[j] = null;
//如果目前位置沒有連結清單 沒有發生Hash沖突
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 { // preserve order
//低位連結清單：存放在擴容之後的數組的下标位置，與目前數組的下标位置一緻
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);
if (loTail != null) {
loTail.next = null;
//新節點位置是原來數組中下标位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//新節點位置是原來數組中下标位置+舊容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
擴容的時機
時機一：在put方法中判斷目前容器中的元素數量是否大于門檻值，如果大于門檻值就會進行擴容
時機二：在put方法中，發生了哈希碰撞，往連結清單中添加元素的時候，當連結清單的長度大于等于8的時候，會進入treeifyBin方法，該方法中會進一步判斷樹化條件之一 （數組長度是否大于等于64），如果數組長度小于64，則會進行擴容，在此處會有擴容的原因是：如果元素數組長度小于這個值，沒有必要去進行結構轉換，當一個數組位置上集中了多個鍵值對，那是因為這些key的hash值和數組長度取模之後結果相同。（并不是因為這些key的hash值相同) 因為hash值相同的機率不高，是以可以通過擴容的方式，來使得最終這些key的hash值在和新的數組長度取模之後，拆分到多個數組位置上
連結清單轉紅黑樹的時機
在添加資料的時候判斷連結清單的長度是否超過了8，如果是則調用treeifyBin方法，該方法裡面會進一步判斷底層數組的長度是否超過了64，當這兩個條件都滿足時就周遊連結清單将每一個元素通過replacementTreeNode方法轉為樹節點，這就是樹化操作了，樹化的具體場所在treeifyBin方法中
為什麼會在putVal方法中進行連結清單轉紅黑樹判斷呢？
因為在添加元素的時候可能會産生哈希沖突，也就可能會導緻連結清單長度增加，當連結清單長度大于8的時候就需要用紅黑樹來解決查詢效率低的問題了
紅黑樹轉連結清單的時機
在添加資料的時候有時候會需要擴容resize方法，該方法中會判斷要複制到新數組的節點的類型是否為樹類型，如果是則會執行split方法進行節點分割拆分，在split方法中判斷目前節點數是否小于等于6，如果是則就執行untreeify方法進行退化（紅黑樹轉連結清單），其中的操作與連結清單轉為紅黑樹類似，周遊紅黑樹将每個節點通過replacementNode方法轉為連結清單節點，這個untreeify方法就是退化的具體執行場所
為什麼會在resize()方法中進行紅黑樹轉連結清單的判斷呢？
因為擴容的目的是為了降低哈希沖突，随着擴容的進行，原數組上因為哈希沖突導緻的連結清單長度會慢慢減小，如果長度小于等于了6的話，就需要轉連結清單了
兩種狀态變化的時機都是從put方法開始，也就是都在增加元素時才會觸發狀态的改變，隻是具體的執行方法不一樣
為什麼門檻值預設為8？
根據泊松分布，在負載因子0.75（HashMap預設）的情況下，單個hash槽内元素個數為8的機率小于百萬分之一，8個元素的hash值相同這種情況是非常少的，也就是連結清單轉為紅黑樹的機率就很低，因為連結清單轉紅黑樹是耗費性能的，說到底雖然連結清單轉紅黑樹是為了提高查詢效率，在節點數多時是一個不錯的解決方案，但是因為紅黑樹本身的複雜結構（相對于連結清單來說），轉化的過程和維護平衡就很耗費時間，是以為了盡量避免連結清單轉紅黑樹的發生就這樣設計了
為什麼加載因子為0.75？
HashMap中的threshold是HashMap所能容納鍵值對的最大值。計算公式為length*LoadFactory。也就是說，在數組定義好長度之後，負載因子越大，所能容納的鍵值對個數也越大，loadFactory越趨近于1，那麼數組中存放的資料（entry也就越來越多），資料也就越密集，也就會有更多的連結清單長度處于更長的數值，我們的查詢效率就會越低，當我們添加資料，産生hash沖突的機率也會更高。loadFactory越小，越趨近于0，數組中個存放的資料(entry)也就越少，表現得更加稀疏
0.75是對空間和時間效率的一種平衡選擇，如果負載因子小一些比如是0.4，那麼初始長度16*0.4=6，數組占滿6個空間就進行擴容，很多空間可能元素很少甚至沒有元素，會造成大量的空間被浪費，如果負載因子大一些比如是0.9，這樣會導緻擴容之前查找元素的效率非常低，loadfactory設定為0.75是經過多重計算檢驗得到的可靠值，可以最大程度的減少rehash的次數，避免過多的性能消耗
為什麼底層數組長度要大于64是樹化的條件之一
和上面的門檻值為8的設計原因一樣，都是為了盡可能的避免紅黑樹的産生，能夠通過擴容桶量就不願意放在樹上
為什麼當紅黑樹的節點小于等于6時退化
主要是一個過渡，避免連結清單和紅黑樹之間頻繁的轉換。如果門檻值是7的話，删除一個元素紅黑樹就必須退化為連結清單，增加一個元素就必須樹化，來回不斷的轉換結構無疑會降低性能，是以門檻值才不設定的那麼臨界。
為什麼要轉成紅黑樹而不是其他的樹
首先發生結構轉變的原因是連結清單的元素太多導緻其查詢效率降低（效率降低的原因：需要從頭到尾周遊元素），這時要轉為的結構需要解決上述問題，那麼可以定位在樹這個結構上，其中在查詢方面占優勢的有兩種樹結構：紅黑樹和二叉查找樹，二叉查找樹在特殊情況下會變成一條單連結清單（特殊情況：後來的元素都比第一個元素大或者小），是以它不适用，而紅黑樹雖然為了維護現有的平衡需要左旋或者右旋，但是相比周遊一整條連結清單，這種性能上的消耗還是在承受範圍内的，是以最後的選擇是紅黑樹
Put方法的傳回值
調用put方法時，如果已經存在一個相同的key， 則傳回的是前一個key對應的value，同時該key的新value覆寫舊value，如果是新的一個key，則傳回的是null；
HashMap與HashTable的差別
首先，Hashmap和hashtable他們的父類不一樣，一個是abstractmap，一個是dictionary，因為在hashtable中所有的方法都加了内置鎖synchronized，是以說在hashtable中所有的方法都是同步方法，是以HashTable是線程安全的，但hashmap是線程不安全的，在hashtable中，我們計算哈希值的方法是不一樣的，hashtable計算哈希值比較簡單，它直接調用hashCode()方法，但hashmap中就是通過取哈希值并通過高位向右移并與自身進行異或運算得到的一個哈希值。此外，他們在擴容時擴容的量不一樣，hashmap擴容是為原來兩倍，但hashtable擴容為原來的2n+1；hashtable在源碼中是在構造方法裡進行數組的初始化，它的初始化容量為11，在hashmap裡面，他是第一次調用put方法的時候會初始化數組，也就是懶加載，且它的初始化容量是16，而且要求hashmap的容量必須是2的次幂以保證它的計算下标效率，在hashmap裡面計算下标是通過容量-1 與 上我們的哈希值 （
(n - 1) & hash
），但在hashtable中是直接将hashCode與數組長度進行取餘計算下标值（
(hash & 0x7FFFFFFF) % tab.length
），HashMap和Hashtable 對于Hash沖突的解決方案都是鍊位址法，連結清單是單向連結清單。HashTable中key和value都不能為null，否則抛出空指針異常，HashMap是支援null鍵和null值的
HashMap1.7與1.8的差別
- 底層資料結構不一樣，JDK1.7的HashMap的底層結構是數組+連結清單，JDK1.8的HashMap的底層結構是數組+單連結清單+紅黑樹，引入紅黑樹的目的是為了解決在Hash碰撞比較激烈的情況下，連結清單長度過長導緻查詢效率降低的問題
- 節點結構不一樣：JDK1.7中節點是Entry對象，該對象中的hash值是可變的，因為涉及到rehash方法，JDK1.8中節點是Node對象（Entry與Node都實作了Map.Entry<K,V>接口，是以這裡不是差別），差別在于Node對象中的hash是被final修飾的，是常量不可變。還有一個差別在于JDK1.8中因為引入了紅黑樹，是以它也引入了新節點TreeNode
- Hash算法不一樣：JDK1.8中計算出來的結果隻可能是一個，是以hash值設定為final修飾。1.7會先判斷這Object是否是String，如果是，因為String存在字元串常量池的問題，可能會導緻這個鍵的hash值唯一，是以為了盡量避免Hash碰撞，就不采用String複寫的hashcode方法。
- 擴容時，連結清單節點插入方式不一樣：JDK1.7中的 HashMap 在擴容時和添加時都是使用頭插法插入元素，在多線程的環境下，擴容的時候有可能導緻環形連結清單的出現，形成死循環。是以，JDK1.8使用尾插法插入元素，在擴容時會保持連結清單元素原本的順序，不會出現環形連結清單的問題
- 擴容和插入的相對順序不一樣：在JDK1.7的時候是先擴容後插入的，這樣就會導緻無論這一次插入是否發生hash沖突都需要進行擴容，如果這次插入的并沒有發生Hash沖突的話，那麼就會造成一次無效擴容，但是在1.8的時候是先插入再擴容的，這樣做的好處就是減少了這一次無效的擴容，原因就是如果這次插入沒有發生Hash沖突的話，那麼其實就不會造成擴容，但是在1.7的時候就會急造成擴容