文档章节

【java集合框架源码剖析系列】java源码剖析之TreeSet

htq
 htq
发布于 2016/07/26 09:39
字数 1207
阅读 5
收藏 0

本博客将从源码的角度带领大家学习TreeSet相关的知识。

一TreeSet类的定义:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
可以看到TreeSet是继承自AbstracSet同时实现了NavigableSet,Cloneable,Serializable三个接口,其中Cloneable,Serializable这两个接口基本上是java集合框架中所有的集合类都要实现的接口。

二TreeSet中的重要属性:

private transient NavigableMap<E,Object> m;

private static final Object PRESENT = new Object();
可以看到第一个属性是NavigableMap接口,该接口是TreeMap的父接口,即TreeMap实现了该接口,据此我们可以推测TreeSet的底层是基于TreeMap的,这一点稍后我们将在TreeSet的构造器中更清楚的看到。第二个参数是以Object对象,与HashSet中的这个属性完全相同,即TreeSet虽然底层是基于TreeMap的,但是同样只是用来保存Key而Value值全部为默认值PRESENT。

三TreeSet内部实现原理:我们来看一下TreeSet的构造器:

TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

 public TreeSet() {
        this(new TreeMap<E,Object>());
    }

 public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
可以看到共5个构造器,其中第一个构造器是私有的,即对外不公开的,而在第二个默认的无参数的构造器中调用了第一个构造器,且可以清楚的看到在这个构造器中创建了一个TreeMap对象作为参数传给第一个构造器,这说明我们上面的推测:TreeSet底层是基于TreeMap的是正确的。另外余下的几个构造器中可以看到当用一个集合作为参数去构造一个TreeSet的时候,都是调用addAll这个方法,我们来看一下其源码:

public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

 public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

可以看到在addAll方法中首先会判断是否传入的集合参数c是否为SortedSet或其子类且c不为空(c.size()>0),如果是则会调用addAllForTreeSet方法,否则会直接返回addAll方法的结果,关于addAll方法请参看我的博客 【java集合框架源码剖析系列】java源码剖析之HashSet相关内容,因为内容相同,在此不做赘述,重点来看一下addAllForTreeSet方法:

void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
        try {
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

private void buildFromSorted(int size, Iterator<?> it,
                                 java.io.ObjectInputStream str,
                                 V defaultVal)
        throws  java.io.IOException, ClassNotFoundException {
        this.size = size;
        root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
                               it, str, defaultVal);
    }
可以看到在addAllForTreeSet方法中调用了buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str,V defaultVal),该方法的作用即是在线性时间内对数据进行排序(Linear time tree building algorithm from sorted data),看到这里我们就明白TreeSet排序的原理了,即当使用一个TreeMap集合作为参数构造一个TreeSet的时候,TreeSet会将Map中的元素先排序,然后将排序后的元素add到TreeSet中。也就是说TreeSet中的元素都是排过序的,另外正因为存在排序过程,所以TreeSet不允许插入null值,因为null值不能排序。

四TreeSet中的重要方法:

<strong> </strong>public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

 public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

public void clear() {
        m.clear();
    }

 public boolean contains(Object o) {
        return m.containsKey(o);
    }

 public E first() {
        return m.firstKey();
    }

 public E last() {
        return m.lastKey();
    }
可以看到TreeSet中与TreeMap中同名的方法全部都是调用的TreeMap中的方法来实现的,其中add方法在调用TreeMap的put方法时第二个参数传入的是固定值PRESENT,一个Object类型对象。

五总结:经过前面TreeMap的源码剖析可以看到TreeSet非常简单

1TreeSet底层是基于TreeMap的(而TreeMap是基于红黑树的),但是仅仅用来保存Key,而不保存Value,因为TreeSet的add()方法在调用TreeMap的put方法的时候第二个参数传入的都是PRESENT这个固定的Object对象。
2可以看到TreeSet中的add与remove等方法均无synchronized关键字修饰,即TreeSet不是线程安全的,如果要使用同步的TreeSet需要使用Collections集合类的静态方法,即Set s=Collections.synchronizedSet(new TreeSet());
3TreeSet中的元素是自动排好序的,插入的值不允许为null。

4TreeSet中元素的值必须是唯一的,因为TreeSet底层是基于TreeMap的,而TreeMap不允许元素key重复。

本文转载自:http://blog.csdn.net/htq__/article/details/51056778

htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
私信 提问
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0
泥沙砖瓦浆木匠/java-core-learning-example

感谢赞助的ta们 Java 核心系列教程,关于Java核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。 包括基础语法,OOP,字符串,集合,IO,反射,线程,网络等。 未完成模块:阿里J...

泥沙砖瓦浆木匠
04/02
0
0
三流程序员与一流程序员之间的区别,看看你是属于哪一类?

源码系列 手写spring mvc框架 基于Spring JDBC手写ORM框架 实现自己的MyBatis Spring AOP实战之源码分析 Spring IOC高级特性应用分析 ORM框架底层实现原理剖析 手写Spring MVC框架实现 手把手...

茶轴的青春
2018/04/17
0
0
Java开发者不会这些永远都只能是三流程序员,细数一下你是不是?

源码系列 手写spring mvc框架 基于Spring JDBC手写ORM框架 实现自己的MyBatis Spring AOP实战之源码分析 Spring IOC高级特性应用分析 ORM框架底层实现原理剖析 手写Spring MVC框架实现 手把手...

美的让人心动
2018/04/16
0
0
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
2018/08/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java agentlib参数分析

Java agentlib参数分析 再用intellij idea进行远程调试的时候,具体的配置选项如下: 标红的一行显示了远程调试需要添加的虚拟机参数。这个参数到底有什么意义? 我在命令行输入java命令,输...

Mr_Tea伯奕
24分钟前
0
0
四种软件架构演进史,程序员会一种就很牛了!

如果一个软件开发人员,不了解软件架构的演进,会制约技术的选型和开发人员的生存、晋升空间。这里我列举了目前主要的四种软件架构以及他们的优缺点,希望能够帮助软件开发人员拓展知识面。 ...

我最喜欢三大框架
28分钟前
3
0
如何做高可用的架构设计?

定义目标 既然我们的目标是做到高可用,那么我们就有必要先明确清楚高可用的含义,并通过拆解目标,让目标可以被量化。按照我的理解,可以将目标按照以下三条进行拆解: 1. 保持业务高稳定性...

别打我会飞
28分钟前
0
0
《错误的行为》的读后感优秀范文4000字

《错误的行为》的读后感优秀范文4000字: 第一章经济人和非理性人。本书中的经纪人是指经济学家经济模式中虚拟的理想人物,非理性人是指现实生活中实实在在存在的人,与经济人相对应的人。 ...

原创小博客
40分钟前
2
0
将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向

作者图解释很好 https://blog.csdn.net/yanxiaolx/article/details/52073221

南桥北木
45分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部