• 前言
• TreeMap
• TreeMap類繼承圖
• TreeMap的域
• TreeMap的構(gòu)造函數(shù)
• TreeMap常見Api解析
  • put(K key, V value)
  • Comparable接口的排序了解一下
  • Comparator接口的排序了解一下
  • Comparable與Comparator接口比較總結(jié)
  • get(Object key)
  • remove(Object key)
  • 遍歷
• 總結(jié)

前言

本文使用用的是jdk1.8

TreeMap

• 基于紅黑樹的NavigableMap的實(shí)現(xiàn)。
• TreeMap實(shí)現(xiàn)了NavigableMap接口盛霎，而NavigableMap接口繼承著SortedMap接口箭启，致使我們的TreeMap符合SotredMap接口的定義螃壤。TreeMap根據(jù)key自然順序進(jìn)行排序栖榨，或者在構(gòu)造實(shí)例構(gòu)造的時(shí)候傳遞 Comparator 進(jìn)行自定義規(guī)則排序找都。
• 由于是實(shí)現(xiàn)自SortedMap捏膨，所以存入TreeMap的所有元素的key都必須是實(shí)現(xiàn)了Comparable接口的却汉，即保證其key相互調(diào)用k1.compareTo(k2)的時(shí)候不會(huì)報(bào)ClassCastException驯妄，或者類型被TreeMap指定的Comparator所接受。
• containsKey合砂、get青扔、put 和 remove 函數(shù)的時(shí)間復(fù)雜度是log(n)
• 有序映射使用它的compareTo（或compare）方法對(duì)所有鍵進(jìn)行比較，只要這兩個(gè)方法認(rèn)為相等翩伪，那么在有序映射中的兩個(gè)鍵就是相等的微猖。
• 非同步的
• 此類的所有方法及視圖返回的所有Entry是其真實(shí)的映射關(guān)系的快照。它們不支持Entry.setValue方法來(lái)更改值缘屹。不過(guò)put函數(shù)中的Entry.setValue是被允許的

TreeMap類繼承圖

實(shí)現(xiàn)了NavigableMap接口凛剥，而NavigableMap接口繼承著SortedMap接口，致使我們的TreeMap符合SotredMap接口的定義轻姿。元素有序

不同的是SortdeMap要求：插入SortedMap的所有元素的鍵都必須實(shí)現(xiàn) Comparable 接口犁珠÷叽叮或者類型在Comparator類(對(duì)應(yīng)TreeMap維護(hù)的comparator變量)中所接受，這也就要求了此時(shí)的TreeMap你必須為其的成員變量comparator賦予了值犁享。即對(duì)有序映射中的任意兩個(gè)鍵 k1 和 k2 執(zhí)行 k1.compareTo(k2)（或 comparator.compare(k1, k2)）必須是正確的余素。

TreeMap的域

/**
 * The comparator used to maintain order in this tree map, or
 * null if it uses the natural ordering of its keys.
 *
 * @serial
 */
private final Comparator<? super K> comparator;

private transient Entry<K,V> root;

/**
 * The number of entries in the tree
 */
private transient int size = 0;

/**
 * The number of structural modifications to the tree.
 */
private transient int modCount = 0;

• comparator:TreeMap中維護(hù)了一個(gè)Comparator類型的變量。用來(lái)保證TreeMap的有序性饼疙。構(gòu)造時(shí)傳入該比較器
• root：紅黑樹根節(jié)點(diǎn)
• size: Entry數(shù)量
• modCount：結(jié)構(gòu)性修改的次數(shù)

TreeMap的構(gòu)造函數(shù)

public TreeMap() {
    comparator = null;
}


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


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

public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

共四個(gè)溺森，每個(gè)都對(duì)其實(shí)例維護(hù)的Comparator引用進(jìn)行了賦值慕爬。

• TreeMap()：無(wú)參構(gòu)造函數(shù)規(guī)定窑眯，插入該有序Map的所有元素的鍵都必須實(shí)現(xiàn)Comparable接口，保證了其的可比較性医窿。進(jìn)而根據(jù)其鍵的自然排序來(lái)生成一個(gè)有序Map磅甩。
• TreeMap(Comparator<? super K> comparator)：參數(shù)是Comparator引用的構(gòu)造函數(shù)規(guī)定，插入該有序Map的所有元素的鍵都需要根據(jù)該Comparator來(lái)進(jìn)行比較姥卢。
• TreeMap(Map<? extends K, ? extends V> m)：參數(shù)是一個(gè)Map映射的構(gòu)造函數(shù)會(huì)在其元素基礎(chǔ)上構(gòu)造一個(gè)TreeMap卷要。同時(shí)該TreeMap規(guī)定元素需要滿足TreeMap的默認(rèn)規(guī)定，即和無(wú)慘構(gòu)造函數(shù)所要求的一樣独榴，既然該構(gòu)造函數(shù)沒有指定TreeMap的域?qū)ο骳ompartor比較器僧叉，那么該Map對(duì)象中的key就必須都滿足TreeMap對(duì)所有Entry的key值的要求，即繼承了Comparable接口且相互之間可以比較棺榔。
• TreeMap(SortedMap<K, ? extends V> m)：參數(shù)是SortedMap的構(gòu)造函數(shù)會(huì)拷貝一份和其相同元素和順序的TreeMap瓶堕。線性時(shí)間

TreeMap常見Api解析

put(K key, V value)

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 如果紅黑樹為空
    if (t == null) {
        // key非空檢查
        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) {// 根據(jù)自定義比較器進(jìn)行比較
        // 根據(jù)key找到元素在樹中應(yīng)該落點(diǎn)的位置
        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 {// 根據(jù)元素的鍵實(shí)現(xiàn)的Comparable接口進(jìn)行比較
        if (key == null)// key不允許為null
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {// 根據(jù)key找好元素在樹的中落點(diǎn)
            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);
    }
    // 循環(huán)跳出，parent即元素所在點(diǎn)的父節(jié)點(diǎn)症歇。
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    // 調(diào)整紅黑樹
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

• put函數(shù)規(guī)定：如果Entry已經(jīng)存在那么oldValue替換成newValue郎笆。如果Entry第一次插入，返回null忘晤。

函數(shù)整體邏輯：判斷當(dāng)前紅黑樹是否為空宛蚓，key是否為空檢查，實(shí)例變量的維護(hù)设塔。通過(guò)Comparable或者Comparator來(lái)找元素的落點(diǎn)凄吏，然后賦值。最后調(diào)整紅黑樹

Comparable接口的排序了解一下

重要：接口的compareTo函數(shù)闰蛔，不支持null元素作為比較的參數(shù)傳入痕钢。因?yàn)閚ull 不是任何類的實(shí)例，如果傳入會(huì)報(bào)NullPointerException钞护。注釋有說(shuō)：

     * @throws NullPointerException if the specified object is null
     */
    public int compareTo(T o);

該接口強(qiáng)行對(duì)實(shí)現(xiàn)它的每個(gè)類的對(duì)象進(jìn)行整體排序(隱式的)盖喷。這種排序被稱為類的自然排序，類的 compareTo 方法被稱為它的自然比較方法难咕。一般情況下我們應(yīng)該盡可能的使它的自然比較方法和它的equals方法的比較結(jié)果保持一致课梳。即一個(gè)類實(shí)現(xiàn)了Comparable接口距辆，那么他必然要重寫compareTo函數(shù)，假設(shè)這個(gè)實(shí)現(xiàn)類是Student那么他的比較規(guī)則可能是

if(this.id > o.id){
     return 0
}
   ……

此時(shí)equals函數(shù)的比較規(guī)則肯定是兩個(gè)id不相等肯定不是同一個(gè)元素暮刃。但是compareTo的比較結(jié)果卻是兩個(gè)對(duì)象相等跨算。這樣的話就很不妥。但是一般情況下椭懊，我們的compareTo和equals的比較結(jié)果應(yīng)該還是一致的诸蚕，在指定比較規(guī)則的時(shí)候我們應(yīng)該想到這些，并考慮周全一些氧猬。

實(shí)現(xiàn)了這個(gè)接口的對(duì)象的列表或數(shù)組可以通過(guò)其Collections.sort或Arrays.sort進(jìn)行自動(dòng)排序背犯。

同時(shí)實(shí)現(xiàn)該接口的對(duì)象可以用作有序映射中的鍵或有序集合中的元素，無(wú)需再指定比較器盅抚。

一般的繼承該接口的類型比較的時(shí)候漠魏，我們應(yīng)該盡量保證其compareTo函數(shù)的比較結(jié)果與equals函數(shù)的比較結(jié)果一致。

Comparator接口的排序了解一下

重要：接口的compare函數(shù)也不支持比較參數(shù)出傳入null值妄均。因?yàn)閚ull不是任何類的實(shí)例柱锹，如果傳入會(huì)報(bào)NullPointerException。注釋有說(shuō)：

  * @throws NullPointerException if an argument is null and this
  *         comparator does not permit null arguments
  */
  int compare(T o1, T o2);

強(qiáng)行對(duì)某個(gè)對(duì)象 collection 進(jìn)行整體排序 的接口丰包〗可以將 Comparator 傳遞給 sort 方法（如 Collections.sort 或 Arrays.sort），從而允許在排序順序上實(shí)現(xiàn)精確控制邑彪。還可以使用 Comparator 來(lái)控制某些數(shù)據(jù)結(jié)構(gòu)（如有序 set或有序映射）的順序瞧毙，或者為那些沒有自然順序的對(duì)象 collection 提供排序。

Comparable與Comparator接口比較總結(jié)

相比于Comparable接口的比較锌蓄，Comparator的比較規(guī)則則是一種自定義規(guī)則的比較升筏。也就意味著，對(duì)于實(shí)現(xiàn)了Comparable接口的類來(lái)說(shuō)如果要想排序必須實(shí)現(xiàn)其compareTo函數(shù)瘸爽，并且只有這一種方式您访。相比于我們自定義比較器可以有多個(gè)實(shí)現(xiàn)類的多個(gè)比較器的比較方式而言比較單一。并且沒有比較器那么自由剪决，可以隨意安插灵汪。

Comparator體現(xiàn)了一種策略模式，就是不改變對(duì)象自身柑潦，而用一個(gè)策略對(duì)象來(lái)改變它的行為享言。

總的來(lái)說(shuō)

Comparable是自已完成比較，Comparator是外部程序?qū)崿F(xiàn)比較渗鬼。

兩種方法各有優(yōu)劣,用Comparable簡(jiǎn)單,只要實(shí)現(xiàn)Comparable 接口的對(duì)象直接就成為一個(gè)可以比較的對(duì)象,但是需要修改源代碼,用Comparator的好處是不需要修改源代碼, 而是另外實(shí)現(xiàn)一個(gè)比較器,當(dāng)某個(gè)自定義的對(duì)象需要作比較的時(shí)候,把比較器和對(duì)象一起傳遞過(guò)去就可以比大小了, 并且在Comparator里面用戶可以自己實(shí)現(xiàn)復(fù)雜的可以通用的邏輯,使其可以匹配一些比較簡(jiǎn)單的對(duì)象,那樣就可以節(jié)省很多重復(fù)勞動(dòng)了览露。

get(Object key)

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)
        // 自定義比較器存在，那么就調(diào)用getEntryUsingComparator函數(shù)來(lái)從紅黑樹中來(lái)找對(duì)應(yīng)的Entry
        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) {
        // 否則通過(guò)Comparable接口的compareTo函數(shù)來(lái)找
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

// 函數(shù)很簡(jiǎn)單譬胎，從紅黑樹中找到key對(duì)應(yīng)的Entry并返回
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;
}

從getEntry函數(shù)可以看出差牛，Entry的獲取途徑有兩種命锄，即先通過(guò)comparator獲取，如果comparator未指定的話再通過(guò)比較各元素的compareTo函數(shù)來(lái)定位偏化。

remove(Object key)

函數(shù)的作用：刪除該Entry脐恩，并返回Entry.value

public V remove(Object key) {
    // 從紅黑樹中找到對(duì)應(yīng)的Entry
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

上面我們分析過(guò)了getEntry的函數(shù)邏輯。而deleteEntry函數(shù)的主要作用則是刪除紅黑樹中該節(jié)點(diǎn)并且調(diào)整紅黑樹侦讨。設(shè)計(jì)紅黑樹的比較復(fù)雜這里就不細(xì)說(shuō)了

遍歷

/**
 * Base class for TreeMap Iterators
 */
abstract class PrivateEntryIterator<T> implements Iterator<T> {
    // 下一個(gè)要迭代到的元素
    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;
    }
}

// 返回下一個(gè)要迭代的元素
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    // 如果元素有右子樹開始迭代右子樹(因?yàn)榧热槐闅v到了該元素驶冒，左子樹肯定遍歷完了)
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        // 找右子樹中最小的
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 該返回其父節(jié)點(diǎn)了
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        // 下一個(gè)該返回的節(jié)點(diǎn)下左右子樹全部清空，往上追溯韵卤，確認(rèn)該節(jié)點(diǎn)的位置
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

對(duì)于successor函數(shù)我們需要時(shí)刻清晰骗污，其迭代順序是前序遍歷的。先左后中后右

總結(jié)

• TreeMap底層是紅黑樹怜俐，能夠?qū)崿F(xiàn)該Map集合有序身堡，很多函數(shù)的時(shí)間復(fù)雜度甚至可以到O(logn)
• key不能為null
• 想要自定義比較，在構(gòu)造方法中傳入Comparator對(duì)象拍鲤，否則使用key的自然排序來(lái)進(jìn)行比較
• 非同步，除非外部手動(dòng)同步或者Collections封裝汞扎。

該數(shù)據(jù)結(jié)構(gòu)的精髓：

如果在構(gòu)造方法中傳遞了Comparator對(duì)象季稳，那么就會(huì)以Comparator對(duì)象的方法進(jìn)行比較，來(lái)排序澈魄。否則景鼠，則使用Comparable的compareTo(T o)方法來(lái)比較排序。

需要注意的是

• 如果TreeMap使用Comparable接口來(lái)保證有序痹扇，那么使用其compareTo(T o)函數(shù)來(lái)比較時(shí)铛漓，key不能為null，并且該key必須實(shí)現(xiàn)了Comparable接口鲫构。
• 相對(duì)的如果是使用的是Comparator接口浓恶，使用compare函數(shù)來(lái)比較，key也不能為null结笨，并且必須是Comparator接口支持的泛型類型包晰。