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

ormsf 發(fā)布于2019-08-15 15:22 / 1279人閱讀

摘要：在這種情況下，是以其為根的樹的最后一個結點。來源二總結底層是紅黑樹，能夠實現(xiàn)該集合有序如果在構造方法中傳遞了對象，那么就會以對象的方法進行比較。

前言

聲明，本文用得是jdk1.8

前面章節(jié)回顧：

Collection總覽

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

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

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

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

本篇主要講解TreeMap~

看這篇文章之前最好是有點數(shù)據(jù)結構的基礎：

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

棧和隊列就是這么簡單

二叉樹就這么簡單

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

一、TreeMap剖析

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

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

在注釋中提到的要點，我來總結一下：

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

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

非同步

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

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

1.1TreeMap的域

1.2TreeMap構造方法

TreeMap的構造方法有4個：

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

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

打個比方：

如果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() +"關注公眾號：Java3y---->" + entry.getValue();

        System.out.println(s);
    }

1.3put方法

我們來看看TreeMap的核心put方法，閱讀它就可以獲取不少關于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);
    }

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

1.4get方法

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

點進去getEntry()看看實現(xiàn)：

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

1.5remove方法

刪除節(jié)點的時候調用的是deleteEntry(Entry p)方法，這個方法主要是刪除節(jié)點并且平衡紅黑樹

平衡紅黑樹的代碼是比較復雜的，我就不說了，你們去看吧(反正我看不懂)....

1.6遍歷方法

在看源碼的時候可能不知道哪個是核心的遍歷方法，因為Iterator有非常非常多~

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

于是乎，我們可以找到：TreeMap遍歷是使用EntryIterator這個內部類的

首先來看看EntryIterator的類結構圖吧：

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

那接下來我們去看看PrivateEntryIterator比較重要的方法：

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

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

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

二、總結

TreeMap底層是紅黑樹，能夠實現(xiàn)該Map集合有序~

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

值得說明的是：如果使用的是compareTo(T o)方法來比較，key一定是不能為null，并且得實現(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)建學生對象
        Student s1 = new Student("潘安", 30);
        Student s2 = new Student("柳下惠", 35);

        //添加元素進集合
        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)的頻率是很高的，因為TreeMap實現(xiàn)有序要么就是外界傳遞進來Comparator對象，要么就使用默認key的Comparable接口(實現(xiàn)自然排序)

最后我就來總結一下TreeMap要點吧：

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

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

想要自定義比較，在構造方法中傳入Comparator對象，否則使用key的自然排序來進行比較

TreeMap非同步的，想要同步可以使用Collections來進行封裝

參考資料：

《Core Java》

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

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

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

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

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

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/69020.html

3分鐘搞掂Set集合

摘要：下面總結一下集合常用的三個子類吧無序，允許為，底層是散列表紅黑樹，非線程同步有序，不允許為，底層是紅黑樹非線程同步迭代有序，允許為，底層是雙向鏈表，非線程同步從結論而言我們就可以根據(jù)自己的實際情況來使用了。前言聲明，本文用的是jdk1.8 前面章節(jié)回顧： Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡單【源碼...

widuu 2019-08-15 15:27 評論0 收藏0
Java集合總結【面試題+腦圖】，將知識點一網(wǎng)打盡！

摘要：而在集合中，值僅僅是一個對象罷了該對象對本身而言是無用的。將這篇文章作為集合的總結篇，但覺得沒什么好寫就回答一些面試題去了，找了一會面試題又覺得不夠系統(tǒng)。前言聲明，本文用的是jdk1.8 花了一個星期，把Java容器核心的知識過了一遍，感覺集合已經(jīng)無所畏懼了??！(哈哈哈....)，現(xiàn)在來總結一下吧~~ 回顧目錄： Collection總覽 List集合就這么簡單【源碼剖析】 Ma...

yearsj 2019-08-15 15:29 評論0 收藏0
HashMap就是這么簡單【源碼剖析】

前言聲明，本文用得是jdk1.8 前面已經(jīng)講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹的基礎了： Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹本篇主要講解HashMap，以及涉及到一些與hashtable的比較~ 看這篇文章之前最好是有點數(shù)據(jù)結構的基礎： Java實現(xiàn)單向鏈表棧和隊列就是這么簡單二叉樹就...

entner 2019-08-15 15:21 評論0 收藏0
ConcurrentHashMap基于JDK1.8源碼剖析

摘要：下面我來簡單總結一下的核心要點底層結構是散列表數(shù)組鏈表紅黑樹，這一點和是一樣的。是將所有的方法進行同步，效率低下。而作為一個高并發(fā)的容器，它是通過部分鎖定算法來進行實現(xiàn)線程安全的。前言聲明，本文用的是jdk1.8 前面章節(jié)回顧： Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、散列表、紅黑樹介紹 HashMap就是這么簡單【源碼剖析】 LinkedHas...

sanyang 2019-08-15 15:25 評論0 收藏0
LinkedHashMap就這么簡單【源碼剖析】

摘要：習慣在微信看技術文章，想要獲取更多的資源的同學，可以關注微信公眾號。為了大家方便，剛新建了一下群，大家也可以去交流交流。謝謝支持了希望能多介紹給其他有需要的朋友前言聲明，本文用得是jdk1.8 前面已經(jīng)講了Collection的總覽和剖析List集合以及散列表、Map集合、紅黑樹還有HashMap基礎了： Collection總覽 List集合就這么簡單【源碼剖析】 Map集合、...

avwu 2019-08-15 15:23 評論0 收藏0