java源码-TreeSet

开篇

 TreeSet作为HashSet的姊妹类型，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();
        }