1 /*
   2  * Copyright (c) 1994, 2008, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 import java.io.*;
  28 
  29 /**
  30  * This class implements a hash table, which maps keys to values. Any
  31  * non-<code>null</code> object can be used as a key or as a value. <p>
  32  *
  33  * To successfully store and retrieve objects from a hashtable, the
  34  * objects used as keys must implement the <code>hashCode</code>
  35  * method and the <code>equals</code> method. <p>
  36  *
  37  * An instance of <code>Hashtable</code> has two parameters that affect its
  38  * performance: <i>initial capacity</i> and <i>load factor</i>.  The
  39  * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
  40  * <i>initial capacity</i> is simply the capacity at the time the hash table
  41  * is created.  Note that the hash table is <i>open</i>: in the case of a "hash
  42  * collision", a single bucket stores multiple entries, which must be searched
  43  * sequentially.  The <i>load factor</i> is a measure of how full the hash
  44  * table is allowed to get before its capacity is automatically increased.
  45  * The initial capacity and load factor parameters are merely hints to
  46  * the implementation.  The exact details as to when and whether the rehash
  47  * method is invoked are implementation-dependent.<p>
  48  *
  49  * Generally, the default load factor (.75) offers a good tradeoff between
  50  * time and space costs.  Higher values decrease the space overhead but
  51  * increase the time cost to look up an entry (which is reflected in most
  52  * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
  53  *
  54  * The initial capacity controls a tradeoff between wasted space and the
  55  * need for <code>rehash</code> operations, which are time-consuming.
  56  * No <code>rehash</code> operations will <i>ever</i> occur if the initial
  57  * capacity is greater than the maximum number of entries the
  58  * <tt>Hashtable</tt> will contain divided by its load factor.  However,
  59  * setting the initial capacity too high can waste space.<p>
  60  *
  61  * If many entries are to be made into a <code>Hashtable</code>,
  62  * creating it with a sufficiently large capacity may allow the
  63  * entries to be inserted more efficiently than letting it perform
  64  * automatic rehashing as needed to grow the table. <p>
  65  *
  66  * This example creates a hashtable of numbers. It uses the names of
  67  * the numbers as keys:
  68  * <pre>   {@code
  69  *   Hashtable<String, Integer> numbers
  70  *     = new Hashtable<String, Integer>();
  71  *   numbers.put("one", 1);
  72  *   numbers.put("two", 2);
  73  *   numbers.put("three", 3);}</pre>
  74  *
  75  * <p>To retrieve a number, use the following code:
  76  * <pre>   {@code
  77  *   Integer n = numbers.get("two");
  78  *   if (n != null) {
  79  *     System.out.println("two = " + n);
  80  *   }}</pre>
  81  *
  82  * <p>The iterators returned by the <tt>iterator</tt> method of the collections
  83  * returned by all of this class's "collection view methods" are
  84  * <em>fail-fast</em>: if the Hashtable is structurally modified at any time
  85  * after the iterator is created, in any way except through the iterator's own
  86  * <tt>remove</tt> method, the iterator will throw a {@link
  87  * ConcurrentModificationException}.  Thus, in the face of concurrent
  88  * modification, the iterator fails quickly and cleanly, rather than risking
  89  * arbitrary, non-deterministic behavior at an undetermined time in the future.
  90  * The Enumerations returned by Hashtable's keys and elements methods are
  91  * <em>not</em> fail-fast.
  92  *
  93  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  94  * as it is, generally speaking, impossible to make any hard guarantees in the
  95  * presence of unsynchronized concurrent modification.  Fail-fast iterators
  96  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
  97  * Therefore, it would be wrong to write a program that depended on this
  98  * exception for its correctness: <i>the fail-fast behavior of iterators
  99  * should be used only to detect bugs.</i>
 100  *
 101  * <p>As of the Java 2 platform v1.2, this class was retrofitted to
 102  * implement the {@link Map} interface, making it a member of the
 103  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 104  *
 105  * Java Collections Framework</a>.  Unlike the new collection
 106  * implementations, {@code Hashtable} is synchronized.  If a
 107  * thread-safe implementation is not needed, it is recommended to use
 108  * {@link HashMap} in place of {@code Hashtable}.  If a thread-safe
 109  * highly-concurrent implementation is desired, then it is recommended
 110  * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
 111  * {@code Hashtable}.
 112  *
 113  * @author  Arthur van Hoff
 114  * @author  Josh Bloch
 115  * @author  Neal Gafter
 116  * @see     Object#equals(java.lang.Object)
 117  * @see     Object#hashCode()
 118  * @see     Hashtable#rehash()
 119  * @see     Collection
 120  * @see     Map
 121  * @see     HashMap
 122  * @see     TreeMap
 123  * @since JDK1.0
 124  */
 125 public class Hashtable<K,V>
 126     extends Dictionary<K,V>
 127     implements Map<K,V>, Cloneable, java.io.Serializable {
 128 
 129     /**
 130      * The hash table data.
 131      */
 132     private transient Entry[] table;
 133 
 134     /**
 135      * The total number of entries in the hash table.
 136      */
 137     private transient int count;
 138 
 139     /**
 140      * The table is rehashed when its size exceeds this threshold.  (The
 141      * value of this field is (int)(capacity * loadFactor).)
 142      *
 143      * @serial
 144      */
 145     private int threshold;
 146 
 147     /**
 148      * The load factor for the hashtable.
 149      *
 150      * @serial
 151      */
 152     private float loadFactor;
 153 
 154     /**
 155      * The number of times this Hashtable has been structurally modified
 156      * Structural modifications are those that change the number of entries in
 157      * the Hashtable or otherwise modify its internal structure (e.g.,
 158      * rehash).  This field is used to make iterators on Collection-views of
 159      * the Hashtable fail-fast.  (See ConcurrentModificationException).
 160      */
 161     private transient int modCount = 0;
 162 
 163     /** use serialVersionUID from JDK 1.0.2 for interoperability */
 164     private static final long serialVersionUID = 1421746759512286392L;
 165 
 166     /**
 167      * Constructs a new, empty hashtable with the specified initial
 168      * capacity and the specified load factor.
 169      *
 170      * @param      initialCapacity   the initial capacity of the hashtable.
 171      * @param      loadFactor        the load factor of the hashtable.
 172      * @exception  IllegalArgumentException  if the initial capacity is less
 173      *             than zero, or if the load factor is nonpositive.
 174      */
 175     public Hashtable(int initialCapacity, float loadFactor) {
 176         if (initialCapacity < 0)
 177             throw new IllegalArgumentException("Illegal Capacity: "+
 178                                                initialCapacity);
 179         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 180             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
 181 
 182         if (initialCapacity==0)
 183             initialCapacity = 1;
 184         this.loadFactor = loadFactor;
 185         table = new Entry[initialCapacity];
 186         threshold = (int)(initialCapacity * loadFactor);
 187     }
 188 
 189     /**
 190      * Constructs a new, empty hashtable with the specified initial capacity
 191      * and default load factor (0.75).
 192      *
 193      * @param     initialCapacity   the initial capacity of the hashtable.
 194      * @exception IllegalArgumentException if the initial capacity is less
 195      *              than zero.
 196      */
 197     public Hashtable(int initialCapacity) {
 198         this(initialCapacity, 0.75f);
 199     }
 200 
 201     /**
 202      * Constructs a new, empty hashtable with a default initial capacity (11)
 203      * and load factor (0.75).
 204      */
 205     public Hashtable() {
 206         this(11, 0.75f);
 207     }
 208 
 209     /**
 210      * Constructs a new hashtable with the same mappings as the given
 211      * Map.  The hashtable is created with an initial capacity sufficient to
 212      * hold the mappings in the given Map and a default load factor (0.75).
 213      *
 214      * @param t the map whose mappings are to be placed in this map.
 215      * @throws NullPointerException if the specified map is null.
 216      * @since   1.2
 217      */
 218     public Hashtable(Map<? extends K, ? extends V> t) {
 219         this(Math.max(2*t.size(), 11), 0.75f);
 220         putAll(t);
 221     }
 222 
 223     /**
 224      * Returns the number of keys in this hashtable.
 225      *
 226      * @return  the number of keys in this hashtable.
 227      */
 228     public synchronized int size() {
 229         return count;
 230     }
 231 
 232     /**
 233      * Tests if this hashtable maps no keys to values.
 234      *
 235      * @return  <code>true</code> if this hashtable maps no keys to values;
 236      *          <code>false</code> otherwise.
 237      */
 238     public synchronized boolean isEmpty() {
 239         return count == 0;
 240     }
 241 
 242     /**
 243      * Returns an enumeration of the keys in this hashtable.
 244      *
 245      * @return  an enumeration of the keys in this hashtable.
 246      * @see     Enumeration
 247      * @see     #elements()
 248      * @see     #keySet()
 249      * @see     Map
 250      */
 251     public synchronized Enumeration<K> keys() {
 252         return this.<K>getEnumeration(KEYS);
 253     }
 254 
 255     /**
 256      * Returns an enumeration of the values in this hashtable.
 257      * Use the Enumeration methods on the returned object to fetch the elements
 258      * sequentially.
 259      *
 260      * @return  an enumeration of the values in this hashtable.
 261      * @see     java.util.Enumeration
 262      * @see     #keys()
 263      * @see     #values()
 264      * @see     Map
 265      */
 266     public synchronized Enumeration<V> elements() {
 267         return this.<V>getEnumeration(VALUES);
 268     }
 269 
 270     /**
 271      * Tests if some key maps into the specified value in this hashtable.
 272      * This operation is more expensive than the {@link #containsKey
 273      * containsKey} method.
 274      *
 275      * <p>Note that this method is identical in functionality to
 276      * {@link #containsValue containsValue}, (which is part of the
 277      * {@link Map} interface in the collections framework).
 278      *
 279      * @param      value   a value to search for
 280      * @return     <code>true</code> if and only if some key maps to the
 281      *             <code>value</code> argument in this hashtable as
 282      *             determined by the <tt>equals</tt> method;
 283      *             <code>false</code> otherwise.
 284      * @exception  NullPointerException  if the value is <code>null</code>
 285      */
 286     public synchronized boolean contains(Object value) {
 287         if (value == null) {
 288             throw new NullPointerException();
 289         }
 290 
 291         Entry tab[] = table;
 292         for (int i = tab.length ; i-- > 0 ;) {
 293             for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
 294                 if (e.value.equals(value)) {
 295                     return true;
 296                 }
 297             }
 298         }
 299         return false;
 300     }
 301 
 302     /**
 303      * Returns true if this hashtable maps one or more keys to this value.
 304      *
 305      * <p>Note that this method is identical in functionality to {@link
 306      * #contains contains} (which predates the {@link Map} interface).
 307      *
 308      * @param value value whose presence in this hashtable is to be tested
 309      * @return <tt>true</tt> if this map maps one or more keys to the
 310      *         specified value
 311      * @throws NullPointerException  if the value is <code>null</code>
 312      * @since 1.2
 313      */
 314     public boolean containsValue(Object value) {
 315         return contains(value);
 316     }
 317 
 318     /**
 319      * Tests if the specified object is a key in this hashtable.
 320      *
 321      * @param   key   possible key
 322      * @return  <code>true</code> if and only if the specified object
 323      *          is a key in this hashtable, as determined by the
 324      *          <tt>equals</tt> method; <code>false</code> otherwise.
 325      * @throws  NullPointerException  if the key is <code>null</code>
 326      * @see     #contains(Object)
 327      */
 328     public synchronized boolean containsKey(Object key) {
 329         Entry tab[] = table;
 330         int hash = key.hashCode();
 331         int index = (hash & 0x7FFFFFFF) % tab.length;
 332         for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
 333             if ((e.hash == hash) && e.key.equals(key)) {
 334                 return true;
 335             }
 336         }
 337         return false;
 338     }
 339 
 340     /**
 341      * Returns the value to which the specified key is mapped,
 342      * or {@code null} if this map contains no mapping for the key.
 343      *
 344      * <p>More formally, if this map contains a mapping from a key
 345      * {@code k} to a value {@code v} such that {@code (key.equals(k))},
 346      * then this method returns {@code v}; otherwise it returns
 347      * {@code null}.  (There can be at most one such mapping.)
 348      *
 349      * @param key the key whose associated value is to be returned
 350      * @return the value to which the specified key is mapped, or
 351      *         {@code null} if this map contains no mapping for the key
 352      * @throws NullPointerException if the specified key is null
 353      * @see     #put(Object, Object)
 354      */
 355     public synchronized V get(Object key) {
 356         Entry tab[] = table;
 357         int hash = key.hashCode();
 358         int index = (hash & 0x7FFFFFFF) % tab.length;
 359         for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
 360             if ((e.hash == hash) && e.key.equals(key)) {
 361                 return e.value;
 362             }
 363         }
 364         return null;
 365     }
 366 
 367     /**
 368      * The maximum size of array to allocate.
 369      * Some VMs reserve some header words in an array.
 370      * Attempts to allocate larger arrays may result in
 371      * OutOfMemoryError: Requested array size exceeds VM limit
 372      */
 373     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 374 
 375     /**
 376      * Increases the capacity of and internally reorganizes this
 377      * hashtable, in order to accommodate and access its entries more
 378      * efficiently.  This method is called automatically when the
 379      * number of keys in the hashtable exceeds this hashtable's capacity
 380      * and load factor.
 381      */
 382     protected void rehash() {
 383         int oldCapacity = table.length;
 384         Entry[] oldMap = table;
 385 
 386         // overflow-conscious code
 387         int newCapacity = (oldCapacity << 1) + 1;
 388         if (newCapacity - MAX_ARRAY_SIZE > 0) {
 389             if (oldCapacity == MAX_ARRAY_SIZE)
 390                 // Keep running with MAX_ARRAY_SIZE buckets
 391                 return;
 392             newCapacity = MAX_ARRAY_SIZE;
 393         }
 394         Entry[] newMap = new Entry[newCapacity];
 395 
 396         modCount++;
 397         threshold = (int)(newCapacity * loadFactor);
 398         table = newMap;
 399 
 400         for (int i = oldCapacity ; i-- > 0 ;) {
 401             for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
 402                 Entry<K,V> e = old;
 403                 old = old.next;
 404 
 405                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
 406                 e.next = newMap[index];
 407                 newMap[index] = e;
 408             }
 409         }
 410     }
 411 
 412     /**
 413      * Maps the specified <code>key</code> to the specified
 414      * <code>value</code> in this hashtable. Neither the key nor the
 415      * value can be <code>null</code>. <p>
 416      *
 417      * The value can be retrieved by calling the <code>get</code> method
 418      * with a key that is equal to the original key.
 419      *
 420      * @param      key     the hashtable key
 421      * @param      value   the value
 422      * @return     the previous value of the specified key in this hashtable,
 423      *             or <code>null</code> if it did not have one
 424      * @exception  NullPointerException  if the key or value is
 425      *               <code>null</code>
 426      * @see     Object#equals(Object)
 427      * @see     #get(Object)
 428      */
 429     public synchronized V put(K key, V value) {
 430         // Make sure the value is not null
 431         if (value == null) {
 432             throw new NullPointerException();
 433         }
 434 
 435         // Makes sure the key is not already in the hashtable.
 436         Entry tab[] = table;
 437         int hash = key.hashCode();
 438         int index = (hash & 0x7FFFFFFF) % tab.length;
 439         for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
 440             if ((e.hash == hash) && e.key.equals(key)) {
 441                 V old = e.value;
 442                 e.value = value;
 443                 return old;
 444             }
 445         }
 446 
 447         modCount++;
 448         if (count >= threshold) {
 449             // Rehash the table if the threshold is exceeded
 450             rehash();
 451 
 452             tab = table;
 453             index = (hash & 0x7FFFFFFF) % tab.length;
 454         }
 455 
 456         // Creates the new entry.
 457         Entry<K,V> e = tab[index];
 458         tab[index] = new Entry<K,V>(hash, key, value, e);
 459         count++;
 460         return null;
 461     }
 462 
 463     /**
 464      * Removes the key (and its corresponding value) from this
 465      * hashtable. This method does nothing if the key is not in the hashtable.
 466      *
 467      * @param   key   the key that needs to be removed
 468      * @return  the value to which the key had been mapped in this hashtable,
 469      *          or <code>null</code> if the key did not have a mapping
 470      * @throws  NullPointerException  if the key is <code>null</code>
 471      */
 472     public synchronized V remove(Object key) {
 473         Entry tab[] = table;
 474         int hash = key.hashCode();
 475         int index = (hash & 0x7FFFFFFF) % tab.length;
 476         for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
 477             if ((e.hash == hash) && e.key.equals(key)) {
 478                 modCount++;
 479                 if (prev != null) {
 480                     prev.next = e.next;
 481                 } else {
 482                     tab[index] = e.next;
 483                 }
 484                 count--;
 485                 V oldValue = e.value;
 486                 e.value = null;
 487                 return oldValue;
 488             }
 489         }
 490         return null;
 491     }
 492 
 493     /**
 494      * Copies all of the mappings from the specified map to this hashtable.
 495      * These mappings will replace any mappings that this hashtable had for any
 496      * of the keys currently in the specified map.
 497      *
 498      * @param t mappings to be stored in this map
 499      * @throws NullPointerException if the specified map is null
 500      * @since 1.2
 501      */
 502     public synchronized void putAll(Map<? extends K, ? extends V> t) {
 503         for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
 504             put(e.getKey(), e.getValue());
 505     }
 506 
 507     /**
 508      * Clears this hashtable so that it contains no keys.
 509      */
 510     public synchronized void clear() {
 511         Entry tab[] = table;
 512         modCount++;
 513         for (int index = tab.length; --index >= 0; )
 514             tab[index] = null;
 515         count = 0;
 516     }
 517 
 518     /**
 519      * Creates a shallow copy of this hashtable. All the structure of the
 520      * hashtable itself is copied, but the keys and values are not cloned.
 521      * This is a relatively expensive operation.
 522      *
 523      * @return  a clone of the hashtable
 524      */
 525     public synchronized Object clone() {
 526         try {
 527             Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
 528             t.table = new Entry[table.length];
 529             for (int i = table.length ; i-- > 0 ; ) {
 530                 t.table[i] = (table[i] != null)
 531                     ? (Entry<K,V>) table[i].clone() : null;
 532             }
 533             t.keySet = null;
 534             t.entrySet = null;
 535             t.values = null;
 536             t.modCount = 0;
 537             return t;
 538         } catch (CloneNotSupportedException e) {
 539             // this shouldn't happen, since we are Cloneable
 540             throw new InternalError();
 541         }
 542     }
 543 
 544     /**
 545      * Returns a string representation of this <tt>Hashtable</tt> object
 546      * in the form of a set of entries, enclosed in braces and separated
 547      * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each
 548      * entry is rendered as the key, an equals sign <tt>=</tt>, and the
 549      * associated element, where the <tt>toString</tt> method is used to
 550      * convert the key and element to strings.
 551      *
 552      * @return  a string representation of this hashtable
 553      */
 554     public synchronized String toString() {
 555         int max = size() - 1;
 556         if (max == -1)
 557             return "{}";
 558 
 559         StringBuilder sb = new StringBuilder();
 560         Iterator<Map.Entry<K,V>> it = entrySet().iterator();
 561 
 562         sb.append('{');
 563         for (int i = 0; ; i++) {
 564             Map.Entry<K,V> e = it.next();
 565             K key = e.getKey();
 566             V value = e.getValue();
 567             sb.append(key   == this ? "(this Map)" : key.toString());
 568             sb.append('=');
 569             sb.append(value == this ? "(this Map)" : value.toString());
 570 
 571             if (i == max)
 572                 return sb.append('}').toString();
 573             sb.append(", ");
 574         }
 575     }
 576 
 577 
 578     private <T> Enumeration<T> getEnumeration(int type) {
 579         if (count == 0) {
 580             return Collections.emptyEnumeration();
 581         } else {
 582             return new Enumerator<T>(type, false);
 583         }
 584     }
 585 
 586     private <T> Iterator<T> getIterator(int type) {
 587         if (count == 0) {
 588             return Collections.emptyIterator();
 589         } else {
 590             return new Enumerator<T>(type, true);
 591         }
 592     }
 593 
 594     // Views
 595 
 596     /**
 597      * Each of these fields are initialized to contain an instance of the
 598      * appropriate view the first time this view is requested.  The views are
 599      * stateless, so there's no reason to create more than one of each.
 600      */
 601     private transient volatile Set<K> keySet = null;
 602     private transient volatile Set<Map.Entry<K,V>> entrySet = null;
 603     private transient volatile Collection<V> values = null;
 604 
 605     /**
 606      * Returns a {@link Set} view of the keys contained in this map.
 607      * The set is backed by the map, so changes to the map are
 608      * reflected in the set, and vice-versa.  If the map is modified
 609      * while an iteration over the set is in progress (except through
 610      * the iterator's own <tt>remove</tt> operation), the results of
 611      * the iteration are undefined.  The set supports element removal,
 612      * which removes the corresponding mapping from the map, via the
 613      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 614      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 615      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
 616      * operations.
 617      *
 618      * @since 1.2
 619      */
 620     public Set<K> keySet() {
 621         if (keySet == null)
 622             keySet = Collections.synchronizedSet(new KeySet(), this);
 623         return keySet;
 624     }
 625 
 626     private class KeySet extends AbstractSet<K> {
 627         public Iterator<K> iterator() {
 628             return getIterator(KEYS);
 629         }
 630         public int size() {
 631             return count;
 632         }
 633         public boolean contains(Object o) {
 634             return containsKey(o);
 635         }
 636         public boolean remove(Object o) {
 637             return Hashtable.this.remove(o) != null;
 638         }
 639         public void clear() {
 640             Hashtable.this.clear();
 641         }
 642     }
 643 
 644     /**
 645      * Returns a {@link Set} view of the mappings contained in this map.
 646      * The set is backed by the map, so changes to the map are
 647      * reflected in the set, and vice-versa.  If the map is modified
 648      * while an iteration over the set is in progress (except through
 649      * the iterator's own <tt>remove</tt> operation, or through the
 650      * <tt>setValue</tt> operation on a map entry returned by the
 651      * iterator) the results of the iteration are undefined.  The set
 652      * supports element removal, which removes the corresponding
 653      * mapping from the map, via the <tt>Iterator.remove</tt>,
 654      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
 655      * <tt>clear</tt> operations.  It does not support the
 656      * <tt>add</tt> or <tt>addAll</tt> operations.
 657      *
 658      * @since 1.2
 659      */
 660     public Set<Map.Entry<K,V>> entrySet() {
 661         if (entrySet==null)
 662             entrySet = Collections.synchronizedSet(new EntrySet(), this);
 663         return entrySet;
 664     }
 665 
 666     private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 667         public Iterator<Map.Entry<K,V>> iterator() {
 668             return getIterator(ENTRIES);
 669         }
 670 
 671         public boolean add(Map.Entry<K,V> o) {
 672             return super.add(o);
 673         }
 674 
 675         public boolean contains(Object o) {
 676             if (!(o instanceof Map.Entry))
 677                 return false;
 678             Map.Entry entry = (Map.Entry)o;
 679             Object key = entry.getKey();
 680             Entry[] tab = table;
 681             int hash = key.hashCode();
 682             int index = (hash & 0x7FFFFFFF) % tab.length;
 683 
 684             for (Entry e = tab[index]; e != null; e = e.next)
 685                 if (e.hash==hash && e.equals(entry))
 686                     return true;
 687             return false;
 688         }
 689 
 690         public boolean remove(Object o) {
 691             if (!(o instanceof Map.Entry))
 692                 return false;
 693             Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
 694             K key = entry.getKey();
 695             Entry[] tab = table;
 696             int hash = key.hashCode();
 697             int index = (hash & 0x7FFFFFFF) % tab.length;
 698 
 699             for (Entry<K,V> e = tab[index], prev = null; e != null;
 700                  prev = e, e = e.next) {
 701                 if (e.hash==hash && e.equals(entry)) {
 702                     modCount++;
 703                     if (prev != null)
 704                         prev.next = e.next;
 705                     else
 706                         tab[index] = e.next;
 707 
 708                     count--;
 709                     e.value = null;
 710                     return true;
 711                 }
 712             }
 713             return false;
 714         }
 715 
 716         public int size() {
 717             return count;
 718         }
 719 
 720         public void clear() {
 721             Hashtable.this.clear();
 722         }
 723     }
 724 
 725     /**
 726      * Returns a {@link Collection} view of the values contained in this map.
 727      * The collection is backed by the map, so changes to the map are
 728      * reflected in the collection, and vice-versa.  If the map is
 729      * modified while an iteration over the collection is in progress
 730      * (except through the iterator's own <tt>remove</tt> operation),
 731      * the results of the iteration are undefined.  The collection
 732      * supports element removal, which removes the corresponding
 733      * mapping from the map, via the <tt>Iterator.remove</tt>,
 734      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 735      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
 736      * support the <tt>add</tt> or <tt>addAll</tt> operations.
 737      *
 738      * @since 1.2
 739      */
 740     public Collection<V> values() {
 741         if (values==null)
 742             values = Collections.synchronizedCollection(new ValueCollection(),
 743                                                         this);
 744         return values;
 745     }
 746 
 747     private class ValueCollection extends AbstractCollection<V> {
 748         public Iterator<V> iterator() {
 749             return getIterator(VALUES);
 750         }
 751         public int size() {
 752             return count;
 753         }
 754         public boolean contains(Object o) {
 755             return containsValue(o);
 756         }
 757         public void clear() {
 758             Hashtable.this.clear();
 759         }
 760     }
 761 
 762     // Comparison and hashing
 763 
 764     /**
 765      * Compares the specified Object with this Map for equality,
 766      * as per the definition in the Map interface.
 767      *
 768      * @param  o object to be compared for equality with this hashtable
 769      * @return true if the specified Object is equal to this Map
 770      * @see Map#equals(Object)
 771      * @since 1.2
 772      */
 773     public synchronized boolean equals(Object o) {
 774         if (o == this)
 775             return true;
 776 
 777         if (!(o instanceof Map))
 778             return false;
 779         Map<K,V> t = (Map<K,V>) o;
 780         if (t.size() != size())
 781             return false;
 782 
 783         try {
 784             Iterator<Map.Entry<K,V>> i = entrySet().iterator();
 785             while (i.hasNext()) {
 786                 Map.Entry<K,V> e = i.next();
 787                 K key = e.getKey();
 788                 V value = e.getValue();
 789                 if (value == null) {
 790                     if (!(t.get(key)==null && t.containsKey(key)))
 791                         return false;
 792                 } else {
 793                     if (!value.equals(t.get(key)))
 794                         return false;
 795                 }
 796             }
 797         } catch (ClassCastException unused)   {
 798             return false;
 799         } catch (NullPointerException unused) {
 800             return false;
 801         }
 802 
 803         return true;
 804     }
 805 
 806     /**
 807      * Returns the hash code value for this Map as per the definition in the
 808      * Map interface.
 809      *
 810      * @see Map#hashCode()
 811      * @since 1.2
 812      */
 813     public synchronized int hashCode() {
 814         /*
 815          * This code detects the recursion caused by computing the hash code
 816          * of a self-referential hash table and prevents the stack overflow
 817          * that would otherwise result.  This allows certain 1.1-era
 818          * applets with self-referential hash tables to work.  This code
 819          * abuses the loadFactor field to do double-duty as a hashCode
 820          * in progress flag, so as not to worsen the space performance.
 821          * A negative load factor indicates that hash code computation is
 822          * in progress.
 823          */
 824         int h = 0;
 825         if (count == 0 || loadFactor < 0)
 826             return h;  // Returns zero
 827 
 828         loadFactor = -loadFactor;  // Mark hashCode computation in progress
 829         Entry[] tab = table;
 830         for (int i = 0; i < tab.length; i++)
 831             for (Entry e = tab[i]; e != null; e = e.next)
 832                 h += e.key.hashCode() ^ e.value.hashCode();
 833         loadFactor = -loadFactor;  // Mark hashCode computation complete
 834 
 835         return h;
 836     }
 837 
 838     /**
 839      * Save the state of the Hashtable to a stream (i.e., serialize it).
 840      *
 841      * @serialData The <i>capacity</i> of the Hashtable (the length of the
 842      *             bucket array) is emitted (int), followed by the
 843      *             <i>size</i> of the Hashtable (the number of key-value
 844      *             mappings), followed by the key (Object) and value (Object)
 845      *             for each key-value mapping represented by the Hashtable
 846      *             The key-value mappings are emitted in no particular order.
 847      */
 848     private synchronized void writeObject(java.io.ObjectOutputStream s)
 849         throws IOException
 850     {
 851         // Write out the length, threshold, loadfactor
 852         s.defaultWriteObject();
 853 
 854         // Write out length, count of elements and then the key/value objects
 855         s.writeInt(table.length);
 856         s.writeInt(count);
 857         for (int index = table.length-1; index >= 0; index--) {
 858             Entry entry = table[index];
 859 
 860             while (entry != null) {
 861                 s.writeObject(entry.key);
 862                 s.writeObject(entry.value);
 863                 entry = entry.next;
 864             }
 865         }
 866     }
 867 
 868     /**
 869      * Reconstitute the Hashtable from a stream (i.e., deserialize it).
 870      */
 871     private void readObject(java.io.ObjectInputStream s)
 872          throws IOException, ClassNotFoundException
 873     {
 874         // Read in the length, threshold, and loadfactor
 875         s.defaultReadObject();
 876 
 877         // Read the original length of the array and number of elements
 878         int origlength = s.readInt();
 879         int elements = s.readInt();
 880 
 881         // Compute new size with a bit of room 5% to grow but
 882         // no larger than the original size.  Make the length
 883         // odd if it's large enough, this helps distribute the entries.
 884         // Guard against the length ending up zero, that's not valid.
 885         int length = (int)(elements * loadFactor) + (elements / 20) + 3;
 886         if (length > elements && (length & 1) == 0)
 887             length--;
 888         if (origlength > 0 && length > origlength)
 889             length = origlength;
 890 
 891         Entry[] table = new Entry[length];
 892         count = 0;
 893 
 894         // Read the number of elements and then all the key/value objects
 895         for (; elements > 0; elements--) {
 896             K key = (K)s.readObject();
 897             V value = (V)s.readObject();
 898             // synch could be eliminated for performance
 899             reconstitutionPut(table, key, value);
 900         }
 901         this.table = table;
 902     }
 903 
 904     /**
 905      * The put method used by readObject. This is provided because put
 906      * is overridable and should not be called in readObject since the
 907      * subclass will not yet be initialized.
 908      *
 909      * <p>This differs from the regular put method in several ways. No
 910      * checking for rehashing is necessary since the number of elements
 911      * initially in the table is known. The modCount is not incremented
 912      * because we are creating a new instance. Also, no return value
 913      * is needed.
 914      */
 915     private void reconstitutionPut(Entry[] tab, K key, V value)
 916         throws StreamCorruptedException
 917     {
 918         if (value == null) {
 919             throw new java.io.StreamCorruptedException();
 920         }
 921         // Makes sure the key is not already in the hashtable.
 922         // This should not happen in deserialized version.
 923         int hash = key.hashCode();
 924         int index = (hash & 0x7FFFFFFF) % tab.length;
 925         for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
 926             if ((e.hash == hash) && e.key.equals(key)) {
 927                 throw new java.io.StreamCorruptedException();
 928             }
 929         }
 930         // Creates the new entry.
 931         Entry<K,V> e = tab[index];
 932         tab[index] = new Entry<K,V>(hash, key, value, e);
 933         count++;
 934     }
 935 
 936     /**
 937      * Hashtable collision list.
 938      */
 939     private static class Entry<K,V> implements Map.Entry<K,V> {
 940         int hash;
 941         K key;
 942         V value;
 943         Entry<K,V> next;
 944 
 945         protected Entry(int hash, K key, V value, Entry<K,V> next) {
 946             this.hash = hash;
 947             this.key = key;
 948             this.value = value;
 949             this.next = next;
 950         }
 951 
 952         protected Object clone() {
 953             return new Entry<K,V>(hash, key, value,
 954                                   (next==null ? null : (Entry<K,V>) next.clone()));
 955         }
 956 
 957         // Map.Entry Ops
 958 
 959         public K getKey() {
 960             return key;
 961         }
 962 
 963         public V getValue() {
 964             return value;
 965         }
 966 
 967         public V setValue(V value) {
 968             if (value == null)
 969                 throw new NullPointerException();
 970 
 971             V oldValue = this.value;
 972             this.value = value;
 973             return oldValue;
 974         }
 975 
 976         public boolean equals(Object o) {
 977             if (!(o instanceof Map.Entry))
 978                 return false;
 979             Map.Entry e = (Map.Entry)o;
 980 
 981             return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
 982                (value==null ? e.getValue()==null : value.equals(e.getValue()));
 983         }
 984 
 985         public int hashCode() {
 986             return hash ^ (value==null ? 0 : value.hashCode());
 987         }
 988 
 989         public String toString() {
 990             return key.toString()+"="+value.toString();
 991         }
 992     }
 993 
 994     // Types of Enumerations/Iterations
 995     private static final int KEYS = 0;
 996     private static final int VALUES = 1;
 997     private static final int ENTRIES = 2;
 998 
 999     /**
1000      * A hashtable enumerator class.  This class implements both the
1001      * Enumeration and Iterator interfaces, but individual instances
1002      * can be created with the Iterator methods disabled.  This is necessary
1003      * to avoid unintentionally increasing the capabilities granted a user
1004      * by passing an Enumeration.
1005      */
1006     private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1007         Entry[] table = Hashtable.this.table;
1008         int index = table.length;
1009         Entry<K,V> entry = null;
1010         Entry<K,V> lastReturned = null;
1011         int type;
1012 
1013         /**
1014          * Indicates whether this Enumerator is serving as an Iterator
1015          * or an Enumeration.  (true -> Iterator).
1016          */
1017         boolean iterator;
1018 
1019         /**
1020          * The modCount value that the iterator believes that the backing
1021          * Hashtable should have.  If this expectation is violated, the iterator
1022          * has detected concurrent modification.
1023          */
1024         protected int expectedModCount = modCount;
1025 
1026         Enumerator(int type, boolean iterator) {
1027             this.type = type;
1028             this.iterator = iterator;
1029         }
1030 
1031         public boolean hasMoreElements() {
1032             Entry<K,V> e = entry;
1033             int i = index;
1034             Entry[] t = table;
1035             /* Use locals for faster loop iteration */
1036             while (e == null && i > 0) {
1037                 e = t[--i];
1038             }
1039             entry = e;
1040             index = i;
1041             return e != null;
1042         }
1043 
1044         public T nextElement() {
1045             Entry<K,V> et = entry;
1046             int i = index;
1047             Entry[] t = table;
1048             /* Use locals for faster loop iteration */
1049             while (et == null && i > 0) {
1050                 et = t[--i];
1051             }
1052             entry = et;
1053             index = i;
1054             if (et != null) {
1055                 Entry<K,V> e = lastReturned = entry;
1056                 entry = e.next;
1057                 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1058             }
1059             throw new NoSuchElementException("Hashtable Enumerator");
1060         }
1061 
1062         // Iterator methods
1063         public boolean hasNext() {
1064             return hasMoreElements();
1065         }
1066 
1067         public T next() {
1068             if (modCount != expectedModCount)
1069                 throw new ConcurrentModificationException();
1070             return nextElement();
1071         }
1072 
1073         public void remove() {
1074             if (!iterator)
1075                 throw new UnsupportedOperationException();
1076             if (lastReturned == null)
1077                 throw new IllegalStateException("Hashtable Enumerator");
1078             if (modCount != expectedModCount)
1079                 throw new ConcurrentModificationException();
1080 
1081             synchronized(Hashtable.this) {
1082                 Entry[] tab = Hashtable.this.table;
1083                 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1084 
1085                 for (Entry<K,V> e = tab[index], prev = null; e != null;
1086                      prev = e, e = e.next) {
1087                     if (e == lastReturned) {
1088                         modCount++;
1089                         expectedModCount++;
1090                         if (prev == null)
1091                             tab[index] = e.next;
1092                         else
1093                             prev.next = e.next;
1094                         count--;
1095                         lastReturned = null;
1096                         return;
1097                     }
1098                 }
1099                 throw new ConcurrentModificationException();
1100             }
1101         }
1102     }
1103 }