原文鏈接-Java TreeMap工作原理及實(shí)現(xiàn)

• 更多相關(guān)文章見(jiàn)筆者博客

1. 概述

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.

之前已經(jīng)學(xué)習(xí)過(guò)HashMap和LinkedHashMap了，HashMap不保證數(shù)據(jù)有序，LinkedHashMap保證數(shù)據(jù)可以保持插入順序，而如果我們希望Map可以保持key的大小順序的時(shí)候，我們就需要利用TreeMap了。

TreeMap<Integer, String> tmap = new TreeMap<Integer, String>();
tmap.put(1, "語(yǔ)文");
tmap.put(3, "英語(yǔ)");
tmap.put(2, "數(shù)學(xué)");
tmap.put(4, "政治");
tmap.put(5, "歷史");
tmap.put(6, "地理");
tmap.put(7, "生物");
tmap.put(8, "化學(xué)");
for(Entry<Integer, String> entry : tmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

image

使用紅黑樹(shù)的好處是能夠使得樹(shù)具有不錯(cuò)的平衡性，這樣操作的速度就可以達(dá)到log(n)的水平了。具體紅黑樹(shù)的實(shí)現(xiàn)不在這里贅述，可以參考數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)、wikipedia-紅黑樹(shù)等的實(shí)現(xiàn)

2. put函數(shù)

Associates the specified value with the specified key in this map.If the map previously contained a mapping for the key, the old value is replaced.

如果存在的話，old value被替換；如果不存在的話，則新添一個(gè)節(jié)點(diǎn)，然后對(duì)做紅黑樹(shù)的平衡操作。

    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;
        //如果該節(jié)點(diǎn)存在，則替換值直接返回
        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);
        }
        // 如果該節(jié)點(diǎn)未存在，則新建
        Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // 紅黑樹(shù)平衡調(diào)整
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

3. get函數(shù)

get函數(shù)則相對(duì)來(lái)說(shuō)比較簡(jiǎn)單，以log(n)的復(fù)雜度進(jìn)行get

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;
        // 按照二叉樹(shù)搜索的方式進(jìn)行搜索，搜到返回
    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;
}
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

4. successor后繼

TreeMap是如何保證其迭代輸出是有序的呢？其實(shí)從宏觀上來(lái)講，就相當(dāng)于樹(shù)的中序遍歷(LDR)。我們先看一下迭代輸出的步驟

for(Entry<Integer, String> entry : tmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

根據(jù)The enhanced for statement，for語(yǔ)句會(huì)做如下轉(zhuǎn)換為：

for(Iterator<Map.Entry<String, String>> it = tmap.entrySet().iterator() ; tmap.hasNext(); ) {
    Entry<Integer, String> entry = it.next();
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

在it.next()的調(diào)用中會(huì)使用nextEntry調(diào)用successor這個(gè)是后繼的重點(diǎn)，具體實(shí)現(xiàn)如下：

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        // 有右子樹(shù)的節(jié)點(diǎn)，后繼節(jié)點(diǎn)就是右子樹(shù)的“最左節(jié)點(diǎn)”
        // 因?yàn)椤白钭笞訕?shù)”是右子樹(shù)的最小節(jié)點(diǎn)
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 如果右子樹(shù)為空，則尋找當(dāng)前節(jié)點(diǎn)所在左子樹(shù)的第一個(gè)祖先節(jié)點(diǎn)
        // 因?yàn)樽笞訕?shù)找完了，根據(jù)LDR該D了
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        // 保證左子樹(shù)
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

怎么理解這個(gè)successor呢？只要記住，這個(gè)是中序遍歷就好了，L-D-R。具體細(xì)節(jié)如下：

a. 空節(jié)點(diǎn)，沒(méi)有后繼

b. 有右子樹(shù)的節(jié)點(diǎn)，后繼就是右子樹(shù)的“最左節(jié)點(diǎn)”

c. 無(wú)右子樹(shù)的節(jié)點(diǎn)，后繼就是該節(jié)點(diǎn)所在左子樹(shù)的第一個(gè)祖先節(jié)點(diǎn)

a.好理解，不過(guò)b, c，有點(diǎn)像繞口令啊，沒(méi)關(guān)系，上圖舉個(gè)例子就懂了

有右子樹(shù)的節(jié)點(diǎn)，節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，肯定在右子樹(shù)中，而右子樹(shù)中“最左”的那個(gè)節(jié)點(diǎn)則是右子樹(shù)中最小的一個(gè)，那么當(dāng)然是右子樹(shù)的“最左節(jié)點(diǎn)”，就好像下圖所示：

image

無(wú)右子樹(shù)的節(jié)點(diǎn)，先找到這個(gè)節(jié)點(diǎn)所在的左子樹(shù)(右圖)，那么這個(gè)節(jié)點(diǎn)所在的左子樹(shù)的父節(jié)點(diǎn)(綠色節(jié)點(diǎn))，就是下一個(gè)節(jié)點(diǎn)。

image

相關(guān)鏈接

TreeMap (Java Platform SE 8)

淺談算法和數(shù)據(jù)結(jié)構(gòu): 九 平衡查找樹(shù)之紅黑樹(shù)

Java提高篇（二七）——-TreeMap

數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)

wikipedia-紅黑樹(shù)

Red-Black Trees How TreeMap searches successor for given Entry?