1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.io.InvalidObjectException;
29
30 /**
31 * This class implements the {@code Set} interface, backed by a hash table
32 * (actually a {@code 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 {@code null}
35 * element.
36 *
37 * <p>This class offers constant time performance for the basic operations
38 * ({@code add}, {@code remove}, {@code contains} and {@code 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 {@code HashSet} instance's size (the number of elements) plus the
42 * "capacity" of the backing {@code 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 * <p><strong>Note that this implementation is not synchronized.</strong>
47 * If multiple threads access a hash set concurrently, and at least one of
48 * the threads modifies the set, it <i>must</i> 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:<pre>
56 * Set s = Collections.synchronizedSet(new HashSet(...));</pre>
57 *
58 * <p>The iterators returned by this class's {@code iterator} method are
59 * <i>fail-fast</i>: if the set is modified at any time after the iterator is
60 * created, in any way except through the iterator's own {@code 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 * <p>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 {@code 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: <i>the fail-fast behavior of iterators
72 * should be used only to detect bugs.</i>
73 *
74 * <p>This class is a member of the
75 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
76 * Java Collections Framework</a>.
77 *
78 * @param <E> 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<E>
90 extends AbstractSet<E>
91 implements Set<E>, Cloneable, java.io.Serializable
92 {
93 static final long serialVersionUID = -5024744406713321676L;
94
95 private transient HashMap<E,Object> 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 {@code 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 {@code 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 {@code 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 {@code 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<E> 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 {@code true} if this set contains no elements.
186 *
187 * @return {@code true} if this set contains no elements
188 */
189 public boolean isEmpty() {
190 return map.isEmpty();
191 }
192
193 /**
194 * Returns {@code true} if this set contains the specified element.
195 * More formally, returns {@code true} if and only if this set
196 * contains an element {@code e} such that
197 * <code>(o==null ? e==null : o.equals(e))</code>.
198 *
199 * @param o element whose presence in this set is to be tested
200 * @return {@code 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 {@code e} to this set if
209 * this set contains no element {@code e2} such that
210 * <code>(e==null ? e2==null : e.equals(e2))</code>.
211 * If this set already contains the element, the call leaves the set
212 * unchanged and returns {@code false}.
213 *
214 * @param e element to be added to this set
215 * @return {@code 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 {@code e} such that
225 * <code>(o==null ? e==null : o.equals(e))</code>,
226 * if this set contains such an element. Returns {@code 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 {@code 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 {@code 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<E> newSet = (HashSet<E>) super.clone();
256 newSet.map = (HashMap<E, Object>) map.clone();
257 return newSet;
258 } catch (CloneNotSupportedException e) {
259 throw new InternalError(e);
260 }
261 }
262
263 /**
264 * Save the state of this {@code HashSet} instance to a stream (that is,
265 * serialize it).
266 *
267 * @serialData The capacity of the backing {@code 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 {@code 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<size; i++) {
332 @SuppressWarnings("unchecked")
333 E e = (E) s.readObject();
334 map.put(e, PRESENT);
335 }
336 }
337
338 /**
339 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
340 * and <em>fail-fast</em> {@link Spliterator} over the elements in this
341 * set.
342 *
343 * <p>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<E> spliterator() {
351 return new HashMap.KeySpliterator<>(map, 0, -1, 0, 0);
352 }
353 }