摘要：在這種情況下，是以其為根的樹的最后一個(gè)結(jié)點(diǎn)。來源二總結(jié)底層是紅黑樹，能夠?qū)崿F(xiàn)該集合有序如果在構(gòu)造方法中傳遞了對象，那么就會以對象的方法進(jìn)行比較。

聲明，本文用得是jdk1.8

前面章節(jié)回顧：

Collection總覽

List集合就這么簡單【源碼剖析】

Map集合、散列表、紅黑樹介紹

HashMap就是這么簡單【源碼剖析】

LinkedHashMap就這么簡單【源碼剖析】

本篇主要講解TreeMap~

看這篇文章之前最好是有點(diǎn)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)：

Java實(shí)現(xiàn)單向鏈表

棧和隊(duì)列就是這么簡單

二叉樹就這么簡單

當(dāng)然了，如果講得有錯的地方還請大家多多包涵并不吝在評論去指正～

按照慣例，我簡單翻譯了一下頂部的注釋(我英文水平渣，如果有錯的地方請多多包涵~歡迎在評論區(qū)下指正)

接著我們來看看類繼承圖：

在注釋中提到的要點(diǎn)，我來總結(jié)一下：

TreeMap實(shí)現(xiàn)了NavigableMap接口，而NavigableMap接口繼承著SortedMap接口，致使我們的TreeMap是有序的！

TreeMap底層是紅黑樹，它方法的時(shí)間復(fù)雜度都不會太高:log(n)~

非同步

使用Comparator或者Comparable來比較key是否相等與排序的問題~

對我而言，Comparator和Comparable我都忘得差不多了~~~下面就開始看TreeMap的源碼來看看它是怎么實(shí)現(xiàn)的，并且回顧一下Comparator和Comparable的用法吧！

TreeMap的構(gòu)造方法有4個(gè)：

可以發(fā)現(xiàn)，TreeMap的構(gòu)造方法大多數(shù)與comparator有關(guān)：

也就是頂部注釋說的：TreeMap有序是通過Comparator來進(jìn)行比較的，如果comparator為null，那么就使用自然順序~

打個(gè)比方：

如果value是整數(shù)，自然順序指的就是我們平常排序的順序(1,2,3,4,5..)~

    TreeMap treeMap = new TreeMap<>();

    treeMap.put(1, 5);
    treeMap.put(2, 4);
    treeMap.put(3, 3);
    treeMap.put(4, 2);
    treeMap.put(5, 1);

    for (Entry entry : treeMap.entrySet()) {

        String s = entry.getKey() +"關(guān)注公眾號：Java3y---->" + entry.getValue();

        System.out.println(s);
    }

我們來看看TreeMap的核心put方法，閱讀它就可以獲取不少關(guān)于TreeMap特性的東西了~

下面是compare(Object k1, Object k2)方法

    /**
     * Compares two keys using the correct comparison method for this TreeMap.
     */
    @SuppressWarnings("unchecked")
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

如果我們設(shè)置key為null，會拋出異常的，就不執(zhí)行下面的代碼了。

接下來我們來看看get方法的實(shí)現(xiàn)：

點(diǎn)進(jìn)去getEntry()看看實(shí)現(xiàn)：

如果Comparator不為null，接下來我們進(jìn)去看看getEntryUsingComparator(Object key)，是怎么實(shí)現(xiàn)的

刪除節(jié)點(diǎn)的時(shí)候調(diào)用的是deleteEntry(Entry p)方法，這個(gè)方法主要是刪除節(jié)點(diǎn)并且平衡紅黑樹

平衡紅黑樹的代碼是比較復(fù)雜的，我就不說了，你們?nèi)タ窗?反正我看不懂)....

在看源碼的時(shí)候可能不知道哪個(gè)是核心的遍歷方法，因?yàn)镮terator有非常非常多~

此時(shí)，我們只需要debug一下看看，跟下去就好！

于是乎，我們可以找到：TreeMap遍歷是使用EntryIterator這個(gè)內(nèi)部類的

首先來看看EntryIterator的類結(jié)構(gòu)圖吧：

可以發(fā)現(xiàn)，EntryIterator大多的實(shí)現(xiàn)都是在父類中：

那接下來我們?nèi)タ纯碢rivateEntryIterator比較重要的方法：

我們進(jìn)去successor(e)方法看看實(shí)現(xiàn)：

successor 其實(shí)就是一個(gè)結(jié)點(diǎn)的 下一個(gè)結(jié)點(diǎn)，所謂 下一個(gè)，是按次序排序后的下一個(gè)結(jié)點(diǎn)。從代碼中可以看出，如果右子樹不為空，就返回右子樹中最小結(jié)點(diǎn)。如果右子樹為空，就要向上回溯了。在這種情況下，t 是以其為根的樹的最后一個(gè)結(jié)點(diǎn)。如果它是其父結(jié)點(diǎn)的左孩子，那么父結(jié)點(diǎn)就是它的下一個(gè)結(jié)點(diǎn)，否則，t 就是以其父結(jié)點(diǎn)為根的樹的最后一個(gè)結(jié)點(diǎn)，需要再次向上回溯。一直到 ch 是 p 的左孩子為止。

來源：https://blog.csdn.net/on_1y/article/details/27231855

TreeMap底層是紅黑樹，能夠?qū)崿F(xiàn)該Map集合有序~

如果在構(gòu)造方法中傳遞了Comparator對象，那么就會以Comparator對象的方法進(jìn)行比較。否則，則使用Comparable的compareTo(T o)方法來比較。

值得說明的是：如果使用的是compareTo(T o)方法來比較，key一定是不能為null，并且得實(shí)現(xiàn)了Comparable接口的。

即使是傳入了Comparator對象，不用compareTo(T o)方法來比較，key也是不能為null的

    public static void main(String[] args) {
        TreeMap map = new TreeMap((o1, o2) -> {
            //主要條件
            int num = o1.getAge() - o2.getAge();

            //次要條件
            int num2 = num == 0 ? o1.getName().compareTo(o2.getName()) : num;

            return num2;
        });

        //創(chuàng)建學(xué)生對象
        Student s1 = new Student("潘安", 30);
        Student s2 = new Student("柳下惠", 35);

        //添加元素進(jìn)集合
        map.put(s1, "宋朝");
        map.put(s2, "元朝");
        map.put(null, "漢朝");

        //獲取key集合
        Set set = map.keySet();

        //遍歷key集合
        for (Student student : set) {
            String value = map.get(student);
            System.out.println(student + "---------" + value);
        }
    }

我們從源碼中的很多地方中發(fā)現(xiàn)：Comparator和Comparable出現(xiàn)的頻率是很高的，因?yàn)門reeMap實(shí)現(xiàn)有序要么就是外界傳遞進(jìn)來Comparator對象，要么就使用默認(rèn)key的Comparable接口(實(shí)現(xiàn)自然排序)

最后我就來總結(jié)一下TreeMap要點(diǎn)吧：

由于底層是紅黑樹，那么時(shí)間復(fù)雜度可以保證為log(n)

key不能為null，為null為拋出NullPointException的

想要自定義比較，在構(gòu)造方法中傳入Comparator對象，否則使用key的自然排序來進(jìn)行比較

TreeMap非同步的，想要同步可以使用Collections來進(jìn)行封裝

參考資料：

《Core Java》

https://blog.csdn.net/panweiwei1994/article/details/76555359

https://www.cnblogs.com/chinajava/p/5808416.html

明天要是無意外的話，可能會寫ConcurrentHashMap集合，敬請期待哦~~~~

文章的目錄導(dǎo)航：https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang

如果文章有錯的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號:Java3y。為了大家方便，剛新建了一下qq群：742919422，大家也可以去交流交流。謝謝支持了！希望能多介紹給其他有需要的朋友