1、本文主要內(nèi)容

• TreeMap及Set介紹
• TreeMap源碼解析
• Set源碼解析

2、TreeMap及Set介紹

首先我們查看Set接口，Set接口定義了add方法，remove方法，唯獨沒有定義get方法，用戶是無法單獨獲取set的某元素，只能通過遍歷獲取。

Set是接口，本期主要講述其中兩個實現(xiàn)，HashSet以及TreeSet。顧名思義，HashSet使用哈希表存儲元素，而TreeSet使用樹結(jié)構存儲元素。接下來的源碼分析可以知道，HashSet利用了成員變量HashMap存儲元素，而TreeSet使用成員變量TreeMap來存儲元素，這也是本文要介紹TreeMap的原因。

TreeMap使用紅黑樹來存儲元素，不過它實現(xiàn)的接口是Map，它存儲的是鍵值對。

3、TreeMap源碼解析

紅黑樹 前期已有介紹，本文不再重復紅黑樹添加修復以及刪除修復內(nèi)容的介紹了，不過先回憶下紅黑樹的5大特性：

• 節(jié)點非黑即紅
• 根節(jié)點為黑
• 葉結(jié)點（NIL結(jié)點，空結(jié)點）為黑
• 紅色結(jié)點的子結(jié)點一定是黑色的，也就是說沒有兩個相連的紅色結(jié)點
• 從根結(jié)點開始到每一個葉結(jié)點（NIL結(jié)點，空結(jié)點）之間的黑色結(jié)點數(shù)量相等

以上是紅黑樹的5大特性，依靠著上述特性，紅黑樹成為了相對平衡的二叉搜索樹。

//put方法，存儲元素
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        //如果根結(jié)點為空，則這是插入的第一個元素，將它設置成根結(jié)點
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    //如果比較器不為null，則使用比較器來比較key之間的大小
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            //如果key小于當前節(jié)點key，則將當前節(jié)點置為它的左子節(jié)點，反之則右子節(jié)點
            //這是二叉搜索樹的性質(zhì)，左子節(jié)點小于父節(jié)點，父節(jié)點小于右子節(jié)點
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        //如果比較器為null，則將key轉(zhuǎn)化為Comparable比較，邏輯同上一樣
        if (key == null)
            throw new NullPointerException();
        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);
    }
    //此時找到的parent即是新節(jié)點的parent節(jié)點
    Entry<K,V> e = new Entry<>(key, value, parent);
    //最后根據(jù)cmp的結(jié)果，確認新節(jié)點是左還是右子結(jié)點
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    //修復紅黑樹
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

put方法比較簡單，結(jié)合二叉搜索樹的性質(zhì)，找到正確的位置，插入新節(jié)點即可。在紅黑樹中，為了盡量少違背那5條特性，一律將新插入的節(jié)點顏色置為紅色，最后修復紅黑樹，使之仍然是一顆正常的紅黑樹，如何修復新增節(jié)點的紅黑樹，請參考以前寫的紅黑樹一文。

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    //刪除節(jié)點，所以size減一
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    //如果刪除的節(jié)點左右子樹都不為空，則需要找出中序遍歷中的后續(xù)節(jié)代替當前節(jié)點
    //后繼節(jié)點可以是左子樹中的最大結(jié)點，也可以是右子樹中的最小節(jié)點
    //最后刪除后繼節(jié)點
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    //經(jīng)過上面的判斷，此時p不可能左右子樹都存在，將存在的其中一個或者空指針，替換要被刪除的節(jié)點
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        //如果替換的節(jié)點不為空，則將替換節(jié)點代替p結(jié)點
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        //將p結(jié)點的關系斬斷
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            //如果p結(jié)點是黑色的，現(xiàn)在刪除p，性質(zhì)5會違背，所以需要修復紅黑樹
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        //如果p沒有父節(jié)點，則說明p結(jié)點為根結(jié)點，將root置空
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            //同理，p顏色為黑色，那么修復紅黑樹
            fixAfterDeletion(p);

        if (p.parent != null) {
            //p的替代節(jié)點為null，但父節(jié)點不為null的情況下，處理p父節(jié)點相關信息
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

刪除節(jié)點比添加節(jié)點稍復雜一些，尤其需要理解后繼節(jié)點的含義，在刪除節(jié)點p時，并不是直接刪除節(jié)點p，如果p的兩個子節(jié)點都存在的情況下，需要找出中序遍歷下的p的后繼節(jié)點，用后繼節(jié)點代替p節(jié)點，最后刪除的其實是后續(xù)節(jié)點。因為后繼節(jié)點肯定最多只有一個子節(jié)點，位于樹的底層，更加好刪除一些。但刪除后紅黑樹的修復更加復雜了，情況更多了。

4、Set源碼解析

Set是接口，本期主要講兩個實現(xiàn)類，HashSet和TreeSet，但閱讀源碼后才知道，這兩個實現(xiàn)類超級簡單，因為它們所有的邏輯都是基于自身的成員變量HashMap和TreeMap，存、刪除等都是調(diào)用成員變量的實現(xiàn)。

另外Set存儲的不是鍵值對，但它們的成員變量存儲的都是鍵值對，這是因為Set只用到了key值，value是一個默認值。

下面看看HashSet的存儲和刪除：

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
public boolean contains(Object o) {
    return map.containsKey(o);
}

代碼實在太簡單了，就不再介紹了?，F(xiàn)在來看看TreeSet的方法：

private transient NavigableMap<E,Object> m;
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}
public TreeSet() {
    this(new TreeMap<E,Object>());
}

由上述方法可知，TreeSet中的成員變量其實是TreeMap。

public boolean add(E e) {
    return m.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

添加和刪除同HashSet一樣。

那么HashSet和TreeSet之間有什么不同呢？TreeSet它是基于紅黑樹的，紅黑樹是二叉搜索樹，如果采用中序遍歷的話，它的key會從大到小按順序排列，所以TreeSet它是有序的。