关于 HashSet

HashSet 的 DOC 注释

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