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 域
