简介

TreeSet 底层是采用TreeMap实现的一种Set， 所以它是有序的，同样也是非线程安全的

继承关系

image.png

源码解析

经过前面我们学习HashSet和LinkedHashSet，基本上已经掌握了Set实现的套路了

  1. package java.util;
  3. // TreeSet实现了NavigableSet接口，所以它是有序的
  4. public class TreeSet<E> extends AbstractSet<E>
  5.     implements NavigableSet<E>, Cloneable, java.io.Serializable
  6. {
  7.     // 元素存储在NavigableMap中
  8.     // 注意它不一定就是TreeMap
  9.     private transient NavigableMap<E,Object> m;
  11.     // 虚拟元素, 用来作为value存储在map中
  12.     private static final Object PRESENT = new Object();
  14.     // 直接使用传进来的NavigableMap存储元素
  15.     // 这里不是深拷贝,如果外面的map有增删元素也会反映到这里
  16.     // 而且, 这个方法不是public的, 说明只能给同包使用
  17.     TreeSet(NavigableMap<E,Object> m) {
  18.         this.m = m;
  19.     }
  21.     // 使用TreeMap初始化
  22.     public TreeSet() {
  23.         this(new TreeMap<E,Object>());
  24.     }
  26.     // 使用带comparator的TreeMap初始化
  27.     public TreeSet(Comparator<? super E> comparator) {
  28.         this(new TreeMap<>(comparator));
  29.     }
  31.     // 将集合c中的所有元素添加的TreeSet中
  32.     public TreeSet(Collection<? extends E> c) {
  33.         this();
  34.         addAll(c);
  35.     }
  37.     // 将SortedSet中的所有元素添加到TreeSet中
  38.     public TreeSet(SortedSet<E> s) {
  39.         this(s.comparator());
  40.         addAll(s);
  41.     }
  43.     // 迭代器
  44.     public Iterator<E> iterator() {
  45.         return m.navigableKeySet().iterator();
  46.     }
  48.     // 逆序迭代器
  49.     public Iterator<E> descendingIterator() {
  50.         return m.descendingKeySet().iterator();
  51.     }
  53.     // 以逆序返回一个新的TreeSet
  54.     public NavigableSet<E> descendingSet() {
  55.         return new TreeSet<>(m.descendingMap());
  56.     }
  58.     // 元素个数
  59.     public int size() {
  60.         return m.size();
  61.     }
  63.     // 判断是否为空
  64.     public boolean isEmpty() {
  65.         return m.isEmpty();
  66.     }
  68.     // 判断是否包含某元素
  69.     public boolean contains(Object o) {
  70.         return m.containsKey(o);
  71.     }
  73.     // 添加元素, 调用map的put()方法, value为PRESENT
  74.     public boolean add(E e) {
  75.         return m.put(e, PRESENT)==null;
  76.     }
  78.     // 删除元素
  79.     public boolean remove(Object o) {
  80.         return m.remove(o)==PRESENT;
  81.     }
  83.     // 清空所有元素
  84.     public void clear() {
  85.         m.clear();
  86.     }
  88.     // 添加集合c中的所有元素
  89.     public  boolean addAll(Collection<? extends E> c) {
  90.         // 满足一定条件时直接调用TreeMap的addAllForTreeSet()方法添加元素
  91.         if (m.size()==0 && c.size() > 0 &&
  92.             c instanceof SortedSet &&
  93.             m instanceof TreeMap) {
  94.             SortedSet<? extends E> set = (SortedSet<? extends E>) c;
  95.             TreeMap<E,Object> map = (TreeMap<E, Object>) m;
  96.             Comparator<?> cc = set.comparator();
  97.             Comparator<? super E> mc = map.comparator();
  98.             if (cc==mc || (cc != null && cc.equals(mc))) {
  99.                 map.addAllForTreeSet(set, PRESENT);
  100.                 return true;
  101.             }
  102.         }
  103.         // 不满足上述条件, 调用父类的addAll()通过遍历的方式一个一个地添加元素
  104.         return super.addAll(c);
  105.     }
  107.     // 子set（NavigableSet中的方法）
  108.     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
  109.                                   E toElement,   boolean toInclusive) {
  110.         return new TreeSet<>(m.subMap(fromElement, fromInclusive,
  111.                                        toElement,   toInclusive));
  112.     }
  114.     // 头set（NavigableSet中的方法）
  115.     public NavigableSet<E> headSet(E toElement, boolean inclusive) {
  116.         return new TreeSet<>(m.headMap(toElement, inclusive));
  117.     }
  119.     // 尾set（NavigableSet中的方法）
  120.     public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
  121.         return new TreeSet<>(m.tailMap(fromElement, inclusive));
  122.     }
  124.     // 子set（SortedSet接口中的方法）
  125.     public SortedSet<E> subSet(E fromElement, E toElement) {
  126.         return subSet(fromElement, true, toElement, false);
  127.     }
  129.     // 头set（SortedSet接口中的方法）
  130.     public SortedSet<E> headSet(E toElement) {
  131.         return headSet(toElement, false);
  132.     }
  134.     // 尾set（SortedSet接口中的方法）
  135.     public SortedSet<E> tailSet(E fromElement) {
  136.         return tailSet(fromElement, true);
  137.     }
  139.     // 比较器
  140.     public Comparator<? super E> comparator() {
  141.         return m.comparator();
  142.     }
  144.     // 返回最小的元素
  145.     public E first() {
  146.         return m.firstKey();
  147.     }
  149.     // 返回最大的元素
  150.     public E last() {
  151.         return m.lastKey();
  152.     }
  154.     // 返回小于e的最大的元素
  155.     public E lower(E e) {
  156.         return m.lowerKey(e);
  157.     }
  159.     // 返回小于等于e的最大的元素
  160.     public E floor(E e) {
  161.         return m.floorKey(e);
  162.     }
  164.     // 返回大于等于e的最小的元素
  165.     public E ceiling(E e) {
  166.         return m.ceilingKey(e);
  167.     }
  169.     // 返回大于e的最小的元素
  170.     public E higher(E e) {
  171.         return m.higherKey(e);
  172.     }
  174.     // 弹出最小的元素
  175.     public E pollFirst() {
  176.         Map.Entry<E,?> e = m.pollFirstEntry();
  177.         return (e == null) ? null : e.getKey();
  178.     }
  180.     public E pollLast() {
  181.         Map.Entry<E,?> e = m.pollLastEntry();
  182.         return (e == null) ? null : e.getKey();
  183.     }
  185.     // 克隆方法
  186.     @SuppressWarnings("unchecked")
  187.     public Object clone() {
  188.         TreeSet<E> clone;
  189.         try {
  190.             clone = (TreeSet<E>) super.clone();
  191.         } catch (CloneNotSupportedException e) {
  192.             throw new InternalError(e);
  193.         }
  195.         clone.m = new TreeMap<>(m);
  196.         return clone;
  197.     }
  199.     // 序列化写出方法
  200.     private void writeObject(java.io.ObjectOutputStream s)
  201.         throws java.io.IOException {
  202.         // Write out any hidden stuff
  203.         s.defaultWriteObject();
  205.         // Write out Comparator
  206.         s.writeObject(m.comparator());
  208.         // Write out size
  209.         s.writeInt(m.size());
  211.         // Write out all elements in the proper order.
  212.         for (E e : m.keySet())
  213.             s.writeObject(e);
  214.     }
  216.     // 序列化写入方法
  217.     private void readObject(java.io.ObjectInputStream s)
  218.         throws java.io.IOException, ClassNotFoundException {
  219.         // Read in any hidden stuff
  220.         s.defaultReadObject();
  222.         // Read in Comparator
  223.         @SuppressWarnings("unchecked")
  224.             Comparator<? super E> c = (Comparator<? super E>) s.readObject();
  226.         // Create backing TreeMap
  227.         TreeMap<E,Object> tm = new TreeMap<>(c);
  228.         m = tm;
  230.         // Read in size
  231.         int size = s.readInt();
  233.         tm.readTreeSet(size, s, PRESENT);
  234.     }
  236.     // 可分割的迭代器
  237.     public Spliterator<E> spliterator() {
  238.         return TreeMap.keySpliteratorFor(m);
  239.     }
  241.     // 序列化id
  242.     private static final long serialVersionUID = -2479143000061671589L;
  243. }

源码比较简单，基本都是调用map 相应的方法。

总结

（1）TreeSet底层使用NavigableMap存储元素；
（2）TreeSet是有序的；
（3）TreeSet是非线程安全的；
（4）TreeSet实现了NavigableSet接口，而NavigableSet继承自SortedSet接口；
（5）TreeSet实现了SortedSet接口