前面介绍了 Map 接口的实现类 LinkedHashMap,LinkedHashMap 存储的元素是有序的,可以保持元素的插入顺序,但不能对元素进行自动排序。在某些场景,如果在数据的存储过程中,能够自动对数据进行排序,将会极大提高编程效率。而 Map 接口有一个重要的实现类 TreeMap,TreeMap 可以实现存储元素的自动排序。
01、摘要
在集合系列的第一章,咱们了解到,Map 的实现类有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties 等等。
本文主要从数据结构和算法层面,探讨 TreeMap 的实现。
02、简介
Java TreeMap 实现了 SortedMap 接口,也就是说会按照 key 的大小顺序对 Map 中的元素进行排序,key 大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。
TreeMap 底层通过红黑树(Red-Black tree)实现,所以要了解 TreeMap 就必须对红黑树有一定的了解,在《集合系列》文章中,如果你已经读过红黑树的讲解,其实本文要讲解的 TreeMap,跟其大同小异。
红黑树又称红-黑二叉树,它首先是一颗二叉树,它具有二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。
对于一棵有效的红黑树二叉树,主要有以下规则:
- 1、每个节点要么是红色,要么是黑色,但根节点永远是黑色的;
- 2、每个红色节点的两个子节点一定都是黑色;
- 3、红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色);
- 4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;
- 5、所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);
这些约束强制了红黑树的关键性质:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。所以红黑树它是复杂而高效的,其检索效率为O(log n)
。下图为一颗典型的红黑二叉树。
在树的结构发生改变时(插入或者删除操作),往往会破坏上述规则3或规则4,需要通过调整使得查找树重新满足红黑树的条件。
调整方式主要有:左旋、右旋和颜色转换!
2.1、左旋
左旋的过程是将 x 的右子树绕 x 逆时针旋转,使得 x 的右子树成为 x 的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。
2.2、右旋
右旋的过程是将 x 的左子树绕 x 顺时针旋转,使得 x 的左子树成为 x 的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。
2.3、颜色转换
颜色转换的过程是将红色节点转换为黑色节点,或者将黑色节点转换为红色节点,以满足红黑树二叉树的规则!
03、常用方法介绍
3.1、get方法
get 方法根据指定的 key 值返回对应的 value,该方法调用了getEntry(Object key)
得到相应的 entry,然后返回entry.value
。
算法思想是根据 key 的自然顺序(或者比较器顺序)对二叉查找树进行查找,直到找到满足k.compareTo(p.key) == 0
的entry
。
源码如下:
1 |
|
如果传入比较器,通过 getEntryUsingComparator 方法获取元素
1 |
|
测试用例:
1 |
|
输出结果:
1 |
|
3.2、put方法
put 方法是将指定的 key, value 对添加到 map 里。该方法首先会对 map 做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于 getEntry() 方法;如果没有找到则会在红黑树中插入新的 entry,如果插入之后破坏了红黑树的约束,还需要进行调整(旋转,改变某些节点的颜色)。
源码如下:
1 |
|
红黑树调整函数fixAfterInsertion(Entry<K,V> x)
1 |
|
上述代码的插入流程:
- 1、首先在红黑树上找到合适的位置;
- 2、然后创建新的entry并插入;
- 3、通过函数fixAfterInsertion(),对某些节点进行旋转、改变某些节点的颜色,进行调整;
调整图解:
3.3、remove方法
remove 的作用是删除 key 值对应的 entry,该方法首先通过上文中提到的getEntry(Object key)
方法找到 key 值对应的 entry,然后调用deleteEntry(Entry<K,V> entry)
删除对应的 entry。由于删除操作会改变红黑树的结构,有可能破坏红黑树的约束,因此有可能要进行调整。
源码如下:
1 |
|
删除函数 deleteEntry()
1 |
|
删除后调整函数 fixAfterDeletion() 的具体代码如下:
1 |
|
上述代码的删除流程:
- 1、首先在红黑树上找到合适的位置;
- 2、然后删除 entry;
- 3、通过函数 fixAfterDeletion(),对某些节点进行旋转、改变某些节点的颜色,进行调整;
04、总结
TreeMap 默认是按键值的升序排序,如果需要自定义排序,可以通过new Comparator
构造参数,重写compare
方法,进行自定义比较。
以上,主要是对 java 集合中的 TreeMap 做了写讲解,如果有理解不当之处,欢迎指正。
05、参考
1、JDK1.7&JDK1.8 源码