HashMap
- 哈希表
- 哈希函式
- 沖突解決
- 位運算子
- HashMap簡介
- 繼承關系
- 成員變數
- DEFAULT_INITIAL_CAPACITY(默認集合初始容量)
- DEFAULT_LOAD_FACTOR
- TREEIFY_THRESHOLD
- table
- threshold
- 添加元素
- 流程
- 原始碼
- treeifyBin方法
- 擴容機制
- 流程
- 原始碼
- 并發問題
默認JDK8，如果有錯誤，麻煩在評論區告訴我一下😁
哈希表
哈希表（Hash table，也叫散串列），能夠根據鍵(key)直接訪問相應的值(value)，查找演算法分為兩步:
- 用哈希函式將被查找的key轉化為陣列的一個索引，理想情況下，不同的key都會轉化為不同的索引值，但現實情況也會存在不同的key有相同的索引值，這就叫碰撞沖突，可以通過拉鏈法或線性探測法解決沖突(后面會講)，
- 通過生成的索引值直接訪問資料，
哈希表是演算法在時間和空間上做出權衡的經典案例，如果沒有記憶體限制，那么我們可以直接將key作為陣列的索引，那么所有的查找操作只需要訪問記憶體一次；如果沒有時間限制，我們可以用無序陣列并進行順序查找，這樣只需要很少的記憶體，但花費的時間太長了，而哈希表則使用了適度的空間和時間并在這兩種極端中找到一個平衡，
哈希函式
假設有一個能夠保存M個鍵值對的陣列，那么我們就需要一個能夠將任意key轉化為該陣列范圍內的索引([0,M-1]范圍內的整數)的哈希函式，這個哈希函式最好還要滿足下面的要求:
- 容易計算并且速度快，
- 計算出來的索引值最好能夠均勻分布所有的鍵，避免產生太多的沖突，
由于key的型別可能是數字，字串，所以我們需要設計不同的哈希函式來對應不同的鍵，Java中為許多常用的資料型別重寫了hashCode()方法，在文章Object中的hashCode()終于搞懂了！！！有詳細的介紹，
沖突解決
當出現兩個或多個key的哈希值相同的情況，可以通過拉鏈法或線性探測法來解決，這篇文章著重講解一下拉鏈法，因為HashMap的底層實作就是基于拉鏈法，
大致思路如下:將大小為M的陣列中的每個元素指向一個鏈表，鏈表中的每個結點都存盤了哈希值為該元素的索引的鍵值對，當要查找某個元素時，首先根據哈希值找到對應的鏈表，然后沿著鏈表順序查找相應的key，并回傳value，
位運算子
在介紹HashMap之前補充一些位運算子的知識
<<：左移，空位補0，被移除的高位丟棄，空缺位補0，>>: 右移，被移位的二進制最高位是0，右移后，空缺位補0；最高位是1，空缺位補1，>>>: 無符號右移，被移位二進制最高位無論是0或者是1，空缺位都用0補，&: 與運算，二進制位進行&運算，只有1&1時結果是1，否則是0;|：或運算，二進制位進行 | 運算，只有0 | 0時結果是0，否則是1;^:異或運算，相同二進制位進行 ^ 運算，結果是0；1^1=0,0^0=0；不相同二進制位 ^ 運算結果是1，1^0=1,0^1=1~:取反運算，正數取反，各二進制碼按補碼各位取反負數取反，各二進制碼按補碼各位取反
HashMap簡介
? HashMap基于哈希表的Map介面實作，是以key-value存盤形式存在，即主要用來存放鍵值對，HashMap 的實作不是同步的，這意味著它不是執行緒安全的，它的key、value都可以為null，此外，HashMap中的映射不是有序的，
? JDK1.8 之前 HashMap 由 陣列+鏈表 組成的，陣列是 HashMap 的主體，鏈表則是主要為了解決哈希沖突 (兩個物件呼叫的hashCode方法計算的哈希碼值一致導致計算的陣列索引值相同) 而存在的（“拉鏈法”解決沖突），
JDK1.8 以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（或者紅黑樹的邊界值，默認為 8）并且當前陣列的長度大于64時，此時此索引位置上的所有資料改為使用紅黑樹存盤，
補充：將鏈表轉換成紅黑樹前會判斷，即使閾值大于8，但是陣列長度小于64，此時并不會將鏈表變為紅黑樹，而是選擇進行陣列擴容，
這樣做的目的是因為陣列比較小，盡量避開紅黑樹結構，這種情況下變為紅黑樹結構，反而會降低效率，因為紅黑樹需要進行左旋，右旋，變色這些操作來保持平衡 ，同時陣列長度小于64時，搜索時間相對要快些，所以綜上所述為了提高性能和減少搜索時間，底層在閾值大于8并且陣列長度大于64時，鏈表才轉換為紅黑樹，具體可以參考treeifyBin方法，
雖然增了紅黑樹作為底層資料結構，結構變得復雜了，但是閾值大于8并且陣列長度大于64時，鏈表轉換為紅黑樹時，效率也變的更高效，
繼承關系
HashMap類實作了一個Map介面，該介面定義了一組鍵值對映射通用的操作,同時還繼承了AbstractMap抽象類，該抽象類繼承Map介面，但是HashMap類通過繼承AbstractMap抽象類也實作了Map介面，是不是多此一舉呀?
據 Java集合框架的創始人Josh Bloch描述，這樣的寫法是一個失誤，在java集合框架中，類似這樣的寫法很多，最開始寫java集合框架的時候，他認為這樣寫，在某些地方可能是有價值的，直到他意識到錯了，顯然的，JDK的維護者，后來不認為這個小小的失誤值得去修改，所以就這樣存在下來了， StackOverFlow問題鏈接
HashMap還實作了Cloneable介面和Serializable介面，分別用來進行物件克隆和物件序列化，
成員變數
下面介紹幾個重要的變數
DEFAULT_INITIAL_CAPACITY(默認集合初始容量)
//默認初始容量是16(必須是2的n次冪)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
可以發現初始容量必須是2的n次冪，具體原因下面分析一下:根據哈希表的原理，我們可以知道當向HashMap中添加一個元素時，需要根據key的哈希值去確定其在陣列中的具體位置，HashMap為了存取高效，要盡量減少沖突碰撞，也就是要盡量把資料分配均勻，每個鏈表長度大致相同，
key的哈希值可能是一個很大的整數，超過散串列的范圍，因此需要把它縮小到適合索引的范圍，假設假設哈希表的索引處于0到n-1之間，將一個整數縮小到0和n-1之間的最常用的做法是使用hash%n,其中n為大于2的素數，比如Hashtable初始化桶大小為11，就是桶大小設計為素數的應用（Hashtable擴容后不能保證還是素數），理想情況下應該為n選擇一個素數，但是選擇一個大的素數將很耗時，而在HashMap中使用的方法很巧妙，它通過hash&(length-1)來計算，當length長度為2的n次冪時，hash&(length-1)的運算結果總是等價于hash%length，&的運算效率也比%更高，
在創建HashMap物件的時候，可以傳入initialCapacity，如果輸入的大小不是2的n次冪，那么底層會通過位移運算和或運算得到一個離你傳入的數字最近的一個2的冪次數，
原始碼如下:
//創建HashMap集合的物件，指定陣列長度是10，不是2的冪
HashMap hashMap = new HashMap(10);
-----------------------------------------------
/*
指定“容量大小”和“加載因子”的建構式
initialCapacity: 指定的容量
loadFactor:指定的加載因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//判斷初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
//如果小于0，則拋出非法的引數例外IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//判斷初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次冪
if (initialCapacity > MAXIMUM_CAPACITY)
//如果超過MAXIMUM_CAPACITY，會將MAXIMUM_CAPACITY賦值給initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
//判斷負載因子loadFactor是否小于等于0或者是否是一個非數值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果滿足上述其中之一，則拋出非法的引數例外IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//將指定的加載因子賦值給HashMap成員變數的負載因子loadFactor
this.loadFactor = loadFactor;
/**
* tableSizeFor(initialCapacity) 判斷指定的初始化容量是否是2的n次冪，如果不是那么會
* 變為比指定初始化容量大的最小的2的n次冪，但是注意，在tableSizeFor方法體內部將計算后的資料回傳給呼叫這里了，
* 并且直接賦值給threshold邊界值了，有些人會覺得這里是一個bug,應該這樣書寫：
* this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
* 這樣才符合threshold的意思（當HashMap的size到達threshold這個閾值時會擴容），
* 但是，請注意，在jdk8以后的構造方法中，并沒有對table這個成員變數進行初始化，
* table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算，put方法的具體實作我們下面會進行講解
*/
this.threshold = tableSizeFor(initialCapacity);
}
最后呼叫了tableSizeFor，來看一下方法實作：
/**
* Returns a power of two size for the given target capacity.
回傳比指定初始化容量大的最小的2的n次冪
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
tableSizeFor(int cap) 是解決initialCapacity不是2的n次冪的核心方法，程序如下圖：
這里說兩個問題：
- 首先，為什么要對cap做減1操作，
int n = cap - 1？這是為了防止，cap已經是2的冪，如果cap已經是2的冪， 又沒有執行這個減1操作，則執行完后面的幾條無符號右移操作之后，回傳的capacity將是這個cap的2倍，比如傳入16，如果不減1，最后結果會是32，讀者可以進行測驗， - 容量最大也就是32bit的正數，因此最后
n |= n >>> 16，最多也就32個1，但是這已經是負數了，在執行tableSizeFor之前，其實會對initialCapacity做了判斷，如果大于MAXIMUM_CAPACITY(2 ^ 30)，則取MAXIMUM_CAPACITY，如果等于MAXIMUM_CAPACITY(2 ^ 30)，會執行移位操作，所以這里面的移位操作之后，最大30個1，不會大于等于MAXIMUM_CAPACITY，30個1，加1之后得2 ^ 30 ，
DEFAULT_LOAD_FACTOR
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默認的裝載因子，用于衡量HashMap滿的程度，計算HashMap的實時裝載因子loadFactor的方法是size/capacity，size是當前HashMap中存放鍵值對的數量，capacity是桶的數量，默認值為0.75，loadFactor太大導致查找元素效率低，太小導致陣列的利用率低，存放的資料會很分散 ，這是對空間和時間效率的一個平衡選擇，建議不要修改，
當HashMap里面容納的元素已經達到HashMap陣列長度的75%時，表示HashMap太擠了，需要擴容，而擴容這個程序涉及到 rehash、復制資料等操作，非常消耗性能，，所以開發中盡量減少擴容的次數，可以通過創建HashMap集合物件時指定初始容量來盡量避免，
TREEIFY_THRESHOLD
//當桶(bucket)上的結點數大于這個值時會轉成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
TreeNodes占用空間是普通Nodes的兩倍，所以只有當bin包含足夠多的節點時才會轉成TreeNodes，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的，當bin中節點數變少時，又會轉成普通的bin，并且我們查看原始碼的時候發現，陣列長度大于64且鏈表長度達到8就轉成紅黑樹，當長度降到6就轉成普通bin，
//當桶(bucket)上的結點數小于這個值時樹轉鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//當集合中的容量大于這個值時，表中的桶才會進行樹形化，否則桶內元素太多時會擴容，
static final int MIN_TREEIFY_CAPACITY = 64;
這樣就解釋了為什么不是一開始就將其轉換為TreeNodes，而是需要一定節點數才轉為TreeNodes，其實就是空間和時間的權衡，
這段內容還說到：當hashCode離散性很好的時候，樹型bin用到的概率非常小，因為資料均勻分布在每個bin中，幾乎不會有bin中鏈表長度會達到閾值，但是在隨機hashCode下，離散性可能會變差，然而JDK又不能阻止用戶實作這種不好的hash演算法，因此就可能導致不均勻的資料分布， 不過理想情況下隨機hashCode演算法下所有bin中節點的分布頻率會遵循泊松分布，我們可以看到，一個bin中鏈表長度達到8個元素的概率為0.00000006，幾乎是不可能事件，所以，之所以選擇8，不是隨便決定的，而是根據 概率統計決定的，由此可見，發展將近30年的Java每一項改動和優化都是非常嚴謹和科學的，
也就是說：選擇8因為符合泊松分布，超過8的時候，概率已經非常小了，所以我們選擇8這個數字，
table
//存盤元素的陣列
transient Node<K,V>[] table;
在JDK8中我們了解到HashMap是由陣列加鏈表加紅黑樹來組成的結構，其中table就是HashMap中的陣列，JDK8之前陣列型別是Entry<K,V>型別，從JDK8之后是Node<K,V>型別，只是換了個名字，都實作了一樣的介面：Map.Entry<K,V>，負責存盤鍵值對資料的，
threshold
// 臨界值 當實際大小(容量*負載因子)超過臨界值時，會進行擴容
int threshold;
計算公式：capacity(陣列長度默認16) * loadFactor(負載因子默認0.75)，這個值是當前已占用陣列長度的最大值，當size>=threshold的時候，那么就要考慮對陣列的resize(擴容)，也就是說，這個的意思就是 衡量陣列是否需要擴增的一個標準， 擴容后的 HashMap 容量是之前容量的兩倍，
添加元素
流程
put方法還是比較復雜的，步驟大致如下:
-
先通過hash值計算出key映射到哪個桶；
-
如果桶上沒有碰撞沖突，則直接插入；
-
如果出現碰撞沖突了，則需要處理沖突：
- 如果該桶使用紅黑樹處理沖突，則呼叫紅黑樹的方法插入資料；
- 否則采用傳統的鏈式方法插入，如果鏈的長度達到臨界值，則把鏈轉變為紅黑樹；
-
如果桶中存在重復的鍵，則為該鍵替換新值value；
-
如果size大于閾值threshold，則進行擴容；
原始碼
具體的方法如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
我們可以看到在putVal()方法中key在這里執行了一下hash()方法，確定哈希桶陣列索引位置需要下面三步:
- 取hashCode值，
key.hashCode()， - 高位參與運算，h>>>16，
- 取模運算，(n-1)&hash，
來看一下Hash方法是如何實作的，
static final int hash(Object key)
{
int h;
/*
1）如果key等于null：
可以看到當key等于null的時候也是有哈希值的，回傳的是0.
2）如果key不等于null：
首先計算出key的hashCode賦值給h,然后與h無符號右移16位后的二進制進行按位異或得到最后的hash值
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashCode()得到的是一個32位int型別的值，通過hashCode()的高16位異或低16位實作，如果當n即陣列長度很小，假設是16的話，那么n-1即為 00000000 00000000 00000000 00001111 ，這樣的值和hashCode()直接做按位與操作，實際上只使用了哈希值的后4位，如果當哈希值的高位變化很大，低位變化很小，這樣就很容易造成哈希沖突了，所以這里把高低位都利用起來，從而解決了這個問題，例如下面這個例子，hashCode值的紅色部分再怎么變化也沒用，如果hashCode值的紅色部分變了，黑色部分沒變，就會造成索引結果仍然是10，從而造成了哈希沖突，
獲取桶陣列索引的步驟如下:
現在看putVal()方法，看看它到底做了什么，
主要引數：
- hash： key的hash值
- key： 原始Key
- value： 要存放的值
- onlyIfAbsent： 如果true代表不更改現有的值
- evict ：如果為false表示table為創建狀態
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/*
1）transient Node<K,V>[] table; 表示存盤Map集合中元素的陣列，
2）(tab = table) == null 表示將空的table賦值給tab,然后判斷tab是否等于null，第一次肯定是null
3）(n = tab.length) == 0 表示將陣列的長度0賦值給n,然后判斷n是否等于0，n等于0
由于if判斷使用雙或，滿足一個即可，則執行代碼 n = (tab = resize()).length;
進行陣列初始化，并將初始化好的陣列長度賦值給n.
4）執行完n = (tab = resize()).length，陣列tab每個空間都是null
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
1）i = (n - 1) & hash 表示計算陣列的索引賦值給i，即確定元素存放在哪個桶中
2）p = tab[i = (n - 1) & hash]表示獲取計算出的位置的資料賦值給節點p
3) (p = tab[i = (n - 1) & hash]) == null 判斷節點位置是否等于null，
如果為null，則執行代碼：tab[i] = newNode(hash, key, value, null);根據鍵值對創建新的節點放入該位置的桶中
小結：如果當前桶沒有哈希碰撞沖突，則直接把鍵值對插入空間位置
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//創建一個新的節點存入到桶中
tab[i] = newNode(hash, key, value, null);
else {
// 執行else說明tab[i]不等于null，表示這個位置已經有值了，
Node<K,V> e; K k;
/*
比較桶中第一個元素(陣列中的結點)的hash值和key是否相等
1）p.hash == hash ：p.hash表示原來存在資料的hash值 hash表示后添加資料的hash值 比較兩個hash值是否相等
說明：p表示tab[i]，即 newNode(hash, key, value, null)方法回傳的Node物件，
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next)
{
return new Node<>(hash, key, value, next);
}
而在Node類中具有成員變數hash用來記錄著之前資料的hash值的
2）(k = p.key) == key ：p.key獲取原來資料的key賦值給k key 表示后添加資料的key 比較 兩個key的地址值是否相等
3）key != null && key.equals(k)：能夠執行到這里說明兩個key的地址值不相等，
那么先判斷后添加的key是否等于null，如果不等于null再呼叫equals方法判斷兩個key的內容是否相等
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
/*
說明：兩個元素哈希值相等，并且key的值也相等
將舊的元素整體物件賦值給e，用e來記錄
*/
e = p;
// hash值不相等或者key不相等；判斷p是否為紅黑樹結點
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 說明是鏈表節點
else {
/*
1)如果是鏈表的話需要遍歷到最后節點然后插入
2)采用回圈遍歷的方式，判斷鏈表中是否有重復的key
*/
for (int binCount = 0; ; ++binCount) {
/*
1)e = p.next 獲取p的下一個元素賦值給e
2)(e = p.next) == null 判斷p.next是否等于null，等于null，
說明p沒有下一個元素，那么此時到達了鏈表的尾部，還沒有找到重復的key,則說明HashMap沒有包含該鍵
將該鍵值對插入鏈表中
*/
if ((e = p.next) == null) {
/*
1）創建一個新的節點插入到尾部
p.next = newNode(hash, key, value, null);
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next)
{
return new Node<>(hash, key, value, next);
}
注意第四個引數next是null，因為當前元素插入到鏈表末尾了，那么下一個節點肯定是null
2）這種添加方式也滿足鏈表資料結構的特點，每次向后添加新的元素
*/
p.next = newNode(hash, key, value, null);
/*
1)節點添加完成之后判斷此時節點個數是否大于TREEIFY_THRESHOLD臨界值8，如果大于則將鏈表轉換為紅黑樹
2）int binCount = 0 ：表示for回圈的初始化值，從0開始計數，記錄著遍歷節點的個數，
值是0表示第一個節點，1表示第二個節點，，，，7表示第八個節點，加上陣列中的的一個元素，元素個數是9
TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7
如果binCount的值是7(加上陣列中的的一個元素，元素個數是9)
TREEIFY_THRESHOLD - 1也是7，此時轉換紅黑樹
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉換為紅黑樹
treeifyBin(tab, hash);
// 跳出回圈
break;
}
/*
執行到這里說明e = p.next 不是null，不是最后一個元素，繼續判斷鏈表中結點的key值與插入的元素的key值是否相等
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出回圈
/*
要添加的元素和鏈表中的存在的元素的key相等了，則跳出for回圈，不用再繼續比較了
直接執行下面的if陳述句去替換去 if (e != null)
*/
break;
/*
說明新添加的元素和當前節點不相等，繼續查找下一個節點，
用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表
*/
p = e;
}
}
/*
表示在桶中找到key值、hash值與插入元素相等的結點
也就是說通過上面的操作找到了重復的鍵，所以這里就是把該鍵的值變為新的值，并回傳舊值
這里完成了put方法的修改功能
*/
if (e != null) {
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent為false或者舊值為null
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值
//e.value 表示舊值 value表示新值
e.value = value;
// 訪問后回呼
afterNodeAccess(e);
// 回傳舊值
return oldValue;
}
}
//修改記錄次數
++modCount;
// 判斷實際大小是否大于threshold閾值，如果超過則擴容
if (++size > threshold)
resize();
// 插入后回呼
afterNodeInsertion(evict);
return null;
}
treeifyBin方法
節點添加完成之后判斷此時節點個數是否大于TREEIFY_THRESHOLD臨界值8，如果大于則將鏈表轉換為紅黑樹(treeifyBin方法里面還會判斷陣列長度是否大于64)，轉換紅黑樹的方法 treeifyBin，整體代碼如下：
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉換為紅黑樹 tab表示陣列名 hash表示哈希值
treeifyBin(tab, hash);
treeifyBin方法如下所示：
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
替換指定哈希表的索引處桶中的所有鏈接節點，除非表太小，否則將修改大小，
Node<K,V>[] tab = tab 陣列名
int hash = hash表示哈希值
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/*
如果當前陣列為慷訓者陣列的長度小于進行樹形化的閾值(MIN_TREEIFY_CAPACITY = 64),
就去擴容，而不是將節點變為紅黑樹，
目的：如果陣列很小，那么轉換紅黑樹，然后遍歷效率要低一些，這時進行擴容，那么重新計算哈希值
，鏈表長度有可能就變短了，資料會放到陣列中，這樣相對來說效率高一些，
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//擴容方法
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
/*
1）執行到這里說明哈希表中的陣列長度大于閾值64，開始進行樹形化
2）e = tab[index = (n - 1) & hash]表示將陣列中的元素取出賦值給e,e是哈希表中指定位置桶里的鏈表節點，從第一個開始
*/
//hd：紅黑樹的頭結點 tl :紅黑樹的尾結點
TreeNode<K,V> hd = null, tl = null;
do {
//新創建一個樹的節點，內容和當前鏈表節點e一致
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
//將新創鍵的p節點賦值給紅黑樹的頭結點
hd = p;
else {
/*
p.prev = tl：將上一個節點p賦值給現在的p的前一個節點
tl.next = p;將現在節點p作為樹的尾結點的下一個節點
*/
p.prev = tl;
tl.next = p;
}
tl = p;
/*
e = e.next 將當前節點的下一個節點賦值給e,如果下一個節點不等于null
則回到上面繼續取出鏈表中節點轉換為紅黑樹
*/
} while ((e = e.next) != null);
/*
讓桶中的第一個元素即陣列中的元素指向新建的紅黑樹的節點，以后這個桶里的元素就是紅黑樹
而不是鏈表資料結構了
*/
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
擴容機制
流程
當HashMap中的元素個數超過capacity(陣列長度默認16) * loadFactor(負載因子默認0.75時，就會進行陣列擴容，loadFactor的默認值(DEFAULT_LOAD_FACTOR)是0.75,這是一個折中的取值，也就是說，默認情況下，陣列大小為16，那么當HashMap中的元素個數超過16×0.75=12(這個值就是閾值或者邊界值threshold值)的時候，就把陣列的大小擴展為2×16=32，即擴大一倍，然后重新計算每個元素在陣列中的位置，而這是一個非常耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那么預知元素的個數能夠有效的提高HashMap的性能，
HashMap在進行擴容時，使用的rehash方式非常巧妙，因為每次擴容都是翻倍，與原來計算的 (n-1)&hash的結果相比，只是多了一個bit位，所以節點要么就在原來的位置，要么就被分配到"原位置+舊容量"這個位置，例如我們從16擴展為32時，具體的變化如下所示：
容量變為原來的二倍后，n-1的二進制數也由1111變為11111，當容量為16時，(n-1)&hash的結果都是0101，即十進制的5；當容量變為32時，hash1的結果是0101，十進制的5，hash2的結果是10101，十進制的21(5+16)，擴容之后所以節點要么就在原來的位置，要么就被分配到"原位置+舊容量"這個位置，
因此，我們在擴充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就可以了，是0的話索引沒變，是1的話索引變成“原索引+oldCap(原位置+舊容量)”，在原始碼中通過e.hash & oldCap進行判斷，oldCap就是擴容之前的容量，在上面的例子中就是16，hash1結果為0，表示還在原位置，hash2結果不為1，表示結果為原位置+舊容量，即5+16=21，
可以看看下圖為16擴充為32的resize示意圖：
正是因為這樣巧妙的rehash方式，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是隨機的，在resize的程序中保證了rehash之后每個桶上的節點數一定小于等于原來桶上的節點數，保證了rehash之后不會出現更嚴重的hash沖突，均勻的把之前的沖突的節點分散到新的桶中了，
原始碼
final Node<K,V>[] resize() {
//得到當前陣列
Node<K,V>[] oldTab = table;
//如果當前陣列等于null長度回傳0，否則回傳當前陣列的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//當前閾值點 默認是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
//如果老的陣列長度大于0
//開始計算擴容后的大小
if (oldCap > 0) {
// 超過最大值就不再擴充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
//修改閾值為int的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
沒超過最大值，就擴充為原來的2倍
1)(newCap = oldCap << 1) < MAXIMUM_CAPACITY 擴大到2倍之后容量要小于最大容量
2）oldCap >= DEFAULT_INITIAL_CAPACITY 原陣列長度大于等于陣列初始化長度16
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//閾值擴大一倍
newThr = oldThr << 1; // double threshold
}
//老閾值點大于0 直接賦值
else if (oldThr > 0) // 老閾值賦值給新的陣列長度
newCap = oldThr;
else {// 直接使用默認值
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計算新的resize最大上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//新的閾值 默認原來是12 乘以2之后變為24
threshold = newThr;
//創建新的哈希表
@SuppressWarnings({"rawtypes","unchecked"})
//newCap是新的陣列長度--》32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//判斷舊陣列是否等于空
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
//遍歷舊的哈希表的每個桶，重新計算桶里元素的新位置
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//原來的資料賦值為null 便于GC回收
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;
//這里來判斷如果等于true e這個節點在resize之后不需要移動位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
好，原始碼就先分析到這里，如果前面看懂了，后面的洗掉查找對你來說相信也不是問題，
并發問題
在多執行緒使用場景中，應該盡量避免使用執行緒不安全的HashMap，而使用執行緒安全的ConcurrentHashMap，在多執行緒環境下，JDK1.7 會產生死回圈、資料丟失、資料覆寫的問題，JDK1.8 中會有資料覆寫和多執行緒同時擴容等問題，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/293595.html
標籤：java
下一篇：Java之面向物件