- 001
/* - 002
* @(#)HashSet.java 1.37 06/04/21 - 003 *
- 004 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
- 005 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
- 006
*/ - 007
- 008package java.util;
- 009
- 010/**
- 011 * This class implements the <tt>Set</tt> interface, backed by a hash table
- 012 * (actually a <tt>HashMap</tt> instance). It makes no guarantees as to the
- 013 * iteration order of the set; in particular, it does not guarantee that the
- 014 * order will remain constant over time. This class permits the <tt>null</tt>
- 015 * element.
- 016 *
- 017 * <p>This class offers constant time performance for the basic operations
- 018 * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
- 019 * assuming the hash function disperses the elements properly among the
- 020 * buckets. Iterating over this set requires time proportional to the sum of
- 021 * the <tt>HashSet</tt> instance's size (the number of elements) plus the
- 022 * "capacity" of the backing <tt>HashMap</tt> instance (the number of
- 023 * buckets). Thus, it's very important not to set the initial capacity too
- 024 * high (or the load factor too low) if iteration performance is important.
- 025 *
- 026 * <p><strong>Note that this implementation is not synchronized.</strong>
- 027 * If multiple threads access a hash set concurrently, and at least one of
- 028 * the threads modifies the set, it <i>must</i> be synchronized externally.
- 029 * This is typically accomplished by synchronizing on some object that
- 030 * naturally encapsulates the set.
- 031 *
- 032 * If no such object exists, the set should be "wrapped" using the
- 033 * {@link Collections#synchronizedSet Collections.synchronizedSet}
- 034 * method. This is best done at creation time, to prevent accidental
- 035 * unsynchronized access to the set:<pre>
- 036 * Set s = Collections.synchronizedSet(new HashSet(...));</pre>
- 037 *
- 038 * <p>The iterators returned by this class's <tt>iterator</tt> method are
- 039 * <i>fail-fast</i>: if the set is modified at any time after the iterator is
- 040 * created, in any way except through the iterator's own <tt>remove</tt>
- 041 * method, the Iterator throws a {@link ConcurrentModificationException}.
- 042 * Thus, in the face of concurrent modification, the iterator fails quickly
- 043 * and cleanly, rather than risking arbitrary, non-deterministic behavior at
- 044 * an undetermined time in the future.
- 045 *
- 046 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
- 047 * as it is, generally speaking, impossible to make any hard guarantees in the
- 048 * presence of unsynchronized concurrent modification. Fail-fast iterators
- 049 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
- 050 * Therefore, it would be wrong to write a program that depended on this
- 051 * exception for its correctness: <i>the fail-fast behavior of iterators
- 052 * should be used only to detect bugs.</i>
- 053 *
- 054 * <p>This class is a member of the
- 055 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
- 056 * Java Collections Framework</a>.
- 057 *
- 058 * @param <E> the type of elements maintained by this set
- 059 *
- 060 * @author Josh Bloch
- 061 * @author Neal Gafter
- 062 * @version 1.37, 04/21/06
- 063 * @see Collection
- 064 * @see Set
- 065 * @see TreeSet
- 066 * @see HashMap
- 067 * @since 1.2
- 068 */
- 069
- 070public class HashSet<E>
- 071 extends AbstractSet<E>
- 072 implements Set<E>, Cloneable, java.io.Serializable
- 073{
- 074 static final long serialVersionUID = -5024744406713321676L;
- 075
- 076 private transient HashMap<E,Object> map;
- 077
- 078 // Dummy value to associate with an Object in the backing Map
- 079 private static final Object PRESENT = new Object();
- 080
- 081 /**
- 082 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
- 083 * default initial capacity (16) and load factor (0.75).
- 084 */
- 085 public HashSet() {
- 086 map = new HashMap<E,Object>();
- 087 }
- 088
- 089 /**
- 090 * Constructs a new set containing the elements in the specified
- 091 * collection. The <tt>HashMap</tt> is created with default load factor
- 092 * (0.75) and an initial capacity sufficient to contain the elements in
- 093 * the specified collection.
- 094 *
- 095 * @param c the collection whose elements are to be placed into this set
- 096 * @throws NullPointerException if the specified collection is null
- 097 */
- 098 public HashSet(Collection<? extends E> c) {
- 099 map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
- 100 addAll(c);
- 101 }
- 102
- 103 /**
- 104 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
- 105 * the specified initial capacity and the specified load factor.
- 106 *
- 107 * @param initialCapacity the initial capacity of the hash map
- 108 * @param loadFactor the load factor of the hash map
- 109 * @throws IllegalArgumentException if the initial capacity is less
- 110 * than zero, or if the load factor is nonpositive
- 111 */
- 112 public HashSet(int initialCapacity, float loadFactor) {
- 113 map = new HashMap<E,Object>(initialCapacity, loadFactor);
- 114 }
- 115
- 116 /**
- 117 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
- 118 * the specified initial capacity and default load factor (0.75).
- 119 *
- 120 * @param initialCapacity the initial capacity of the hash table
- 121 * @throws IllegalArgumentException if the initial capacity is less
- 122 * than zero
- 123 */
- 124 public HashSet(int initialCapacity) {
- 125 map = new HashMap<E,Object>(initialCapacity);
- 126 }
- 127
- 128 /**
- 129 * Constructs a new, empty linked hash set. (This package private
- 130 * constructor is only used by LinkedHashSet.) The backing
- 131 * HashMap instance is a LinkedHashMap with the specified initial
- 132 * capacity and the specified load factor.
- 133 *
- 134 * @param initialCapacity the initial capacity of the hash map
- 135 * @param loadFactor the load factor of the hash map
- 136 * @param dummy ignored (distinguishes this
- 137 * constructor from other int, float constructor.)
- 138 * @throws IllegalArgumentException if the initial capacity is less
- 139 * than zero, or if the load factor is nonpositive
- 140 */
- 141 HashSet(int initialCapacity, float loadFactor, boolean dummy) {
- 142 map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
- 143 }
- 144
- 145 /**
- 146 * Returns an iterator over the elements in this set. The elements
- 147 * are returned in no particular order.
- 148 *
- 149 * @return an Iterator over the elements in this set
- 150 * @see ConcurrentModificationException
- 151 */
- 152 public Iterator<E> iterator() {
- 153 return map.keySet().iterator();
- 154 }
- 155
- 156 /**
- 157 * Returns the number of elements in this set (its cardinality).
- 158 *
- 159 * @return the number of elements in this set (its cardinality)
- 160 */
- 161 public int size() {
- 162 return map.size();
- 163 }
- 164
- 165 /**
- 166 * Returns <tt>true</tt> if this set contains no elements.
- 167 *
- 168 * @return <tt>true</tt> if this set contains no elements
- 169 */
- 170 public boolean isEmpty() {
- 171 return map.isEmpty();
- 172 }
- 173
- 174 /**
- 175 * Returns <tt>true</tt> if this set contains the specified element.
- 176 * More formally, returns <tt>true</tt> if and only if this set
- 177 * contains an element <tt>e</tt> such that
- 178 * <tt>(o==null ? e==null : o.equals(e))</tt>.
- 179 *
- 180 * @param o element whose presence in this set is to be tested
- 181 * @return <tt>true</tt> if this set contains the specified element
- 182 */
- 183 public boolean contains(Object o) {
- 184 return map.containsKey(o);
- 185 }
- 186
- 187 /**
- 188 * Adds the specified element to this set if it is not already present.
- 189 * More formally, adds the specified element <tt>e</tt> to this set if
- 190 * this set contains no element <tt>e2</tt> such that
- 191 * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
- 192 * If this set already contains the element, the call leaves the set
- 193 * unchanged and returns <tt>false</tt>.
- 194 *
- 195 * @param e element to be added to this set
- 196 * @return <tt>true</tt> if this set did not already contain the specified
- 197 * element
- 198 */
- 199 public boolean add(E e) {
- 200 return map.put(e, PRESENT)==null;
- 201 }
- 202
- 203 /**
- 204 * Removes the specified element from this set if it is present.
- 205 * More formally, removes an element <tt>e</tt> such that
- 206 * <tt>(o==null ? e==null : o.equals(e))</tt>,
- 207 * if this set contains such an element. Returns <tt>true</tt> if
- 208 * this set contained the element (or equivalently, if this set
- 209 * changed as a result of the call). (This set will not contain the
- 210 * element once the call returns.)
- 211 *
- 212 * @param o object to be removed from this set, if present
- 213 * @return <tt>true</tt> if the set contained the specified element
- 214 */
- 215 public boolean remove(Object o) {
- 216 return map.remove(o)==PRESENT;
- 217 }
- 218
- 219 /**
- 220 * Removes all of the elements from this set.
- 221 * The set will be empty after this call returns.
- 222 */
- 223 public void clear() {
- 224 map.clear();
- 225 }
- 226
- 227 /**
- 228 * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
- 229 * themselves are not cloned.
- 230 *
- 231 * @return a shallow copy of this set
- 232 */
- 233 public Object clone() {
- 234 try {
- 235 HashSet<E> newSet = (HashSet<E>) super.clone();
- 236 newSet.map = (HashMap<E, Object>) map.clone();
- 237 return newSet;
- 238 } catch (CloneNotSupportedException e) {
- 239 throw new InternalError();
- 240 }
- 241 }
- 242
- 243 /**
- 244 * Save the state of this <tt>HashSet</tt> instance to a stream (that is,
- 245 * serialize it).
- 246 *
- 247 * @serialData The capacity of the backing <tt>HashMap</tt> instance
- 248 * (int), and its load factor (float) are emitted, followed by
- 249 * the size of the set (the number of elements it contains)
- 250 * (int), followed by all of its elements (each an Object) in
- 251 * no particular order.
- 252 */
- 253 private void writeObject(java.io.ObjectOutputStream s)
- 254 throws java.io.IOException {
- 255 // Write out any hidden serialization magic
- 256 s.defaultWriteObject();
- 257
- 258 // Write out HashMap capacity and load factor
- 259 s.writeInt(map.capacity());
- 260 s.writeFloat(map.loadFactor());
- 261
- 262 // Write out size
- 263 s.writeInt(map.size());
- 264
- 265 // Write out all elements in the proper order.
- 266 for (Iterator i=map.keySet().iterator(); i.hasNext(); )
- 267 s.writeObject(i.next());
- 268 }
- 269
- 270 /**
- 271 * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
- 272 * deserialize it).
- 273 */
- 274 private void readObject(java.io.ObjectInputStream s)
- 275 throws java.io.IOException, ClassNotFoundException {
- 276 // Read in any hidden serialization magic
- 277 s.defaultReadObject();
- 278
- 279 // Read in HashMap capacity and load factor and create backing HashMap
- 280 int capacity = s.readInt();
- 281 float loadFactor = s.readFloat();
- 282 map = (((HashSet)this) instanceof LinkedHashSet ?
- 283 new LinkedHashMap<E,Object>(capacity, loadFactor) :
- 284 new HashMap<E,Object>(capacity, loadFactor));
- 285
- 286 // Read in size
- 287 int size = s.readInt();
- 288
- 289 // Read in all elements in the proper order.
- 290 for (int i=0; i<size; i++) {
- 291 E e = (E) s.readObject();
- 292 map.put(e, PRESENT);
- 293 }
- 294 }
- 295}
