1. 導讀

這次的分享是關於HashMap::put, 主要是圍繞下面幾個方面展開:.1 HashMap::put源碼解析;.2 紅黑樹插入的處理;.3 紅黑樹與鏈表的互轉;

2. HashMap::put源碼解析

因為HashMap::put的源碼較長, 用下面的流程圖來替代:

下面我們一步步來分析:.1 因為HashMap在初始化的時候, 沒有初始化table, 所以在第一次插入時需要初始化table;.2 判斷table[(n - 1) & hash]是否為空, 如果為空則證明是首節點, 直接插入即可;.3 若不為空, 則需判斷掛載的是鏈表還是紅黑樹, 若是紅黑樹, 則走紅黑樹的插入;.5 遍歷鏈表, 如果key相同且hash相同, 則直接退出循環;.6 如果已經到了尾節點, 則直接插入, 再判斷鏈表的長度是否大於8; 若大於8需要轉成紅黑樹;

.7 退出循環後再判斷相同key能否覆蓋, 能覆蓋時直接覆蓋, 並返回結果;

.8 插入完成後再判斷HashMap.size 是否大於 threshold; 為真時需要擴容;.9 HashMap::put正常插入的返回結果都為null;.10 HashMap::put流程中的afterNodeAccess(), afterNodeInsertion()無需關注, 這是LinkedHashMap的處理;HashMap::put的主流程還是比較清晰的, 但是在JAVA8以後加入了紅黑樹的處理, 我們需要關注下紅黑樹的插入與鏈錶轉紅黑樹的操作;3. 紅黑樹的插入HashMap.TreeNode::putTreeVal是紅黑樹插入的主邏輯:

.1 從根節點遍歷槽點的紅黑樹;

.2 判斷待插入節點位於左子樹還是右子樹, key相等時直接返回, 由主流程判斷是否更新節點值;

.3 當遍歷到當前節點的左(右)子節點為空時, 插入待插入節點;.4 再次平衡紅黑樹;判斷節點位於左右子樹的過程在前面的HashMap::get中已經詳細的講解過了, 先比較hash再比較key是否實現了Comparable介面;如果不實現時, 調用HashMap.TreeNode::tieBreakOrder, 我們來看下tieBreakOrder方法做了什麼:tie bread在網球比賽中叫做平局決勝, 如果把判斷節點位於那顆子樹作為比賽的話:.1 比較節點的hash值是第一輪;.2 通過Comparable比較是第二輪;.3 如果前面兩輪沒有分出結果, 那麼tieBreakOrder就作為決勝輪來比較出一個結果;.4 當然如果key沒有實現Comparable介面, 那麼第一輪沒結果就會直接進入決勝輪;我們來看下作為決勝輪的tieBreakOrder方法是如何做到必定出結果的:

static int tieBreakOrder(Object a, Object b) {

int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1); return d; }.1 當兩個對象都不為空時, 使用類名做比較; 因為JAVA中的類型是String, 而String實現了Comparable介面, 故可直接使用String::compareTo比較;

.2 當第一步的結果為0, 或者至少有一個對象為空時, 會調用System::identityHashCode來做比較;

.3 System::identityHashCode 與 Obejct::hashCode的區別是: 前者不能被重寫, 而且當傳入的對象為null時, 返回的結果是0; 所以即使兩個對象都為null, 也可以通過 <= 返回一個 -1;紅黑樹的再次平衡過程因為內容較多, 我們放到後面專門講解; 接下來我們再看下鏈錶轉換為紅黑樹的過程:4. 鏈錶轉紅黑樹 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null;

do {

TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null);

if ((tab[index] = hd) != null)

hd.treeify(tab); } }上面的代碼是將鏈表升級為紅黑樹的主流程:.1 通過遍歷鏈表, 將鏈表節點轉換為樹節點(這時候還沒設置左右子樹以及顏色);.2 設置節點的父節點與子節點, 這時候其實是將單向鏈表升級為雙向鏈表;.3 調用HashMap.TreeNode::treeify給雙向鏈表上色以及設置左右子樹;我們發現在鏈表升級為紅黑樹的主流程中, 先是將單向鏈表升級為雙向鏈表, 並且設置父子節點; 但是我們不通過這步操作直接調用HashMap.TreeNode::treeify也可以實現鏈錶轉紅黑樹, 為什麼要多此一舉呢?因為在HashMap中不僅有鏈錶轉紅黑樹, 也有紅黑樹轉鏈表的操作, 上面轉雙向鏈表的操作其實是維護了當前的鏈表結構, 方便紅黑樹轉鏈表;

HashMap.TreeNode::treeify的流程可以理解為遍歷鏈表數據並插入紅黑樹, 所以HashMap.TreeNode::treeify的實現和紅黑樹的插入核心基本一致, 這裡就不做重複敘述了;

本次分享到此結束了, 主要是分享了HashMap對紅黑樹插入的處理, 但是紅黑樹插入節點後再平衡的過程會放到下次分享;如果看了本次對你有幫助, 煩請點贊轉發, 感謝;

推薦閱讀：

相关文章