說明
此次深入原始碼解剖是為了搞明白幾個問題
1、HashMap是如何初始化的
2、HashMap的擴容機制是怎樣的
3、元素是如何put進HashMap的，具體位置在哪（重難點）
4、擴容后，元素是如何重新分布的（重難點）
注：為了方便讀者復盤，我截取原始碼時會將原始碼行號也帶上，
jdk版本：1.8
在深入原始碼之前，應該先有個大致的了解，在JDK8里面，HashMap的底層資料結構已經變為陣列+鏈表+紅黑樹的結構
HashMap結構示意圖
陣列就是原始碼中的table
鏈表就是內部類Node
紅黑樹就是內部類TreeNode
解剖思路
先創建一個無參建構式，往其內添加一個元素，看看HashMap是如何初始化的，然后再創建一個有參建構式，并往其中添加若干元素，直至觸發擴容機制
無參建構式
在無參建構式之前，打個斷點，以debug模式啟動，關于除錯鍵的使用請參照：IDEA除錯鍵的說明，在此不再贅訴，
點擊Step Over到HashMap map = new HashMap();所在的這行
點擊Force Step Into，會發現先呼叫的是類加載器
這不是今天的重點，我們直接Step Out，然后再次點擊Force Step Into，進入原始碼
初始化負載因子
這行代碼的意思是loadFactor設定為默認的負載因子 0.75，上面的因為注釋說同時初始容量為16，這里暫時沒看到在哪了賦值了
反倒是你在475行點擊Force Step Into會發現它呼叫的父類的建構式
這也補充一個知識點，有父類建構式的先執行父類的建構式，再執行自己的建構式
執行完父類的建構式，將負載因子設定為默認，初始化就此完成了
繼續點擊Force Step Into，來到map.put("debug","HashMap");
繼續點擊Force Step Into，進入原始碼611行
計算key的hash值
繼續點擊Force Step Into來到計算key的hash值
繼續點擊Force Step Into會發現因為key的型別是String，最終呼叫的是String的hashCode，經過計算后key的hash值為95458899
繼續點擊Force Step Into，算完key的hash值，然后呼叫putVul
初始擴容
因為是剛剛構造的所以tab為null,所以要走一波resize()
點擊Force Step Into進去看看，用紅線框出執行路徑
因為oldTab是為null的所以直接回傳newTab
回顧一下這段原始碼，雖然很長很復雜，但對于此次除錯，核心的就是以下三行
將容量設定為默認容量DEFAULT_INITIAL_CAPACITY為16，將擴容閾值設定為(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)是 16*0.75 = 12，然后以該容量（16）為長度創建一個鏈表陣列Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]，并回傳該陣列
所以所謂的默認容量和默認擴容閾值是在插入第一個元素時，呼叫resize()方法賦值的，并不是用建構式初始化時設定的
元素定位
繼續Force Step Into回到putVal，此時陣列已經創建好了，長度n=16
下一步if ((p = tab[i = (n - 1) & hash]) == null)這拆開來看，先看(n - 1) & hash，這是用陣列的長度&上key的hash，得到的結果作為該鍵值對在陣列中的位置，這個值是多少呢，我們可以自己算一下
這里的&是計算機的二進制按位與，n-1=15，二進制為1111，key的hash值為95458899，這個二進制是多少，用 工具 轉換一下
按位&，有0為0，全是1才是1，出來的結果是多少，是在不行也用 工具 吧
我們計算的結果是3，看看原始碼計算的結果，果然也是3
那么，由于這是第一個元素，3號位之前肯定是空的，即該元素將放置在3這個位置，放一個什么進去呢
newNode(hash, key, value, null)
最終就是一個這個Node
示意圖
我們繼續除錯，執行完放入元素之后，modCount自增，size自增，并和擴容閾值（當前是12）比較
這個，modCount不展開講，簡單提一下，它是用在執行緒迭代集合時，如果發這個值變動了，和當前的值不一樣，說明有人操作該集合，改變了內部資料，就會報出一個ConcurrentModificationException例外
完成
至此，無參構造，插入一個元素就完成了
下回
下回我們再分析有參構造函數的初始化，和元素增多導致的擴容，元素重新定位問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/9112.html
標籤：java
上一篇：多重雙向鏈表實作LFU演算法