HashSet的实现其实很简单 HashSet是无序 不可重复的 查看源码可以了解到 内部是用了一个HashMap HashSet的元素其实就是HashMap的KeySet, HashMap的实现是数组 + 链表的数据结构 HashSet既然是利用的HashMap 那么HashSet也是线程不安全的 HashSet源码如下
1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
4 *
5 *
6 *
7 *
8 *
9 *
10 *
11 *
12 *
13 *
14 *
15 *
16 *
17 *
18 *
19 *
20 *
21 *
22 *
23 *
24 */
25
26 package java.util;
27
28 import java.io.InvalidObjectException;
29
30 /**
31 * This class implements the Set interface, backed by a hash table
32 * (actually a HashMap instance). It makes no guarantees as to the
33 * iteration order of the set; in particular, it does not guarantee that the
34 * order will remain constant over time. This class permits the null
35 * element.
36 *
37 * This class offers constant time performance for the basic operations
38 * (add, remove, contains and size),
39 * assuming the hash function disperses the elements properly among the
40 * buckets. Iterating over this set requires time proportional to the sum of
41 * the HashSet instance's size (the number of elements) plus the
42 * "capacity" of the backing HashMap instance (the number of
43 * buckets). Thus, it's very important not to set the initial capacity too
44 * high (or the load factor too low) if iteration performance is important.
45 *
46 * Note that this implementation is not synchronized.
47 * If multiple threads access a hash set concurrently, and at least one of
48 * the threads modifies the set, it must be synchronized externally.
49 * This is typically accomplished by synchronizing on some object that
50 * naturally encapsulates the set.
51 *
52 * If no such object exists, the set should be "wrapped" using the
53 * {@link Collections#synchronizedSet Collections.synchronizedSet}
54 * method. This is best done at creation time, to prevent accidental
55 * unsynchronized access to the set:
56 * Set s = Collections.synchronizedSet(new HashSet(...));
57 *
58 * The iterators returned by this class's iterator method are
59 * fail-fast: if the set is modified at any time after the iterator is
60 * created, in any way except through the iterator's own remove
61 * method, the Iterator throws a {@link ConcurrentModificationException}.
62 * Thus, in the face of concurrent modification, the iterator fails quickly
63 * and cleanly, rather than risking arbitrary, non-deterministic behavior at
64 * an undetermined time in the future.
65 *
66 * Note that the fail-fast behavior of an iterator cannot be guaranteed
67 * as it is, generally speaking, impossible to make any hard guarantees in the
68 * presence of unsynchronized concurrent modification. Fail-fast iterators
69 * throw ConcurrentModificationException on a best-effort basis.
70 * Therefore, it would be wrong to write a program that depended on this
71 * exception for its correctness: the fail-fast behavior of iterators
72 * should be used only to detect bugs.
73 *
74 * This class is a member of the
75 * docRoot}/../technotes/guides/collections/index.html">
76 * Java Collections Framework.
77 *
78 * @param the type of elements maintained by this set
79 *
80 * @author Josh Bloch
81 * @author Neal Gafter
82 * @see Collection
83 * @see Set
84 * @see TreeSet
85 * @see HashMap
86 * @since 1.2
87 */
88
89 public class HashSet
90 extends AbstractSet
91 implements Set, Cloneable, java.io.Serializable
92 {
93 static final long serialVersionUID = -5024744406713321676L;
94
95 private transient HashMap map;
96
97 // Dummy value to associate with an Object in the backing Map
98 private static final Object PRESENT = new Object();
99
100 /**
101 * Constructs a new, empty set; the backing HashMap instance has
102 * default initial capacity (16) and load factor (0.75).
103 */
104 public HashSet() {
105 map = new HashMap<>();
106 }
107
108 /**
109 * Constructs a new set containing the elements in the specified
110 * collection. The HashMap is created with default load factor
111 * (0.75) and an initial capacity sufficient to contain the elements in
112 * the specified collection.
113 *
114 * @param c the collection whose elements are to be placed into this set
115 * @throws NullPointerException if the specified collection is null
116 */
117 public HashSet(Collection<? extends E> c) {
118 map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
119 addAll(c);
120 }
121
122 /**
123 * Constructs a new, empty set; the backing HashMap instance has
124 * the specified initial capacity and the specified load factor.
125 *
126 * @param initialCapacity the initial capacity of the hash map
127 * @param loadFactor the load factor of the hash map
128 * @throws IllegalArgumentException if the initial capacity is less
129 * than zero, or if the load factor is nonpositive
130 */
131 public HashSet(int initialCapacity, float loadFactor) {
132 map = new HashMap<>(initialCapacity, loadFactor);
133 }
134
135 /**
136 * Constructs a new, empty set; the backing HashMap instance has
137 * the specified initial capacity and default load factor (0.75).
138 *
139 * @param initialCapacity the initial capacity of the hash table
140 * @throws IllegalArgumentException if the initial capacity is less
141 * than zero
142 */
143 public HashSet(int initialCapacity) {
144 map = new HashMap<>(initialCapacity);
145 }
146
147 /**
148 * Constructs a new, empty linked hash set. (This package private
149 * constructor is only used by LinkedHashSet.) The backing
150 * HashMap instance is a LinkedHashMap with the specified initial
151 * capacity and the specified load factor.
152 *
153 * @param initialCapacity the initial capacity of the hash map
154 * @param loadFactor the load factor of the hash map
155 * @param dummy ignored (distinguishes this
156 * constructor from other int, float constructor.)
157 * @throws IllegalArgumentException if the initial capacity is less
158 * than zero, or if the load factor is nonpositive
159 */
160 HashSet(int initialCapacity, float loadFactor, boolean dummy) {
161 map = new LinkedHashMap<>(initialCapacity, loadFactor);
162 }
163
164 /**
165 * Returns an iterator over the elements in this set. The elements
166 * are returned in no particular order.
167 *
168 * @return an Iterator over the elements in this set
169 * @see ConcurrentModificationException
170 */
171 public Iterator iterator() {
172 return map.keySet().iterator();
173 }
174
175 /**
176 * Returns the number of elements in this set (its cardinality).
177 *
178 * @return the number of elements in this set (its cardinality)
179 */
180 public int size() {
181 return map.size();
182 }
183
184 /**
185 * Returns true if this set contains no elements.
186 *
187 * @return true if this set contains no elements
188 */
189 public boolean isEmpty() {
190 return map.isEmpty();
191 }
192
193 /**
194 * Returns true if this set contains the specified element.
195 * More formally, returns true if and only if this set
196 * contains an element e such that
197 * (o==null ? e==null : o.equals(e)).
198 *
199 * @param o element whose presence in this set is to be tested
200 * @return true if this set contains the specified element
201 */
202 public boolean contains(Object o) {
203 return map.containsKey(o);
204 }
205
206 /**
207 * Adds the specified element to this set if it is not already present.
208 * More formally, adds the specified element e to this set if
209 * this set contains no element e2 such that
210 * (e==null ? e2==null : e.equals(e2)).
211 * If this set already contains the element, the call leaves the set
212 * unchanged and returns false.
213 *
214 * @param e element to be added to this set
215 * @return true if this set did not already contain the specified
216 * element
217 */
218 public boolean add(E e) {
219 return map.put(e, PRESENT)==null;
220 }
221
222 /**
223 * Removes the specified element from this set if it is present.
224 * More formally, removes an element e such that
225 * (o==null ? e==null : o.equals(e)),
226 * if this set contains such an element. Returns true if
227 * this set contained the element (or equivalently, if this set
228 * changed as a result of the call). (This set will not contain the
229 * element once the call returns.)
230 *
231 * @param o object to be removed from this set, if present
232 * @return true if the set contained the specified element
233 */
234 public boolean remove(Object o) {
235 return map.remove(o)==PRESENT;
236 }
237
238 /**
239 * Removes all of the elements from this set.
240 * The set will be empty after this call returns.
241 */
242 public void clear() {
243 map.clear();
244 }
245
246 /**
247 * Returns a shallow copy of this HashSet instance: the elements
248 * themselves are not cloned.
249 *
250 * @return a shallow copy of this set
251 */
252 @SuppressWarnings("unchecked")
253 public Object clone() {
254 try {
255 HashSet newSet = (HashSet) super.clone();
256 newSet.map = (HashMap) map.clone();
257 return newSet;
258 } catch (CloneNotSupportedException e) {
259 throw new InternalError(e);
260 }
261 }
262
263 /**
264 * Save the state of this HashSet instance to a stream (that is,
265 * serialize it).
266 *
267 * @serialData The capacity of the backing HashMap instance
268 * (int), and its load factor (float) are emitted, followed by
269 * the size of the set (the number of elements it contains)
270 * (int), followed by all of its elements (each an Object) in
271 * no particular order.
272 */
273 private void writeObject(java.io.ObjectOutputStream s)
274 throws java.io.IOException {
275 // Write out any hidden serialization magic
276 s.defaultWriteObject();
277
278 // Write out HashMap capacity and load factor
279 s.writeInt(map.capacity());
280 s.writeFloat(map.loadFactor());
281
282 // Write out size
283 s.writeInt(map.size());
284
285 // Write out all elements in the proper order.
286 for (E e : map.keySet())
287 s.writeObject(e);
288 }
289
290 /**
291 * Reconstitute the HashSet instance from a stream (that is,
292 * deserialize it).
293 */
294 private void readObject(java.io.ObjectInputStream s)
295 throws java.io.IOException, ClassNotFoundException {
296 // Read in any hidden serialization magic
297 s.defaultReadObject();
298
299 // Read capacity and verify non-negative.
300 int capacity = s.readInt();
301 if (capacity < 0) {
302 throw new InvalidObjectException("Illegal capacity: " +
303 capacity);
304 }
305
306 // Read load factor and verify positive and non NaN.
307 float loadFactor = s.readFloat();
308 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
309 throw new InvalidObjectException("Illegal load factor: " +
310 loadFactor);
311 }
312
313 // Read size and verify non-negative.
314 int size = s.readInt();
315 if (size < 0) {
316 throw new InvalidObjectException("Illegal size: " +
317 size);
318 }
319
320 // Set the capacity according to the size and load factor ensuring that
321 // the HashMap is at least 25% full but clamping to maximum capacity.
322 capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
323 HashMap.MAXIMUM_CAPACITY);
324
325 // Create backing HashMap
326 map = (((HashSet<?>)this) instanceof LinkedHashSet ?
327 new LinkedHashMap(capacity, loadFactor) :
328 new HashMap(capacity, loadFactor));
329
330 // Read in all elements in the proper order.
331 for (int i=0; i) {
332 @SuppressWarnings("unchecked")
333 E e = (E) s.readObject();
334 map.put(e, PRESENT);
335 }
336 }
337
338 /**
339 * Creates a late-binding
340 * and fail-fast {@link Spliterator} over the elements in this
341 * set.
342 *
343 * The {
@code Spliterator} reports {@link Spliterator#SIZED} and
344 * {@link Spliterator#DISTINCT}. Overriding implementations should document
345 * the reporting of additional characteristic values.
346 *
347 * @return a {@code Spliterator} over the elements in this set
348 * @since 1.8
349 */
350 public Spliterator spliterator() {
351 return new HashMap.KeySpliterator(map, 0, -1, 0, 0);
352 }
353 }