开发者社区> 晴天哥> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

java源码-TreeSet

简介: 开篇  TreeSet作为HashSet的姊妹类型,TreeSet是用来排序的, 可以指定一个顺序, 对象存入之后会按照指定的顺序排列。 TreeSet类图 TreeSet类图 TreeSet类图  TreeSet秉承了HashSet的一贯做法,内部通过Map来保存key/value数据,由于Set只保存key,所以内部的Map的value公用了一个定义的Object对象PRESENT。
+关注继续查看

开篇

 TreeSet作为HashSet的姊妹类型,TreeSet是用来排序的, 可以指定一个顺序, 对象存入之后会按照指定的顺序排列。

TreeSet类图

img_768808a009f2f288a5635058ae2363f4.png
TreeSet类图


TreeSet类图

 TreeSet秉承了HashSet的一贯做法,内部通过Map来保存key/value数据,由于Set只保存key,所以内部的Map的value公用了一个定义的Object对象PRESENT。
 TreeSet由于维持有序性,所以内部通过TreeMap存储数据。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // 用于保存TreeMap的对象,会在构造函数当中赋值TreeMap对象
    private transient NavigableMap<E,Object> m;

    // TreeMap当中所有的value都是保存的PRESENT对象
    private static final Object PRESENT = new Object();
}


TreeSet的构造函数

 TreeSet的构造函数分为两大类:

  • 通过创建TreeMap对象赋值给TreeSet当中NavigableMap<E,Object> m变量;
  • 通过创建NavigableMap<E,Object> m变量并通过addAll方法方法添加到TreeMap当中。
  • 在TreeSet的addAll()方法通过super.addAll()方法调用AbstractCollection的addAll()方法,在该方法内部最后又调用TreeSet的add()方法添加到TreeMap m当中。
 TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }


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


public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }


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


public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }


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 add(E e) {
        return m.put(e, PRESENT)==null;
    }

----------AbstractCollection.java中代码-----------

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


TreeSe常用操作

 TreeSet常用的操作其实都是针对TreeMap进行的操作,这里就不再多做啰嗦了,基本上都是TreeMap对外提供的api而已。

private transient NavigableMap<E,Object> m;


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

    
  public E last() {
        return m.lastKey();
    }

  public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }

  public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }


TreeSet迭代器

 TreeSet的iterator本质也是TreeMap当中实现的,在TreeMap.java中的navigableKeySet()方法中创建KeySet类对象,在KeySet类iterator方法当中我们可以看出来其实就是应用了TreeMap的keyIterator()方法。
 这里再一次印证了TreeSet只是使用了TreeMap的key而已。

    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }


----------------TreeMap.java------------------------
    public NavigableSet<K> navigableKeySet() {
        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }


    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {

        private final NavigableMap<E, ?> m;

        KeySet(NavigableMap<E,?> map) { m = map; }

        public Iterator<E> iterator() {
            if (m instanceof TreeMap)
                return ((TreeMap<E,?>)m).keyIterator();
            else
                return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
        }

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Java并发编程笔记之FutureTask源码分析
FutureTask可用于异步获取执行结果或取消执行任务的场景。通过传入Runnable或者Callable的任务给FutureTask,直接调用其run方法或者放入线程池执行,之后可以在外部通过FutureTask的get方法异步获取执行结果,因此,FutureTask非常适合用于耗时的计算,主线程可以在完成自己的任务后,再去获取结果。
4135 0
Java并发编程笔记之Timer源码分析
timer在JDK里面,是很早的一个API了。具有延时的,并具有周期性的任务,在newScheduledThreadPool出来之前我们一般会用Timer和TimerTask来做,但是Timer存在一些缺陷,为什么这么说呢?   Timer只创建唯一的线程来执行所有Timer任务。
2859 0
Java并发编程笔记之Semaphore信号量源码分析
JUC 中 Semaphore 的使用与原理分析,Semaphore 也是 Java 中的一个同步器,与 CountDownLatch 和 CycleBarrier 不同在于它内部的计数器是递增的,那么,Semaphore 的内部实现是怎样的呢?   Semaphore 信号量也是Java 中一个同步容器,与CountDownLatch 和 CyclicBarrier 不同之处在于它内部的计数器是递增的。
4153 0
Java并发编程笔记之CyclicBarrier源码分析
JUC 中 回环屏障 CyclicBarrier 的使用与分析,它也可以实现像 CountDownLatch 一样让一组线程全部到达一个状态后再全部同时执行,但是 CyclicBarrier 可以被复用。
2083 0
Java并发编程笔记之ArrayBlockingQueue源码分析
JDK 中基于数组的阻塞队列 ArrayBlockingQueue 原理剖析,ArrayBlockingQueue 内部如何基于一把独占锁以及对应的两个条件变量实现出入队操作的线程安全? 首先我们先大概的浏览一下ArrayBlockingQueue 的内部构造,如下类图: 如类图所示,可以看到ArrayBlockingQueue 内部有个数组items 用来存放队列元素,putIndex变量标示入队元素的下标,takeIndex是出队的下标,count是用来统计队列元素个数, 从定义可以知道,这些属性并没有使用valatile修饰,这是因为访问这些变量的使用都是在锁块内被用。
4180 0
Java并发编程笔记之读写锁 ReentrantReadWriteLock 源码分析
我们知道在解决线程安全问题上使用 ReentrantLock 就可以,但是 ReentrantLock 是独占锁,同时只有一个线程可以获取该锁,而实际情况下会有写少读多的场景,显然 ReentrantLock 满足不了需求,所以 ReentrantReadWriteLock 应运而生,ReentrantReadWriteLock 采用读写分离,多个线程可以同时获取读锁。
2990 0
Java并发编程笔记之ReentrantLock源码分析
ReentrantLock是可重入的独占锁,同时只能有一个线程可以获取该锁,其他获取该锁的线程会被阻塞后放入该锁的AQS阻塞队列里面。 首先我们先看一下ReentrantLock的类图结构,如下图所示: 从类图可以知道,ReentrantLock最终还是使用AQS来实现,并且根据参数决定内部是公平锁还是非公平锁,默认是非公平锁。
4149 0
Java并发编程笔记之AbstractQueuedSynchronizer源码分析
为什么要说AbstractQueuedSynchronizer呢? 因为AbstractQueuedSynchronizer是JUC并发包中锁的底层支持,AbstractQueuedSynchronizer是抽象同步队列,简称AQS,是实现同步器的基础组件,并发包中锁的实现底层就是使用AQS实现,另外大多数人可能不会直接用到AQS, 但是知道其原理对于架构设计还是很有帮助的。
16975 0
Java并发编程笔记之CopyOnWriteArrayList源码分析
并发包中并发List只有CopyOnWriteArrayList这一个,CopyOnWriteArrayList是一个线程安全的ArrayList,对其进行修改操作和元素迭代操作都是在底层创建一个拷贝数组(快照)上进行的,也就是写时拷贝策略。
19437 0
Java并发编程笔记之ThreadLocal源码分析
多线程的线程安全问题是微妙而且出乎意料的,因为在没有进行适当同步的情况下多线程中各个操作的顺序是不可预期的,多线程访问同一个共享变量特别容易出现并发问题,特别是多个线程需要对一个共享变量进行写入时候,为了保证线程安全, 一般需要使用者在访问共享变量的时候进行适当的同步,如下图所示:   可以看到同步的措施一般是加锁,这就需要使用者对锁也要有一定了解,这显然加重了使用者的负担。
1843 0
+关注
晴天哥
专注java技术,热爱长跑和阅读开源代码 邮箱 lebron374@163.com
403
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载