javatreemap源码解析-java开发java经验技巧

《javatreemap源码解析-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、JavaTrccMap源码解析-编程开发技术JavaTreeMap源码解析原文出处：liujiacai(@jiacai2050)继上篇文章介绍完了HashMap,这篇文章开始介绍Map系列另一个比较重要的类TreeMapo大家也许能感觉到，网络上介绍IlashMap的文章比较多，但是介绍TreeMap反而不那么多，这里而是冇原因：一方而HashMap的使用场景比较多；二是相对于HashMap来说，TreeMap所用到的数拯结构更为复杂。废话不多说,进入正题。签名(signature)publicclassTreeMapextendsAbs

2、tractMapimplementsNavigableMap,Cioneable,java.io.Serializable口J以看到，相比HashMap來说，TreeMap多继承了一个接口Navigab1eMap,也就是这个接口,决定了TreeMap与HashMap的不同：HashMap的key是无序的，TreeMap的key是有序的接口Navigab1eMap首先看下Navigab1eMap的签名publicinterfaceNavigablcMapextendsSortcdMap发现Navigab1eMa

3、p继承了SortedMap,再看SortedMap的签名SortedMappublicinterfaceSortedMapextendsMapSortedMap就像其名字那样，说明这个Ifep是有序的。这个顺序一般是指由Comparable接口提供的keys的自然序(naturalordering),或者也可以在创建SortedMap实例时，指定一个Comparator来决定。当我们在用集合视角(collectionviews,与HashMap—样，也是由entrySet、keySet与values方法提供)来迭代(iterat

4、e)—个SortedMap实例时会体现出key的顺序。这里引申下关于ComparableComparator的区别(参考这里)：•Comparable一般表示类的自然序，比如定义一个Student类，学号为默认排序•Comparator一般表示类在某种场合下的特殊分类，盂要定制化排序。比如现在想按照Student类的age来排序插入SortedMap中的key的类类都必须继承Comparable类(或指定一个comparator),这样才能确定如何比较(通iikl.compareTo(k2)或comparator,compare(kl,k2))两个

5、key,否则，在插入时，会报ClassCastExccption的异常。此为，SortedMap屮key的顺序性应该与equals方法保持一致。也就是说kl.compareTo(k2)或comparator,compare(kl,k2)为true时,kl.equals(k2)也应该为true。介绍完TSortedMap,再來回到我们的Navigab1eMap上面来。Navigab1eMap是JDK1.6新增的，在SortedMap的基础上，增加了一些"导航方法”(navigationmethods)來返冋与搜索目标最近的元素。例如下面这些方法：•l

6、owerEntry,返冋所有比给定Map.Entry小的元素•floorEntry,返冋所有比给定Map.Entry小或相等的元素•ceilingEntry,返回所冇比给定Map.Entry大或相等的元素•higherEntry,返回所有比给定Map.Entry大的元素设计理念(designconcept)红黑树(Red-blacktree)TreeMap是用红黑树作为基础实现的，红黑树是一种二叉搜索树，让我们在一起回忆卜'二叉搜索树的一些性质二叉搜索树先看看二叉搜索树(binarysearchtree,BST)长什么样呢?二叉搜索树相信大家对这个

7、图都不陌生，关键点是：左子树的值小于根节点，右子树的值大于根节点。二叉搜索树的优势在于毎进行一次判断就是能将问题的规模减少一半，所以如果二叉搜索树是平衡的话，查找元素的时间复杂度为log(n)，也就是树的高度。我这里想到一个比较严肃的问题，如果说二叉搜索树将问题规模减少了一半，那么三叉搜索树不就将问题规模减少了三分Z二，这不是更好嘛，以此类推，我们还可以冇四叉搜索树，五叉搜索树……对于更一般的情况：n个元素，K叉树搜索树的K为多少时效率是最好的？K=2时吗？K叉搜索树如果大家按照我上面分析，很可能也陷入一个误区，就是三叉搜索树在将问题规模减少三分Z

8、二时，所需比较操作的次数是两次(二叉搜索树再将问题规模减少一半时，只需要一次比较操作)我们不能把这两次给忽略了，对于更一般