[Java]似乎很多人搞錯了HashMap紅黑樹退化？（圖文並茂）详情 - java,數據庫,程序員,segmentfault,leetcode GEDY 日志

進入掘金瀏覽，效果更加哦😊~

先省流，説結論：

HashMap去樹化有兩種情況

在樹拆分過程中，拆完的兩棵樹分別判定，如果總節點<=6的話就去樹化

在去除樹節點時，通過一系列條件判定，一般會在樹節點2-6時進行去樹化

前言

之前在準備面試背八股時，看了一堆HashMap樹化的東西，但是似乎沒啥人講去樹化，而有的文章可能會略點一二，但是似乎解答也不統一（非引戰，只做討論）

疊甲

本人才疏學淺，對HashMap只略懂一二。如果內容有問題，請指正orz😂，我們會第一時間去研究和修改內容，非常感謝(^\_^)。
本文使用Java8源碼，目前最新的Java22源碼幾乎沒有對去樹化進行修改，總流程一致。
本文着重講去樹化，一些頂層方法如resize、put、remove並不做展開，需要讀者自己can can。

正文

1. 什麼是去樹化,如何去樹化

去樹化指的就是HashMap中當紅黑樹節點數過少時,將紅黑樹轉為鏈表的操作
HashMap去樹化使用的是untreeify方法，流程很簡單，就是從當前的node開始，逐個使用replacementNode把樹節點改為普通節點

final HashMap.Node<K,V> untreeify(HashMap<K,V> map) {
    // hd 鏈表頭 tl 鏈表尾
    HashMap.Node<K,V> hd = null, tl = null;
    // 從當前Node開始,逐個調用replacementNode將書樹節點換成鏈表節點
    for (HashMap.Node<K,V> q = this; q != null; q = q.next) {
        HashMap.Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

2. 哪裏會調用去樹化

HashMap中有兩個地方會調用去樹化，這也是大部分説法都忽視的。具體的方法:removeNode和split，由於split方法是大家津津樂道的 <=6去樹化的理論，就先説説split方法吧

`split`中的去樹化

split，顧名思義，就是把樹撕成兩棵樹，至於是怎麼撕為什麼撕，各位八股好手應該記得resize方法中根據Node中根據hash值的高bit位對鏈表/樹進行拆分，這是老生常談的玩意了，這裏就不做展開,感興趣可以看這個:HashMap之resize詳解。而這個過程中如果哪一棵樹節點<=6，就進行untreeify/去樹化

具體流程

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    // ...通過hash值的高位bit，分出hi,lo兩條鏈表
    // 分別判斷它們長度是否<=UNTREEIFY_THRESHOLD(6)
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

`removeNode`中的去樹化

這個方法大家其實很常用，就是remove的底層調用，而裏面作者的原話：The test triggers somewhere between 2 and 6 nodes, depending on tree structure，説人話就是大概2-6個節點去樹化

<p align=center>這裏使用的是IDEA的Translation插件,強推!非廣!絕對的頂級!</p>

具體流程

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    // ... 定位出節點所在樹的根節點
    // 調用untreeify條件
    if (root == null|| (movable
            && (root.right == null|| (rl = root.left) == null
            || rl.left == null))) {
            tab[index] = first.untreeify(map); // too small
        return;
    }
    // ... 節點的刪除/替換
}

代碼中的條件root.right == null|| (rl = root.left) == null|| rl.left == null比較抽象，我畫個圖吧，假如圖中A\~C中有一個節點為null則條件成立（源代碼這裏註釋了個tooSmall，後面我們就稱這個條件為tooSmall情況吧）

那在什麼情況下條件成立呢，根據紅黑樹的規則

ok，到這裏可以算是破案了，HashMap去樹化有倆方法，而且條件不一致，難怪網上説的總是奇奇怪怪。但是，真的嗎，我不信（魯豫臉），本着實踐出真知的原則，我想再實操一下

實踐環節

實踐內容僅為印證觀點，嫌我囉嗦的小夥伴可以直接跳過

為了代碼量小點，導入了lombok，小夥伴copy了代碼的話可能要適配一下

感興趣的小夥伴也可以copy代碼（為了不影響觀感，我把代碼統一放在後面）

下面我會分別復現split和tooSmall這兩種情況

1. split中出現單鏈<=6情況

這個場景實在是很難復現，因為

我需要通過hash值相等才能讓節點都落入同一個hash槽
但是在split時由於hash值一致，節點只會歸到同一條鏈表而不是散列在兩條鏈表中
如果不散列在兩條列表,最後的長度也不會<=6

不過沒事，我還想到了個無賴方法😁：反射

重寫hashCode和equals方法，讓所有node都進入到同一個hash槽，生成紅黑樹
通過反射修改節點hash值
插入大量無關節點，觸發HashMap擴容
擴容中，split方法根據高位bit拆分出hiHead和loHead兩條鏈表，而由於我把hash值改了，原本的節點會隨機進入鏈表，最後大概率會出現一條鏈表<=6的情況

2. removeNode中樹出現tooSmall情況

重寫hashCode和equals方法，讓所有node都進入到同一個hash槽，並生成紅黑樹
一邊刪除樹的節點，一邊對樹的情況進行打印和判斷

由於這種情況可能的節點比較多，我就只給出最少節點和最多節點的部分操作吧

2個節點

可能會有小夥伴問：畫的節點不是三個嗎，為什麼算兩個

因為是先判斷條件再刪除結點的，在刪除節點0操作時仍然不會出現tooSmall而是在刪除後滿足tooSmall條件，而在刪除2、4、8任意一個節點時進行判斷，才會觸發去樹化

5個節點

由於情景很多，我只復現了去樹化時節點為2和節點為5，感興趣的小夥伴可以copy下代碼，通過debug一個一個刪除節點來嘗試不同的樹結構

TIPS🤔：很怪，我想不到作者提出的6個節點就去樹化的情況，如果有小夥伴能夠復現也可以告訴我一下嘿😀

總結

個人認為網上大部分關於HashMap untreeify的觀點是有待商榷的，個人感覺應該是：

HashMap去樹化有兩種情況

1.在樹拆分過程中，拆完的兩棵樹分別判定，如果總節點<=6的話就去樹化

2.在去除樹節點時，通過一系列條件判定，一般會在樹節點2-6時進行去樹化

後語

第一次寫文章，沒想到這麼累orz😭，要考慮的東西太多了圖片比例深淺色主題適配文案風格啥都得想，單單寫這一篇小文章就小一天過去了，實在太佩服那些寫長文的大佬了orz💪。

btw有的小夥伴如果是背八股的時候看到這篇文章，可能會問這個考不考。

我覺得沒人會考這個的，但是我覺得不一定要面試官問你才説這個知識點，可以試着把面試官"勾引"到這個問題上來，我曾經就得手過一次：先借機點一下這個問題，接着面試官問，那剛剛這個問題你有了解過答案嗎。嘿嘿，我的回合😍！個人感覺這樣不僅能拿到一點面試主動權，而且也是一個比較加分的點，能體現出你不只是八股好手，還有去深入研究過源碼這樣嘿嘿。

最後再疊一個甲，這是我的處女文，如果文章內容出現表達不清晰/邏輯不通/內容錯誤等地方，請諒解，如果你能指出問題，非常感謝orz。

如果感覺文章不錯的話,希望能點一個贊,這是對我們的莫大支持,非常感謝嘿嘿❤️。

源代碼

/**
 * 重寫了hashcode和equals方法
 * 1.在put過程中因為hashcode相同會進入同一hash槽
 * 2.因為equals比較的是value,節點於鏈表/樹上的每個節點都不同,追加到鏈表/樹上
 */
@Getter
@AllArgsConstructor
class CustomKey {
    private Integer value;
    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof CustomKey && ((CustomKey) obj).getValue() == this.value;
    }
}

public class Test {

    public static void main(String[] args) {
        tooSmallWithFiveNode();
        tooSmallWithTwoNode();
        split();
    }

    private static Map<Object, Integer> buildMap() {
        // 由於樹化需要table大於64,預設為64,不然需要放入到11個節點時才樹化
        // 原因可參考 https://www.bilibili.com/video/BV1fh411y7R8?p=539
        Map<Object, Integer> map = new HashMap<>(64);
        // 讓0-8所有節點都在條鏈上,在8節點進入時,通過判定到當前鏈表長度(binCount)大於8,觸發樹化
        for (int i = 0; i < 9; i++) {
            CustomKey customKey = new CustomKey(i);
            map.put(customKey, i);
        }
        return map;
    }

    private static void removeNodeAndPrint(Map<Object, Integer> map, Integer i) {
        System.out.println("去掉節點" + i);
        map.remove(new CustomKey(i));
        printTreeStructure(map);
    }

    @SneakyThrows
    private static void printTreeStructure(Map<Object, Integer> map) {
        java.lang.reflect.Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);
        for (Object node : table) {
            if (node != null) {
                Class<?> treeNodeClass = Class.forName("java.util.HashMap$TreeNode");
                if (treeNodeClass.isInstance(node)) {
                    printTreeNode(treeNodeClass.cast(node), "", true);
                } else {
                    System.out.println("已經不是樹結構,此時節點數" + map.size());
                }
            }
        }
    }

    @SneakyThrows
    private static void printTreeNode(Object node, String prefix, boolean isTail) {
        Class<?> nodeClass = Class.forName("java.util.HashMap$Node");
        java.lang.reflect.Field keyField = nodeClass.getDeclaredField("key");
        java.lang.reflect.Field valueField = nodeClass.getDeclaredField("value");
        java.lang.reflect.Field leftField = node.getClass().getDeclaredField("left");
        java.lang.reflect.Field rightField = node.getClass().getDeclaredField("right");
        java.lang.reflect.Field redField = node.getClass().getDeclaredField("red");
        keyField.setAccessible(true);
        valueField.setAccessible(true);
        leftField.setAccessible(true);
        rightField.setAccessible(true);
        redField.setAccessible(true);
        Object key = keyField.get(node);
        Object value = valueField.get(node);
        Object left = leftField.get(node);
        Object right = rightField.get(node);
        boolean isRed = redField.getBoolean(node);
        System.out.println(prefix + (isTail ? "└── " : "├── ") +
                (isRed ? "紅" : "黑") + "(" + key + ", " + value + ")");
        if (left != null) {
            printTreeNode(left, prefix +
                    (isTail ? "    " : "│   ") + "L-", right == null);
        }
        if (right != null) {
            printTreeNode(right, prefix +
                    (isTail ? "    " : "│   ") + "R-", true);
        }
    }

    public static void tooSmallWithFiveNode() {
        Map<Object, Integer> map = buildMap();
        removeNodeAndPrint(map, 7);
        removeNodeAndPrint(map, 1);
        // 當前樹結構:   4
        //           /   \
        //          2     8
        //        /  \  /   \
        //       0   3  5    6
        removeNodeAndPrint(map, 0);
        // 當前樹結構:   4
        //           /   \
        //          2     8
        //           \   / \
        //            3 5   6
        // 已經出現tooSmall情況,但是這裏和樹化同理(可見buildMap方法)
        // 必須要再調用一次removeNode才能觸發條件判斷,從而去樹化
        removeNodeAndPrint(map, 2);
        // 最後去掉2節點之後，hash槽中節點數為5
    }

    public static void tooSmallWithTwoNode() {
        Map<Object, Integer> map = buildMap();
        removeNodeAndPrint(map, 7);
        removeNodeAndPrint(map, 1);
        removeNodeAndPrint(map, 6);
        removeNodeAndPrint(map, 5);
        removeNodeAndPrint(map, 3);
        // 當前樹結構:   4
        //           /   \
        //          2     8
        //         /
        //        0
        removeNodeAndPrint(map, 0);
        // 當前樹結構:    4
        //            /   \
        //           2     8
        // 已經滿足tooSmall情況,但是這裏和樹化同理(可見buildMap方法)
        // 必須要再調用一次removeNode才能觸發條件判斷,從而去樹化
        removeNodeAndPrint(map, 2);
        // 最後去掉2節點之後，hash槽中節點數為2
    }

    private static void split() {
        Map<Object, Integer> map = buildMap();
        changeHash(map);
        for (int i = 2; i < 100; i++) {
            map.put(i, i);
        }
    }

    private static void modifyHash(Object node) throws Exception {
        if (node == null) return;
        Class<?> nodeClass = Class.forName("java.util.HashMap$Node");
        // 修改hash值
        Field hashField = nodeClass.getDeclaredField("hash");
        hashField.setAccessible(true);
        hashField.setInt(node, (int) (Math.random() * 100 + 1));
        // 遞歸修改左右子樹
        Class<?> treeNodeClass = Class.forName("java.util.HashMap$TreeNode");
        Field leftField = treeNodeClass.getDeclaredField("left");
        leftField.setAccessible(true);
        Field rightField = treeNodeClass.getDeclaredField("right");
        rightField.setAccessible(true);
        modifyHash(leftField.get(node));
        modifyHash(rightField.get(node));
    }

    @SneakyThrows
    private static void changeHash(Map<Object, Integer> map) {
        java.lang.reflect.Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);
        // 這裏我把紅黑樹放table[1]中,就不做校驗直接改了
        Object root = table[1];
        Class<?> treeNodeClass = Class.forName("java.util.HashMap$Node");
        java.lang.reflect.Field hashField = treeNodeClass.getDeclaredField("hash");
        hashField.setAccessible(true);
        //  通過left和right循環獲得所有節點,並修改hash屬性
        modifyHash(treeNodeClass.cast(root));
    }
}

GEDY 日志

@gedyh

标签

JAVA (556)

數據庫 (310)

程序員 (231)

segmentfault (33)

leetcode (32)

动态

[Java]似乎很多人搞錯了HashMap紅黑樹退化？（圖文並茂） - 动态详情

前言

疊甲

正文

1. 什麼是去樹化,如何去樹化

2. 哪裏會調用去樹化

`split`中的去樹化

具體流程

`removeNode`中的去樹化

具體流程

實踐環節

1. split中出現單鏈<=6情況

2. removeNode中樹出現tooSmall情況

2個節點

5個節點

總結

後語

源代碼

Add a new 评论

GEDY 日志

@gedyh

标签

JAVA (556)

數據庫 (310)

程序員 (231)

segmentfault (33)

leetcode (32)

动态

[Java]似乎很多人搞錯了HashMap紅黑樹退化？（圖文並茂） - 动态 详情

前言

疊甲

正文

1. 什麼是去樹化,如何去樹化

2. 哪裏會調用去樹化

split中的去樹化

具體流程

removeNode中的去樹化

具體流程

實踐環節

1. split中出現單鏈<=6情況

2. removeNode中樹出現tooSmall情況

2個節點

5個節點

總結

後語

源代碼

Add a new 评论

[Java]似乎很多人搞錯了HashMap紅黑樹退化？（圖文並茂） - 动态详情

`split`中的去樹化

`removeNode`中的去樹化