home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1995 November / PCWK1195.iso / inne / win95 / sieciowe / hotja32.lzh / hotjava / classsrc / java / util / hashtable.java < prev    next >
Text File  |  1995-08-11  |  11KB  |  397 lines
  1. /*
  2.  * @(#)Hashtable.java    1.21 95/04/20  
  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 = (HashtableEntry)super.clone();
  33.     entry.next = (next != null) ? (HashtableEntry)next.clone() : null;
  34.     return entry;
  35.     }
  36. }
  37.  
  38. /**
  39.  * Hashtable class. Maps keys to values. Any object can be used as
  40.  * a key and/or value.<p>
  41.  *
  42.  * To sucessfully store and retrieve objects from a hash table the
  43.  * object used as the key must implement the hashCode() and equals()
  44.  * methods.<p>
  45.  *
  46.  * This example creates a hashtable of numbers. It uses the names of
  47.  * the numbers as keys:
  48.  * <pre>
  49.  *    Hashtable numbers = new Hashtable();
  50.  *    numbers.put("one", new Integer(1));
  51.  *    numbers.put("two", new Integer(1));
  52.  *    numbers.put("three", new Integer(1));
  53.  * </pre>
  54.  * To retrieve a number use:
  55.  * <pre>
  56.  *    Integer n = (Integer)numbers.get("two");
  57.  *    if (n != null) {
  58.  *        System.out.println("two = " + n);
  59.  *    }
  60.  * </pre>
  61.  *
  62.  * @see java.lang.Object#hashCode
  63.  * @see java.lang.Object#equals
  64.  * @version     1.21, 20 Apr 1995
  65.  * @author    Arthur van Hoff
  66.  */
  67. public
  68. class Hashtable {
  69.     /**
  70.      * The hash table data.
  71.      */
  72.     private HashtableEntry table[];
  73.  
  74.     /**
  75.      * The total number of entries in the hash table.
  76.      */
  77.     private int count;
  78.  
  79.     /**
  80.      * Rehashes the table when count exceeds this threshold.
  81.      */
  82.     private int threshold;
  83.  
  84.     /**
  85.      * The load factor for the hashTable.
  86.      */
  87.     private float loadFactor;
  88.  
  89.     /**
  90.      * Construct a new, empty hashtable with the specified initial capacity
  91.      * and the specified load factor.
  92.      * @param initialCapacity the initial number of buckets
  93.      * @param loadFactor a number between 0.0 and 1.0, it defines
  94.      *        the threshold for rehashing the hashtable into
  95.      *        a bigger one.
  96.      */
  97.     public Hashtable(int initialCapacity, float loadFactor) {
  98.     if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
  99.         throw new IllegalArgumentException();
  100.     }
  101.     this.loadFactor = loadFactor;
  102.     table = new HashtableEntry[initialCapacity];
  103.     threshold = (int)(initialCapacity * loadFactor);
  104.     }
  105.  
  106.     /**
  107.      * Constructs a new, empty hashtable with the specified initial capacity.
  108.      * @param initialCapacity the initial number of buckets
  109.      */
  110.     public Hashtable(int initialCapacity) {
  111.     this(initialCapacity, 0.75);
  112.     }
  113.  
  114.     /**
  115.      * Constructs a new, empty hashtable. A default capacity and load factor
  116.      * is used. Note that the hashtable will automatically grow when it gets
  117.      * full.
  118.      */
  119.     public Hashtable() {
  120.     this(101, 0.75);
  121.     }
  122.  
  123.     /**
  124.      * Returns the hashtable's size (the number of elements it contains).
  125.      */
  126.     public int size() {
  127.     return count;
  128.     }
  129.  
  130.     /**
  131.      * Returns true if the hashtable contains no elements.
  132.      */
  133.     public boolean isEmpty() {
  134.     return count == 0;
  135.     }
  136.  
  137.     /**
  138.      * Returns an enumeration of the hashtable's keys.
  139.      * @see Hashtable#elements
  140.      * @see Enumeration
  141.      */
  142.     public synchronized Enumeration keys() {
  143.     return new HashtableEnumerator(table, true);
  144.     }
  145.  
  146.     /**
  147.      * Returns an enumeration of the elements. Use the Enumeration methods on
  148.      * the returned object to fetch the elements sequentially.
  149.      * @see Hashtable#keys
  150.      * @see Enumeration
  151.      */
  152.     public synchronized Enumeration elements() {
  153.     return new HashtableEnumerator(table, false);
  154.     }
  155.  
  156.     /**
  157.      * Returns true if the specified object is an element of the hashtable.
  158.      * This operation is more expensive than containsKey()
  159.      * @param value the value that we are looking for
  160.      * @see Hashtable#containsKey
  161.      */
  162.     public synchronized boolean contains(Object value) {
  163.     if (value == null) {
  164.         throw new NullPointerException();
  165.     }
  166.  
  167.     HashtableEntry tab[] = table;
  168.     for (int i = tab.length ; i-- > 0 ;) {
  169.         for (HashtableEntry e = tab[i] ; e != null ; e = e.next) {
  170.         if (e.value.equals(value)) {
  171.             return true;
  172.         }
  173.         }
  174.     }
  175.     return false;
  176.     }
  177.  
  178.     /**
  179.      * Returns true if the collection contains an element for the key.
  180.      * @param key the key that we are looking for
  181.      * @see Hashtable#contains
  182.      */
  183.     public synchronized boolean containsKey(Object key) {
  184.     HashtableEntry tab[] = table;
  185.     int hash = key.hashCode();
  186.     int index = (hash & 0x7FFFFFFF) % tab.length;
  187.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  188.         if ((e.hash == hash) && e.key.equals(key)) {
  189.         return true;
  190.         }
  191.     }
  192.     return false;
  193.     }
  194.  
  195.     /**
  196.      * Gets the object associated with a key in the hashtable.
  197.      * @returns the element for the key or null if the key
  198.      *         is not defined in the hash table.
  199.      * @see Hashtable#put
  200.      */
  201.     public synchronized Object get(Object key) {
  202.     HashtableEntry tab[] = table;
  203.     int hash = key.hashCode();
  204.     int index = (hash & 0x7FFFFFFF) % tab.length;
  205.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  206.         if ((e.hash == hash) && e.key.equals(key)) {
  207.         return e.value;
  208.         }
  209.     }
  210.     return null;
  211.     }
  212.  
  213.     /**
  214.      * Rehashes the content of the table into a bigger table.
  215.      * This is method called automatically when the hashtable's
  216.      * size exeeds a threshold.
  217.      */
  218.     protected void rehash() {
  219.     int oldCapacity = table.length;
  220.     HashtableEntry oldTable[] = table;
  221.  
  222.     int newCapacity = oldCapacity * 2 + 1;
  223.     HashtableEntry newTable[] = new HashtableEntry[newCapacity];
  224.  
  225.     threshold = (int)(newCapacity * loadFactor);
  226.     table = newTable;
  227.  
  228.     //System.out.println("rehash old=" + oldCapacity + ", new=" + newCapacity + ", thresh=" + threshold + ", count=" + count);
  229.  
  230.     for (int i = oldCapacity ; i-- > 0 ;) {
  231.         for (HashtableEntry old = oldTable[i] ; old != null ; ) {
  232.         HashtableEntry e = old;
  233.         old = old.next;
  234.  
  235.         int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  236.         e.next = newTable[index];
  237.         newTable[index] = e;
  238.         }
  239.     }
  240.     }
  241.  
  242.     /**
  243.      * Puts the specified element into the hashtable, using the specified
  244.      * key.  The element may be retrieved by doing a get() with the same key.
  245.      * The key can't be null and the element can't be null.
  246.      * @see Hashtable#get
  247.      * @return the old value of the key, or null if it didn't have one
  248.      */
  249.     public synchronized Object put(Object key, Object value) {
  250.     // Make sure the value is not null
  251.     if (value == null) {
  252.         throw new NullPointerException();
  253.     }
  254.  
  255.     // Makes sure the key is not already in the hashtable.
  256.     HashtableEntry tab[] = table;
  257.     int hash = key.hashCode();
  258.     int index = (hash & 0x7FFFFFFF) % tab.length;
  259.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  260.         if ((e.hash == hash) && e.key.equals(key)) {
  261.         Object old = e.value;
  262.         e.value = value;
  263.         return old;
  264.         }
  265.     }
  266.  
  267.     if (count >= threshold) {
  268.         // Rehash the table if the threshold is exceeded
  269.         rehash();
  270.         return put(key, value);
  271.     } 
  272.  
  273.     // Creates the new entry.
  274.     HashtableEntry e = new HashtableEntry();
  275.     e.hash = hash;
  276.     e.key = key;
  277.     e.value = value;
  278.     e.next = tab[index];
  279.     tab[index] = e;
  280.     count++;
  281.     return null;
  282.     }
  283.  
  284.     /**
  285.      * Removes the element corresponding to the key. Does nothing if the
  286.      * key isn't present.
  287.      * @param key the key that needs to be removed
  288.      * @return the value of key, or null if the key was not found
  289.      */
  290.     public synchronized Object remove(Object key) {
  291.     HashtableEntry tab[] = table;
  292.     int hash = key.hashCode();
  293.     int index = (hash & 0x7FFFFFFF) % tab.length;
  294.     for (HashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
  295.         if ((e.hash == hash) && e.key.equals(key)) {
  296.         if (prev != null) {
  297.             prev.next = e.next;
  298.         } else {
  299.             tab[index] = e.next;
  300.         }
  301.         count--;
  302.         return e.value;
  303.         }
  304.     }
  305.     return null;
  306.     }
  307.  
  308.     /**
  309.      * Clears the hash table so that it has no more elements in it.
  310.      */
  311.     public synchronized void clear() {
  312.     HashtableEntry tab[] = table;
  313.     for (int index = tab.length; --index >= 0; )
  314.         tab[index] = null;
  315.     count = 0;
  316.     }
  317.  
  318.  
  319.     /**
  320.      * Creates a clone of the hashtable. A shallow copy is made,
  321.      * the keys and elements themselves are NOT cloned. This is a
  322.      * relatively expensive operation.
  323.      */
  324.     public synchronized Object clone() {
  325.     Hashtable t = (Hashtable)super.clone();
  326.     t.table = new HashtableEntry[table.length];
  327.     for (int i = table.length ; i-- > 0 ; ) {
  328.         t.table[i] = (table[i] != null) ? (HashtableEntry)table[i].clone() : null;
  329.     }
  330.     return t;
  331.     }
  332.  
  333.     /**
  334.      * Converts to a rather lengthy string.
  335.      */
  336.     public synchronized String toString() {
  337.     int max = size() - 1;
  338.     StringBuffer buf = new StringBuffer();
  339.     Enumeration k = keys();
  340.     Enumeration e = elements();
  341.     buf.append("{");
  342.  
  343.     for (int i = 0; i <= max; i++) {
  344.         String s1 = k.nextElement().toString();
  345.         String s2 = e.nextElement().toString();
  346.         buf.append(s1 + "=" + s2);
  347.         if (i < max) {
  348.         buf.append(", ");
  349.         }
  350.     }
  351.     buf.append("}");
  352.     return buf.toString();
  353.     }
  354. }
  355.  
  356. /**
  357.  * A hashtable enumerator class.This class should remain opague 
  358.  * to the client. It will use the Enumeration interface. 
  359.  */
  360. class HashtableEnumerator implements Enumeration {
  361.     boolean keys;
  362.     int index;
  363.     HashtableEntry table[];
  364.     HashtableEntry entry;
  365.  
  366.     HashtableEnumerator(HashtableEntry table[], boolean keys) {
  367.     this.table = table;
  368.     this.keys = keys;
  369.     this.index = table.length;
  370.     }
  371.     
  372.     public boolean hasMoreElements() {
  373.     if (entry != null) {
  374.         return true;
  375.     }
  376.     while (index-- > 0) {
  377.         if ((entry = table[index]) != null) {
  378.         return true;
  379.         }
  380.     }
  381.     return false;
  382.     }
  383.  
  384.     public Object nextElement() {
  385.     if (entry == null) {
  386.         while ((index-- > 0) && ((entry = table[index]) == null));
  387.     }
  388.     if (entry != null) {
  389.         HashtableEntry e = entry;
  390.         entry = e.next;
  391.         return keys ? e.key : e.value;
  392.     }
  393.     throw new NoSuchElementException("HashtableEnumerator");
  394.     }
  395.             
  396. }
  397.