home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 1998 February / VPR9802A.ISO / APP_DEMO / VC / MAIN.BIN / Hashtable.java < prev    next >
Text File  |  1997-10-27  |  17KB  |  553 lines
  1. /*
  2.  * @(#)Hashtable.java    1.41 97/01/28
  3.  * 
  4.  * Copyright (c) 1995, 1996 Sun Microsystems, Inc. All Rights Reserved.
  5.  * 
  6.  * This software is the confidential and proprietary information of Sun
  7.  * Microsystems, Inc. ("Confidential Information").  You shall not
  8.  * disclose such Confidential Information and shall use it only in
  9.  * accordance with the terms of the license agreement you entered into
  10.  * with Sun.
  11.  * 
  12.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
  13.  * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
  14.  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  15.  * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
  16.  * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
  17.  * THIS SOFTWARE OR ITS DERIVATIVES.
  18.  * 
  19.  * CopyrightVersion 1.1_beta
  20.  * 
  21.  */
  22.  
  23. package java.util;
  24.  
  25. import java.io.*;
  26.  
  27. /**
  28.  * Hashtable collision list.
  29.  */
  30. class HashtableEntry {
  31.     int hash;
  32.     Object key;
  33.     Object value;
  34.     HashtableEntry next;
  35.  
  36.     protected Object clone() {
  37.     HashtableEntry entry = new HashtableEntry();
  38.     entry.hash = hash;
  39.     entry.key = key;
  40.     entry.value = value;
  41.     entry.next = (next != null) ? (HashtableEntry)next.clone() : null;
  42.     return entry;
  43.     }
  44. }
  45.  
  46. /**
  47.  * This class implements a hashtable, which maps keys to values. Any 
  48.  * non-<code>null</code> object can be used as a key or as a value. 
  49.  * <p>
  50.  * To successfully store and retrieve objects from a hashtable, the 
  51.  * objects used as keys must implement the <code>hashCode</code> 
  52.  * method and the <code>equals</code> method. 
  53.  * <p>
  54.  * An instance of <code>Hashtable</code> has two parameters that 
  55.  * affect its efficiency: its <i>capacity</i> and its <i>load 
  56.  * factor</i>. The load factor should be between 0.0 and 1.0. When 
  57.  * the number of entries in the hashtable exceeds the product of the 
  58.  * load factor and the current capacity, the capacity is increased by 
  59.  * calling the <code>rehash</code> method. Larger load factors use 
  60.  * memory more efficiently, at the expense of larger expected time 
  61.  * per lookup. 
  62.  * <p>
  63.  * If many entries are to be made into a <code>Hashtable</code>, 
  64.  * creating it with a sufficiently large capacity may allow the 
  65.  * entries to be inserted more efficiently than letting it perform 
  66.  * automatic rehashing as needed to grow the table. 
  67.  * <p>
  68.  * This example creates a hashtable of numbers. It uses the names of 
  69.  * the numbers as keys: 
  70.  * <p><blockquote><pre>
  71.  *     Hashtable numbers = new Hashtable();
  72.  *     numbers.put("one", new Integer(1));
  73.  *     numbers.put("two", new Integer(2));
  74.  *     numbers.put("three", new Integer(3));
  75.  * </pre></blockquote>
  76.  * <p>
  77.  * To retrieve a number, use the following code: 
  78.  * <p><blockquote><pre>
  79.  *     Integer n = (Integer)numbers.get("two");
  80.  *     if (n != null) {
  81.  *         System.out.println("two = " + n);
  82.  *     }
  83.  * </pre></blockquote>
  84.  *
  85.  * @author  Arthur van Hoff
  86.  * @version 1.41, 01/28/97
  87.  * @see     java.lang.Object#equals(java.lang.Object)
  88.  * @see     java.lang.Object#hashCode()
  89.  * @see     java.util.Hashtable#rehash()
  90.  * @since   JDK1.0
  91.  */
  92. public
  93. class Hashtable extends Dictionary implements Cloneable, java.io.Serializable {
  94.     /**
  95.      * The hash table data.
  96.      */
  97.     private transient HashtableEntry table[];
  98.  
  99.     /**
  100.      * The total number of entries in the hash table.
  101.      */
  102.     private transient int count;
  103.  
  104.     /**
  105.      * Rehashes the table when count exceeds this threshold.
  106.      */
  107.     private int threshold;
  108.  
  109.     /**
  110.      * The load factor for the hashtable.
  111.      */
  112.     private float loadFactor;
  113.  
  114.     /** use serialVersionUID from JDK 1.0.2 for interoperability */
  115.     private static final long serialVersionUID = 1421746759512286392L;
  116.  
  117.     /**
  118.      * Constructs a new, empty hashtable with the specified initial 
  119.      * capacity and the specified load factor. 
  120.      *
  121.      * @param      initialCapacity   the initial capacity of the hashtable.
  122.      * @param      loadFactor        a number between 0.0 and 1.0.
  123.      * @exception  IllegalArgumentException  if the initial capacity is less
  124.      *               than or equal to zero, or if the load factor is less than
  125.      *               or equal to zero.
  126.      * @since      JDK1.0
  127.      */
  128.     public Hashtable(int initialCapacity, float loadFactor) {
  129.     if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
  130.         throw new IllegalArgumentException();
  131.     }
  132.     this.loadFactor = loadFactor;
  133.     table = new HashtableEntry[initialCapacity];
  134.     threshold = (int)(initialCapacity * loadFactor);
  135.     }
  136.  
  137.     /**
  138.      * Constructs a new, empty hashtable with the specified initial capacity
  139.      * and default load factor.
  140.      *
  141.      * @param   initialCapacity   the initial capacity of the hashtable.
  142.      * @since   JDK1.0
  143.      */
  144.     public Hashtable(int initialCapacity) {
  145.     this(initialCapacity, 0.75f);
  146.     }
  147.  
  148.     /**
  149.      * Constructs a new, empty hashtable with a default capacity and load
  150.      * factor. 
  151.      *
  152.      * @since   JDK1.0
  153.      */
  154.     public Hashtable() {
  155.     this(101, 0.75f);
  156.     }
  157.  
  158.     /**
  159.      * Returns the number of keys in this hashtable.
  160.      *
  161.      * @return  the number of keys in this hashtable.
  162.      * @since   JDK1.0
  163.      */
  164.     public int size() {
  165.     return count;
  166.     }
  167.  
  168.     /**
  169.      * Tests if this hashtable maps no keys to values.
  170.      *
  171.      * @return  <code>true</code> if this hashtable maps no keys to values;
  172.      *          <code>false</code> otherwise.
  173.      * @since   JDK1.0
  174.      */
  175.     public boolean isEmpty() {
  176.     return count == 0;
  177.     }
  178.  
  179.     /**
  180.      * Returns an enumeration of the keys in this hashtable.
  181.      *
  182.      * @return  an enumeration of the keys in this hashtable.
  183.      * @see     java.util.Enumeration
  184.      * @see     java.util.Hashtable#elements()
  185.      * @since   JDK1.0
  186.      */
  187.     public synchronized Enumeration keys() {
  188.     return new HashtableEnumerator(table, true);
  189.     }
  190.  
  191.     /**
  192.      * Returns an enumeration of the values in this hashtable.
  193.      * Use the Enumeration methods on the returned object to fetch the elements
  194.      * sequentially.
  195.      *
  196.      * @return  an enumeration of the values in this hashtable.
  197.      * @see     java.util.Enumeration
  198.      * @see     java.util.Hashtable#keys()
  199.      * @since   JDK1.0
  200.      */
  201.     public synchronized Enumeration elements() {
  202.     return new HashtableEnumerator(table, false);
  203.     }
  204.  
  205.     /**
  206.      * Tests if some key maps into the specified value in this hashtable.
  207.      * This operation is more expensive than the <code>containsKey</code>
  208.      * method.
  209.      *
  210.      * @param      value   a value to search for.
  211.      * @return     <code>true</code> if some key maps to the
  212.      *             <code>value</code> argument in this hashtable;
  213.      *             <code>false</code> otherwise.
  214.      * @exception  NullPointerException  if the value is <code>null</code>.
  215.      * @see        java.util.Hashtable#containsKey(java.lang.Object)
  216.      * @since      JDK1.0
  217.      */
  218.     public synchronized boolean contains(Object value) {
  219.     if (value == null) {
  220.         throw new NullPointerException();
  221.     }
  222.  
  223.     HashtableEntry tab[] = table;
  224.     for (int i = tab.length ; i-- > 0 ;) {
  225.         for (HashtableEntry e = tab[i] ; e != null ; e = e.next) {
  226.         if (e.value.equals(value)) {
  227.             return true;
  228.         }
  229.         }
  230.     }
  231.     return false;
  232.     }
  233.  
  234.     /**
  235.      * Tests if the specified object is a key in this hashtable.
  236.      * 
  237.      * @param   key   possible key.
  238.      * @return  <code>true</code> if the specified object is a key in this
  239.      *          hashtable; <code>false</code> otherwise.
  240.      * @see     java.util.Hashtable#contains(java.lang.Object)
  241.      * @since   JDK1.0
  242.      */
  243.     public synchronized boolean containsKey(Object key) {
  244.     HashtableEntry tab[] = table;
  245.     int hash = key.hashCode();
  246.     int index = (hash & 0x7FFFFFFF) % tab.length;
  247.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  248.         if ((e.hash == hash) && e.key.equals(key)) {
  249.         return true;
  250.         }
  251.     }
  252.     return false;
  253.     }
  254.  
  255.     /**
  256.      * Returns the value to which the specified key is mapped in this hashtable.
  257.      *
  258.      * @param   key   a key in the hashtable.
  259.      * @return  the value to which the key is mapped in this hashtable;
  260.      *          <code>null</code> if the key is not mapped to any value in
  261.      *          this hashtable.
  262.      * @see     java.util.Hashtable#put(java.lang.Object, java.lang.Object)
  263.      * @since   JDK1.0
  264.      */
  265.     public synchronized Object get(Object key) {
  266.     HashtableEntry tab[] = table;
  267.     int hash = key.hashCode();
  268.     int index = (hash & 0x7FFFFFFF) % tab.length;
  269.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  270.         if ((e.hash == hash) && e.key.equals(key)) {
  271.         return e.value;
  272.         }
  273.     }
  274.     return null;
  275.     }
  276.  
  277.     /**
  278.      * Rehashes the contents of the hashtable into a hashtable with a 
  279.      * larger capacity. This method is called automatically when the 
  280.      * number of keys in the hashtable exceeds this hashtable's capacity 
  281.      * and load factor. 
  282.      *
  283.      * @since   JDK1.0
  284.      */
  285.     protected void rehash() {
  286.     int oldCapacity = table.length;
  287.     HashtableEntry oldTable[] = table;
  288.  
  289.     int newCapacity = oldCapacity * 2 + 1;
  290.     HashtableEntry newTable[] = new HashtableEntry[newCapacity];
  291.  
  292.     threshold = (int)(newCapacity * loadFactor);
  293.     table = newTable;
  294.  
  295.     //System.out.println("rehash old=" + oldCapacity + ", new=" + newCapacity + ", thresh=" + threshold + ", count=" + count);
  296.  
  297.     for (int i = oldCapacity ; i-- > 0 ;) {
  298.         for (HashtableEntry old = oldTable[i] ; old != null ; ) {
  299.         HashtableEntry e = old;
  300.         old = old.next;
  301.  
  302.         int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  303.         e.next = newTable[index];
  304.         newTable[index] = e;
  305.         }
  306.     }
  307.     }
  308.  
  309.     /**
  310.      * Maps the specified <code>key</code> to the specified 
  311.      * <code>value</code> in this hashtable. Neither the key nor the 
  312.      * value can be <code>null</code>. 
  313.      * <p>
  314.      * The value can be retrieved by calling the <code>get</code> method 
  315.      * with a key that is equal to the original key. 
  316.      *
  317.      * @param      key     the hashtable key.
  318.      * @param      value   the value.
  319.      * @return     the previous value of the specified key in this hashtable,
  320.      *             or <code>null</code> if it did not have one.
  321.      * @exception  NullPointerException  if the key or value is
  322.      *               <code>null</code>.
  323.      * @see     java.lang.Object#equals(java.lang.Object)
  324.      * @see     java.util.Hashtable#get(java.lang.Object)
  325.      * @since   JDK1.0
  326.      */
  327.     public synchronized Object put(Object key, Object value) {
  328.     // Make sure the value is not null
  329.     if (value == null) {
  330.         throw new NullPointerException();
  331.     }
  332.  
  333.     // Makes sure the key is not already in the hashtable.
  334.     HashtableEntry tab[] = table;
  335.     int hash = key.hashCode();
  336.     int index = (hash & 0x7FFFFFFF) % tab.length;
  337.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  338.         if ((e.hash == hash) && e.key.equals(key)) {
  339.         Object old = e.value;
  340.         e.value = value;
  341.         return old;
  342.         }
  343.     }
  344.  
  345.     if (count >= threshold) {
  346.         // Rehash the table if the threshold is exceeded
  347.         rehash();
  348.         return put(key, value);
  349.     } 
  350.  
  351.     // Creates the new entry.
  352.     HashtableEntry e = new HashtableEntry();
  353.     e.hash = hash;
  354.     e.key = key;
  355.     e.value = value;
  356.     e.next = tab[index];
  357.     tab[index] = e;
  358.     count++;
  359.     return null;
  360.     }
  361.  
  362.     /**
  363.      * Removes the key (and its corresponding value) from this 
  364.      * hashtable. This method does nothing if the key is not in the hashtable.
  365.      *
  366.      * @param   key   the key that needs to be removed.
  367.      * @return  the value to which the key had been mapped in this hashtable,
  368.      *          or <code>null</code> if the key did not have a mapping.
  369.      * @since   JDK1.0
  370.      */
  371.     public synchronized Object remove(Object key) {
  372.     HashtableEntry tab[] = table;
  373.     int hash = key.hashCode();
  374.     int index = (hash & 0x7FFFFFFF) % tab.length;
  375.     for (HashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
  376.         if ((e.hash == hash) && e.key.equals(key)) {
  377.         if (prev != null) {
  378.             prev.next = e.next;
  379.         } else {
  380.             tab[index] = e.next;
  381.         }
  382.         count--;
  383.         return e.value;
  384.         }
  385.     }
  386.     return null;
  387.     }
  388.  
  389.     /**
  390.      * Clears this hashtable so that it contains no keys. 
  391.      *
  392.      * @since   JDK1.0
  393.      */
  394.     public synchronized void clear() {
  395.     HashtableEntry tab[] = table;
  396.     for (int index = tab.length; --index >= 0; )
  397.         tab[index] = null;
  398.     count = 0;
  399.     }
  400.  
  401.     /**
  402.      * Creates a shallow copy of this hashtable. The keys and values 
  403.      * themselves are not cloned. 
  404.      * This is a relatively expensive operation.
  405.      *
  406.      * @return  a clone of the hashtable.
  407.      * @since   JDK1.0
  408.      */
  409.     public synchronized Object clone() {
  410.     try { 
  411.         Hashtable t = (Hashtable)super.clone();
  412.         t.table = new HashtableEntry[table.length];
  413.         for (int i = table.length ; i-- > 0 ; ) {
  414.         t.table[i] = (table[i] != null) 
  415.             ? (HashtableEntry)table[i].clone() : null;
  416.         }
  417.         return t;
  418.     } catch (CloneNotSupportedException e) { 
  419.         // this shouldn't happen, since we are Cloneable
  420.         throw new InternalError();
  421.     }
  422.     }
  423.  
  424.     /**
  425.      * Returns a rather long string representation of this hashtable.
  426.      *
  427.      * @return  a string representation of this hashtable.
  428.      * @since   JDK1.0
  429.      */
  430.     public synchronized String toString() {
  431.     int max = size() - 1;
  432.     StringBuffer buf = new StringBuffer();
  433.     Enumeration k = keys();
  434.     Enumeration e = elements();
  435.     buf.append("{");
  436.  
  437.     for (int i = 0; i <= max; i++) {
  438.         String s1 = k.nextElement().toString();
  439.         String s2 = e.nextElement().toString();
  440.         buf.append(s1 + "=" + s2);
  441.         if (i < max) {
  442.         buf.append(", ");
  443.         }
  444.     }
  445.     buf.append("}");
  446.     return buf.toString();
  447.     }
  448.  
  449.     /**
  450.      * WriteObject is called to save the state of the hashtable to a stream.
  451.      * Only the keys and values are serialized since the hash values may be
  452.      * different when the contents are restored.
  453.      * iterate over the contents and write out the keys and values.
  454.      */
  455.     private synchronized void writeObject(java.io.ObjectOutputStream s)
  456.         throws IOException
  457.     {
  458.     // Write out the length, threshold, loadfactor
  459.     s.defaultWriteObject();
  460.  
  461.     // Write out length, count of elements and then the key/value objects
  462.     s.writeInt(table.length);
  463.     s.writeInt(count);
  464.     for (int index = table.length-1; index >= 0; index--) {
  465.         HashtableEntry entry = table[index];
  466.  
  467.         while (entry != null) {
  468.         s.writeObject(entry.key);
  469.         s.writeObject(entry.value);
  470.         entry = entry.next;
  471.         }
  472.     }
  473.     }
  474.  
  475.     /**
  476.      * readObject is called to restore the state of the hashtable from
  477.      * a stream.  Only the keys and values are serialized since the
  478.      * hash values may be different when the contents are restored.
  479.      * Read count elements and insert into the hashtable. 
  480.      */
  481.     private synchronized void readObject(java.io.ObjectInputStream s)
  482.          throws IOException, ClassNotFoundException
  483.     {
  484.     // Read in the length, threshold, and loadfactor
  485.     s.defaultReadObject();
  486.  
  487.     // Read the original length of the array and number of elements
  488.     int origlength = s.readInt();
  489.     int elements = s.readInt();
  490.  
  491.     // Compute new size with a bit of room 5% to grow but
  492.     // No larger than the original size.  Make the length
  493.     // odd if it's large enough, this helps distribute the entries.
  494.     // Guard against the length ending up zero, that's not valid.
  495.     int length = (int)(elements * loadFactor) + (elements / 20) + 3;
  496.     if (length > elements && (length & 1) == 0)
  497.         length--;
  498.     if (origlength > 0 && length > origlength)
  499.         length = origlength;
  500.  
  501.     table = new HashtableEntry[length];
  502.     count = 0;
  503.  
  504.     // Read the number of elements and then all the key/value objects
  505.     for (; elements > 0; elements--) {
  506.         Object key = s.readObject();
  507.         Object value = s.readObject();
  508.         put(key, value);
  509.     }
  510.     }
  511. }
  512.  
  513. /**
  514.  * A hashtable enumerator class.  This class should remain opaque 
  515.  * to the client. It will use the Enumeration interface. 
  516.  */
  517. class HashtableEnumerator implements Enumeration {
  518.     boolean keys;
  519.     int index;
  520.     HashtableEntry table[];
  521.     HashtableEntry entry;
  522.  
  523.     HashtableEnumerator(HashtableEntry table[], boolean keys) {
  524.     this.table = table;
  525.     this.keys = keys;
  526.     this.index = table.length;
  527.     }
  528.     
  529.     public boolean hasMoreElements() {
  530.     if (entry != null) {
  531.         return true;
  532.     }
  533.     while (index-- > 0) {
  534.         if ((entry = table[index]) != null) {
  535.         return true;
  536.         }
  537.     }
  538.     return false;
  539.     }
  540.  
  541.     public Object nextElement() {
  542.     if (entry == null) {
  543.         while ((index-- > 0) && ((entry = table[index]) == null));
  544.     }
  545.     if (entry != null) {
  546.         HashtableEntry e = entry;
  547.         entry = e.next;
  548.         return keys ? e.key : e.value;
  549.     }
  550.     throw new NoSuchElementException("HashtableEnumerator");
  551.     }
  552. }
  553.