如果您在手機上閱讀不便可以 CSDN 搜索 SoWhat1412 觀看完整版文章。或者搜索公眾號:sowhat1412 觀看哦
預備知識
位運算知識
位運算操作是由處理器支持的底層操作，底層硬件只支持01這樣的數字，因此位運算運行速度很快。儘管現代計算機處理器擁有了更長的指令流水線和更優的架構設計，使得加法和乘法運算幾乎與位運算一樣快，但是位運算消耗更少的資源。常用的位運算如下：
位與 &
(1&1=1 1&0=0 0&0=0)
位或 |
(1|1=1 1|0=1 0|0=0)
位非 ~
（ ~1=0 ~0=1）
位異或 ^
(1^1=0 1^0=1 0^0=0)
有符號右移 >>
在執行右移操作時，若參與運算的數字為正數，則在高位補0；若為負數，則在高位補1。
無符號右移 >>>
無論參與運算的數字為正數或為負數，在執運算時，都會在高位補0。
左移
對於左移是沒有正數跟負數這一說的，因為負數在CPU中是以補碼的形式存儲的，對於正數左移相當於乘以2的N次冪。
敲重點：上面的重重都是簡單的只是為了引出下面的結論：
a % (Math.pow(2,n)) 等價於 a&( Math.pow(2,n)-1)
比如a%16最終的結果一定是0～15之間的數字，而a&1111正好把a除16後的餘數有效的現實出來了因為如果是1 1111這樣的話最前面一位其實代表的16，也就是說二進制從倒數第五位開始只要出現了1那絕對代表的是16的倍數。 結論：位運算比除法運算在運行效率上更高，對一個數取餘儘量用a&二進制數這樣可以更好的提速。
ArrayList
我們知道ArrayList是一個數組隊列，相當於動態數組 。與Java中的基本數組相比，它的容量能動態增長。它具有以下幾個重點。
ArrayList 實際上是通過一個數組去保存數據的。當我們構造ArrayList時；若使用默認構造函數，則ArrayList的默認容量大小是10。
當ArrayList容量不足以容納全部元素時，ArrayList會重新設置容量：原來容量的1.5倍。
ArrayList的克隆函數，即是將全部元素克隆到一個數組中。
克隆的底層是System.arraycopy(0,oldsrc,0,newsrc,length);
ArrayList實現java.io.Serializable的方式。當寫入到輸出流時，先寫入“容量”，再依次寫入“每一個元素”；當讀出輸入流時，先讀取“容量”，再依次讀取“每一個元素”。
優點：
根據下標遍歷元素效率較高。
根據下標訪問元素效率較高。
在數組的基礎上封裝了對元素操作的方法。
這樣的動態數組在內地地址上是空間連續的。
可以自動擴容。
缺點：
插入和刪除的效率比較低。
根據內容查找元素的效率較低。
擴容規則：每次擴容現有容量的50%。
LinkedList
雙向鏈表每一個節點包含三部分(data,prev,next)，它不要求空間是連續的。類似於節點跟節點之間通過前後兩條線串聯起來的。
ArrayList和LinkedList總結：
ArrayList是實現了基於動態數組的數據結構，LinkedList是基於鏈表結構。
對於隨機訪問的get和set方法，ArrayList要優於LinkedList，因為LinkedList要移動指針。
對於新增和刪除操作add和remove，LinkedList比較佔優勢，因為ArrayList要移動數據。
ArrayList使用在查詢比較多，但是插入和刪除比較少的情況，而LinkedList用在查詢比較少而插入刪除比較多的情況
RedBlackTree
首先你需要對二叉樹有個瞭解，知道這是什麼樣子的一個數據組合方式，然後知道二叉樹查找的時候缺點，可能發生數據傾斜。因此引入了平衡二叉樹，平衡二叉樹的左右節點深度之差不會超過1，查找方便構建麻煩，因此又出現了
紅黑樹。紅黑樹是一種平衡的二叉查找樹，是一種計算機科學中常用的數據結構，最典型的應用是實現數據的關聯，例如map等數據結構的實現，紅黑樹重要特性是( 左節點 < 根節點 < 右節點) 紅黑樹有以下限制：節點必須是紅色或者是黑色
根節點是黑色的
所有的葉子節點是黑色的。
每個紅色節點的兩個子節點是黑色的，也就是不能存在父子兩個節點全是紅色
從任意每個節點到其每個葉子節點的所有簡單路徑上黑色節點的數量是相同的。
如果您對紅黑樹還不太瞭解推薦看下博主以前寫的RBT
HashTable
Hash表是一種特殊的數據結構，它同數組、鏈表以及二叉排序樹等相比較有很明顯的區別，它能夠快速定位到想要查找的記錄，而不是與表中存在的記錄的關鍵字進行比較來進行查找。這個源於Hash表設計的特殊性，它採用了==函數映射==的思想將記錄的存儲位置與記錄的關鍵字關聯起來，從而能夠很快速地進行查找。評價函數的性能關鍵在於==裝填因子==，以及如何合理的解決哈希衝突，具體的可看博主以前寫的
徹底搞定哈希表HashMap源碼剖析
概述
通常具備前面一些知識點的鋪墊就可以很好的開展HashMap的講解了，既然ArrayList，LinkedList，Red Black Tree各有優缺點，我們能不能集百家之長實現一個綜合產物呢 === >HashMap，本文所以講解都是基於JDK8。
HashMap的組成部分：數組 + 鏈表 + 紅黑樹。HashMap的主幹是一個Node數組。Node是HashMap的基本組成單元，每一個Node包含一個key-value鍵值對。HashMap的時間複雜讀幾乎可以接近O(1)(如果出現了 哈希衝突可能會波動下)，並且HashMap的空間利用率一般就是在40%左右。HashMap的大致圖如下：
PS:其中幾個重要節點關係如下：
- java.util.Map.Entry 這就是個interface定義了一些比較的接口函數。
- java.util.HashMap.Node 就是我們HashMap中存儲的基本的KV。
- java.util.LinkedHashMap.Enrty Enrty這個類繼承自HashMap.Node這個類，Enrty是LIinkedHashMap的一個內部類，
- java.util.HashMap.TreeNode TreeNode的構造函數向上追溯繼承了LinkedHashMap.Entry，而後者又繼承了HashMap.Node。所以TreeNode既保有Node的屬性，同時由於添加了prev這個前驅指針使得==鏈表==變為了==雙向==。前三個節點跟第五個紅黑樹相關，第四個跟next跟雙向鏈表相關。 數據存儲的大致步驟有三步。
- 每個數據通過HashTable裡的映射函數來決定將該數據放到數組的那個地方，數組初始化時候一定是2的次冪，默認16，初始化傳入的任何數字都會經過tableSizeFor調整為2次冪。
- 如果同一個數組的地方被分配到太多數據就用鏈表法來解決哈希衝突。
- 如果同一個節點的鏈表數據節點個數 > TREEIFY_THRESHOLD=8且數組長度 >= MIN_TREEIFY_CAPACITY=64，則會將該鏈表進化位RedBlackTree,如果RedBlackTree中節點個數小於UNTREEIFY_THRESHOLD=6會退化為鏈表。
特別提醒：讀HashMap源碼之前需要知道它大致特性如下：
HashMap的存取是沒有順序的
KV均允許為NULL
多線程情況下該類安全，可以考慮用HashTable。
JDk8底層是數組 + 鏈表 + 紅黑樹，JDK7底層是數組 + 鏈表。
初始容量和裝載因子是決定整個類性能的關鍵點,輕易不要動。
HashMap是懶漢式創建的，只有在你put數據時候才會build
單向鏈表轉換為紅黑樹的時候會先變化為雙向鏈表最終轉換為紅黑樹，雙向鏈表跟紅黑樹是共存的，切記。
對於傳入的兩個key，會強制性的判別出個高低，判別高低主要是為了決定向左還是向右。
鏈表轉紅黑樹後會努力將紅黑樹的root節點和鏈表的頭節點 跟table[i]節點融合成一個。
在刪除的時候是先判斷刪除節點紅黑樹個數是否需要轉鏈表，不轉鏈表就跟RBT類似，找個合適的節點來填充已刪除的節點。
紅黑樹的root節點不一定跟table[i]也就是鏈表的頭節點是同一個哦，三者同步是靠MoveRootToFront實現的。而HashIterator.remove()會在調用removeNode的時候movable=false。
在這裡插入圖片描述
重要參數
靜態參數
- static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
初始容量，默認容量=16，箱子的個數不能太多或太少。如果太少，很容易觸發擴容，如果太多，遍歷哈希表會比較慢。
- static final int MAXIMUM_CAPACITY = 1 << 30
數組的最大容量，一般情況下只要內存夠用，哈希表不會出現問題
- static final float DEFAULT_LOAD_FACTOR = 0.75f
默認的負載因子。因此初始情況下，當存儲的所有節點數 > (16 * 0.75 = 12 )時，就會觸發擴容。 默認負載因子（0.75）在時間和空間成本上提供了很好的折衷。較高的值會降低空間開銷，但提高查找成本（體現在大多數的HashMap類的操作，包括get和put）。設置初始大小時，應該考慮預計的entry數在map及其負載係數，並且儘量減少rehash操作的次數。如果初始容量大於最大條目數除以負載因子，rehash操作將不會發生。
從上面的表中可以看到當桶中元素到達8個的時候，概率已經變得非常小，也就是說用0.75作為加載因子，每個碰撞位置的鏈表長度超過８個是幾乎不可能的。 4. static final int TREEIFY_THRESHOLD = 8
這個值表示當某個箱子(數組的某個item)中，鏈表長度 >= 8 時，有可能會轉化成樹。設置為8，是系統根據泊松分佈的數據分佈圖來設定的。
- static final int UNTREEIFY_THRESHOLD = 6
在哈希表擴容時，如果發現鏈表長度 <= 6，則會由樹重新退化為鏈表。 設置為6猜測是因為時間和空間的權衡
當鏈表長度為6時 查詢的平均長度為 n/2=3，紅黑樹 log(6) = 2.6 為8時 :鏈表 8/2=4， 紅黑樹 log(8)=3
- static final int MIN_TREEIFY_CAPACITY = 64
鏈表轉變成樹之前，還會有一次判斷，只有數組長度大於 64 才會發生轉換。這是為了避免在哈希表建立初期，多個鍵值對恰好被放入了同一個鏈表中而導致不必要的轉化。
動態參數
- transient Node[] table
HashMap的鏈表數組。無論我們初始化時候是否傳參，它在自擴容時總是2的次冪。
- transient Set> entrySet
HashMap實例中的Entry的Set集合
- transient int size
HashMap表中存儲的實例KV個數。
- transient int modCount
凡是我們做的增刪改都會引發modCount值的變化，跟版本控制功能類似，可以理解成version，在特定的操作下需要對version進行檢查，適用於Fai-Fast機制。
在java的集合類中存在一種Fail-Fast的錯誤檢測機制，當多個線程對同一集合的內容進行操作時，可能就會產生此類異常。 比如當A通過iterator去遍歷某集合的過程中，其他線程修改了此集合，此時會拋出ConcurrentModificationException異常。 此類機制就是通過modCount實現的，在迭代器初始化時，會賦值expectedModCount，在迭代過程中判斷modCount和expectedModCount是否一致。
- int threshold
擴容閾值 threshold = capacity * loadFactor
- final float loadFactor
可自定義的負載因子，不過一般都是用系統自帶的0.75。
四種構造方法
- 默認構造方法
- 傳入初始容量大小
- 傳入初始容量大小及負載因子 ==tableSizeFor==:作用是返回大於輸入參數且最小的2的整數次冪的數。比如10，則返回16。 詳解如下：
先來分析有關n位操作部分：先來假設n的二進制為01xxx...xxx。接著 對n右移1位：001xx...xxx，再位或：011xx...xxx 對n右移2為：00011...xxx，再位或：01111...xxx 此時前面已經有四個1了，再右移4位且位或可得8個1 同理，有8個1，右移8位肯定會讓後八位也為1。
綜上可得，該算法讓最高位的1後面的位全變為1。最後再讓結果n+1，即得到了2的整數次冪的值了。 現在回來看看第一條語句：
int n = cap - 1;
讓cap-1再賦值給n的目的是另找到的目標值大於或等於原值。例如二進制1000，十進制數值為8。如果不對它減1而直接操作，將得到答案10000，即16。顯然不是結果。減1後二進制為111，再進行操作則會得到原來的數值1000，這種二進制方法的效率非常高。
- 構造函數傳入一個map 使用默認的負載因子，然後根據當前map的大小來反推需要的threshold，同時還可能會涉到resize，然後住個put到 容器中。
在這裡插入圖片描述
Hash值
無論我們put數據還是get數據都要先獲得該數據在這個哈希表中對應的位置。比如put數據，它的流程分為2步。
1.先獲得key對應的hash值。 2. 將該數據的hash值A，跟將A右無符號移動16位後再^得到最終值。這個操作叫擾動，原因是怕低幾位出現想同的概率太大，儘可能的將數據實現均勻分佈。
在這裡插入圖片描述
同時JDK8跟JDK7的擾動目的一樣，不過複雜程度不一樣。
1. get
相對來說很簡單,為方便理解先說下代碼大致流程思路。
獲得key的hash然後根據hash和key按照插入時候的思路去查找get。
如果數組位置為NULL則直接返回 NULL。
如果數組位置不為NULL則先直接看數組位置是否符合。
如果數組位置有類型說紅黑樹類型，則按照紅黑樹類型查找返回。
如果數組有next，則按照遍歷鏈表的方式查找返回。
在這裡插入圖片描述
1.1 getNode
宏觀查找函數細節：
1.3 getTreeNode
紅黑樹查找節點細節：
先獲得根節點，左節點，右節點。
根據 左節點 < 根節點 < 右節點 對對數據進行逐步範圍的縮小查找。
如果實現了Comparable方法則直接對比。
否則如果根節點不符合則遞歸性的調用find查找函數。
在這裡插入圖片描述
1.4 ComparableClassFor:
查詢該key是否實現了Comparable接口。
1.5 compareComparables:
既然實現了Comparable接口就用該實現進行對比判斷如何何去何從。
2. put流程
跟隨源碼梳理下put操作的大致流程。
數據插入的時候大致流程如下：
- 對數據進行Hash值計算。
- 將數據插入前先查看下當前table的狀態，如果table是空需要調用resize來進行初始化。
- 通過位運算獲得key的目標位置。並判斷當前位置情況。
- 如果當前位置為空則直接進行放置，如果跟當前key一直則進行覆蓋。
- 如果當前有數據則看當前數據類型是否是紅黑樹，是的話需要調用putTreeVal。
- 否則就認為是個鏈表，然後循環的查找進行尾部==插入==。同時還要考慮當前鏈表轉紅黑樹。
在JDK8中尋找待插入點 e是通過==尾插法==(類似與排隊在最後面)，而在JDK7中是==前插法==(類似與加塞在最前面，之所以這樣做是HashMap發明者認為後插入節被訪問概率更大)，對應代碼如下。
在這裡插入圖片描述
- 對找到的舊節點e進行判斷
oldValue對應的舊值如果為NULL，那麼無論onlyIfAbsent是否決定替換。都將被替換。
oldValue對應的舊值如果不為NULL，那麼如果onlyIfAbsent是false就替換。
onlyIfAbsent:只有在缺席的情況下才替換，不缺席不替換。跟redis Setnx 同樣的功能。
- 數據最終添加完畢後要對對修改後的變量modCount加1，同時看最新的總的節點數是否需要擴容了，如果是就擴容。
2 put
在這裡插入圖片描述
2.1 putTreeVal
- 先找到根節點，然後判斷是從左邊找還是右邊找key。
- 找到了則直接返回找到的節點。
- 沒找到則新建節點將該新建節點放到適當的位置，同時考慮紅黑樹跟雙向鏈表的節點插入情況。
2.2 treeifyBin
主要功能是根據參數的閾值範圍絕對是否將鏈表轉化為紅黑樹，然後首先將單項鍊表轉化為雙向鏈表，再調用treeify以頭節點為根節點構建紅黑樹。
2.3 treeify
雙向鏈表跟紅黑樹創建，主要步驟分3步。
- 從該雙向鏈表中找第一個節點為root節點。
- 每一個雙向鏈表節點都在root節點為根都二叉樹中找位置然後將該數據插入到紅黑樹中，同時要注意balance。
- 最終要注意將根節點跟當前table[i]對應好。
2.4 moveRootToFront
確保將root節點挪動到table[first]上，如果紅黑樹構建成功而沒成功執行這個任務會導致tablle[first]對應的節點不是紅黑樹的root節點。正常執行的時候主要步驟分2步。
- 找到跟節點然後將root節點放到跟節點，至此關於紅黑樹到操作搞定。
- 原來鏈表頭是first節點，現在將可能是中間節點的root節點挪到first節點前面。 其中 checkInvariants函數的作用：校驗TreeNode對象是否滿足紅黑樹和雙鏈表的特性。因為併發情況下會發生很多異常。
3 resize
獲得老table數據，如果老table已經足夠大則不再擴容，只調節閾值。
老table擴容後的範圍也符合要求直接將容器大小跟閾值都擴容 。
如果是帶參數構造函數則需要將閾值複製給容器容量。
否則認為該容器初始化時未傳參，需初始化。
如果老table有數據，新他變了大小設置好了但是閾值沒設置成功。此時要設置新閾值。
創建新容器。
老table成功擴容為新table，涉及到數據的轉移。
數據不為空是單獨的節點則直接重新hash分配新位置。
數據不為空後面是一個鏈表，則要把鏈表數據進行區分看那些分到老地方那些分到新地方。
如果該節點類型是個紅黑樹則調用split.
鏈表形式的重新劃分解釋如下： 注意：不是(e.hash & (oldCap-1))而是(e.hash & oldCap), 後一個得到的是 元素的在數組中的位置是否需要移動,示例如下
示例1： e.hash= 10 0000 1010 oldCap=16 0001 0000 & =0 0000 0000 比較高位的第一位 0 結論：元素位置在擴容後數組中的位置沒有發生改變 示例2： e.hash= 17 0001 0001 oldCap=16 0001 0000 & =1 0001 0000 比較高位的第一位 1 結論：元素位置在擴容後數組中的位置發生了改變，新的下標位置是原下標位置+原數組長度
在這裡插入圖片描述
3.1 split
擴容後如何處理原來一個table[i]上的紅黑樹，代碼的整體思路跟處理鏈表的時候差不多，只要理解節點關係保存紅黑樹的時候也保存了雙向鏈表就OK了。
4. find
函數功能就是以指定的一個節點為根節點，根據指定的key跟value進行查找。
通過hash值判斷 左邊找還是右邊找。
如果找到的很簡單直接返回。
可能出現hash值相等可是key不一樣，繼續查找分為三種情況。
左節點為空則找右節點
右節點為空則找左節點
左右節點都不會空，嘗試通Comparable對數據看向左還是向右。
無法通過comparable比較或者比較之後還是相等。
直接從右節點遞歸查找下。
否則就從左邊查找。
在這裡插入圖片描述
4.1 tieBreakOrder
對兩個對象進行比較，一定能比出個高低。
a 跟 b 都是字符串則直接在if判斷裡比拼完畢
a 跟 b 都是對象則直接查看對象在JVM中的hash地址，然後比較。
在這裡插入圖片描述
4. remove
函數入口而已：
4.1 removeNode
removeNode無非就是查看table[i]是否存在，然後是否在首節點上，是否在紅黑樹上，是否在鏈表上。這幾種情況，找到了則直接刪除，同時注意平衡性。
4.2 removeTreeNode
該函數的 目的就是移除調用此方法的節點，也就是該方法中的this節點。移除包括鏈表的處理和紅黑樹的處理。可以看以前寫過的RBT，刪除的時候思路大致是一樣的，這裡大致分為3步驟。
紅黑樹也是雙向鏈表，以鏈表的角度來刪除節點，然後判斷是否需要退化為鏈表。
根據當前的p節點嘗試從pr找最小的或者從pl找最大的目標節點s，將兩點兌換。
找到要replacement來跟p進行替換。
實施替換。
替換後為保持紅黑樹特性可能需要進行balance。
在這裡插入圖片描述
4.3 untreeify
紅黑樹退化成鏈表
4.4 balanceDeletion
關於這個問題可以直接看博主以前寫的紅黑叔添加跟刪除RBT
JDK7死環問題
JDK7對舊table數據重定位到新table的函數transfer如下，其中重點關注部分以標出。
- 頭插法正常情況下：
- 併發情況下 線程1只執行了Entry next = e.next就被掛起了，而線程2正常執行完畢，結果圖如下： 線程1接著下面繼續執行： 通過逐步分析跟繪圖可以知道 會有環產生。
HashIterator 的 remove 方法
7vs8
7中找Hash用了4次，8中只用了1次。
7 = 數組 + 鏈表，8 = 數組 + 鏈表 + 紅黑樹
7中是頭插法，多線程容易造成環，8中是尾插法。
7的擴容是全部數據重新定位，8中是位置不變+ 移動舊size大小來實現更好些。
7是先判斷是否要擴容再插入，8中是先插入再看是否要擴容。
HashMap不管78都是現場不安全的，多線程情況下記得用ConcurrentHashmap。ConcurrentHashmap下篇文章說。
常見問題
隨機蒐羅了一些常見HashMap問題，如果把上述代碼都看懂了應付這些應該沒問題。
HashMap原理，內部數據結構。
HashMap中的put,get,remove大致過程。
HashMap中 hash函數實現。
HashMap如何擴容。
HashMap幾個重要參數為什麼這樣設定。
HashMap為什麼線程不安全，如何替換。
HashMap在JDK7跟JDK8中的區別。
HashMap中鏈表跟紅黑樹切換思路。
參考
HashMap講解 HashMap詳解 疫苗JAVA HASHMAP的死循環
本文使用 mdnice 排版
