JDK源码-Set系列

Set*

/**
 * A collection that contains no duplicate elements.  More formally, sets
 * contain no pair of elements <code>e1</code> and <code>e2</code> such that
 * <code>e1.equals(e2)</code>, and at most one null element.  As implied by
 * its name, this interface models the mathematical <i>set</i> abstraction.
   Set是一个没有重复元素的集合.在一个 Set 中，不能有两个引用指向同一个对象，
或两个指向 null 的引用。如果对象 a 和 b 的引用满足条件 a.equals(b)，那么这两个
对象也不能同时出现在集合中。
该接口的大部分方法继承于Collection.
 *
 * <p>The <tt>Set</tt> interface places additional stipulations, beyond those
 * inherited from the <tt>Collection</tt> interface, on the contracts of all
 * constructors and on the contracts of the <tt>add</tt>, <tt>equals</tt> and
 * <tt>hashCode</tt> methods.  Declarations for other inherited methods are
 * also included here for convenience.  (The specifications accompanying these
 * declarations have been tailored to the <tt>Set</tt> interface, but they do
 * not contain any additional stipulations.)
  Set除了继承Collection接口的一些方法之后,具有很多一些其他的规定.
 *
 * <p>The additional stipulation on constructors is, not surprisingly,
 * that all constructors must create a set that contains no duplicate elements
 * (as defined above).
 *
 * <p>Note: Great care must be exercised if mutable objects are used as set
 * elements.  The behavior of a set is not specified if the value of an object
 * is changed in a manner that affects <tt>equals</tt> comparisons while the
 * object is an element in the set.  A special case of this prohibition is
 * that it is not permissible for a set to contain itself as an element.
 *
 * <p>Some set implementations have restrictions on the elements that
 * they may contain.  For example, some implementations prohibit null elements,
 * and some have restrictions on the types of their elements.  Attempting to
 * add an ineligible element throws an unchecked exception, typically
 * <tt>NullPointerException</tt> or <tt>ClassCastException</tt>.  Attempting
 * to query the presence of an ineligible element may throw an exception,
 * or it may simply return false; some implementations will exhibit the former
 * behavior and some will exhibit the latter.  More generally, attempting an
 * operation on an ineligible element whose completion would not result in
 * the insertion of an ineligible element into the set may throw an
 * exception or it may succeed, at the option of the implementation.
 * Such exceptions are marked as "optional" in the specification for this
 * interface.
 *
 * <p>This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *

类图:

TreeSet实现

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, 
or by a Comparator provided at set creation time, depending on which constructor is used.This 
implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

• TreeSet主要依赖于NavigableMap实现,由于NavigableMap只是一个接口，因此底层依然是使用TreeMap来包含Set集合中的所有元素.TreeMap本身是有序的,所以TreeSet也是有序的.

/**
     * Constructs a new, empty tree set, sorted according to the
     * natural ordering of its elements.  All elements inserted into
     * the set must implement the {@link Comparable} interface.
     * Furthermore, all such elements must be <i>mutually
     * comparable</i>: {@code e1.compareTo(e2)} must not throw a
     * {@code ClassCastException} for any elements {@code e1} and
     * {@code e2} in the set.  If the user attempts to add an element
     * to the set that violates this constraint (for example, the user
     * attempts to add a string element to a set whose elements are
     * integers), the {@code add} call will throw a
     * {@code ClassCastException}.
     */
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

• 添加元素时,通过在内置的map添加一个<元素,PRESENT(dummy Obejct)>.

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element {@code e} to this set if
     * the set contains no element {@code e2} such that
     * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns {@code false}.
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     *         element
     * @throws ClassCastException if the specified object cannot be compared
     *         with the elements currently in this set
     * @throws NullPointerException if the specified element is null
     *         and this set uses natural ordering, or its comparator
     *         does not permit null elements
     */
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

HashSet

• HashSet 实现了 Set 接口，而 Set 接口是继承于 Collection 接口，所以可以认为 Set 接口是 List 接口的兄弟。

• HashSet底层是通过HashMap实现,所以他也是无序的.

• 其实就是 HashSet 用了一个空对象，如 private static final Object PRESENT = new Object
  用这个空对象来填充 HashMap 的 value 域
  用这个空对象来填充 HashMap 的 value 域
  用这个空对象来填充 HashMap 的 value 域
  如下面的 add 方法：

private transient HashMap<E,Object> map;

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

• so:从这里就可以看出：
  利用了 HashMap 实现。HashSet 的方法就是调用 HashMap 的对应的方法。
  用空对象来填充 HashMap 的 value 域