001: /*
002: * @(#)HashSet.java 1.26 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027:
028: package java.util;
029:
030: /**
031: * This class implements the <tt>Set</tt> interface, backed by a hash table
032: * (actually a <tt>HashMap</tt> instance). It makes no guarantees as to the
033: * iteration order of the set; in particular, it does not guarantee that the
034: * order will remain constant over time. This class permits the <tt>null</tt>
035: * element.<p>
036: *
037: * This class offers constant time performance for the basic operations
038: * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
039: * assuming the hash function disperses the elements properly among the
040: * buckets. Iterating over this set requires time proportional to the sum of
041: * the <tt>HashSet</tt> instance's size (the number of elements) plus the
042: * "capacity" of the backing <tt>HashMap</tt> instance (the number of
043: * buckets). Thus, it's very important not to set the initial capacity too
044: * high (or the load factor too low) if iteration performance is important.<p>
045: *
046: * <b>Note that this implementation is not synchronized.</b> If multiple
047: * threads access a set concurrently, and at least one of the threads modifies
048: * the set, it <i>must</i> be synchronized externally. This is typically
049: * accomplished by synchronizing on some object that naturally encapsulates
050: * the set. If no such object exists, the set should be "wrapped" using the
051: * <tt>Collections.synchronizedSet</tt> method. This is best done at creation
052: * time, to prevent accidental unsynchronized access to the <tt>HashSet</tt>
053: * instance:
054: *
055: * <pre>
056: * Set s = Collections.synchronizedSet(new HashSet(...));
057: * </pre><p>
058: *
059: * The iterators returned by this class's <tt>iterator</tt> method are
060: * <i>fail-fast</i>: if the set is modified at any time after the iterator is
061: * created, in any way except through the iterator's own <tt>remove</tt>
062: * method, the Iterator throws a <tt>ConcurrentModificationException</tt>.
063: * Thus, in the face of concurrent modification, the iterator fails quickly
064: * and cleanly, rather than risking arbitrary, non-deterministic behavior at
065: * an undetermined time in the future.
066: *
067: * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
068: * as it is, generally speaking, impossible to make any hard guarantees in the
069: * presence of unsynchronized concurrent modification. Fail-fast iterators
070: * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
071: * Therefore, it would be wrong to write a program that depended on this
072: * exception for its correctness: <i>the fail-fast behavior of iterators
073: * should be used only to detect bugs.</i><p>
074: *
075: * This class is a member of the
076: * <a href="{@docRoot}/../guide/collections/index.html">
077: * Java Collections Framework</a>.
078: *
079: * @author Josh Bloch
080: * @version 1.19, 02/02/00
081: * @see Collection
082: * @see Set
083: * @see TreeSet
084: * @see Collections#synchronizedSet(Set)
085: * @see HashMap
086: * @since 1.2
087: */
088:
089: public class HashSet extends AbstractSet implements Set, Cloneable,
090: java.io.Serializable {
091: static final long serialVersionUID = -5024744406713321676L;
092:
093: private transient HashMap map;
094:
095: // Dummy value to associate with an Object in the backing Map
096: private static final Object PRESENT = new Object();
097:
098: /**
099: * 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 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, which is
136: * <tt>0.75</tt>.
137: *
138: * @param initialCapacity the initial capacity of the hash table.
139: * @throws IllegalArgumentException if the initial capacity is less
140: * than zero.
141: */
142: public HashSet(int initialCapacity) {
143: map = new HashMap(initialCapacity);
144: }
145:
146: /**
147: * Constructs a new, empty linked hash set. (This package private
148: * constructor is only used by LinkedHashSet.) The backing
149: * HashMap instance is a LinkedHashMap with the specified initial
150: * capacity and the specified load factor.
151: *
152: * @param initialCapacity the initial capacity of the hash map.
153: * @param loadFactor the load factor of the hash map.
154: * @param dummy ignored (distinguishes this
155: * constructor from other int, float constructor.)
156: * @throws IllegalArgumentException if the initial capacity is less
157: * than zero, or if the load factor is nonpositive.
158: */
159: HashSet(int initialCapacity, float loadFactor, boolean dummy) {
160: map = new LinkedHashMap(initialCapacity, loadFactor);
161: }
162:
163: /**
164: * Returns an iterator over the elements in this set. The elements
165: * are returned in no particular order.
166: *
167: * @return an Iterator over the elements in this set.
168: * @see ConcurrentModificationException
169: */
170: public Iterator iterator() {
171: return map.keySet().iterator();
172: }
173:
174: /**
175: * Returns the number of elements in this set (its cardinality).
176: *
177: * @return the number of elements in this set (its cardinality).
178: */
179: public int size() {
180: return map.size();
181: }
182:
183: /**
184: * Returns <tt>true</tt> if this set contains no elements.
185: *
186: * @return <tt>true</tt> if this set contains no elements.
187: */
188: public boolean isEmpty() {
189: return map.isEmpty();
190: }
191:
192: /**
193: * Returns <tt>true</tt> if this set contains the specified element.
194: *
195: * @param o element whose presence in this set is to be tested.
196: * @return <tt>true</tt> if this set contains the specified element.
197: */
198: public boolean contains(Object o) {
199: return map.containsKey(o);
200: }
201:
202: /**
203: * Adds the specified element to this set if it is not already
204: * present.
205: *
206: * @param o element to be added to this set.
207: * @return <tt>true</tt> if the set did not already contain the specified
208: * element.
209: */
210: public boolean add(Object o) {
211: return map.put(o, PRESENT) == null;
212: }
213:
214: /**
215: * Removes the specified element from this set if it is present.
216: *
217: * @param o object to be removed from this set, if present.
218: * @return <tt>true</tt> if the set contained the specified element.
219: */
220: public boolean remove(Object o) {
221: return map.remove(o) == PRESENT;
222: }
223:
224: /**
225: * Removes all of the elements from this set.
226: */
227: public void clear() {
228: map.clear();
229: }
230:
231: /**
232: * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
233: * themselves are not cloned.
234: *
235: * @return a shallow copy of this set.
236: */
237: public Object clone() {
238: try {
239: HashSet newSet = (HashSet) super .clone();
240: newSet.map = (HashMap) map.clone();
241: return newSet;
242: } catch (CloneNotSupportedException e) {
243: throw new InternalError();
244: }
245: }
246:
247: /**
248: * Save the state of this <tt>HashSet</tt> instance to a stream (that is,
249: * serialize this set).
250: *
251: * @serialData The capacity of the backing <tt>HashMap</tt> instance
252: * (int), and its load factor (float) are emitted, followed by
253: * the size of the set (the number of elements it contains)
254: * (int), followed by all of its elements (each an Object) in
255: * no particular order.
256: */
257: private void writeObject(java.io.ObjectOutputStream s)
258: throws java.io.IOException {
259: // Write out any hidden serialization magic
260: s.defaultWriteObject();
261:
262: // Write out HashMap capacity and load factor
263: s.writeInt(map.capacity());
264: s.writeFloat(map.loadFactor());
265:
266: // Write out size
267: s.writeInt(map.size());
268:
269: // Write out all elements in the proper order.
270: for (Iterator i = map.keySet().iterator(); i.hasNext();)
271: s.writeObject(i.next());
272: }
273:
274: /**
275: * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
276: * deserialize it).
277: */
278: private void readObject(java.io.ObjectInputStream s)
279: throws java.io.IOException, ClassNotFoundException {
280: // Read in any hidden serialization magic
281: s.defaultReadObject();
282:
283: // Read in HashMap capacity and load factor and create backing HashMap
284: int capacity = s.readInt();
285: float loadFactor = s.readFloat();
286: map = (this instanceof LinkedHashSet ? new LinkedHashMap(
287: capacity, loadFactor) : new HashMap(capacity,
288: loadFactor));
289:
290: // Read in size
291: int size = s.readInt();
292:
293: // Read in all elements in the proper order.
294: for (int i = 0; i < size; i++) {
295: Object e = s.readObject();
296: map.put(e, PRESENT);
297: }
298: }
299: }
|