TreeSet的整体架构

TreeSet 大致的结构和 HashSet 相似，底层组合的是 TreeMap，所以拥有 TreeMap key 能够排序的功能，迭代时，也可以按照 key 的排序顺序进行迭代。

  1. public class TreeSet<E> extends AbstractSet<E>
  2.     implements NavigableSet<E>, Cloneable, java.io.Serializable {
  4.     // 底层的 map
  5.     private transient NavigableMap<E,Object> m;
  7.     // 虚拟值，以关联一个对象在 map 的 value 值
  8.     // 简而言之，该值是 TreeMap 中的 value
  9.     private static final Object PRESENT = new Object();
  11.     /**
  12.      * Constructs a set backed by the specified navigable map.
  13.      */
  14.     TreeSet(NavigableMap<E,Object> m) {
  15.         this.m = m;
  16.     }
  18.     /**
  19.      * Constructs a new, empty tree set, sorted according to the
  20.      * natural ordering of its elements.  All elements inserted into
  21.      * the set must implement the {@link Comparable} interface.
  22.      * Furthermore, all such elements must be <i>mutually
  23.      * comparable</i>: {@code e1.compareTo(e2)} must not throw a
  24.      * {@code ClassCastException} for any elements {@code e1} and
  25.      * {@code e2} in the set.  If the user attempts to add an element
  26.      * to the set that violates this constraint (for example, the user
  27.      * attempts to add a string element to a set whose elements are
  28.      * integers), the {@code add} call will throw a
  29.      * {@code ClassCastException}.
  30.      */
  31.     public TreeSet() {
  32.         this(new TreeMap<E,Object>());
  33.     }
  35.     /**
  36.      * Constructs a new, empty tree set, sorted according to the specified
  37.      * comparator.  All elements inserted into the set must be <i>mutually
  38.      * comparable</i> by the specified comparator: {@code comparator.compare(e1,
  39.      * e2)} must not throw a {@code ClassCastException} for any elements
  40.      * {@code e1} and {@code e2} in the set.  If the user attempts to add
  41.      * an element to the set that violates this constraint, the
  42.      * {@code add} call will throw a {@code ClassCastException}.
  43.      *
  44.      * @param comparator the comparator that will be used to order this set.
  45.      *        If {@code null}, the {@linkplain Comparable natural
  46.      *        ordering} of the elements will be used.
  47.      */
  48.     public TreeSet(Comparator<? super E> comparator) {
  49.         this(new TreeMap<>(comparator));
  50.     }
  52.     /**
  53.      * Constructs a new tree set containing the elements in the specified
  54.      * collection, sorted according to the <i>natural ordering</i> of its
  55.      * elements.  All elements inserted into the set must implement the
  56.      * {@link Comparable} interface.  Furthermore, all such elements must be
  57.      * <i>mutually comparable</i>: {@code e1.compareTo(e2)} must not throw a
  58.      * {@code ClassCastException} for any elements {@code e1} and
  59.      * {@code e2} in the set.
  60.      *
  61.      * @param c collection whose elements will comprise the new set
  62.      * @throws ClassCastException if the elements in {@code c} are
  63.      *         not {@link Comparable}, or are not mutually comparable
  64.      * @throws NullPointerException if the specified collection is null
  65.      */
  66.     public TreeSet(Collection<? extends E> c) {
  67.         this();
  68.         addAll(c);
  69.     }
  71.     /**
  72.      * Constructs a new tree set containing the same elements and
  73.      * using the same ordering as the specified sorted set.
  74.      *
  75.      * @param s sorted set whose elements will comprise the new set
  76.      * @throws NullPointerException if the specified sorted set is null
  77.      */
  78.     public TreeSet(SortedSet<E> s) {
  79.         this(s.comparator());
  80.         addAll(s);
  81.     }

TreeSet的

TreeSet的

TreeSet的

TreeSet复用TreeMap的不同方式

TreeSet 组合 TreeMap 实现的两种思路：

  • TreeSet 直接使用 TreeMap 的某些功能，自己包装成新的 api
  • TreeSet 定义自己想要的 api，自己定义接口规范，让 TreeMap 去实现

思路 1 和 2 的调用关系，都是 TreeSet 调用 TreeMap，但功能的实现关系完全相反，
第一种是：功能的定义和实现都在 TreeMap，TreeSet 只是简单的调用而已。
第二种是： TreeSet 把接口定义出来后，让 TreeMap 去实现内部逻辑，这样子的话因为接口是 TreeSet 定义的，所以实现一定是 TreeSet 最想要的，TreeSet 甚至都不用包装，可以直接把返回值吐出去都行。

场景一： TreeSet 的 add() ，其底层源码实现如下：

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

可以看到，底层直接使用的是 HashMap 的 put 的能力，直接拿来用。

场景二：TreeSet 的迭代 ，其底层源码实现如下：

  1. // NavigableSet 接口，其定义了迭代的一些规范，和取值的一些特殊方法
  2. // TreeSet 实现了该方法，也就是说 TreeSet 本身已经定义了迭代的规范
  3. // 这是一个单独的接口（只写出了其中的两个方法，还有其他的）
  4. public interface NavigableSet<E> extends SortedSet<E> {
  5.     // 按升序返回该集合中元素的迭代器
  6.     Iterator<E> iterator();
  7.     E lower(E e);
  8. }
  9. // m.navigableKeySet() 是 TreeMap 写了一个子类实现了 NavigableSet
  10. // 接口，实现了 TreeSet 定义的迭代规范
  11. // 这是 TreeSet 类中的方法
  12. public Iterator<E> iterator() {
  13.     return m.navigableKeySet().iterator();
  14. }

从下面 TreeMap 的源码中可以看出 TreeMap 实现了 TreeSet 定义的各种特殊方法。
这种思路是 TreeSet 定义了接口的规范，TreeMap 负责去实现，实现思路和场景一是相反的。 

  1. // TreeMap 类中的部分源码
  2. // TreeMap 中对 NavigableSet 接口的实现源码
  3. static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
  4.     private final NavigableMap<E, ?> m;
  5.     KeySet(NavigableMap<E,?> map) { m = map; }
  7.     public Iterator<E> iterator() {
  8.         if (m instanceof TreeMap)
  9.             return ((TreeMap<E,?>)m).keyIterator();
  10.         else
  11.             return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
  12.     }
  14.     public Iterator<E> descendingIterator() {
  15.         if (m instanceof TreeMap)
  16.             return ((TreeMap<E,?>)m).descendingKeyIterator();
  17.         else
  18.             return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator();
  19.     }
  21.     public int size() { return m.size(); }
  22.     public boolean isEmpty() { return m.isEmpty(); }
  23.     public boolean contains(Object o) { return m.containsKey(o); }
  24.     public void clear() { m.clear(); }
  25.     public E lower(E e) { return m.lowerKey(e); }
  26.     public E floor(E e) { return m.floorKey(e); }
  27.     public E ceiling(E e) { return m.ceilingKey(e); }
  28.     public E higher(E e) { return m.higherKey(e); }
  29.     public E first() { return m.firstKey(); }
  30.     public E last() { return m.lastKey(); }
  31.     public Comparator<? super E> comparator() { return m.comparator(); }
  32.     public E pollFirst() {
  33.         Map.Entry<E,?> e = m.pollFirstEntry();
  34.         return (e == null) ? null : e.getKey();
  35.     }
  36.     public E pollLast() {
  37.         Map.Entry<E,?> e = m.pollLastEntry();
  38.         return (e == null) ? null : e.getKey();
  39.     }
  40.     public boolean remove(Object o) {
  41.         int oldSize = size();
  42.         m.remove(o);
  43.         return size() != oldSize;
  44.     }
  45.     public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
  46.                                   E toElement,   boolean toInclusive) {
  47.         return new KeySet<>(m.subMap(fromElement, fromInclusive,
  48.                                      toElement,   toInclusive));
  49.     }
  50.     public NavigableSet<E> headSet(E toElement, boolean inclusive) {
  51.         return new KeySet<>(m.headMap(toElement, inclusive));
  52.     }
  53.     public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
  54.         return new KeySet<>(m.tailMap(fromElement, inclusive));
  55.     }
  56.     public SortedSet<E> subSet(E fromElement, E toElement) {
  57.         return subSet(fromElement, true, toElement, false);
  58.     }
  59.     public SortedSet<E> headSet(E toElement) {
  60.         return headSet(toElement, false);
  61.     }
  62.     public SortedSet<E> tailSet(E fromElement) {
  63.         return tailSet(fromElement, true);
  64.     }
  65.     public NavigableSet<E> descendingSet() {
  66.         return new KeySet<>(m.descendingMap());
  67.     }
  69.     public Spliterator<E> spliterator() {
  70.         return keySpliteratorFor(m);
  71.     }
  72. }

TreeSet的常见问题

说一下TreeSet的使用场景

答：我们一般都是在需要把元素进行排序的时候使用 TreeSet。
使用 TreeSet 时需要注意，元素最好实现 Comparable 接口，这样方便底层的 TreeMap 根据 key 进行排序。