java 集合源碼探究之 treemap 如何保證有序，put過程， get過程。

TreeMap

PUT 過程

public V put(K key, V value) {
        // 目前的根節點
        Entry<K,V> t = root;
        // 第一次添加節點
        if (t == null) {
            // 檢查類型和null值
            compare(key, key); // type (and possibly null) check
            // 建立一個  Entry節點, 作為 root 節點
            root = new Entry<>(key, value, null);
            // map中節點的數量
            size = 1;
            // 修改次數
            modCount++;
            return null;
        }
        // 往後都是 非首次添加節點了
        int cmp;
        Entry<K,V> parent;
        // tree map的比較器
        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 {
             //沒有指定節點之間的比較器
            // 檢查 key 是否 null值 
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            // 得到key的比較器
                Comparable<? super K> k = (Comparable<? super K>) key;
            // 進入循環,周遊整棵樹, 尋找存放位置
            do {
                // 此時 t 為根節點
                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 的位置
        // 建立一個 Entry
        Entry<K,V> e = new Entry<>(key, value, parent);
        // 小于 添加左子樹
        if (cmp < 0)
            parent.left = e;
        // 大于 添加右子樹
        else
            parent.right = e;
        // 插入之後 調整方法
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
           

Entry

内置存儲節點,是使用樹型的結構

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }
           

調整樹過程

fixAfterInsertion

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;
    }
           

GET過程

public V get(Object key) {
        // 得到節點
        Entry<K,V> p = getEntry(key);
        // 傳回節點的 value 
        return (p==null ? null : p.value);
    }
           

getEntry(Object key)

final Entry<K,V> getEntry(Object key) {
        //  有指定的比較器的話, 就是用指定的比較器來獲得元素
        if (comparator != null)
            return getEntryUsingComparator(key);
        // 抛出異常
        if (key == null)
            throw new NullPointerException();
        // 得到比較器
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        // p 是根節點
        Entry<K,V> p = root;
        while (p != null) {
            // 得到比較的結果
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                // 小于 周遊左子樹
                p = p.left;
            else if (cmp > 0)
                // 大于 周遊右子樹
                p = p.right;
            else
                // 相等就直接傳回目前節點
                return p;
        }
        // 無元素
        return null;
    }
           

getEntryUsingComparator(Object key)

final Entry<K,V> getEntryUsingComparator(Object key) {
        @SuppressWarnings("unchecked")
            K k = (K) key;
        // 得到比較器
        Comparator<? super K> cpr = comparator;
        // 比較器不為空
        if (cpr != null) {
            // p 是根節點
            Entry<K,V> p = root;
            while (p != null) {
                 // 得到比較的結果
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                // 小于 周遊左子樹
                    p = p.left;
                else if (cmp > 0)
                // 大于 周遊右子樹
                    p = p.right;
                else
                    // 相等直接傳回
                    return p;
            }
        }
        // 無此節點
        return null;
    }
           

總結

• 是用樹作為存儲機關
  • 内部紅黑樹
• 是一個有序的map
• 可以指定元素的比較器
  • 也可以不指定