Java 容器源碼分析之 TreeMap

TreeMap 是一種基于紅黑樹實作的 Key-Value 結構。在使用集合視圖在 HashMap 中疊代時，是不能保證疊代順序的； LinkedHashMap 使用了雙向連結清單，保證按照插入順序或者通路順序進行疊代。但是有些時候，我們可能需要按照鍵的大小進行按序疊代，或者在使用哈希表的同時希望按鍵值進行排序，這個時候 TreeMap 就有其用武之地了。 TreeMap 支援按鍵值進行升序通路，或者由傳入的比較器（Comparator）來控制。

下面基于 JDK 8 的源碼對 TreeMap 進行一個簡單的分析。

1
2
3

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

同 HashMap 一樣， TreeMap 也繼承了 AbstractMap，并實作了 Cloneable， Serializable 接口。不同的是， TreeMap 還實作 NavigableMap 接口。

NavigableMap 接口和 SortedMap

SortedMap 是一個擴充自 Map 的一個接口，對該接口的實作要保證所有的 Key 是完全有序的。

這個順序一般是指 Key 的自然序（實作 Comparable 接口）或在建立 SortedMap 時指定一個比較器（Comparator）。當我們使用集合的視角（Collection View，由 entrySet、keySet 與 values 方法提供）來疊代時，就可以按序通路其中的元素。

插入 SortedMap 中的所有 Key 的類都必須實作 Comparable 接口（或者可以作為指定的 Comparator 的參數）。在比較兩個 Key 時通過調用

k1.compareTo(k2)

(or

comparator.compare(k1, k2)

)，因而所有的 Key 都必須能夠互相比較，否則會抛出

ClassCastException

的異常。

SortedMap 中 Key 的順序必須和 equals 保持一緻（consistent with equals），

即

k1.compareTo(k2) == 0

comparator.compare(k1, k2)

) 和

k1.equals(k2)

要有相同的布爾值。（Comparable 接口的實作不強制要求這一點，但通常都會遵守。）這是因為 Map 接口的定義中，比較 Key 是通過 equals 方法，而在 SortedMap 中比較 Key 則是通過 compareTo (or compare) 方法。如果不一緻的，就破壞了 Map 接口的約定。

通過 SortedMap 可以擷取其中的一段資料，如

subMap(K fromKey, K toKey)

headMap(K toKey)

tailMap(K fromKey)

等，所有的區間操作都是左閉右開的。也可以通過

firstKey()

和

lastKey()

來擷取第一個和最後一個鍵。

NavigableMap 是 JDK 1.6 之後新增的接口，擴充了 SortedMap 接口，提供了一些導航方法（navigation methods）來傳回最接近搜尋目标的比對結果。

lowerEntry(K key) lowerKey(K key) )，小于給定 Key 的 Entry (or Key)
floorEntry(K key) floorKey(K key) )，小于等于給定 Key 的 Entry (or Key)
higherEntry(K key) higherKey(K key) )，大于給定 Key 的 Entry (or Key)
ceilingEntry(K key) ceilingKey(K key) )，大于等于給定 Key 的 Entry (or Key)

這些方法都有重載的版本，來控制是否包含端點。

subMap(K fromKey, K toKey)

headMap(K toKey)

tailMap(K fromKey)

等方法也是如此。

NavigableMap 可以按照 Key 的升序或降序進行通路和周遊。

descendingMap()

descendingKeySet()

則會擷取和原來的順序相反的集合，集合中的元素則是同樣的引用，在該視圖上的修改會影響到原始的資料。

底層結構

TreeMap 是基于紅黑樹來實作的，排序時按照鍵的自然序（要求實作 Comparable 接口）或者提供一個 Comparator 用于排序。

//比較器，沒有指定的話預設使用Key的自然序
  private final Comparator<? super K> comparator;

  //紅黑樹根節點
  private transient Entry<K,V> root;

  //樹中節點的數量
  private transient int size = 0;

  //結構化修改的次數
  private transient int modCount = 0;

TreeMap 同樣不是線程安全的，基于結構化修改的次數來實作 fail-fast 機制。因而要在多線程環境下使用時，可能需要手動進行同步，或者使用

Collections.synchronizedSortedMap

進行包裝。

TreeMap 中的紅黑樹使用的是「算法導論」中的實作，除了左右連結、紅黑辨別以外，還有一個指向父節點的連接配接。紅黑樹的具體插入及删除細節這裡不作過多的解釋，更深入的細節可以參考「算法導論」一書，不過建議先看一下 Sedgewick 的講解。

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

    /**
     * Returns the key.
     *
     * @return the key
     */
    public K getKey() {
        return key;
    }

    /**
     * Returns the value associated with the key.
     *
     * @return the value associated with the key
     */
    public V getValue() {
        return value;
    }

    /**
     * Replaces the value currently associated with the key with the given
     * value.
     *
     * @return the value associated with the key before this method was
     *         called
     */
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        //Key 和 Value都要 equals
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }

    //哈希值的計算，Key和Value的哈希值進行位異或
    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;
    }
}

添加及更新操作

為了維持有序，添加及更新的代價較高，複雜度為 O(log(n)) 。插入節點後需要修複紅黑樹，使其恢複平衡狀态，該操作在此不作介紹。

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) { //根節點為空
        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
    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); //Key 存在，更新value
        } while (t != null);
    }
    else { //比較器為null，Key 必須實作 Comparable 接口
        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); //Key 存在，更新value
        } while (t != null);
    }
    //Key 不存在，建立節點，插入二叉樹
    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;
}

删除

從紅黑樹中删除一個節點比插入更為複雜，這裡不作展開。

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

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    // 被删除節點的左右子樹都不為空
    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.
    // 左子節點存在，則 replacement 為左子節點，否則為右子節點
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) { //至少一個子節點存在
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null) //p 就是根節點
            root = replacement;
        else if (p == p.parent.left)//p 是父節點的左子節點
            p.parent.left  = replacement;
        else//p 是父節點的右子節點
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 修複紅黑樹
    } else if (p.parent == null) { // return if we are the only node.
        // 沒有父節點，則該節點是樹中唯一的節點
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        //沒有子節點
        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;
        }
    }
}

查找

紅黑樹也是排序二叉樹，按照排序二叉樹的查找方法進行查找。複雜度為 O(log(n)) 。

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null) //定制的比較器
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    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;
}

//使用比較器進行查找
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);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

判斷是否包含 key 或 value :

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

public boolean containsValue(Object value) {
    //從第一個節點開始，不斷查找後繼節點
    for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
        if (valEquals(value, e.value))
            return true;
    return false;
}

導航方法

NaviableMap 接口支援一系列的導航方法，有 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() 等，它們的實作原理都是類似的，差別在于如何在排序的二叉樹中查找到對應的節點。

以 lowerEntry() 和 floorEntry() 為例：

//小于給定的Key
public Map.Entry<K,V> lowerEntry(K key) {
    return exportEntry(getLowerEntry(key));
}

final Entry<K,V> getLowerEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        //1. 如果節點 p 小于 key
        if (cmp > 0) { 
            //1.1 節點 p 有右子樹，則在右子樹中搜尋
            if (p.right != null)
                p = p.right;
            //1.2 節點 p 沒有右子樹，找到目标
            else
                return p;
        //2. 節點 p 大于等于 key
        } else {
            //2.1 節點 p 有左子樹，則在左子樹中繼續搜尋
            if (p.left != null) {
                p = p.left;
            //2.2 節點 p 無左子樹，找出 p 的前驅節點，并傳回
            //前驅節點要麼不存在，要麼就是小于 key 的最大節點
            //因為從根節點一直周遊到 p，那麼之前經過的所有節點都是大于等于 key 的
            //且 p 沒有左子樹，即 p 是大于等于 key 的所有節點中最小的
            //則 p 的前驅一定是查找的目标
            } else {
                //查找前驅節點
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

public K lowerKey(K key) {
    return keyOrNull(getLowerEntry(key));
}

//小于等于
public Map.Entry<K,V> floorEntry(K key) {
    return exportEntry(getFloorEntry(key));
}

//和 getLowerEntry 類似，相等時的處理不同
final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else if (cmp < 0) {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;

    }
    return null;
}

查找的過程可以和前驅節點的方法進行類比。 TreeMap 并沒有直接暴露 getLowerEntry() 方法，而是使用

exportEntry(getLowerEntry(key))

進行了一次包裝。看似“多此一舉”，實際上是為了防止對節點進行修改。SimpleImmutableEntry 類可以看作不可修改的 Key-Value 對，因為成員變量 key 和 value 都是 final 的。

即通過暴露出來的接口 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry() 是不可以修改擷取的節點的，否則會抛出異常。

/**
 * Return SimpleImmutableEntry for entry, or null if null
 */
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
    return (e == null) ? null :
        new AbstractMap.SimpleImmutableEntry<>(e);
}

//AbstractMap.SimpleImmutableEntry
public static class SimpleImmutableEntry<K,V>
    implements Entry<K,V>, java.io.Serializable
{
    private static final long serialVersionUID = 7138329143949025153L;

    private final K key;
    private final V value;

    public SimpleImmutableEntry(Entry<? extends K, ? extends V> entry) {
        this.key   = entry.getKey();
        this.value = entry.getValue();
    }

    public V setValue(V value) {
        throw new UnsupportedOperationException();
    }
    //....
    //
}

pollFirstEntry() 、 pollLastEntry() 擷取第一個和最後一個節點，并将它們從紅黑樹中删除。

public Map.Entry<K,V> pollFirstEntry() {
    Entry<K,V> p = getFirstEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        deleteEntry(p);
    return result;
}

public Map.Entry<K,V> pollLastEntry() {
    Entry<K,V> p = getLastEntry();
    Map.Entry<K,V> result = exportEntry(p);
    if (p != null)
        deleteEntry(p);
    return result;
}

周遊

可以按照鍵的順序周遊對 TreeSet 進行周遊，因為底層使用了紅黑樹來保證有序性，疊代器的實作就是按序通路排序二叉樹中的節點。

先看一些内部抽象類

PrivateEntryIterator

，它是 TreeMap 中所有疊代器的基礎：

abstract class PrivateEntryIterator<T> implements Iterator<T> {
    Entry<K,V> next;
    Entry<K,V> lastReturned;
    int expectedModCount;

    PrivateEntryIterator(Entry<K,V> first) {
        expectedModCount = modCount;
        lastReturned = null;
        next = first;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        next = successor(e); //後繼節點
        lastReturned = e;
        return e;
    }

    final Entry<K,V> prevEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        next = predecessor(e); //前驅節點
        lastReturned = e;
        return e;
    }

    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // deleted entries are replaced by their successors
        if (lastReturned.left != null && lastReturned.right != null)
            next = lastReturned;
        deleteEntry(lastReturned);
        expectedModCount = modCount;
        lastReturned = null;
    }
}

因為紅黑樹自身就是有序的，疊代是隻要從第一個節點不斷擷取後繼節點即可。當然，逆序時則是從最後一個節點不斷擷取前驅節點。通過疊代器通路時基于 modCount 實作對并發修改的檢查。

在排序二叉樹中擷取前驅和後繼節點的方法如下：

//後繼節點
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        //右子樹存在，則取右子樹的最小節點
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        //右子樹不存在
        //若父節點為null，則該節點是最大節點（根節點，且無右子樹），無後繼，傳回null
        //若目前節點是父節點的左子節點，直接傳回父節點
        //若目前節點是父節點的右子節點，則目前節點是以父節點為根的子樹中最大的節點
        Entry<K,V> p = t.parent; //父節點
        Entry<K,V> ch = t;//目前節點
        while (p != null && ch == p.right) {
            //是右子節點，向上疊代，直到是左子節點
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

//前驅節點，同後繼節點處理邏輯一緻，左右颠倒
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) {
        //左子樹存在，則取左子樹的最小節點
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else {
        //左子樹不存在
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

其它方法

TreeMap 中還實作了一些其它的方法，如區間操作: headMap(), tailMap(), subMap() ；擷取逆序的 map：

descendingMap()

descendingKeySet()

。隻要了解了前面介紹的各種操作的原理，再來看這些方法的實作應該也不難了解。由于篇幅太長，這裡就不再介紹了。

小結

TreeMap 是基于紅黑樹實作的一種 Key-Value 結構，最大的特點在于可以按照 Key 的順序進行通路，要求 Key 實作 Comparable 接口或傳入 Comparator 作為比較器。因為基于紅黑樹實作，TreeMap 内部在實作插入和删除操作時代價較高。

TreeMap 實作了 NavigableMap 接口，可以支援一系列導航方法，有 firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry() ；還可以支援區間操作擷取 map 的一部分，如 subMap(), headMap(), tailMap(K fromKey) 。除此以外， TreeMap 還支援通過 descendingMap() 擷取和原來順序相反的 map。

如果 TreeMap 沒有使用自定義的 Comparator，則是不支援鍵為 null 的，因為調用 compareTo() 可能會發生異常；如果自定義的比較器可以接受 null 作為參數，那麼是可以支援将 null 作為鍵的。

TreeMap 不是線程安全的，多線程情況下要手動進行同步或使用

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

。

熬夜不易,點選請老王喝杯烈酒！！！！！！！

Java 容器源碼分析之 TreeMap

NavigableMap 接口和 SortedMap

底層結構

添加及更新操作

删除

查找

導航方法

周遊

其它方法

小結

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method