当前位置: 首页 > 科技观察

JavaTreeMap源码分析

时间:2023-03-13 13:27:28 科技观察

继上一篇介绍了HashMap之后,本文开始介绍Map系列中的另一个重要类TreeMap。大家可能会觉得网上介绍HashMap的文章很多,但是介绍TreeMap的就没有那么多了。这是有原因的:一方面,HashMap的使用场景更多;其次,与HashMap相比,TreeMap使用的数据结构更加复杂。话不多说,进入正题。Signature(签名)publicclassTreeMapextendsAbstractMapimplementsNavigableMap,Cloneable,java.io.Serializable可以看到,TreeMap比HashMapNavigableMap多继承了一个接口,即,这个接口,决定了TreeMap和HashMap的区别:HashMap的key是无序的,TreeMap的key是有序的发现NavigableMap继承了SortedMap,再看SortedMap的签名SortedMappublicinterfaceSortedMapextendsMapSortedMap就像它的名字一样,说明这个Map是有序的。这个顺序一般是指Comparable接口提供的键的自然排序,也可以通过在创建SortedMap实例时指定一个Comparator来确定。当我们使用集合视图(collectionviews,likeHashMap,alsoprovidedbyentrySet,keySetandvaluesmethods)迭代(iterate)一个SortedMap实例时,键的顺序就会体现出来。这里介绍一下Comparable和Comparator的区别(参考这里):Comparable一般表示类的自然顺序,比如定义一个Student类,学生ID默认排序。例如,如果要根据Student类的年龄对插入到SortedMap中的键进行排序,则必须继承Comparable类(或指定一个比较器),以便确定如何进行比较(通过k1.compareTo(k2)或comparator.compare(k1,k2))两个key,否则插入时会报ClassCastException异常。即SortedMap中key的顺序要和equals方法保持一致。也就是说,当k1.compareTo(k2)或comparator.compare(k1,k2)为真时,k1.equals(k2)也应该为真。介绍完SortedMap,再回到我们的NavigableMap。NavigableMap是JDK1.6的新增功能。在SortedMap的基础上,增加了一些“导航方法”(navigationmethods),返回离搜索目标最近的元素。例如以下方法:lowerEntry,返回所有小于给定Map.Entry的元素floorEntry,返回所有小于等于给定Map.Entry的元素ceilingEntry,返回所有大于等于thegivenMap.Entry,higherEntry,返回所有大于给定Map.Entry的元素。设计概念(designconcept)红黑树(Red-blacktree)TreeMap是基于红黑树的。红黑树是二叉搜索树。让我们一起回忆一下二叉搜索树的一些性质。我们先看看二叉搜索树。二叉搜索树(BST)是什么样的?二叉查找树这个图相信大家都不陌生,关键点是:左子树的值小于根节点,右子树的值大于根节点。二叉搜索树的优点是每一次判断都能将问题的规模缩小一半,所以如果二叉搜索树是平衡的,寻找元素的时间复杂度就是log(n),也就是树的高度。我在这里想到一个更严肃的问题。如果二叉搜索树将问题大小减少一半,那么三元搜索树会将问题大小减少三分之二。那不是更好吗?以此类推,我们还有可以有四叉搜索树,五叉搜索树……对于更一般的情况:n个元素,K叉搜索树效率最高的K是多少?当K=2?K-叉搜索树如果按照我上面的分析,你可能也会陷入一个误区,即三元搜索树将问题的大小减少三分之二时,需要的比较操作次数为2(二元搜索树则将问题缩小到当规模缩小一半时,只需要一次比较操作)我们不能忽略这两次。对于更一般的情况:n个元素,K树搜索树所需的平均比较次数为k*log(n/k)。对于极端情况k=n,将K叉树转化为线性表,复杂度为O(n)。如果从数学的角度来解决这个问题,就相当于:当n为固定值时,k取什么值?时,k*log(n/k)的值最小?k*log(n/k)根据对数运算规则可以转化为ln(n)*k/ln(k),ln(n)是常数,相当于取最小值k/ln(k)。这道题对于刚学高等数学的新生来说再简单不过了。这里我们直接看结果。当k=e时,k/ln(k)取最小值。自然数e的值约为2.718。可以看出二叉树基本就是这样解决的。在NodejsREPL函数中执行以下操作foo(k){returnk/Math.log(k);}>foo(2)2.8853900817779268>foo(3)2.730717679880512>foo(4)2.8853900817779268>foo(5)3.1066704574798看起来像k=3,k=2时得到的结果更小,也就是说三叉搜索树应该比二叉搜索树好,但是为什么二叉搜索树更受欢迎呢?后来在***stackoverflow上找到了答案。主要思想如下:目前的CPU可以针对二进制逻辑(binarylogic)代码进行优化,将三重逻辑分解为多个二进制逻辑。通过这种方式,我们可以大致理解为什么二叉树如此受欢迎,因为我们最多可以通过执行比较操作将问题大小减少一半。好了说到这里有点远了,我们还是回到红黑树吧。红黑树的本质先看一下红黑树的表象:红黑树示例上图摘自wiki。需要说明的一点是:叶子节点就是上图中的NIL节点,在国内的一些教材上是找不到的,我们在画图的时候有时候会省略这些NIL节点,但是需要明确一点,我们说的叶子节点,指的就是这些NIL节点。红黑树通过以下五个规则保证树是平衡的:树的节点只有红色和黑色。根节点是黑色的。叶节点是黑色的。红色节点的节点必须是黑色的。从任意一个节点开始到后续叶子节点的路径,黑色节点的个数是相同的。满足以上5个条件后,可以保证从根节点到叶子节点的最长路径不会大于从根节点到叶子节点的最短路径的两倍。其实这个很好理解,主要是利用性质4和5。这里简单介绍一下:假设从根节点到叶子节点的最短路径中黑色节点的个数为B,则根据性质5,从根节点到叶子节点的最长路径路径中,黑色节点的个数也是B,最长的情况是每两个黑色节点之间有一个红色节点(即红黑的情况alternates),所以红色节点的最大数量是B-1。这可以证明上面的结论。红黑树操作红黑树旋转示例(NIL节点未画)关于红黑树的插入、删除、左旋、右旋操作,我觉得***可以形象化,并且文字表达比较繁琐,这里就描述一下吧我不再秀丑了,网上可以找更多的,比如v_July_v的《教你透彻了解红黑树》。这里推荐一个swf教学视频(视频是英文的,不用怕,重点是看图??),7分钟左右,大家可以参考一下。这里还有一个交互式红黑树可视化网页。大家可以自己上去操作一下,插入几个节点,删除几个节点玩一玩,看看左右旋转是怎么玩的。源码分析由于这里不讲红黑树的运行,这里基本没有源码可以讲,因为这里重要的算法都是FromCLR,这里的CLR指的是Cormen,Leiserson,Rivest,他们是《算法导论》的作者,也就是说TreeMap中的算法参考了《算法导论》的伪代码。因为红黑树是平衡二叉搜索树,所以它的put(包括update操作)、get、remove的时间复杂度都是log(n)。小结至此,TreeMap和HashMap的实现已经介绍完了。可以看到他们的实现方式不同,这就决定了他们应用场景的不同:TreeMap的key是有序的,增删改查操作的时间复杂度是O(log(n)),为了保证红黑树的平衡,必要时会轮换。将调整大小。另外,我这里没有说明具体的代码,难免有些头条。请大家见谅,等我深入了解以后再补坑。