关于 HashSet

发表于 更新于 分类于

HashSet 的 DOC 注释

-Basic JDK7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * This class implements the <tt>Set</tt> interface, backed by a hash table
 * (actually a <tt>HashMap</tt> instance).  It makes no guarantees as to the
 * iteration order of the set; in particular, it does not guarantee that the
 * order will remain constant over time.  This class permits the <tt>null</tt>
 * element.
 * 该类是由 hash table(实际上是 HashMap 实例) 支持的 Set 接口的实现类。它不能保证 set 的迭代顺序；特别是，它不保证 set 内元素的顺序随着时间的变化不会改变。该类允许(添加) null 元素。
 * <p>This class offers constant time performance for the basic operations
 * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
 * assuming the hash function disperses the elements properly among the
 * buckets.  Iterating over this set requires time proportional to the sum of
 * the <tt>HashSet</tt> instance's size (the number of elements) plus the
 * "capacity" of the backing <tt>HashMap</tt> instance (the number of
 * buckets).  Thus, it's very important not to set the initial capacity too
 * high (or the load factor too low) if iteration performance is important.
 * 该类的基本操作(add，remove，contains 和 size)提供O(1)的级别的性能表现，假设 hash 方法将元素均匀的分布在桶中。遍历整个 set 所需的时间与 HashSet 实例的 size(元素数量) * (底层 HashMap 实例的 capacity(桶的数量)) 成正比。
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a hash set concurrently, and at least one of
 * the threads modifies the set, it <i>must</i> be synchronized externally.
 * This is typically accomplished by synchronizing on some object that
 * naturally encapsulates the set.
 * 参见 HashMap
 * If no such object exists, the set should be "wrapped" using the
 * {@link Collections#synchronizedSet Collections.synchronizedSet}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the set:<pre>
 *   Set s = Collections.synchronizedSet(new HashSet(...));</pre>
 * 参见 HashMap
 * <p>The iterators returned by this class's <tt>iterator</tt> method are
 * <i>fail-fast</i>: if the set is modified at any time after the iterator is
 * created, in any way except through the iterator's own <tt>remove</tt>
 * method, the Iterator throws a {@link ConcurrentModificationException}.
 * Thus, in the face of concurrent modification, the iterator fails quickly
 * and cleanly, rather than risking arbitrary, non-deterministic behavior at
 * an undetermined time in the future.
 * 参见 HashMap
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * 参见 HashMap
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <E> the type of elements maintained by this set
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     Set
 * @see     TreeSet
 * @see     HashMap
 * @since   1.2
 */
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

HashSet 的类属性、构造方法及 add() 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
// 由 Map 接口支持的虚拟对象
private static final Object PRESENT = new Object();

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 * 构造一个新的空的 set；提供底层支持的 HashMap 实例的 默认初始 capacity 为 16，负载因子为 0.75。
 */
public HashSet() {
    map = new HashMap<>();
}

/**
 * Constructs a new set containing the elements in the specified
 * collection.  The <tt>HashMap</tt> is created with default load factor
 * (0.75) and an initial capacity sufficient to contain the elements in
 * the specified collection.
 * 构造一个包含指定 collection 中的元素的新 set 实例。
 * @param c the collection whose elements are to be placed into this set
 * @throws NullPointerException if the specified collection is null
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
/**
 * {@inheritDoc}
 * 该方法继承自 AbstractCollection(即，HashSet 没有重写 addAll()，直接指向的是 AbstractCollection.addAll()方法) 
 * <p>This implementation iterates over the specified collection, and adds
 * each object returned by the iterator to this collection, in turn.
 * 该方法实现遍历整个指定的 collection，并且将 collection 的 iterator 返回的每个 对象按顺序添加到 set 中。
 * <p>Note that this implementation will throw an
 * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
 * overridden (assuming the specified collection is non-empty).
 * 需要注意的是，这个方法实现会抛出一个 UnsupportedOperationException 异常，除非 add() 被重写(假设指定的 collection 是非空的)。
 * @throws UnsupportedOperationException {@inheritDoc}
 * @throws ClassCastException            {@inheritDoc}
 * @throws NullPointerException          {@inheritDoc}
 * @throws IllegalArgumentException      {@inheritDoc}
 * @throws IllegalStateException         {@inheritDoc}
 *
 * @see #add(Object)
 */
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}
/**
 * Adds the specified element to this set if it is not already present.
 * More formally, adds the specified element <tt>e</tt> to this set if
 * this set contains no element <tt>e2</tt> such that
 * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
 * If this set already contains the element, the call leaves the set
 * unchanged and returns <tt>false</tt>.
 * 添加指定元素到 set 中，如果 set 中还没有该元素。严谨来说，添加一个元素 e 到该 set 中，如果 set 中不存在一个满足这样条件的 (e2: e==null ? e2==null : e.equals(e2)).如果 set 中已经存在一个这样的元素，当次调用不会改变 set，并且放回 false。
 * @param e element to be added to this set
 * @return <tt>true</tt> if this set did not already contain the specified
 * element
 */
public boolean add(E e) {
    // map.put() 返回 null，说明添加新值成功；否则说明添加的元素发生哈希碰撞，或者是重复添加相同元素。
    // 另外，需要注意到的是 PRESENT，即影子对象，没有实际意义，纯粹为了填充 value。
    return map.put(e, PRESENT)==null;
}
    
/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and the specified load factor.
 * 构建一个新的空的 set；指定构建由底层提供支持的 HashMap 实例时的初始容量，和负载因子。
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and default load factor (0.75).
 * 构建一个新的空 set；指定构建由底层提供支持的 HashMap 实例时的初始容量，负载因子默认为 0.75.
 * @param      initialCapacity   the initial capacity of the hash table
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 * 构建一个新的空 Linked Hash set。(这个包级作用域私有的构造器只能被 LinkedHashSet 使用)。底层提供支持的 HashMap 实例是一个 由指定初始容量和指定负载因子的 LinkedHashMap。
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

remove()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Removes the specified element from this set if it is present.
 * More formally, removes an element <tt>e</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
 * if this set contains such an element.  Returns <tt>true</tt> if
 * this set contained the element (or equivalently, if this set
 * changed as a result of the call).  (This set will not contain the
 * element once the call returns.)
 *
 * @param o object to be removed from this set, if present
 * @return <tt>true</tt> if the set contained the specified element
 */
public boolean remove(Object o) {
    // 见 HashMap.remove()
    return map.remove(o)==PRESENT;
}

iterator()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Returns an iterator over the elements in this set.  The elements
 * are returned in no particular order.
 * 返回 set 中元素的 iterator。(迭代器)返回的元素是无序的。
 * @return an Iterator over the elements in this set
 * @see ConcurrentModificationException
 */
public Iterator<E> iterator() {
    return map.keySet().iterator();
}
// 最终指向 HashMap 中的 KeyIterator
private final class KeyIterator extends HashIterator<K> {
    public K next() {
        return nextEntry().getKey();
    }
}
// nextEntry 位于 HashIterator；
// getKey() 是 Entry<K,V> 类中 key getter 方法。
final Entry<K,V> nextEntry() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    Entry<K,V> e = next;
    if (e == null)
        throw new NoSuchElementException();

    if ((next = e.next) == null) {
        Entry[] t = table;
        while (index < t.length && (next = t[index++]) == null)
            ;
    }
    current = e;
    return e;
}

其他方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 以下方法都是对 HashMap 的方法的封装
/**
 * Returns the number of elements in this set (its cardinality).
 * 返回 set 中元素的个数(它的基数???)。
 * @return the number of elements in this set (its cardinality)
 */
public int size() {
    // map.size 为 map 中键值对的数量
    return map.size();
}

/**
 * Returns <tt>true</tt> if this set contains no elements.
 *
 * @return <tt>true</tt> if this set contains no elements
 */
public boolean isEmpty() {
    // return map.size==0
    return map.isEmpty();
}

/**
 * Returns <tt>true</tt> if this set contains the specified element.
 * More formally, returns <tt>true</tt> if and only if this set
 * contains an element <tt>e</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 * 如果 set 中包含指定元素，则返回 true。严谨来说：当且仅当 (o==null ? e==null : o.equals(e))时，返回 true.
 * @param o element whose presence in this set is to be tested
 * @return <tt>true</tt> if this set contains the specified element
 */
public boolean contains(Object o) {
    // return map.getEntry(key) != null;
    return map.containsKey(o);
}