概述

本文是記錄學(xué)習(xí)惭聂，文中有理解錯(cuò)誤的地方蒲肋，請(qǐng)指出共同探討改正。
前面介紹了HashMap巧颈，因?yàn)镠ashMap是一種無(wú)序的存儲(chǔ)集合畦木，當(dāng)某些時(shí)候需要特定的存儲(chǔ)順序的時(shí)候，就只能另尋他法了砸泛，在jdk中為我們提供了LinkedHashmap和TreeMap以供我們使用十籍，本文先介紹TreeMap蛆封。
TreeMap和HashMap一樣都是繼承至AbstractMap，并且實(shí)現(xiàn)了NavigableMap()勾栗，TreeMap是在NavigableMap基礎(chǔ)上基于紅黑樹(shù)的實(shí)現(xiàn)惨篱，他是一種順序的存儲(chǔ)結(jié)構(gòu)。
TreeMap數(shù)據(jù)結(jié)構(gòu)為Entry围俘，Entry簡(jiǎn)單實(shí)現(xiàn)如下：

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left; // 左節(jié)點(diǎn)
    Entry<K,V> right; // 右節(jié)點(diǎn)
    Entry<K,V> parent; // 父節(jié)點(diǎn)
    boolean color = BLACK;
    // ... 其他代碼省略
}

常用變量

• root
  root的定義為：private transient Entry<K,V> root砸讳，可以理解為一個(gè)短暫的 Entry
• size
  size的定義為：private transient int size = 0， 記錄樹(shù)中的數(shù)量
• modCount
  modCount的定義為：private transient int modCount = 0界牡，記錄結(jié)構(gòu)性發(fā)生變化的次數(shù)簿寂，比如刪除節(jié)點(diǎn)。
• comparator
  comparator的定義為：private final Comparator<? super K> comparator,用于維護(hù)此樹(shù)形圖中的順序欢揖，如果使用其鍵的自然順序陶耍，則comparator為空。

構(gòu)造方法

public TreeMap()

代碼如下：

public TreeMap() {
    comparator = null;
}

構(gòu)造方法她混，沒(méi)有指定comparator烈钞，所以使用它的自然順序排序。

public TreeMap(Comparator<? super K> comparator)

代碼如下：

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

構(gòu)造方法坤按，使用給定的comparator規(guī)則排序

public TreeMap(Map<? extends K, ? extends V> m)

代碼如下：

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

構(gòu)造一個(gè)新的 tree map毯欣，其中包含給定map的相同的映射，根據(jù)key的自然順序進(jìn)行排序臭脓，插入的新map的所有key必須實(shí)現(xiàn) Comparable接口

public TreeMap(SortedMap<K, ? extends V> m)

實(shí)現(xiàn)代碼如下：

public TreeMap(SortedMap<K, ? extends V> m) {
    // 將SoretdMap的排序方法賦給comparator
    comparator = m.comparator();
    try {
        // 構(gòu)建 tree map
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

構(gòu)造一個(gè)新的 tree map酗钞，其中包含給定map的相同的映射，并且使用給定的 sorted map 的排序方式進(jìn)行排序

常用方法

put() 插入

插入方法是我們開(kāi)發(fā)常用的方法来累，接下來(lái)看看砚作，TreeMap的put方法具體是怎么實(shí)現(xiàn)的，為了方便閱讀部分注釋直接寫(xiě)在了代碼中嘹锁，代碼如下：

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        // 比較連個(gè)key值葫录，使用此時(shí)正確的compare方法。
        compare(key, key); // type (and possibly null) check
        // new 一個(gè) entry節(jié)點(diǎn)
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++; // 記錄結(jié)構(gòu)變化的次數(shù)
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        // 設(shè)置value到特定的位置
        do {
            parent = t;
            cmp = cpr.compare(key, t.key); // 比較 key 和 t.key
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value); // cmp=0领猾，設(shè)置value
        } while (t != null);
    }
    else {
        if (key == null) // 不允許key為null
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        // 設(shè)置value到特定的位置
        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);
    }
    // 走到了這里米同， 說(shuō)明了，cmp != 0摔竿，沒(méi)有找到對(duì)應(yīng)的key值面粮，新建一個(gè)entry e，并將e放在相應(yīng)的parent左右節(jié)點(diǎn)下面
    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;
}

put方法還是比較容易能理解的继低，首先判斷root是否為空熬苍，如果沒(méi)空，直接new Entry即可袁翁。不為空柴底，根據(jù)comparator的值钱磅，查找要設(shè)置value的位置。如果沒(méi)有找到匹配的key似枕，則新建一個(gè)Entry e，再根據(jù)cmp的值年柠，將Entry e設(shè)置到對(duì)應(yīng)的位置即可凿歼。

get 獲取Entry

根據(jù)key獲取一個(gè)Entry，具體實(shí)現(xiàn)如下：

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        // 如果默認(rèn)comparator不為空冗恨，調(diào)用getEntryUsingComparator方法
        return getEntryUsingComparator(key);
    if (key == null) // key不允許為null
        throw new NullPointerException();
    // 走到了這里答憔，說(shuō)明comparator為空，使用默認(rèn)排序方法掀抹。
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    // 將當(dāng)前root賦值給p
    Entry<K,V> p = root;
    // 循環(huán)遍歷p
    while (p != null) {
        // 通過(guò)compareTo方法比較key與p的key
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left; // 將p.left賦值給p
        else if (cmp > 0)
            p = p.right; // 將p.right賦值給p
        else
            return p; // 說(shuō)明key與p.key相等虐拓，返回當(dāng)前p節(jié)點(diǎn)
    }
    // 如果p節(jié)點(diǎn)中，沒(méi)有找到對(duì)應(yīng)的key傲武，返回null
    return null;
}

獲取Entry的方法的過(guò)程大致為：根據(jù)comparator獲取Entry蓉驹，其實(shí)就是遍歷root，查找比較key揪利，有匹配的返回對(duì)應(yīng)的entry即可态兴。注意key值不允許為空，會(huì)拋出空指針異常疟位。
在獲取Entry的方法中瞻润，如果comparator不為空，則使用getEntryUsingComparator方法獲取甜刻。實(shí)現(xiàn)如下：

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) {
            // 通過(guò)自定義的compare方法比較key與p的key
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left; // 將p.left賦值給p
            else if (cmp > 0)
                p = p.right; // 將p.right賦值給p
            else
                return p;// 說(shuō)明key與p.key相等绍撞，返回當(dāng)前p節(jié)點(diǎn)
        }
    }
    // 如果p節(jié)點(diǎn)中，沒(méi)有找到對(duì)應(yīng)的key得院，返回null
    return null;
}

實(shí)現(xiàn)過(guò)程和上面差不多傻铣，只是比較key值的方法換了而已。

firstKey 獲取第一個(gè)key

public K firstKey() {
    // getFirstEntry得到第一個(gè)Entry尿招，調(diào)用key(),得到key值矾柜。
    return key(getFirstEntry());
}
該方法比較簡(jiǎn)單，就不細(xì)說(shuō)了就谜。

lastKey 獲取最后一個(gè)key

public K lastKey() {
    // getLastEntry得到最后一個(gè)Entry怪蔑，調(diào)用key(),得到key值。
    return key(getLastEntry());
}

lastKey的具體實(shí)現(xiàn)過(guò)程在getLastEntry中丧荐，實(shí)現(xiàn)如下：

final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

實(shí)現(xiàn)方法和firstKey差不多缆瓣。一直找到最右節(jié)點(diǎn)為止。

remove 刪除

具體代碼實(shí)現(xiàn)如下：

// 根據(jù)key刪除entry節(jié)點(diǎn)虹统，返回value
public V remove(Object key) {
    // 根據(jù)key得到對(duì)應(yīng)entry節(jié)點(diǎn)
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    // 刪除entity弓坞，后面會(huì)介紹
    deleteEntry(p);
    return oldValue;
}

首先根據(jù)key查找Entry隧甚，如果不為空，則調(diào)用deleteEntry方法刪除渡冻。
deleteEntry方法是實(shí)現(xiàn)如下：

/**
 * Delete node p, and then rebalance the tree.
 * 刪除節(jié)點(diǎn)p戚扳，從新平衡樹(shù)
 */
private void deleteEntry(Entry<K,V> p) {
    // 增加一次結(jié)構(gòu)發(fā)生變化的次數(shù)
    modCount++;
    // 此TreeMap節(jié)點(diǎn)數(shù)量減一
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    // 被刪除節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都不為空，那么就用 p節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)代替 p 節(jié)點(diǎn)
    if (p.left != null && p.right != null) {
        // successor: 得到p后面的節(jié)點(diǎn)
        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為替代節(jié)點(diǎn)族吻，如果p的左節(jié)點(diǎn)不為空帽借，則為p的左節(jié)點(diǎn)，反之為p的右節(jié)點(diǎn)
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    // 如果replacement不為空
    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null) 
            // 如p沒(méi)有父節(jié)點(diǎn)超歌，則根root直接變?yōu)樘娲?jié)點(diǎn)
            root = replacement;
        else if (p == p.parent.left) //如果P為左節(jié)點(diǎn)砍艾，則用replacement來(lái)替代為左節(jié)點(diǎn)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement; //如果P為右節(jié)點(diǎn)，則用replacement來(lái)替代為右節(jié)點(diǎn)

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null; //去除p節(jié)點(diǎn)

        // Fix replacement
        // 根據(jù)節(jié)點(diǎn)的顏色巍举，來(lái)刪除脆荷。紅色：直接刪除，黑色：刪除之后懊悯，需要平衡樹(shù)蜓谋，調(diào)整位置。
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        // 說(shuō)明是唯一的節(jié)點(diǎn)炭分，當(dāng)前root直接返回 null 即可
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);
        // 刪除p節(jié)點(diǎn)
        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;
        }
    }
}

最后

本文是對(duì)TreeMap做了一個(gè)簡(jiǎn)單的介紹孤澎，沒(méi)有對(duì)刪除節(jié)點(diǎn)之后，紅黑樹(shù)怎么自動(dòng)平衡做講解欠窒，后面會(huì)專門(mén)寫(xiě)一篇文章對(duì)紅黑樹(shù)做一個(gè)學(xué)習(xí)覆旭。
文章和本人博客同步更新。