25.java集合类深入分析之treemap

《25.java集合类深入分析之treemap》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、java集合类深入分析之TreeMap/TreeSet篇简介  TreeMap和TreeSet算是java集合类里面比较有难度的数据结构。和普通的HashMap不一样，普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占优，但是它内部的元素都是排序的，当需要查找某些元素以及顺序输出元素的时候它能够带来比较理想的结果。可以说，TreeMap是一个内部元素排序版的HashMap。这里会对TreeMap内部的具体实现机制和它所基于的红黑树做一个详细的介绍。另外，针对

2、具体jdk里面TreeMap的详细实现，这里也会做详细的分析。TreeMap和TreeSet之间的关系  和前面一篇文章类似，这里比较有意思的地方是，似乎有Map和Set的地方，Set几乎都成了Map的一个马甲。此话怎讲呢?在前面一篇讨论HashMap和HashSet的详细实现讨论里，我们发现HashSet的详细实现都是通过封装了一个HashMap的成员变量来实现的。这里，TreeSet也不例外。我们先看部分代码：里面声明了成员变量：Java代码  1.private transient NavigableMap m;  Java代码  1.p

3、rivate transient NavigableMap m;    这里NavigableMap本身是TreeMap所实现的一个接口。我们再看下面和构造函数相关的实现：Java代码  1.TreeSet(NavigableMap m) {  2.    this.m = m;  3.}  4.  5.public TreeSet() {   // 无参数构造函数  6.    this(new TreeMap());  7.}  8.  9.public TreeSet(Comparator

4、per E> comparator) { // 包含比较器的构造函数  10.    this(new TreeMap<>(comparator));  11.}  12.  13.public TreeSet(Collection c) {  14.    this();  15.    addAll(c);  16.}  17.  18.public TreeSet(SortedSet s) {  19.    this(s.comparator());  20.    addAll(s);  21.}  22.  23.pub

5、lic  boolean addAll(Collection c) {  24.    // Use linear-time version if applicable  1.    if (m.size()==0 && c.size() > 0 &&  2.        c instanceof SortedSet &&  3.        m instanceof TreeMap) {  4.        SortedSet set = (SortedSet) c;  5.  

6、      TreeMap map = (TreeMap) m;  6.        Comparator cc = (Comparator) set.comparator();  7.        Comparator mc = map.comparator();  8.        if (cc==mc 

7、

8、 (cc != null && cc.equals(mc))) {  9.            map.addAllForTreeSet(s

9、et, PRESENT);  10.            return true;  11.        }  12.    }  13.    return super.addAll(c);  14.}  Java代码  1.TreeSet(NavigableMap m) {  2.    this.m = m;  3.}  4.  5.public TreeSet() {   // 无参数构造函数  6.    this(new TreeMap());  7.}  8.  9.public TreeSet(Compa

10、rator