home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1997 May / Pcwk0597.iso / sybase / starbuck / java.z / Hashtable.java < prev    next >
Text File  |  1996-05-03  |  11KB  |  420 lines
  1. /*
  2.  * @(#)Hashtable.java    1.33 95/12/15  
  3.  *
  4.  * Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
  5.  *
  6.  * Permission to use, copy, modify, and distribute this software
  7.  * and its documentation for NON-COMMERCIAL purposes and without
  8.  * fee is hereby granted provided that this copyright notice
  9.  * appears in all copies. Please refer to the file "copyright.html"
  10.  * for further important copyright and licensing information.
  11.  *
  12.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  13.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  14.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  15.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  16.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  17.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  18.  */
  19.  
  20. package java.util;
  21.  
  22. /**
  23.  * Hashtable collision list.
  24.  */
  25. class HashtableEntry {
  26.     int hash;
  27.     Object key;
  28.     Object value;
  29.     HashtableEntry next;
  30.  
  31.     protected Object clone() {
  32.     HashtableEntry entry = new HashtableEntry();
  33.     entry.hash = hash;
  34.     entry.key = key;
  35.     entry.value = value;
  36.     entry.next = (next != null) ? (HashtableEntry)next.clone() : null;
  37.     return entry;
  38.     }
  39.  
  40.  
  41. }
  42.  
  43. /**
  44.  * Hashtable class. Maps keys to values. Any object can be used as
  45.  * a key and/or value.<p>
  46.  *
  47.  * To sucessfully store and retrieve objects from a hash table, the
  48.  * object used as the key must implement the hashCode() and equals()
  49.  * methods.<p>
  50.  *
  51.  * This example creates a hashtable of numbers. It uses the names of
  52.  * the numbers as keys:
  53.  * <pre>
  54.  *    Hashtable numbers = new Hashtable();
  55.  *    numbers.put("one", new Integer(1));
  56.  *    numbers.put("two", new Integer(2));
  57.  *    numbers.put("three", new Integer(3));
  58.  * </pre>
  59.  * To retrieve a number use:
  60.  * <pre>
  61.  *    Integer n = (Integer)numbers.get("two");
  62.  *    if (n != null) {
  63.  *        System.out.println("two = " + n);
  64.  *    }
  65.  * </pre>
  66.  *
  67.  * @see java.lang.Object#hashCode
  68.  * @see java.lang.Object#equals
  69.  * @version     1.33, 15 Dec 1995
  70.  * @author    Arthur van Hoff
  71.  */
  72. public
  73. class Hashtable extends Dictionary implements Cloneable {
  74.     /**
  75.      * The hash table data.
  76.      */
  77.     private HashtableEntry table[];
  78.  
  79.     /**
  80.      * The total number of entries in the hash table.
  81.      */
  82.     private int count;
  83.  
  84.     /**
  85.      * Rehashes the table when count exceeds this threshold.
  86.      */
  87.     private int threshold;
  88.  
  89.     /**
  90.      * The load factor for the hashtable.
  91.      */
  92.     private float loadFactor;
  93.  
  94.     /**
  95.      * Constructs a new, empty hashtable with the specified initial 
  96.      * capacity and the specified load factor.
  97.      * @param initialCapacity the initial number of buckets
  98.      * @param loadFactor a number between 0.0 and 1.0, it defines
  99.      *        the threshold for rehashing the hashtable into
  100.      *        a bigger one.
  101.      * @exception IllegalArgumentException If the initial capacity
  102.      * is less than or equal to zero.
  103.      * @exception IllegalArgumentException If the load factor is
  104.      * less than or equal to zero.
  105.      */
  106.     public Hashtable(int initialCapacity, float loadFactor) {
  107.     if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
  108.         throw new IllegalArgumentException();
  109.     }
  110.     this.loadFactor = loadFactor;
  111.     table = new HashtableEntry[initialCapacity];
  112.     threshold = (int)(initialCapacity * loadFactor);
  113.     }
  114.  
  115.     /**
  116.      * Constructs a new, empty hashtable with the specified initial 
  117.      * capacity.
  118.      * @param initialCapacity the initial number of buckets
  119.      */
  120.     public Hashtable(int initialCapacity) {
  121.     this(initialCapacity, 0.75f);
  122.     }
  123.  
  124.     /**
  125.      * Constructs a new, empty hashtable. A default capacity and load factor
  126.      * is used. Note that the hashtable will automatically grow when it gets
  127.      * full.
  128.      */
  129.     public Hashtable() {
  130.     this(101, 0.75f);
  131.     }
  132.  
  133.     /**
  134.      * Returns the number of elements contained in the hashtable. 
  135.      */
  136.     public int size() {
  137.     return count;
  138.     }
  139.  
  140.     /**
  141.      * Returns true if the hashtable contains no elements.
  142.      */
  143.     public boolean isEmpty() {
  144.     return count == 0;
  145.     }
  146.  
  147.     /**
  148.      * Returns an enumeration of the hashtable's keys.
  149.      * @see Hashtable#elements
  150.      * @see Enumeration
  151.      */
  152.     public synchronized Enumeration keys() {
  153.     return new HashtableEnumerator(table, true);
  154.     }
  155.  
  156.     /**
  157.      * Returns an enumeration of the elements. Use the Enumeration methods 
  158.      * on the returned object to fetch the elements sequentially.
  159.      * @see Hashtable#keys
  160.      * @see Enumeration
  161.      */
  162.     public synchronized Enumeration elements() {
  163.     return new HashtableEnumerator(table, false);
  164.     }
  165.  
  166.     /**
  167.      * Returns true if the specified object is an element of the hashtable.
  168.      * This operation is more expensive than the containsKey() method.
  169.      * @param value the value that we are looking for
  170.      * @exception NullPointerException If the value being searched 
  171.      * for is equal to null.
  172.      * @see Hashtable#containsKey
  173.      */
  174.     public synchronized boolean contains(Object value) {
  175.     if (value == null) {
  176.         throw new NullPointerException();
  177.     }
  178.  
  179.     HashtableEntry tab[] = table;
  180.     for (int i = tab.length ; i-- > 0 ;) {
  181.         for (HashtableEntry e = tab[i] ; e != null ; e = e.next) {
  182.         if (e.value.equals(value)) {
  183.             return true;
  184.         }
  185.         }
  186.     }
  187.     return false;
  188.     }
  189.  
  190.     /**
  191.      * Returns true if the collection contains an element for the key.
  192.      * @param key the key that we are looking for
  193.      * @see Hashtable#contains
  194.      */
  195.     public synchronized boolean containsKey(Object key) {
  196.     HashtableEntry tab[] = table;
  197.     int hash = key.hashCode();
  198.     int index = (hash & 0x7FFFFFFF) % tab.length;
  199.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  200.         if ((e.hash == hash) && e.key.equals(key)) {
  201.         return true;
  202.         }
  203.     }
  204.     return false;
  205.     }
  206.  
  207.     /**
  208.      * Gets the object associated with the specified key in the 
  209.      * hashtable.
  210.      * @param key the specified key
  211.      * @returns the element for the key or null if the key
  212.      *         is not defined in the hash table.
  213.      * @see Hashtable#put
  214.      */
  215.     public synchronized Object get(Object key) {
  216.     HashtableEntry tab[] = table;
  217.     int hash = key.hashCode();
  218.     int index = (hash & 0x7FFFFFFF) % tab.length;
  219.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  220.         if ((e.hash == hash) && e.key.equals(key)) {
  221.         return e.value;
  222.         }
  223.     }
  224.     return null;
  225.     }
  226.  
  227.     /**
  228.      * Rehashes the content of the table into a bigger table.
  229.      * This method is called automatically when the hashtable's
  230.      * size exceeds the threshold.
  231.      */
  232.     protected void rehash() {
  233.     int oldCapacity = table.length;
  234.     HashtableEntry oldTable[] = table;
  235.  
  236.     int newCapacity = oldCapacity * 2 + 1;
  237.     HashtableEntry newTable[] = new HashtableEntry[newCapacity];
  238.  
  239.     threshold = (int)(newCapacity * loadFactor);
  240.     table = newTable;
  241.  
  242.     //System.out.println("rehash old=" + oldCapacity + ", new=" + newCapacity + ", thresh=" + threshold + ", count=" + count);
  243.  
  244.     for (int i = oldCapacity ; i-- > 0 ;) {
  245.         for (HashtableEntry old = oldTable[i] ; old != null ; ) {
  246.         HashtableEntry e = old;
  247.         old = old.next;
  248.  
  249.         int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  250.         e.next = newTable[index];
  251.         newTable[index] = e;
  252.         }
  253.     }
  254.     }
  255.  
  256.     /**
  257.      * Puts the specified element into the hashtable, using the specified
  258.      * key.  The element may be retrieved by doing a get() with the same key.
  259.      * The key and the element cannot be null. 
  260.      * @param key the specified key in the hashtable
  261.      * @param value the specified element
  262.      * @exception NullPointerException If the value of the element 
  263.      * is equal to null.
  264.      * @see Hashtable#get
  265.      * @return the old value of the key, or null if it did not have one.
  266.      */
  267.     public synchronized Object put(Object key, Object value) {
  268.     // Make sure the value is not null
  269.     if (value == null) {
  270.         throw new NullPointerException();
  271.     }
  272.  
  273.     // Makes sure the key is not already in the hashtable.
  274.     HashtableEntry tab[] = table;
  275.     int hash = key.hashCode();
  276.     int index = (hash & 0x7FFFFFFF) % tab.length;
  277.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  278.         if ((e.hash == hash) && e.key.equals(key)) {
  279.         Object old = e.value;
  280.         e.value = value;
  281.         return old;
  282.         }
  283.     }
  284.  
  285.     if (count >= threshold) {
  286.         // Rehash the table if the threshold is exceeded
  287.         rehash();
  288.         return put(key, value);
  289.     } 
  290.  
  291.     // Creates the new entry.
  292.     HashtableEntry e = new HashtableEntry();
  293.     e.hash = hash;
  294.     e.key = key;
  295.     e.value = value;
  296.     e.next = tab[index];
  297.     tab[index] = e;
  298.     count++;
  299.     return null;
  300.     }
  301.  
  302.     /**
  303.      * Removes the element corresponding to the key. Does nothing if the
  304.      * key is not present.
  305.      * @param key the key that needs to be removed
  306.      * @return the value of key, or null if the key was not found.
  307.      */
  308.     public synchronized Object remove(Object key) {
  309.     HashtableEntry tab[] = table;
  310.     int hash = key.hashCode();
  311.     int index = (hash & 0x7FFFFFFF) % tab.length;
  312.     for (HashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
  313.         if ((e.hash == hash) && e.key.equals(key)) {
  314.         if (prev != null) {
  315.             prev.next = e.next;
  316.         } else {
  317.             tab[index] = e.next;
  318.         }
  319.         count--;
  320.         return e.value;
  321.         }
  322.     }
  323.     return null;
  324.     }
  325.  
  326.     /**
  327.      * Clears the hash table so that it has no more elements in it.
  328.      */
  329.     public synchronized void clear() {
  330.     HashtableEntry tab[] = table;
  331.     for (int index = tab.length; --index >= 0; )
  332.         tab[index] = null;
  333.     count = 0;
  334.     }
  335.  
  336.     /**
  337.      * Creates a clone of the hashtable. A shallow copy is made,
  338.      * the keys and elements themselves are NOT cloned. This is a
  339.      * relatively expensive operation.
  340.      */
  341.     public synchronized Object clone() {
  342.     try { 
  343.         Hashtable t = (Hashtable)super.clone();
  344.         t.table = new HashtableEntry[table.length];
  345.         for (int i = table.length ; i-- > 0 ; ) {
  346.         t.table[i] = (table[i] != null) 
  347.             ? (HashtableEntry)table[i].clone() : null;
  348.         }
  349.         return t;
  350.     } catch (CloneNotSupportedException e) { 
  351.         // this shouldn't happen, since we are Cloneable
  352.         throw new InternalError();
  353.     }
  354.     }
  355.  
  356.     /**
  357.      * Converts to a rather lengthy String.
  358.      */
  359.     public synchronized String toString() {
  360.     int max = size() - 1;
  361.     StringBuffer buf = new StringBuffer();
  362.     Enumeration k = keys();
  363.     Enumeration e = elements();
  364.     buf.append("{");
  365.  
  366.     for (int i = 0; i <= max; i++) {
  367.         String s1 = k.nextElement().toString();
  368.         String s2 = e.nextElement().toString();
  369.         buf.append(s1 + "=" + s2);
  370.         if (i < max) {
  371.         buf.append(", ");
  372.         }
  373.     }
  374.     buf.append("}");
  375.     return buf.toString();
  376.     }
  377. }
  378.  
  379. /**
  380.  * A hashtable enumerator class.  This class should remain opaque 
  381.  * to the client. It will use the Enumeration interface. 
  382.  */
  383. class HashtableEnumerator implements Enumeration {
  384.     boolean keys;
  385.     int index;
  386.     HashtableEntry table[];
  387.     HashtableEntry entry;
  388.  
  389.     HashtableEnumerator(HashtableEntry table[], boolean keys) {
  390.     this.table = table;
  391.     this.keys = keys;
  392.     this.index = table.length;
  393.     }
  394.     
  395.     public boolean hasMoreElements() {
  396.     if (entry != null) {
  397.         return true;
  398.     }
  399.     while (index-- > 0) {
  400.         if ((entry = table[index]) != null) {
  401.         return true;
  402.         }
  403.     }
  404.     return false;
  405.     }
  406.  
  407.     public Object nextElement() {
  408.     if (entry == null) {
  409.         while ((index-- > 0) && ((entry = table[index]) == null));
  410.     }
  411.     if (entry != null) {
  412.         HashtableEntry e = entry;
  413.         entry = e.next;
  414.         return keys ? e.key : e.value;
  415.     }
  416.     throw new NoSuchElementException("HashtableEnumerator");
  417.     }
  418.             
  419. }
  420.