TreeMap源码解析

在前几篇中我们主要介绍了底层是通过数组、链表、哈希表等方式实现的集合，今天我们来学习一种新的集合叫做TreeMap。TreeMap底层并不是通过哈希表的方式实现的，而是采用了一种全新的数据结构，红黑树结构存储的。下面我们简单介绍一下红黑树的相关知识。

• 红黑树的基本概念

红黑树也叫红黑二叉树，所以它也是二叉树的一种，除了具有二叉树的基本特性外，还有自己独特的一些特性。二叉树也就是说在每个树节点最多有两个子节点的树结构。并且二叉树的子节点有左右之分，且左节点的值都要小于右节点的。所以，通过二叉树结构存储的数据在检索元素时速度会很快，因为从树根节点检索时，就会过滤掉将近一半的数据（理想情况下）。并且红黑树是一种平衡二叉树，这也是红黑树的一种特性。下面我们来看一下什么是平衡二叉树。

• 红黑树特性

平衡二叉树主要具有以下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是一棵平衡二叉树。说白了红黑树就是平衡二叉树的一种实现算法，除此算法外还有AVL、Treap、伸展树、SBT等算法。（主要来源为百度百科）

下面我们继续介绍红黑树的其它特性，红黑树顾名思义就是通过设置红色或黑色等状态来保证树的平衡的。所以红黑树的主要特性如下：

• 每个节点只能是红色，或黑色
• 根节点必须是黑色
• 每个叶节点（NIL或NULL）是黑色
• 如果一个节点是红色的，则它的子节点必须是黑色（全部节点）
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
• 红黑树的旋转

上面是红黑树的相关特性，也就是说无论任何时候红黑树都必须保证具有上面的全部特性。但是在我们日常开发时，常常需要向集合中添加或者删除元素，那么在执行上述操作时，难免会破坏红黑树的相关特性，那么这时应该怎么处理呢？事实上，每当我们执行添加或者删除操作时，如果破坏了红黑树的特性，那么这时就会进行树的旋转，以保证红黑树的相关特性。红黑树的旋转主要分为左旋和右旋。下面我们分别看看具体的实现。

• 左旋

红黑树进行左旋的逻辑是，将要左旋的节点的父节点设置为自己的左节点，然后将原左节点设置为新左节点的右节点。

• 右旋

红黑树进行右旋的逻辑是，将要右旋的节点的父节点设置为自己的右节点，然后将原右节点设置为新右节点的左节点。

现在我们已经知道了有关红黑树的所有知识，下面我们分析一下TreeMap的底层源码，看TreeMap底层是怎么实现红黑树的逻辑的。我们还是和其它集合一样还是先看TreeMap的初始化。

上面是TreeMap的无参构造函数，我们发现当我们通过参构造函数创建TreeMap对象时，并不会执行底层树结构的初始化，而只是将comparator设置为空。那么通过我们以往分析其它集合时总结的规律，TreeMap的初始化一定是在第一次调用put方法时执行的。下面我们将重点看一下TreeMap中的put方法。

下面我们看一下上述方法中提到的fixAfterInsertion方法的具体逻辑也就是左旋和右旋的具体实现。

左旋和右旋的具体逻辑这里就不在详细分析了，主要的实现逻辑就是上面所说的，左旋就是讲要左旋的节点的父节点设置为自己的左节点，然后将原左节点设置为新左节点的右节点。右旋就是讲右旋的的父节点设置为自己的右节点，然后将原右节点设置为新右节点的左节点。

• 总结
• 在TreeMap中不允许用null做为key保存到TreeMap集合中
• 我们在分析源码时并没有发现同步关键字synchronized，这就说明TreeMap也不是一个线程安全的集合类
• 我们在分析源码时知道TreeMap每次都添加元素时都会进行key的比较，所以我们在使用TreeMap集合是必须保证存储在TreeMap中的元素是可以比较的，否则虚拟机会直接抛出一场。例如