HashMap之節點刪除

大家一直關注的都是HashMap如何添加節點，當節點數量大于8的時候轉化為紅黑樹，否則使用鏈表等等，但大家是否有看過刪除節點的處理邏輯呢？ 今天來看看HashMap刪除節點的神來之筆

問題來源

在查看HashMap源碼時，有個以下字段，在刪除的時候，判斷節點數量，最多在小于6的時候，會untreeifying(樹轉化為鏈表)，在點擊這個字段時發現，只有在split()方法中使用，但split()方法在resize()方法中使用，與刪除節點無關，遂去翻刪除節點的代碼邏輯

節點刪除

通過remove方法，一路進來，找到刪除節點的地方。如下圖：

我們進入removeTreeNode方法中，代碼如下：

查看方法注釋，里面介紹到：如果節點太少，就會把當前bin轉換成普通bin。不理解注釋沒關系，我們進入這個方法中唯一有轉化的地方。進入untreeify()方法查看下。代碼如下：

噢，第一行看一下，if,else看一下，嗯，這個方法就是獲取返回了一個列表(這些方法都是TreeNode類里面的方法，所以請注意，this就是當前要操作的TreeNode節點)。到此明白，這個方法就是把紅黑樹轉化成鏈表的，那么我的就得分析分析是如何操作的了，而沒有使用到定義的全局變量。

刪除判斷邏輯分析

我們來分析分析上面這個邏輯，進入這個untreeify() 的要求是，root == null, root.right ==null, root.left==null, root.left.left==null四種情況，我們以7個節點的紅黑樹來分析，A為root節點。

所以進入這個方法主要有以下幾種情況，我們一種一種的來分析當滿足要求時，節點的個數。(這里默認認為知道紅黑樹的5個特點，主要是黑平衡)

當這四種情況都滿足時，我們可以看出最多節點有如上圖所示個數，可以為7個。(大于8個不考慮，因為大于8會變成紅黑樹)。

1. 最多節點情況：當我們刪除節點D時，只滿足root.left.left==null這個條件，這棵樹仍可以維持紅黑樹的特點，這時的最大節點數為6.

2. 最少節點情況：當EFG不存在時，在A,B,C,D中刪除任意一個節點，都會滿足上述四種規則中的一種。則存在最少節點情況，有3個節點。

以上情況都是會將樹轉化成鏈表，此時的節點是 3<= nodes <=6 ，由此可以看出，當節點數在小于6時，是可能轉化成鏈表，但不是絕對情況， 所以使用定義的變量(固定數量6)也不正確。只好通過判斷去動態獲取節點數。

節點數量原因分析

為什么在小于6的時候可能轉換成鏈表，而在大于8的時候轉化成紅黑樹？

主要通過時間查詢節點分析，紅黑樹的平均查詢時間為 log(n), 而鏈表是O(n)，平均是O(n)/2。

當節點數為8時，紅黑樹查詢時間3，鏈表查詢時間是4, 可以看出來當紅黑樹查詢效率大于了鏈表。(兩個函數曲線問題，當節點更多是，比紅黑樹需要的時間更多)

當節點數為6時，為什么轉換成鏈表，我認為主要時因為節點數太少，如果還是用紅黑樹，為了維持紅黑樹的特點，則需要翻轉，左旋，右旋，等，更消耗性能。

為什么不是7是轉化？

主要是為了給一個過渡，防止頻繁轉化。 也如上圖，7個節點可能正好是一個滿二叉樹。

來自：https://www.cnblogs.com/lifacheng/p/11032482.html