TreeSet源码分析

刺骨的言语ヽ痛彻心扉 2023-01-19 03:13 185阅读 0赞

**阅读本文章之前推荐先阅读博主的关于HashSet和TreeMap的源码分析，传送地址：  
[HashSet源码分析，基于JDK1.8详细分析][HashSet_JDK1.8]  
[TreeMap源码分析，基于JDK1.8详细分析][TreeMap_JDK1.8]**

# TreeSet源码分析 #

### 文章目录 ###

*  TreeSet源码分析
 *   *  一、基本介绍
     *  二、源码分析
     *   *  1. 成员变量
         *  2. 构造方法
         *  3. 增删方法
         *  4. 其余方法
     *  三、TreeSet和LinkedHashSet的不同

## 一、基本介绍 ##

*  TreeSet的作用是保存无重复的数据，底层是采用TreeMap（红黑树）实现的一种Set，所以它是有序的，迭代的时候，可以按照 key 的排序顺序进行迭代
 *  TreeSet是非线程安全的
 *  TreeSet是基于TreeMap实现的，TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建 TreeSet 时提供的 Comparator 比较器进行排序，这取决于使用的构造方法
 *  继承体系
    
    ![image-20210430095101552][]

## 二、源码分析 ##

### 1. 成员变量 ###

//存放元素的集合，TreeMap实现了NavigableMap接口
    private transient NavigableMap<E,Object> m;
    
    //类似于HashSet，键值对的value始终是PRESENT
    private static final Object PRESENT = new Object();

**TreeMap继承体系如下图所示：**

![image-20210430102316254][]

### 2. 构造方法 ###

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);
    }

通过上述源码发现HashSet底层就是new了一个TreeMap来实现的，同时还可以指定自己的比较器

### 3. 增删方法 ###

//add方法其实就是TreeMap的put方法，value是固定值
    public boolean add(E e) { 
        return m.put(e, PRESENT)==null; //判断是否==null
    }
    
    //remove方法其实就是TreeMap的remove方法
    public boolean remove(Object o) { 
        return m.remove(o)==PRESENT;
    }

**问题：既然TreeSet只使用了NavigableMap的key，那么直接使用null作为NavigableMap的value不就行了吗？还可以节省内存**

解答：

观察上述的add方法，调用put方法之后还需要判断返回值是否等于null，添加元素有两种情况：

*  元素e不重复，直接插入即可
 *  元素e重复，调用 `m.put(e, PRESENT)` 发现e这个key已经存在了，就会将PRESENT替换掉相应的value值，然后Map返回这个value。在add方法中进行判断，value不等于null，于是add方法返回false，很明显插入失败了，符合预期；
    
    但是如果把PRESENT替换成null呢？这时候 `m.put(e, PRESENT)` 发现e这个key已经存在了，于是Map返回null。在add方法中进行判断，`null == null` ，整个add方法返回的就是true。此时发生了矛盾，插入的是重复数据，返回的结果依然还是true，明显没有插入成功，不符合预期；
    
    所以使用PRESENT这个对象作为value就能有效地避免这种情况

### 4. 其余方法 ###

public int size() { 
        return m.size();
    }
    
    public boolean isEmpty() { 
        return m.isEmpty();
    }
    
    public boolean contains(Object o) { 
        return m.containsKey(o);
    }
    
    public void clear() { 
        m.clear();
    }
    
    //返回最小的元素
    public E first() { 
        return m.firstKey();
    }
    
    //返回最大的元素
    public E last() { 
        return m.lastKey();
    }
    
    //返回小于e的最大的元素
    public E lower(E e) { 
        return m.lowerKey(e);
    }
    
    //返回小于等于e的最大的元素
    public E floor(E e) { 
        return m.floorKey(e);
    }
    
    //省略其余...

通过上述源码可以得出，TreeSet中的方法基本都是调用TreeMap中的方法

## 三、TreeSet和LinkedHashSet的不同 ##

*  二者都是有序的
 *  LinkedHashSet并没有实现SortedSet接口，它的有序性主要依赖于LinkedHashMap的有序性，所以它的有序性是指按照插入顺序保证的有序性
 *  TreeSet实现了SortedSet接口，它的有序性主要依赖于NavigableMap的有序性，而NavigableMap又继承自SortedMap，这个接口的有序性是指按照key的自然排序保证的有序性，而key的自然排序又有两种实现方式，一种是key实现Comparable接口，一种是构造方法传入Comparator比较器

[HashSet_JDK1.8]: https://blog.csdn.net/weixin_49343190/article/details/116290342
[TreeMap_JDK1.8]: https://blog.csdn.net/weixin_49343190/article/details/116258928
[image-20210430095101552]: /images/20221021/8b88aa5f272d49ba86e7cab1041a78c9.png
[image-20210430102316254]: /images/20221021/21b9adf5fd354cfc9afdf68e327028fd.png