之前花了很多时间写了HashMap，HashMap算是超级重要的一个知识点了，面试的时候特种问题各种变形都有可能会问到。相对于HashMap，好像TreeMap显得有点不那么重要了，但是常常会伴随着HashMap来提问。因此花了一部分时间对其进行整理了一下。
一、认识TreeMap
1、继承关系
其实从名字就可以看出主要是和树有关，而且这棵树还是赫赫有名的红黑树。因为其处于java集合体系一个一个知识点，我们还是先看一下这个TreeMap处于整个集合体系的一个什么位置？
从类图中我们可以看到，TreeMap继承自AbstractMap。这张图太宏观了，知道其处于一个什么位置，我们按住TreeMap别动，逐渐把视线转变成以TreeMap为中心，看一下他的继承关系。
在这里我们就很清晰了，TreeMap继承于AbstractMap，实现了Cloneable,NavigableMap,Serializable接口。当然这只是让我们去认识一下TreeMap，核心知识还需要往下看。
2、红黑树
我们之前提到，TreeMap的底层是基于红黑树的，那什么是红黑树呢？我们在这里简单的认识一下，了解一下红黑树的特点：红黑树是一颗自平衡的排序二叉树。我们就先从二叉树开始说起。
（1）二叉树
二叉树很容易理解，就是一棵树分俩叉。
上面这颗就是一颗最普通的二叉树。但是你会发现看起来不那么美观，因为你以H为根节点，发现左右两边高低不平衡，高度相差达到了2。于是出现了平衡二叉树，使得左右两边高低差不多。
（2）平衡二叉树
这下子应该能看到，不管是从任何一个字母为根节点，左右两边的深度差不了2，最多是1。这就是平衡二叉树。不过好景不长，有一天，突然要把字母变成数字，还要保持这种特性怎么办呢？于是又出现了平衡二叉排序树。
（3）平衡二叉排序树
不管是从长相（平衡），还是从规律（排序）感觉这棵树超级完美。但是有一个问题，那就是在增加删除节点的时候，你要时刻去让这棵树保持平衡，需要做太多的工作了，旋转的次数超级多，于是乎出现了红黑树。
（4）红黑树
这就是传说中的红黑树，和平衡二叉排序树的区别就是每个节点涂上了颜色，他有下列五条性质：
每个节点都只能是红色或者黑色根节点是黑色每个叶节点（NIL节点，空节点）是黑色的。如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。这些性质有什么优点呢？就是插入效率超级高。因为在插入一个元素的时候，最多只需三次旋转，O(1)的复杂度，但是有一点需要说明他的查询效率略微逊色于平衡二叉树，因为他比平衡二叉树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较。如何去旋转呢？来一张动图表示（从谷歌上找的图，如有侵权问题还请联系我删除）
首先是左旋：
然后是右旋：
当然这里不是专门讲解红黑树的，因此不会特别详细的去说。这里只起到抛砖引玉的作用，想要继续往下看一定要明白红黑树的原理。重要的事说三遍：
想要继续往下看一定要先明白红黑树的原理！
想要继续往下看一定要先明白红黑树的原理！
想要继续往下看一定要先明白红黑树的原理！
说了这么久回归我们的TreeMap正题，TreeMap底层就是使用的这种红黑树。那么他的插入操作肯定效率也是很高的。我们就深入到他的源码中，正式的了解一下：
二、源码分析TreeMap
1、简单使用案例
在源码分析之前，我们先来看TreeMap的一个简单的使用：
这里只是简单的演示一下基本的增加元素和遍历元素，其他的方法可以自己测试一下，很简单。下面我们就开始分析：
2、基本属性
和HashMap一样，聚焦TreeMap，然后F3进入源码。映入眼帘的就是他的继承关系了。
可以看到继承了AbstractMap，实现了NavigableMapK,V、Cloneable、Serializable接口。然后往下看，会有一些属性，我们先解释一下，下面会用到：
里面一共就这4个属性，每个属性的含义也很简单，其中有一点需要我们注意，每个节点是一个Entry，那么这个Entry长什么样呢？我们不妨看一下：
这个类也是很简单，学过数据结构都知道其含义，在这里就不赘述了。
3、构造方法
TreeMap的构造方法一共有四个：
在这里可以看到，对于TreeMap来说，不管是哪一种构造方法，都离不开比较器。这也符合底层红黑树的要求，增删改查都需要知道元素大小，来确定位置。
在第三个构造方法中，指定一个map创建的意思就是在创建TreeMap的时候就往里存一些东西。方法就是putAll。我们可以进入到这个方法看看，是如何把map放到TreeMap中的。
也就是使用了SortedMap的比较器，迭代排序之后插入，插入操作是父类调用的。
4、插入元素
插入元素是put方法，在一开始的基本使用中也演示了，我们进入到这个方法中看一下：
到了map这一部分的源码都很恶心，直接看确实看不下去，我们可以把上面的代码用个流程图来表示一下：
有了这个流程图，你再来重新看一下上面的代码，应该就能看明白了，不过上面有一个知识点，需要我们去注意，那就是插入之后红黑树为了保持其性质如何调整呢？代码定位到fixAfterInsertion方法。跟进去看看：
如果看不明白那就百度一下红黑树的原理，相信会有所收获。
5、删除元素
删除元素是remove。我们还是进入到这里面看看：
我们会发现删除的核心代码就是调用了deleteEntry方法。我们不妨再跟进去看看：
删除操作同样是红黑树的删除，只是用代码实现了一遍。红黑树的删除就是被删除路径上的黑色节点减少，于是需要进行一系列旋转和着色。
6、查找元素
这个方法就比较简单了。也就是get方法。
到了这一步，很简单，真正获取元素的操作是getEntry方法，再跟进去就OK了。
这个更简单，核心代码就是左右子树查找。
三、总结
如果看起来比较懵逼，建议还是先了解一下红黑树，把这种数据机构搞清楚了，上面的代码确实都是小儿科。下面我们就对其来个总结：
1、基于红黑树的数据结构实现。
2、不允许插入为Null的key，HashMap可以为空，注意区别
4、若Key重复，则后面插入的直接覆盖原来的Value
5、非线程安全：底层没有synchronized这类的关键字。
6、可传入自己的比较器：从构造方法就可以看出。
OK，先到这里，如有问题，还请批评指正。