TreeMap就这么简单【源码剖析】

矫情吗；* 2021-09-15 05:22 372阅读 0赞

# 前言 #

> 声明，本文用得是jdk1.8

前面章节回顾：

*  [Collection总览][Collection]
 *  [List集合就这么简单【源码剖析】][List]
 *  [Map集合、散列表、红黑树介绍][Map]
 *  [HashMap就是这么简单【源码剖析】][HashMap]
 *  [LinkedHashMap就这么简单【源码剖析】][LinkedHashMap]

本篇**主要讲解TreeMap**~

看这篇文章之前最好是有点数据结构的基础：

*  [Java实现单向链表][Java]
 *  [栈和队列就是这么简单][Link 1]
 *  [二叉树就这么简单][Link 2]

当然了，如果讲得有错的地方还请大家多多包涵并不吝在评论去指正～

# 一、TreeMap剖析 #

按照惯例，我简单翻译了一下顶部的注释(我英文水平渣，如果有错的地方请多多包涵~欢迎在评论区下指正)

![oQTasBj.png][]

接着我们来看看类继承图：

![2r5pI45.png][]

在注释中提到的要点，我来总结一下：

*  TreeMap实现了NavigableMap接口，而NavigableMap接口继承着SortedMap接口，致使我们的**TreeMap是有序的**！
 *  TreeMap底层是红黑树，它方法的时间复杂度都不会太高:log(n)~
 *  非同步
 *  使用Comparator或者Comparable来比较key是否相等与排序的问题~

对我而言，Comparator和Comparable我都忘得差不多了~~~下面就开始看TreeMap的源码来看看它是怎么实现的，并且回顾一下Comparator和Comparable的用法吧！

## 1.1TreeMap的域 ##

![RvSb7xG.png][]

## 1.2TreeMap构造方法 ##

TreeMap的构造方法有4个：

![BbASiWY.png][]

可以发现，TreeMap的构造方法大多数与comparator有关：

![NyYVtUt.png][]

也就是顶部注释说的：TreeMap有序是通过Comparator来进行比较的，**如果comparator为null，那么就使用自然顺序**~

打个比方：

*  如果value是整数，自然顺序指的就是我们平常排序的顺序(1,2,3,4,5..)~

TreeMap<Integer, Integer> 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<Integer, Integer> entry : treeMap.entrySet()) {
    
            String s = entry.getKey() +"关注公众号：Java3y---->" + entry.getValue();
    
            System.out.println(s);
        }

![kwrOnru.png][]

## 1.3put方法 ##

我们来看看TreeMap的核心put方法，阅读它就可以获取不少关于TreeMap特性的东西了~

![lVbPb85.png][]

下面是`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<? super K>)k1).compareTo((K)k2)
                : comparator.compare((K)k1, (K)k2);
        }

如果我们设置key为null，会抛出异常的，就不执行下面的代码了。

![e24Taai.png][]

## 1.4get方法 ##

接下来我们来看看get方法的实现：

![1G930lW.png][]

点进去`getEntry()`看看实现：

![l1bjCYP.png][]

如果Comparator不为null，接下来我们进去看看`getEntryUsingComparator(Object key)`，是怎么实现的

![6CVB9K9.png][]

## 1.5remove方法 ##

![Syzy7Ne.png][]

删除节点的时候调用的是`deleteEntry(Entry<K,V> p)`方法，这个方法主要是**删除节点并且平衡红黑树**

平衡红黑树的代码是比较复杂的，我就不说了，你们去看吧(反正我看不懂)….

## 1.6遍历方法 ##

在看源码的时候可能不知道哪个是核心的遍历方法，因为Iterator有非常非常多~

![XJLzCnM.png][]

此时，我们只需要debug一下看看，跟下去就好！

![ehZPREa.png][]

![xJmK5s4.png][]

于是乎，我们可以找到：**TreeMap遍历是使用EntryIterator这个内部类的**

首先来看看EntryIterator的类结构图吧：

![xEScfRR.png][]

可以发现，EntryIterator大多的实现都是在父类中：

![zqvXm3m.png][]

那接下来我们去看看PrivateEntryIterator比较重要的方法：

![ZPDGD65.png][]

我们进去`successor(e)`方法看看实现：

> successor 其实就是一个结点的 下一个结点，所谓 下一个，是按次序排序后的下一个结点。从代码中可以看出，如果右子树不为空，就返回右子树中最小结点。如果右子树为空，就要向上回溯了。在这种情况下，t 是以其为根的树的最后一个结点。如果它是其父结点的左孩子，那么父结点就是它的下一个结点，否则，t 就是以其父结点为根的树的最后一个结点，需要再次向上回溯。一直到 ch 是 p 的左孩子为止。

来源：[https://blog.csdn.net/on\_1y/article/details/27231855][https_blog.csdn.net_on_1y_article_details_27231855]

![5NK3AWx.png][]

# 二、总结 #

TreeMap底层是红黑树，能够实现该Map集合有序~

如果在构造方法中传递了Comparator对象，那么就会以Comparator对象的方法进行比较。否则，则使用Comparable的`compareTo(T o)`方法来比较。

*  值得说明的是：如果使用的是`compareTo(T o)`方法来比较，**key一定是不能为null**，并且得实现了Comparable接口的。
 *  即使是传入了Comparator对象，不用`compareTo(T o)`方法来比较，key\*\*也是\*\*不能为null的

public static void main(String[] args) {
            TreeMap<Student, String> map = new TreeMap<Student, String>((o1, o2) -> {
                //主要条件
                int num = o1.getAge() - o2.getAge();
    
                //次要条件
                int num2 = num == 0 ? o1.getName().compareTo(o2.getName()) : num;
    
                return num2;
            });
    
            //创建学生对象
            Student s1 = new Student("潘安", 30);
            Student s2 = new Student("柳下惠", 35);
    
            //添加元素进集合
            map.put(s1, "宋朝");
            map.put(s2, "元朝");
            map.put(null, "汉朝");
    
            //获取key集合
            Set<Student> set = map.keySet();
    
            //遍历key集合
            for (Student student : set) {
                String value = map.get(student);
                System.out.println(student + "---------" + value);
            }
        }

![hrWbD06.png][]

我们从源码中的很多地方中发现：Comparator和Comparable出现的频率是很高的，因为TreeMap实现有序要么就是外界传递进来Comparator对象，要么就使用默认key的Comparable接口(实现自然排序)

最后我就来总结一下TreeMap要点吧：

1.  由于底层是红黑树，那么时间复杂度可以保证为log(n)
2.  key不能为null，为null为抛出NullPointException的
3.  想要自定义比较，在构造方法中传入Comparator对象，否则使用key的自然排序来进行比较
4.  TreeMap非同步的，想要同步可以使用Collections来进行封装

参考资料：

*  《Core Java》
 *  [https://blog.csdn.net/panweiwei1994/article/details/76555359][https_blog.csdn.net_panweiwei1994_article_details_76555359]
 *  [https://www.cnblogs.com/chinajava/p/5808416.html][https_www.cnblogs.com_chinajava_p_5808416.html]

--------------------

![dtmIM0T.jpg][]

明天要是无意外的话，可能会写ConcurrentHashMap集合，敬请期待哦~~~~

**文章的目录导航**：[https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang][https_zhongfucheng.bitcron.com_post_shou-ji_wen-zhang-dao-hang]

> 如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以**关注微信公众号:Java3y**。为了大家方便，刚新建了一下**qq群：742919422**，大家也可以去交流交流。谢谢支持了！希望能多介绍给其他有需要的朋友

[Collection]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484122&idx=1&sn=c3bd6436b3e661ae15cb9d7154d82b89&chksm=ebd743dbdca0cacdcb272576f4be48c466bd73160a87227314e8fb21d5e4f9156c23902198ab#rd
[List]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484130&idx=1&sn=4052ac3c1db8f9b33ec977b9baba2308&chksm=ebd743e3dca0caf51b170fd4285345c9d992a5a56afc28f2f45076f5a820ad7ec08c260e7d39#rd
[Map]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484135&idx=1&sn=be2221572ffc82f5792dd4ef1ea8e309&chksm=ebd743e6dca0caf00f188cabafc73665b875bf1cbe92cf3626cedb4f80313bb20a7429b8ec3f#rd
[HashMap]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484139&idx=1&sn=bb73ac07081edabeaa199d973c3cc2b0&chksm=ebd743eadca0cafc532f298b6ab98b08205e87e37af6a6a2d33f5f2acaae245057fa01bd93f4#rd
[LinkedHashMap]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484143&idx=1&sn=8d94f92f26b87dcea9181a04c78a9743&chksm=ebd743eedca0caf84ede91e6cd295664f92d2b167068d4c4a15f8cb4002844b819378f1e8e3d#rd
[Java]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484086&idx=1&sn=24127ceb5e0fed7f832f82579c4fbc19&chksm=ebd743b7dca0caa1dce912d47251548225aa59b4b48742a963ac52b05e13ec923a738ebcb836#rd
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484090&idx=1&sn=d46205eed74e9b253ec08796124192c1&chksm=ebd743bbdca0caad2129f0d76f002b7e14e125900ecac1fa9a3a433e3a9bcd2831275a1e260c#rd
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484064&idx=1&sn=ba783e3e83b8007fcdf129ec0839b6c2&chksm=ebd743a1dca0cab7eed0ba42d1c5d343d88858c17e90a803e0ce9e6644187e5297b29ffbb020#rd
[oQTasBj.png]: https://i.imgur.com/oQTasBj.png
[2r5pI45.png]: https://i.imgur.com/2r5pI45.png
[RvSb7xG.png]: https://i.imgur.com/RvSb7xG.png
[BbASiWY.png]: https://i.imgur.com/BbASiWY.png
[NyYVtUt.png]: https://i.imgur.com/NyYVtUt.png
[kwrOnru.png]: https://i.imgur.com/kwrOnru.png
[lVbPb85.png]: https://i.imgur.com/lVbPb85.png
[e24Taai.png]: https://i.imgur.com/e24Taai.png
[1G930lW.png]: https://i.imgur.com/1G930lW.png
[l1bjCYP.png]: https://i.imgur.com/l1bjCYP.png
[6CVB9K9.png]: https://i.imgur.com/6CVB9K9.png
[Syzy7Ne.png]: https://i.imgur.com/Syzy7Ne.png
[XJLzCnM.png]: https://i.imgur.com/XJLzCnM.png
[ehZPREa.png]: https://i.imgur.com/ehZPREa.png
[xJmK5s4.png]: https://i.imgur.com/xJmK5s4.png
[xEScfRR.png]: https://i.imgur.com/xEScfRR.png
[zqvXm3m.png]: https://i.imgur.com/zqvXm3m.png
[ZPDGD65.png]: https://i.imgur.com/ZPDGD65.png
[https_blog.csdn.net_on_1y_article_details_27231855]: https://blog.csdn.net/on_1y/article/details/27231855
[5NK3AWx.png]: https://i.imgur.com/5NK3AWx.png
[hrWbD06.png]: https://i.imgur.com/hrWbD06.png
[https_blog.csdn.net_panweiwei1994_article_details_76555359]: https://blog.csdn.net/panweiwei1994/article/details/76555359
[https_www.cnblogs.com_chinajava_p_5808416.html]: https://www.cnblogs.com/chinajava/p/5808416.html
[dtmIM0T.jpg]: https://i.imgur.com/dtmIM0T.jpg
[https_zhongfucheng.bitcron.com_post_shou-ji_wen-zhang-dao-hang]: https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang