1 TreeMap基本介紹 Java TreeMap實現了SortedMap介面，也就是說會按照key的大小順序對Map中的元素進行排序 key大小的評判可以通過其本身的自然順序(natural ordering)，也可以通過構造時傳入的比較器(Comparator)。 TreeMap底層通過紅黑樹 ...

1 TreeMap基本介紹
2 紅黑樹數據結構回顧
3 成員變數
4 內部類Entry
5 構造函數
6 重要方法分析
7 解惑：
- - 1 TreeMap支持key自定義排序，而紅黑樹對key的固定的排序規則，兩者如何相容的?

1 TreeMap基本介紹

Java TreeMap實現了SortedMap介面，也就是說會按照key的大小順序對Map中的元素進行排序
key大小的評判可以通過其本身的自然順序(natural ordering)，也可以通過構造時傳入的比較器(Comparator)。
TreeMap底層通過紅黑樹實現
TreeMap是非同步的。可以通過如下方式將TreeMap包裝成同步的：SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
TreeMap 跟 HashMap是兩種不同的結構，TreeMap沒有使用hash相關概念

2 紅黑樹數據結構回顧

每個節點顏色不是黑色，就是紅色

根節點是黑色的

紅色節點不能連續

對於每個節點，從該節點到其樹尾端的簡單路徑上，均包含相同數目的黑色節點

3 成員變數

    private final Comparator<? super K> comparator;  //排序器，如果空，按照key的字典順序來排序（升序）；comparator為空時用Comparable的排序介面
    private transient Entry<K,V> root; //根節點
    private transient int size = 0; //樹中entry個數 ，即紅黑樹大小
    private transient int modCount = 0;  //數結構被修改的次數的
     /**
     * Fields initialized to contain an instance of the entry set view
     * the first time this view is requested.  Views are stateless, so
     * there's no reason to create more than one.
     */
    private transient EntrySet entrySet;
    private transient KeySet<K> navigableKeySet;
    private transient NavigableMap<K,V> descendingMap;
     /**
     * Dummy value serving as unmatchable fence key for unbounded
     * SubMapIterators
     */
    private static final Object UNBOUNDED = new Object();
    private static final boolean RED   = false; //紅節點 預設false
    private static final boolean BLACK = true;  // 黑節點 預設true

4 內部類Entry

它是組成樹的節點的類型

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;   // key
        V value;  //value
        Entry<K,V> left; //左孩子
        Entry<K,V> right;  //右孩子
        Entry<K,V> parent;  //父節點
        boolean color = BLACK;  //預設黑色

        //根據 key  value 父節點創建新節點
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }

        public K getKey() {
            return key;
        }
        public V getValue() {
            return value;
        }

     //替換value，返回舊value
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        // 重寫equals方法：key 和 value的引用都相等
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;

            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }
        
        //重寫hashCode方法，返回 key 和 value的hashCode 的異或運算結構
        public int hashCode() {
            int keyHash = (key==null ? 0 : key.hashCode());
            int valueHash = (value==null ? 0 : value.hashCode());
            return keyHash ^ valueHash;
        }

        public String toString() {
            return key + "=" + value;
        }
    }

5 構造函數

    // 構造函數一：不指定排序器。按照key的字典順序來排序（升序）
    public TreeMap() {
        comparator = null;
    }
    // 構造函數二：指定排序器
     public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    //構造函數三：構造並返回跟參數m有相同鍵值映射結構的treeMap（m變為紅黑樹）
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
     //構造函數四：構造並返回跟參數m（有序的）有相同鍵值映射結構的treeMap
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

Comparator Integer類型倒序排序

    public static void main(String[] args) {
        TreeMap treeMap = new TreeMap<Integer ,String>(new ComparatorObj());
        treeMap.put(2,"ss");
        treeMap.put(3,"sss");
        System.out.println(treeMap);
    }

    static class ComparatorObj implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1; //倒序排序
        }
    }

輸出結果：

2022-07-11 18:02:23,871 [INFO] main: {3=sss, 2=ss}

6 重要方法分析

6.1 get方法分析

（實際調用getEntry(Object key)）

get(Object key)方法是對介面Map的方法實現
get(Object key)方法轉為對getEntry(Object key)方法的實現分析：演算法思想是根據key的自然順序(或者比較器順序)對二叉查找樹進行查找，直到找到滿足k.compareTo(p.key) == 0的entry，再返回entry的value。

源碼分析如下：

public V get(Object key) {
    Entry<K,V> p = getEntry(key);  //根據key找到entry，再返回其value
    return (p==null ? null : p.value);
}
//重點分析該方法
final Entry<K,V> getEntry(Object key) {
    if (comparator != null)
        return getEntryUsingComparator(key); 
    if (key == null)
        throw new NullPointerException();  //key非空校驗
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;  //自然順序，使用Comparable的排序介面
    Entry<K,V> p = root; 
    while (p != null) {  //從根節點開始 迴圈遍歷
        int cmp = k.compareTo(p.key);  //compareTo：左邊減去右邊
        if (cmp < 0) //參數key值小於父節點key
            p = p.left; //取左子節點
        else if (cmp > 0)
            p = p.right;  //參數key值大於父節點key，取右子節點
        else
            return p;  //key相等，則直接返回當前entry
    }
    return null;
}

查詢方法說明：

在while迴圈外，創建動態游標節點，游標首次指向root節點，以游標!=null作為迴圈條件

在while迴圈內，根據compareTo結果，取游標的左子節點或右子節點，作為新的游標

找到滿足k.compareTo(p.key) == 0的entry，退出迴圈

getEntryUsingComparator源碼：

//提供自定義排序器的查詢找方法，原理類似
final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key); //cpr.compare 第一個參數減去第二個參數
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

6.2 put方法分析

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 情況一：根節點為空，將當前key value作為root
    if (t == null) {
        compare(key, key); //key為null則拋異常
        root = new Entry<>(key, value, null);//初始化root
        size = 1;  //葉子個數+1
        modCount++; // 結構修改次數自增
        return null;  //新葉子，所以old value 為空
    }
    // 情況二：如果找到key相同的，則更新value ，過程類似get方法
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    //情況三：沒有相同的key，則添加新葉子。
    //經過上面的兩種遍歷，完成了二分法查找，找到適合插入的地方：parent。
    Entry<K,V> e = new Entry<>(key, value, parent); //創建新的entry
    //確定新增葉子作為parent的左孩子還是右孩子，插入的動作完成
    if (cmp < 0)  
        parent.left = e;  
    else
        parent.right = e;
    fixAfterInsertion(e);  //插入完成後，對二叉樹進行調整
    size++;
    modCount++;
    return null;
}
//這個方法實際上是對key做null檢查，如果是null會拋出異常（測試代碼驗證過）
public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
  }

put方法說明：

如果root為空，則新增的entry作為root

遍歷搜索是否存在相同的key，存在則替換value。這過程也是二叉排序樹的二分查找法：找到了作為插入點的parent。

插入操作：找到parent，並將其left或者right指向新的entry。

如果是插入，則需要對紅黑樹進行結構調整。（插入：節點預設為紅色，root節點：設置為黑色，覆蓋節點：顏色保持不變）

維護成員變數：size，modCount。

6.3 插入調整函數fixAfterInsertion()解析

/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;  //新增節點預設為紅色，再進行規則判斷
    // 從樹末端開始遍歷：父節點是紅色，則需要對樹進行調整
    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;  //在遍歷外面，確保root一定是黑色
}

方法說明：

新增的節點預設為紅色，並從樹末端往上遍歷
如果新增節點的父親是紅色，則需要進行結構調整
結構調整這部分有點複雜，回頭再深入理解todo

6.4 刪除方法remove()解析

知識回顧：
二叉排序樹的刪除過程：（情況一，treeMap用後繼代替，其實用前驅或者後繼是一樣的）

源碼如下：

// 調用getEntry(key)找到對應entry，調用deleteEntry 刪除節點
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

//執行刪除操作
private void deleteEntry(Entry<K,V> p) {
     //先對全局變數modCount、size 進行調整
    modCount++;
    size--;
    
    //情況1：左右孩子都不為空：後繼節點代替
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p); //尋找後繼 （另外分析）
        //將刪除點的key、value、引用分別更新為代替節點
        p.key = s.key;  
        p.value = s.value;
        p = s;   //
    }

    //情況2：有1個孩子
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        replacement.parent = p.parent;  //左孩子父親更新刪除節點的父親
        //父親為root，則後繼變為新的root
        if (p.parent == null)
            root = replacement;  
        //左孩子頂上
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        //右孩子頂上
        else
            p.parent.right = replacement;

        // 刪除節點的left、right、parent置空：被移除出樹
        p.left = p.right = p.parent = null;

        // 刪除黑色節點：調整結構
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { //刪除root節點
        root = null;
    } else { //  情況1：沒孩子
        if (p.color == BLACK)
            fixAfterDeletion(p);
        //將父親的左孩子或者有孩子清空
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

刪除說明：

刪除過程遵從二叉排序樹的刪除特點（1、有一個孩子則孩子頂上；2兩個孩子就用後繼頂上，沒有孩子則直接移除）

節點刪除，即left、right、parent置空；刪除後，需要更新父親節點的的左孩子或右孩子

考慮是否需要更新全局變數root節點

只有刪除點是BLACK的時候，才會觸發調整函數，因為刪除RED節點不會破壞紅黑樹的任何約束，而刪除BLACK節點會破壞規則4。

6.5 刪除調整函數fixAfterDeletion()解析

private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }

            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // symmetric
            Entry<K,V> sib = leftOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK &&
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }

    setColor(x, BLACK);
}

說明：結構調整這部分有點複雜，回頭再深入理解todo

6.6 尋找後繼函數successor()解析

//尋找任意節點後繼
    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
            //情況1：右孩子不為空，向後代遍歷：找到右孩子中孫子最小的那個節點（不斷尋找left，直至為空）
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            while (p.left != null)
                p = p.left;
            return p;
        } else {
        // 情況2：右孩子為空，向祖先遍歷，當任意節點是它父親的左孩子時，則該節點的父親為t的後繼
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
    }

尋找後繼的演算法說明：
對於任意k：

情況一：k的右孩子不為空，向後代遍歷：找到右孩子的子孫子中輩分最低的左孩子（不斷尋找left，直至為空）
情況二：key的右孩子為空，向祖先遍歷：當任意節點是它父親的左孩子時，則該節點的父親為t的後繼

右孩子不為空的後繼尋找：

右孩子為空為空的後繼尋找：

7 解惑：

1 TreeMap支持key自定義排序，而紅黑樹對key的固定的排序規則，兩者如何相容的?

支持key自定義排序：指通過自定義的排序器，計算出任意key相對其它key的大小關係
紅黑樹對key的固定的排序：指按照紅黑樹的數據結構（二叉排序樹+紅黑節點規則），來組織key的樹狀結構，其中二叉排序的大小關係是根據排序器的計算出來的
兩者不衝突

3、TreeMap源碼解析