home *** CD-ROM | disk | FTP | other *** search
/ Java 1.2 How-To / JavaHowTo.iso / 3rdParty / jbuilder / unsupported / JDK1.2beta3 / SOURCE / SRC.ZIP / java / util / HashSet.java < prev    next >
Encoding:
Java Source  |  1998-03-20  |  7.3 KB  |  229 lines
  1. /*
  2.  * @(#)HashSet.java    1.9 98/03/18
  3.  *
  4.  * Copyright 1997, 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. /**
  18.  * This class implements the Set interface, backed by a hash table (actually a
  19.  * HashMap).  It offers constant time performance for the basic operations
  20.  * (add, remove, contains and size), assuming the the hash function disperses
  21.  * the elements properly among the buckets.  This Set does not permit the null
  22.  * element.
  23.  * <p>
  24.  * <strong>Note that this implementation is not synchronized.</strong> If
  25.  * multiple threads access a HashSet concurrently, and at least one of the
  26.  * threads modifies the HashSet, it <em>must</em> be synchronized externally.
  27.  * This is typically accomplished by synchronizing on some object that
  28.  * naturally encapsulates the HashSet.  If no such object exists, the HashSet
  29.  * should be "wrapped" using the Collections.synchronizedSet method.  This is
  30.  * best done at creation time, to prevent accidental unsynchronized access to
  31.  * the HashSet:
  32.  * <pre>
  33.  *    Set s = Collections.synchronizedSet(new HashSet(...));
  34.  * </pre>
  35.  * <p>
  36.  * The Iterators returned by HashSet's iterator method are <em>fail-fast</em>:
  37.  * if the HashSet is modified at any time after the Iterator is created, in
  38.  * any way except through the Iterator's own remove method, the Iterator will
  39.  * throw a ConcurrentModificationException.  Thus, in the face of concurrent
  40.  * modification, the Iterator fails quickly and cleanly, rather than
  41.  * risking arbitrary, non-deterministic behavior at an undetermined time
  42.  * in the future.
  43.  * 
  44.  * @author  Josh Bloch
  45.  * @version 1.9 03/18/98
  46.  * @see        Collection
  47.  * @see        Set
  48.  * @see        ArraySet
  49.  * @see        Collections.synchronizedSet
  50.  * @see        HashMap
  51.  * @since JDK1.2
  52.  */
  53.  
  54. public class HashSet extends AbstractSet
  55.              implements Set, Cloneable, java.io.Serializable {
  56.     private transient HashMap map;
  57.  
  58.     // Dummy value to associate with an Object in the backing Map
  59.     private static final Object PRESENT = new Object();
  60.  
  61.     /**
  62.      * Constructs a new, empty HashSet; the backing HashMap has default
  63.      * capacity and load factor.
  64.      */
  65.     public HashSet() {
  66.     map = new HashMap();
  67.     }
  68.  
  69.     /**
  70.      * Constructs a new HashSet containing the elements in the specified
  71.      * Collection.  The capacity of the backing HashMap is twice the
  72.      * size of the specified Collection, and the default load factor is used.
  73.      *
  74.      * @exception  NullPointerException if the specified collection or one of
  75.      *           its elements is null.
  76.      */
  77.     public HashSet(Collection c) {
  78.     map = new HashMap(Math.max(3*c.size(), 11));
  79.     addAll(c);
  80.     }
  81.  
  82.     /**
  83.      * Constructs a new, empty HashSet; the backing HashMap has the
  84.      * specified initial capacity and the specified load factor.
  85.      *
  86.      * @param      initialCapacity   the initial capacity of the hashtable.
  87.      * @param      loadFactor        a number between 0.0 and 1.0.
  88.      * @exception  IllegalArgumentException if the initial capacity is less
  89.      *             than or equal to zero, or if the load factor is less than
  90.      *             or equal to zero.
  91.      */
  92.     public HashSet(int initialCapacity, float loadFactor) {
  93.     map = new HashMap(initialCapacity, loadFactor);
  94.     }
  95.  
  96.     /**
  97.      * Constructs a new, empty HashSet; the backing HashMap has the
  98.      * specified initial capacity and default load factor.
  99.      *
  100.      * @param      initialCapacity   the initial capacity of the hashtable.
  101.      * @exception  IllegalArgumentException if the initial capacity is less
  102.      *             than or equal to zero, or if the load factor is less than
  103.      *             or equal to zero.
  104.      */
  105.     public HashSet(int initialCapacity) {
  106.     map = new HashMap(initialCapacity);
  107.     }
  108.  
  109.     /**
  110.      * Returns an Iterator over the elements in this HashSet.  The elements are
  111.      * returned in no particular order.
  112.      *
  113.      * @see ConcurrentModificationException
  114.      */
  115.     public Iterator iterator() {
  116.     return map.keySet().iterator();
  117.     }
  118.  
  119.     /**
  120.      * Returns the number of elements in this HashSet (its cardinality).
  121.      */
  122.     public int size() {
  123.     return map.size();
  124.     }
  125.  
  126.     /**
  127.      * Returns true if this HashSet contains no elements.
  128.      */
  129.     public boolean isEmpty() {
  130.     return map.isEmpty();
  131.     }
  132.  
  133.     /**
  134.      * Returns true if this HashSet contains the specified element.
  135.      *
  136.      * @exception  NullPointerException if the specified element is null.
  137.      */
  138.     public boolean contains(Object o) {
  139.     return map.containsKey(o);
  140.     }
  141.  
  142.     /**
  143.      * Adds the specified element to this HashSet if it is not already present.
  144.      *
  145.      * @param o element to be added to this HashSet.
  146.      * @return true if the HashSet did not already contain the specified
  147.      *           element. 
  148.      * @exception  NullPointerException if the specified element is null.
  149.      */
  150.     public boolean add(Object o) {
  151.     return map.put(o, PRESENT)==null;
  152.     }
  153.  
  154.     /**
  155.      * Removes the given element from this HashSet if it is present.
  156.      *
  157.      * @param o object to be removed from this HashSet, if present.
  158.      * @return true if the HashSet contained the specified element.
  159.      * @exception  NullPointerException if the specified element is null.
  160.      */
  161.     public boolean remove(Object o) {
  162.     return map.remove(o)==PRESENT;
  163.     }
  164.  
  165.     /**
  166.      * Removes all of the elements from this HashSet.
  167.      */
  168.     public void clear() {
  169.     map.clear();
  170.     }
  171.  
  172.     /**
  173.      * Returns a shallow copy of this HashSet. (The elements themselves
  174.      * are not cloned.)
  175.      */
  176.     public Object clone() {
  177.     try { 
  178.         HashSet newSet = (HashSet)super.clone();
  179.         newSet.map = (HashMap)map.clone();
  180.         return newSet;
  181.     } catch (CloneNotSupportedException e) { 
  182.         throw new InternalError();
  183.     }
  184.     }
  185.  
  186.     /**
  187.      * Save the state of the HashSet to a stream (i.e., serialize it).
  188.      */
  189.     private synchronized void writeObject(java.io.ObjectOutputStream s)
  190.         throws java.io.IOException {
  191.     // Write out any hidden serialization magic
  192.     s.defaultWriteObject();
  193.  
  194.         // Write out HashMap capacity and load factor
  195.         s.writeInt(map.capacity());
  196.         s.writeFloat(map.loadFactor());
  197.  
  198.         // Write out size
  199.         s.writeInt(map.size());
  200.  
  201.     // Write out all elements in the proper order.
  202.     for (Iterator i=map.keySet().iterator(); i.hasNext(); )
  203.             s.writeObject(i.next());
  204.     }
  205.  
  206.     /**
  207.      * Reconstitute the LinkedList from a stream (i.e., deserialize it).
  208.      */
  209.     private synchronized void readObject(java.io.ObjectInputStream s)
  210.         throws java.io.IOException, ClassNotFoundException {
  211.     // Read in any hidden serialization magic
  212.     s.defaultReadObject();
  213.  
  214.         // Read in HashMap capacity and load factor and create backing HashMap
  215.         int capacity = s.readInt();
  216.         float loadFactor = s.readFloat();
  217.         map = new HashMap(capacity, loadFactor);
  218.  
  219.         // Read in size
  220.         int size = s.readInt();
  221.  
  222.     // Read in all elements in the proper order.
  223.     for (int i=0; i<size; i++) {
  224.             Object e = s.readObject();
  225.             map.put(e, PRESENT);
  226.         }
  227.     }
  228. }
  229.