1: /* HashSet.java -- a class providing a HashMap-backed Set 2: Copyright (C) 1998, 1999, 2001, 2004, 2005 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package java.util; 40: 41: import java.io.IOException; 42: import java.io.ObjectInputStream; 43: import java.io.ObjectOutputStream; 44: import java.io.Serializable; 45: 46: /** 47: * This class provides a HashMap-backed implementation of the Set interface. 48: * <p> 49: * 50: * Most operations are O(1), assuming no hash collisions. In the worst 51: * case (where all hashes collide), operations are O(n). Setting the 52: * initial capacity too low will force many resizing operations, but 53: * setting the initial capacity too high (or loadfactor too low) leads 54: * to wasted memory and slower iteration. 55: * <p> 56: * 57: * HashSet accepts the null key and null values. It is not synchronized, 58: * so if you need multi-threaded access, consider using:<br> 59: * <code>Set s = Collections.synchronizedSet(new HashSet(...));</code> 60: * <p> 61: * 62: * The iterators are <i>fail-fast</i>, meaning that any structural 63: * modification, except for <code>remove()</code> called on the iterator 64: * itself, cause the iterator to throw a 65: * {@link ConcurrentModificationException} rather than exhibit 66: * non-deterministic behavior. 67: * 68: * @author Jon Zeppieri 69: * @author Eric Blake (ebb9@email.byu.edu) 70: * @see Collection 71: * @see Set 72: * @see TreeSet 73: * @see Collections#synchronizedSet(Set) 74: * @see HashMap 75: * @see LinkedHashSet 76: * @since 1.2 77: * @status updated to 1.4 78: */ 79: public class HashSet<T> extends AbstractSet<T> 80: implements Set<T>, Cloneable, Serializable 81: { 82: /** 83: * Compatible with JDK 1.2. 84: */ 85: private static final long serialVersionUID = -5024744406713321676L; 86: 87: /** 88: * The HashMap which backs this Set. 89: */ 90: private transient HashMap<T, String> map; 91: 92: /** 93: * Construct a new, empty HashSet whose backing HashMap has the default 94: * capacity (11) and loadFacor (0.75). 95: */ 96: public HashSet() 97: { 98: this(HashMap.DEFAULT_CAPACITY, HashMap.DEFAULT_LOAD_FACTOR); 99: } 100: 101: /** 102: * Construct a new, empty HashSet whose backing HashMap has the supplied 103: * capacity and the default load factor (0.75). 104: * 105: * @param initialCapacity the initial capacity of the backing HashMap 106: * @throws IllegalArgumentException if the capacity is negative 107: */ 108: public HashSet(int initialCapacity) 109: { 110: this(initialCapacity, HashMap.DEFAULT_LOAD_FACTOR); 111: } 112: 113: /** 114: * Construct a new, empty HashSet whose backing HashMap has the supplied 115: * capacity and load factor. 116: * 117: * @param initialCapacity the initial capacity of the backing HashMap 118: * @param loadFactor the load factor of the backing HashMap 119: * @throws IllegalArgumentException if either argument is negative, or 120: * if loadFactor is POSITIVE_INFINITY or NaN 121: */ 122: public HashSet(int initialCapacity, float loadFactor) 123: { 124: map = init(initialCapacity, loadFactor); 125: } 126: 127: /** 128: * Construct a new HashSet with the same elements as are in the supplied 129: * collection (eliminating any duplicates, of course). The backing storage 130: * has twice the size of the collection, or the default size of 11, 131: * whichever is greater; and the default load factor (0.75). 132: * 133: * @param c a collection of initial set elements 134: * @throws NullPointerException if c is null 135: */ 136: public HashSet(Collection<? extends T> c) 137: { 138: this(Math.max(2 * c.size(), HashMap.DEFAULT_CAPACITY)); 139: addAll(c); 140: } 141: 142: /** 143: * Adds the given Object to the set if it is not already in the Set. 144: * This set permits a null element. 145: * 146: * @param o the Object to add to this Set 147: * @return true if the set did not already contain o 148: */ 149: public boolean add(T o) 150: { 151: return map.put(o, "") == null; 152: } 153: 154: /** 155: * Empties this Set of all elements; this takes constant time. 156: */ 157: public void clear() 158: { 159: map.clear(); 160: } 161: 162: /** 163: * Returns a shallow copy of this Set. The Set itself is cloned; its 164: * elements are not. 165: * 166: * @return a shallow clone of the set 167: */ 168: public Object clone() 169: { 170: HashSet<T> copy = null; 171: try 172: { 173: copy = (HashSet<T>) super.clone(); 174: } 175: catch (CloneNotSupportedException x) 176: { 177: // Impossible to get here. 178: } 179: copy.map = (HashMap<T, String>) map.clone(); 180: return copy; 181: } 182: 183: /** 184: * Returns true if the supplied element is in this Set. 185: * 186: * @param o the Object to look for 187: * @return true if it is in the set 188: */ 189: public boolean contains(Object o) 190: { 191: return map.containsKey(o); 192: } 193: 194: /** 195: * Returns true if this set has no elements in it. 196: * 197: * @return <code>size() == 0</code>. 198: */ 199: public boolean isEmpty() 200: { 201: return map.size == 0; 202: } 203: 204: /** 205: * Returns an Iterator over the elements of this Set, which visits the 206: * elements in no particular order. For this class, the Iterator allows 207: * removal of elements. The iterator is fail-fast, and will throw a 208: * ConcurrentModificationException if the set is modified externally. 209: * 210: * @return a set iterator 211: * @see ConcurrentModificationException 212: */ 213: public Iterator<T> iterator() 214: { 215: // Avoid creating intermediate keySet() object by using non-public API. 216: return map.iterator(HashMap.KEYS); 217: } 218: 219: /** 220: * Removes the supplied Object from this Set if it is in the Set. 221: * 222: * @param o the object to remove 223: * @return true if an element was removed 224: */ 225: public boolean remove(Object o) 226: { 227: return (map.remove(o) != null); 228: } 229: 230: /** 231: * Returns the number of elements in this Set (its cardinality). 232: * 233: * @return the size of the set 234: */ 235: public int size() 236: { 237: return map.size; 238: } 239: 240: /** 241: * Helper method which initializes the backing Map. Overridden by 242: * LinkedHashSet for correct semantics. 243: * 244: * @param capacity the initial capacity 245: * @param load the initial load factor 246: * @return the backing HashMap 247: */ 248: HashMap init(int capacity, float load) 249: { 250: return new HashMap(capacity, load); 251: } 252: 253: /** 254: * Serializes this object to the given stream. 255: * 256: * @param s the stream to write to 257: * @throws IOException if the underlying stream fails 258: * @serialData the <i>capacity</i> (int) and <i>loadFactor</i> (float) 259: * of the backing store, followed by the set size (int), 260: * then a listing of its elements (Object) in no order 261: */ 262: private void writeObject(ObjectOutputStream s) throws IOException 263: { 264: s.defaultWriteObject(); 265: // Avoid creating intermediate keySet() object by using non-public API. 266: Iterator<T> it = map.iterator(HashMap.KEYS); 267: s.writeInt(map.buckets.length); 268: s.writeFloat(map.loadFactor); 269: s.writeInt(map.size); 270: while (it.hasNext()) 271: s.writeObject(it.next()); 272: } 273: 274: /** 275: * Deserializes this object from the given stream. 276: * 277: * @param s the stream to read from 278: * @throws ClassNotFoundException if the underlying stream fails 279: * @throws IOException if the underlying stream fails 280: * @serialData the <i>capacity</i> (int) and <i>loadFactor</i> (float) 281: * of the backing store, followed by the set size (int), 282: * then a listing of its elements (Object) in no order 283: */ 284: private void readObject(ObjectInputStream s) 285: throws IOException, ClassNotFoundException 286: { 287: s.defaultReadObject(); 288: 289: map = init(s.readInt(), s.readFloat()); 290: for (int size = s.readInt(); size > 0; size--) 291: map.put((T) s.readObject(), ""); 292: } 293: }