Source for java.util.HashSet

   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: }