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