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