1 TreeMap基本介紹
2 紅黑樹資料結構回顧
3 成員變數
4 內部類Entry
5 建構式
6 重要方法分析
- 6.1 get方法分析
- 6.2 put方法分析
- 6.3 插入調整函式fixAfterInsertion()決議
- 6.4 洗掉方法remove()決議
- 6.5 洗掉調整函式fixAfterDeletion()決議
- 6.6 尋找后繼函式successor()決議
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 = https://www.cnblogs.com/knowledgeispower/p/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 = https://www.cnblogs.com/knowledgeispower/p/p.value;
    deleteEntry(p);
    return oldValue;
}

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

    //情況2：有1個孩子
    Entry 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的樹狀結構，其中二叉排序的大小關系是根據排序器的計算出來的
兩者不沖突

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/544172.html

標籤：Java

上一篇：關于靜態代碼塊和匿名代碼塊以及結構體在程式運行程序中的呼叫順序實驗（續）

下一篇：ElasticSearch系列01

3、TreeMap原始碼決議