1 /*
   2  * Copyright (c) 1994, 2013, 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 
  28 import java.io.*;
  29 import java.util.function.BiConsumer;
  30 import java.util.function.Function;
  31 import java.util.function.BiFunction;
  32 
  33 /**
  34  * This class implements a hash table, which maps keys to values. Any
  35  * non-<code>null</code> object can be used as a key or as a value. <p>
  36  *
  37  * To successfully store and retrieve objects from a hashtable, the
  38  * objects used as keys must implement the <code>hashCode</code>
  39  * method and the <code>equals</code> method. <p>
  40  *
  41  * An instance of <code>Hashtable</code> has two parameters that affect its
  42  * performance: <i>initial capacity</i> and <i>load factor</i>.  The
  43  * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
  44  * <i>initial capacity</i> is simply the capacity at the time the hash table
  45  * is created.  Note that the hash table is <i>open</i>: in the case of a "hash
  46  * collision", a single bucket stores multiple entries, which must be searched
  47  * sequentially.  The <i>load factor</i> is a measure of how full the hash
  48  * table is allowed to get before its capacity is automatically increased.
  49  * The initial capacity and load factor parameters are merely hints to
  50  * the implementation.  The exact details as to when and whether the rehash
  51  * method is invoked are implementation-dependent.<p>
  52  *
  53  * Generally, the default load factor (.75) offers a good tradeoff between
  54  * time and space costs.  Higher values decrease the space overhead but
  55  * increase the time cost to look up an entry (which is reflected in most
  56  * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
  57  *
  58  * The initial capacity controls a tradeoff between wasted space and the
  59  * need for <code>rehash</code> operations, which are time-consuming.
  60  * No <code>rehash</code> operations will <i>ever</i> occur if the initial
  61  * capacity is greater than the maximum number of entries the
  62  * <tt>Hashtable</tt> will contain divided by its load factor.  However,
  63  * setting the initial capacity too high can waste space.<p>
  64  *
  65  * If many entries are to be made into a <code>Hashtable</code>,
  66  * creating it with a sufficiently large capacity may allow the
  67  * entries to be inserted more efficiently than letting it perform
  68  * automatic rehashing as needed to grow the table. <p>
  69  *
  70  * This example creates a hashtable of numbers. It uses the names of
  71  * the numbers as keys:
  72  * <pre>   {@code
  73  *   Hashtable<String, Integer> numbers
  74  *     = new Hashtable<String, Integer>();
  75  *   numbers.put("one", 1);
  76  *   numbers.put("two", 2);
  77  *   numbers.put("three", 3);}</pre>
  78  *
  79  * <p>To retrieve a number, use the following code:
  80  * <pre>   {@code
  81  *   Integer n = numbers.get("two");
  82  *   if (n != null) {
  83  *     System.out.println("two = " + n);
  84  *   }}</pre>
  85  *
  86  * <p>The iterators returned by the <tt>iterator</tt> method of the collections
  87  * returned by all of this class's "collection view methods" are
  88  * <em>fail-fast</em>: if the Hashtable is structurally modified at any time
  89  * after the iterator is created, in any way except through the iterator's own
  90  * <tt>remove</tt> method, the iterator will throw a {@link
  91  * ConcurrentModificationException}.  Thus, in the face of concurrent
  92  * modification, the iterator fails quickly and cleanly, rather than risking
  93  * arbitrary, non-deterministic behavior at an undetermined time in the future.
  94  * The Enumerations returned by Hashtable's {@link #keys keys} and
  95  * {@link #elements elements} methods are <em>not</em> fail-fast; if the
  96  * Hashtable is structurally modified at any time after the enumeration is
  97  * created then the results of enumerating are undefined.
  98  *
  99  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 100  * as it is, generally speaking, impossible to make any hard guarantees in the
 101  * presence of unsynchronized concurrent modification.  Fail-fast iterators
 102  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 103  * Therefore, it would be wrong to write a program that depended on this
 104  * exception for its correctness: <i>the fail-fast behavior of iterators
 105  * should be used only to detect bugs.</i>
 106  *
 107  * <p>As of the Java 2 platform v1.2, this class was retrofitted to
 108  * implement the {@link Map} interface, making it a member of the
 109  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 110  *
 111  * Java Collections Framework</a>.  Unlike the new collection
 112  * implementations, {@code Hashtable} is synchronized.  If a
 113  * thread-safe implementation is not needed, it is recommended to use
 114  * {@link HashMap} in place of {@code Hashtable}.  If a thread-safe
 115  * highly-concurrent implementation is desired, then it is recommended
 116  * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
 117  * {@code Hashtable}.
 118  *
 119  * @param <K> the type of keys maintained by this map
 120  * @param <V> the type of mapped values
 121  *
 122  * @author  Arthur van Hoff
 123  * @author  Josh Bloch
 124  * @author  Neal Gafter
 125  * @see     Object#equals(java.lang.Object)
 126  * @see     Object#hashCode()
 127  * @see     Hashtable#rehash()
 128  * @see     Collection
 129  * @see     Map
 130  * @see     HashMap
 131  * @see     TreeMap
 132  * @since 1.0
 133  */
 134 public class Hashtable<K,V>
 135     extends Dictionary<K,V>
 136     implements Map<K,V>, Cloneable, java.io.Serializable {
 137 
 138     /**
 139      * The hash table data.
 140      */
 141     private transient Entry<?,?>[] table;
 142 
 143     /**
 144      * The total number of entries in the hash table.
 145      */
 146     private transient int count;
 147 
 148     /**
 149      * The table is rehashed when its size exceeds this threshold.  (The
 150      * value of this field is (int)(capacity * loadFactor).)
 151      *
 152      * @serial
 153      */
 154     private int threshold;
 155 
 156     /**
 157      * The load factor for the hashtable.
 158      *
 159      * @serial
 160      */
 161     private float loadFactor;
 162 
 163     /**
 164      * The number of times this Hashtable has been structurally modified
 165      * Structural modifications are those that change the number of entries in
 166      * the Hashtable or otherwise modify its internal structure (e.g.,
 167      * rehash).  This field is used to make iterators on Collection-views of
 168      * the Hashtable fail-fast.  (See ConcurrentModificationException).
 169      */
 170     private transient int modCount = 0;
 171 
 172     /** use serialVersionUID from JDK 1.0.2 for interoperability */
 173     private static final long serialVersionUID = 1421746759512286392L;
 174 
 175     /**
 176      * Constructs a new, empty hashtable with the specified initial
 177      * capacity and the specified load factor.
 178      *
 179      * @param      initialCapacity   the initial capacity of the hashtable.
 180      * @param      loadFactor        the load factor of the hashtable.
 181      * @exception  IllegalArgumentException  if the initial capacity is less
 182      *             than zero, or if the load factor is nonpositive.
 183      */
 184     public Hashtable(int initialCapacity, float loadFactor) {
 185         if (initialCapacity < 0)
 186             throw new IllegalArgumentException("Illegal Capacity: "+
 187                                                initialCapacity);
 188         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 189             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
 190 
 191         if (initialCapacity==0)
 192             initialCapacity = 1;
 193         this.loadFactor = loadFactor;
 194         table = new Entry<?,?>[initialCapacity];
 195         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
 196     }
 197 
 198     /**
 199      * Constructs a new, empty hashtable with the specified initial capacity
 200      * and default load factor (0.75).
 201      *
 202      * @param     initialCapacity   the initial capacity of the hashtable.
 203      * @exception IllegalArgumentException if the initial capacity is less
 204      *              than zero.
 205      */
 206     public Hashtable(int initialCapacity) {
 207         this(initialCapacity, 0.75f);
 208     }
 209 
 210     /**
 211      * Constructs a new, empty hashtable with a default initial capacity (11)
 212      * and load factor (0.75).
 213      */
 214     public Hashtable() {
 215         this(11, 0.75f);
 216     }
 217 
 218     /**
 219      * Constructs a new hashtable with the same mappings as the given
 220      * Map.  The hashtable is created with an initial capacity sufficient to
 221      * hold the mappings in the given Map and a default load factor (0.75).
 222      *
 223      * @param t the map whose mappings are to be placed in this map.
 224      * @throws NullPointerException if the specified map is null.
 225      * @since   1.2
 226      */
 227     public Hashtable(Map<? extends K, ? extends V> t) {
 228         this(Math.max(2*t.size(), 11), 0.75f);
 229         putAll(t);
 230     }
 231 
 232     /**
 233      * Returns the number of keys in this hashtable.
 234      *
 235      * @return  the number of keys in this hashtable.
 236      */
 237     public synchronized int size() {
 238         return count;
 239     }
 240 
 241     /**
 242      * Tests if this hashtable maps no keys to values.
 243      *
 244      * @return  <code>true</code> if this hashtable maps no keys to values;
 245      *          <code>false</code> otherwise.
 246      */
 247     public synchronized boolean isEmpty() {
 248         return count == 0;
 249     }
 250 
 251     /**
 252      * Returns an enumeration of the keys in this hashtable.
 253      * Use the Enumeration methods on the returned object to fetch the keys
 254      * sequentially. If the hashtable is structurally modified while enumerating
 255      * over the keys then the results of enumerating are undefined.
 256      *
 257      * @return  an enumeration of the keys in this hashtable.
 258      * @see     Enumeration
 259      * @see     #elements()
 260      * @see     #keySet()
 261      * @see     Map
 262      */
 263     public synchronized Enumeration<K> keys() {
 264         return this.<K>getEnumeration(KEYS);
 265     }
 266 
 267     /**
 268      * Returns an enumeration of the values in this hashtable.
 269      * Use the Enumeration methods on the returned object to fetch the elements
 270      * sequentially. If the hashtable is structurally modified while enumerating
 271      * over the values then the results of enumerating are undefined.
 272      *
 273      * @return  an enumeration of the values in this hashtable.
 274      * @see     java.util.Enumeration
 275      * @see     #keys()
 276      * @see     #values()
 277      * @see     Map
 278      */
 279     public synchronized Enumeration<V> elements() {
 280         return this.<V>getEnumeration(VALUES);
 281     }
 282 
 283     /**
 284      * Tests if some key maps into the specified value in this hashtable.
 285      * This operation is more expensive than the {@link #containsKey
 286      * containsKey} method.
 287      *
 288      * <p>Note that this method is identical in functionality to
 289      * {@link #containsValue containsValue}, (which is part of the
 290      * {@link Map} interface in the collections framework).
 291      *
 292      * @param      value   a value to search for
 293      * @return     <code>true</code> if and only if some key maps to the
 294      *             <code>value</code> argument in this hashtable as
 295      *             determined by the <tt>equals</tt> method;
 296      *             <code>false</code> otherwise.
 297      * @exception  NullPointerException  if the value is <code>null</code>
 298      */
 299     public synchronized boolean contains(Object value) {
 300         if (value == null) {
 301             throw new NullPointerException();
 302         }
 303 
 304         Entry<?,?> tab[] = table;
 305         for (int i = tab.length ; i-- > 0 ;) {
 306             for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
 307                 if (e.value.equals(value)) {
 308                     return true;
 309                 }
 310             }
 311         }
 312         return false;
 313     }
 314 
 315     /**
 316      * Returns true if this hashtable maps one or more keys to this value.
 317      *
 318      * <p>Note that this method is identical in functionality to {@link
 319      * #contains contains} (which predates the {@link Map} interface).
 320      *
 321      * @param value value whose presence in this hashtable is to be tested
 322      * @return <tt>true</tt> if this map maps one or more keys to the
 323      *         specified value
 324      * @throws NullPointerException  if the value is <code>null</code>
 325      * @since 1.2
 326      */
 327     public boolean containsValue(Object value) {
 328         return contains(value);
 329     }
 330 
 331     /**
 332      * Tests if the specified object is a key in this hashtable.
 333      *
 334      * @param   key   possible key
 335      * @return  <code>true</code> if and only if the specified object
 336      *          is a key in this hashtable, as determined by the
 337      *          <tt>equals</tt> method; <code>false</code> otherwise.
 338      * @throws  NullPointerException  if the key is <code>null</code>
 339      * @see     #contains(Object)
 340      */
 341     public synchronized boolean containsKey(Object key) {
 342         Entry<?,?> tab[] = table;
 343         int hash = key.hashCode();
 344         int index = (hash & 0x7FFFFFFF) % tab.length;
 345         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 346             if ((e.hash == hash) && e.key.equals(key)) {
 347                 return true;
 348             }
 349         }
 350         return false;
 351     }
 352 
 353     /**
 354      * Returns the value to which the specified key is mapped,
 355      * or {@code null} if this map contains no mapping for the key.
 356      *
 357      * <p>More formally, if this map contains a mapping from a key
 358      * {@code k} to a value {@code v} such that {@code (key.equals(k))},
 359      * then this method returns {@code v}; otherwise it returns
 360      * {@code null}.  (There can be at most one such mapping.)
 361      *
 362      * @param key the key whose associated value is to be returned
 363      * @return the value to which the specified key is mapped, or
 364      *         {@code null} if this map contains no mapping for the key
 365      * @throws NullPointerException if the specified key is null
 366      * @see     #put(Object, Object)
 367      */
 368     @SuppressWarnings("unchecked")
 369     public synchronized V get(Object key) {
 370         Entry<?,?> tab[] = table;
 371         int hash = key.hashCode();
 372         int index = (hash & 0x7FFFFFFF) % tab.length;
 373         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 374             if ((e.hash == hash) && e.key.equals(key)) {
 375                 return (V)e.value;
 376             }
 377         }
 378         return null;
 379     }
 380 
 381     /**
 382      * The maximum size of array to allocate.
 383      * Some VMs reserve some header words in an array.
 384      * Attempts to allocate larger arrays may result in
 385      * OutOfMemoryError: Requested array size exceeds VM limit
 386      */
 387     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 388 
 389     /**
 390      * Increases the capacity of and internally reorganizes this
 391      * hashtable, in order to accommodate and access its entries more
 392      * efficiently.  This method is called automatically when the
 393      * number of keys in the hashtable exceeds this hashtable's capacity
 394      * and load factor.
 395      */
 396     @SuppressWarnings("unchecked")
 397     protected void rehash() {
 398         int oldCapacity = table.length;
 399         Entry<?,?>[] oldMap = table;
 400 
 401         // overflow-conscious code
 402         int newCapacity = (oldCapacity << 1) + 1;
 403         if (newCapacity - MAX_ARRAY_SIZE > 0) {
 404             if (oldCapacity == MAX_ARRAY_SIZE)
 405                 // Keep running with MAX_ARRAY_SIZE buckets
 406                 return;
 407             newCapacity = MAX_ARRAY_SIZE;
 408         }
 409         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
 410 
 411         modCount++;
 412         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
 413         table = newMap;
 414 
 415         for (int i = oldCapacity ; i-- > 0 ;) {
 416             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
 417                 Entry<K,V> e = old;
 418                 old = old.next;
 419 
 420                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
 421                 e.next = (Entry<K,V>)newMap[index];
 422                 newMap[index] = e;
 423             }
 424         }
 425     }
 426 
 427     private void addEntry(int hash, K key, V value, int index) {
 428         Entry<?,?> tab[] = table;
 429         if (count >= threshold) {
 430             // Rehash the table if the threshold is exceeded
 431             rehash();
 432 
 433             tab = table;
 434             hash = key.hashCode();
 435             index = (hash & 0x7FFFFFFF) % tab.length;
 436         }
 437 
 438         // Creates the new entry.
 439         @SuppressWarnings("unchecked")
 440         Entry<K,V> e = (Entry<K,V>) tab[index];
 441         tab[index] = new Entry<>(hash, key, value, e);
 442         count++;
 443         modCount++;
 444     }
 445 
 446     /**
 447      * Maps the specified <code>key</code> to the specified
 448      * <code>value</code> in this hashtable. Neither the key nor the
 449      * value can be <code>null</code>. <p>
 450      *
 451      * The value can be retrieved by calling the <code>get</code> method
 452      * with a key that is equal to the original key.
 453      *
 454      * @param      key     the hashtable key
 455      * @param      value   the value
 456      * @return     the previous value of the specified key in this hashtable,
 457      *             or <code>null</code> if it did not have one
 458      * @exception  NullPointerException  if the key or value is
 459      *               <code>null</code>
 460      * @see     Object#equals(Object)
 461      * @see     #get(Object)
 462      */
 463     public synchronized V put(K key, V value) {
 464         // Make sure the value is not null
 465         if (value == null) {
 466             throw new NullPointerException();
 467         }
 468 
 469         // Makes sure the key is not already in the hashtable.
 470         Entry<?,?> tab[] = table;
 471         int hash = key.hashCode();
 472         int index = (hash & 0x7FFFFFFF) % tab.length;
 473         @SuppressWarnings("unchecked")
 474         Entry<K,V> entry = (Entry<K,V>)tab[index];
 475         for(; entry != null ; entry = entry.next) {
 476             if ((entry.hash == hash) && entry.key.equals(key)) {
 477                 V old = entry.value;
 478                 entry.value = value;
 479                 return old;
 480             }
 481         }
 482 
 483         addEntry(hash, key, value, index);
 484         return null;
 485     }
 486 
 487     /**
 488      * Removes the key (and its corresponding value) from this
 489      * hashtable. This method does nothing if the key is not in the hashtable.
 490      *
 491      * @param   key   the key that needs to be removed
 492      * @return  the value to which the key had been mapped in this hashtable,
 493      *          or <code>null</code> if the key did not have a mapping
 494      * @throws  NullPointerException  if the key is <code>null</code>
 495      */
 496     public synchronized V remove(Object key) {
 497         Entry<?,?> tab[] = table;
 498         int hash = key.hashCode();
 499         int index = (hash & 0x7FFFFFFF) % tab.length;
 500         @SuppressWarnings("unchecked")
 501         Entry<K,V> e = (Entry<K,V>)tab[index];
 502         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
 503             if ((e.hash == hash) && e.key.equals(key)) {
 504                 if (prev != null) {
 505                     prev.next = e.next;
 506                 } else {
 507                     tab[index] = e.next;
 508                 }
 509                 modCount++;
 510                 count--;
 511                 V oldValue = e.value;
 512                 e.value = null;
 513                 return oldValue;
 514             }
 515         }
 516         return null;
 517     }
 518 
 519     /**
 520      * Copies all of the mappings from the specified map to this hashtable.
 521      * These mappings will replace any mappings that this hashtable had for any
 522      * of the keys currently in the specified map.
 523      *
 524      * @param t mappings to be stored in this map
 525      * @throws NullPointerException if the specified map is null
 526      * @since 1.2
 527      */
 528     public synchronized void putAll(Map<? extends K, ? extends V> t) {
 529         for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
 530             put(e.getKey(), e.getValue());
 531     }
 532 
 533     /**
 534      * Clears this hashtable so that it contains no keys.
 535      */
 536     public synchronized void clear() {
 537         Entry<?,?> tab[] = table;
 538         for (int index = tab.length; --index >= 0; )
 539             tab[index] = null;
 540         modCount++;
 541         count = 0;
 542     }
 543 
 544     /**
 545      * Creates a shallow copy of this hashtable. All the structure of the
 546      * hashtable itself is copied, but the keys and values are not cloned.
 547      * This is a relatively expensive operation.
 548      *
 549      * @return  a clone of the hashtable
 550      */
 551     public synchronized Object clone() {
 552         try {
 553             Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
 554             t.table = new Entry<?,?>[table.length];
 555             for (int i = table.length ; i-- > 0 ; ) {
 556                 t.table[i] = (table[i] != null)
 557                     ? (Entry<?,?>) table[i].clone() : null;
 558             }
 559             t.keySet = null;
 560             t.entrySet = null;
 561             t.values = null;
 562             t.modCount = 0;
 563             return t;
 564         } catch (CloneNotSupportedException e) {
 565             // this shouldn't happen, since we are Cloneable
 566             throw new InternalError(e);
 567         }
 568     }
 569 
 570     /**
 571      * Returns a string representation of this <tt>Hashtable</tt> object
 572      * in the form of a set of entries, enclosed in braces and separated
 573      * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each
 574      * entry is rendered as the key, an equals sign <tt>=</tt>, and the
 575      * associated element, where the <tt>toString</tt> method is used to
 576      * convert the key and element to strings.
 577      *
 578      * @return  a string representation of this hashtable
 579      */
 580     public synchronized String toString() {
 581         int max = size() - 1;
 582         if (max == -1)
 583             return "{}";
 584 
 585         StringBuilder sb = new StringBuilder();
 586         Iterator<Map.Entry<K,V>> it = entrySet().iterator();
 587 
 588         sb.append('{');
 589         for (int i = 0; ; i++) {
 590             Map.Entry<K,V> e = it.next();
 591             K key = e.getKey();
 592             V value = e.getValue();
 593             sb.append(key   == this ? "(this Map)" : key.toString());
 594             sb.append('=');
 595             sb.append(value == this ? "(this Map)" : value.toString());
 596 
 597             if (i == max)
 598                 return sb.append('}').toString();
 599             sb.append(", ");
 600         }
 601     }
 602 
 603 
 604     private <T> Enumeration<T> getEnumeration(int type) {
 605         if (count == 0) {
 606             return Collections.emptyEnumeration();
 607         } else {
 608             return new Enumerator<>(type, false);
 609         }
 610     }
 611 
 612     private <T> Iterator<T> getIterator(int type) {
 613         if (count == 0) {
 614             return Collections.emptyIterator();
 615         } else {
 616             return new Enumerator<>(type, true);
 617         }
 618     }
 619 
 620     // Views
 621 
 622     /**
 623      * Each of these fields are initialized to contain an instance of the
 624      * appropriate view the first time this view is requested.  The views are
 625      * stateless, so there's no reason to create more than one of each.
 626      */
 627     private transient volatile Set<K> keySet;
 628     private transient volatile Set<Map.Entry<K,V>> entrySet;
 629     private transient volatile Collection<V> values;
 630 
 631     /**
 632      * Returns a {@link Set} view of the keys contained in this map.
 633      * The set is backed by the map, so changes to the map are
 634      * reflected in the set, and vice-versa.  If the map is modified
 635      * while an iteration over the set is in progress (except through
 636      * the iterator's own <tt>remove</tt> operation), the results of
 637      * the iteration are undefined.  The set supports element removal,
 638      * which removes the corresponding mapping from the map, via the
 639      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 640      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 641      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
 642      * operations.
 643      *
 644      * @since 1.2
 645      */
 646     public Set<K> keySet() {
 647         if (keySet == null)
 648             keySet = Collections.synchronizedSet(new KeySet(), this);
 649         return keySet;
 650     }
 651 
 652     private class KeySet extends AbstractSet<K> {
 653         public Iterator<K> iterator() {
 654             return getIterator(KEYS);
 655         }
 656         public int size() {
 657             return count;
 658         }
 659         public boolean contains(Object o) {
 660             return containsKey(o);
 661         }
 662         public boolean remove(Object o) {
 663             return Hashtable.this.remove(o) != null;
 664         }
 665         public void clear() {
 666             Hashtable.this.clear();
 667         }
 668     }
 669 
 670     /**
 671      * Returns a {@link Set} view of the mappings contained in this map.
 672      * The set is backed by the map, so changes to the map are
 673      * reflected in the set, and vice-versa.  If the map is modified
 674      * while an iteration over the set is in progress (except through
 675      * the iterator's own <tt>remove</tt> operation, or through the
 676      * <tt>setValue</tt> operation on a map entry returned by the
 677      * iterator) the results of the iteration are undefined.  The set
 678      * supports element removal, which removes the corresponding
 679      * mapping from the map, via the <tt>Iterator.remove</tt>,
 680      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
 681      * <tt>clear</tt> operations.  It does not support the
 682      * <tt>add</tt> or <tt>addAll</tt> operations.
 683      *
 684      * @since 1.2
 685      */
 686     public Set<Map.Entry<K,V>> entrySet() {
 687         if (entrySet==null)
 688             entrySet = Collections.synchronizedSet(new EntrySet(), this);
 689         return entrySet;
 690     }
 691 
 692     private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 693         public Iterator<Map.Entry<K,V>> iterator() {
 694             return getIterator(ENTRIES);
 695         }
 696 
 697         public boolean add(Map.Entry<K,V> o) {
 698             return super.add(o);
 699         }
 700 
 701         public boolean contains(Object o) {
 702             if (!(o instanceof Map.Entry))
 703                 return false;
 704             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
 705             Object key = entry.getKey();
 706             Entry<?,?>[] tab = table;
 707             int hash = key.hashCode();
 708             int index = (hash & 0x7FFFFFFF) % tab.length;
 709 
 710             for (Entry<?,?> e = tab[index]; e != null; e = e.next)
 711                 if (e.hash==hash && e.equals(entry))
 712                     return true;
 713             return false;
 714         }
 715 
 716         public boolean remove(Object o) {
 717             if (!(o instanceof Map.Entry))
 718                 return false;
 719             Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
 720             Object key = entry.getKey();
 721             Entry<?,?>[] tab = table;
 722             int hash = key.hashCode();
 723             int index = (hash & 0x7FFFFFFF) % tab.length;
 724 
 725             @SuppressWarnings("unchecked")
 726             Entry<K,V> e = (Entry<K,V>)tab[index];
 727             for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
 728                 if (e.hash==hash && e.equals(entry)) {
 729                     if (prev != null)
 730                         prev.next = e.next;
 731                     else
 732                         tab[index] = e.next;
 733 
 734                     e.value = null; // clear for gc.
 735                     modCount++;
 736                     count--;
 737                     return true;
 738                 }
 739             }
 740             return false;
 741         }
 742 
 743         public int size() {
 744             return count;
 745         }
 746 
 747         public void clear() {
 748             Hashtable.this.clear();
 749         }
 750     }
 751 
 752     /**
 753      * Returns a {@link Collection} view of the values contained in this map.
 754      * The collection is backed by the map, so changes to the map are
 755      * reflected in the collection, and vice-versa.  If the map is
 756      * modified while an iteration over the collection is in progress
 757      * (except through the iterator's own <tt>remove</tt> operation),
 758      * the results of the iteration are undefined.  The collection
 759      * supports element removal, which removes the corresponding
 760      * mapping from the map, via the <tt>Iterator.remove</tt>,
 761      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 762      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
 763      * support the <tt>add</tt> or <tt>addAll</tt> operations.
 764      *
 765      * @since 1.2
 766      */
 767     public Collection<V> values() {
 768         if (values==null)
 769             values = Collections.synchronizedCollection(new ValueCollection(),
 770                                                         this);
 771         return values;
 772     }
 773 
 774     private class ValueCollection extends AbstractCollection<V> {
 775         public Iterator<V> iterator() {
 776             return getIterator(VALUES);
 777         }
 778         public int size() {
 779             return count;
 780         }
 781         public boolean contains(Object o) {
 782             return containsValue(o);
 783         }
 784         public void clear() {
 785             Hashtable.this.clear();
 786         }
 787     }
 788 
 789     // Comparison and hashing
 790 
 791     /**
 792      * Compares the specified Object with this Map for equality,
 793      * as per the definition in the Map interface.
 794      *
 795      * @param  o object to be compared for equality with this hashtable
 796      * @return true if the specified Object is equal to this Map
 797      * @see Map#equals(Object)
 798      * @since 1.2
 799      */
 800     public synchronized boolean equals(Object o) {
 801         if (o == this)
 802             return true;
 803 
 804         if (!(o instanceof Map))
 805             return false;
 806         Map<?,?> t = (Map<?,?>) o;
 807         if (t.size() != size())
 808             return false;
 809 
 810         try {
 811             for (Map.Entry<K, V> e : entrySet()) {
 812                 K key = e.getKey();
 813                 V value = e.getValue();
 814                 if (value == null) {
 815                     if (!(t.get(key) == null && t.containsKey(key)))
 816                         return false;
 817                 } else {
 818                     if (!value.equals(t.get(key)))
 819                         return false;
 820                 }
 821             }
 822         } catch (ClassCastException unused)   {
 823             return false;
 824         } catch (NullPointerException unused) {
 825             return false;
 826         }
 827 
 828         return true;
 829     }
 830 
 831     /**
 832      * Returns the hash code value for this Map as per the definition in the
 833      * Map interface.
 834      *
 835      * @see Map#hashCode()
 836      * @since 1.2
 837      */
 838     public synchronized int hashCode() {
 839         /*
 840          * This code detects the recursion caused by computing the hash code
 841          * of a self-referential hash table and prevents the stack overflow
 842          * that would otherwise result.  This allows certain 1.1-era
 843          * applets with self-referential hash tables to work.  This code
 844          * abuses the loadFactor field to do double-duty as a hashCode
 845          * in progress flag, so as not to worsen the space performance.
 846          * A negative load factor indicates that hash code computation is
 847          * in progress.
 848          */
 849         int h = 0;
 850         if (count == 0 || loadFactor < 0)
 851             return h;  // Returns zero
 852 
 853         loadFactor = -loadFactor;  // Mark hashCode computation in progress
 854         Entry<?,?>[] tab = table;
 855         for (Entry<?,?> entry : tab) {
 856             while (entry != null) {
 857                 h += entry.hashCode();
 858                 entry = entry.next;
 859             }
 860         }
 861 
 862         loadFactor = -loadFactor;  // Mark hashCode computation complete
 863 
 864         return h;
 865     }
 866 
 867     @Override
 868     public synchronized V getOrDefault(Object key, V defaultValue) {
 869         V result = get(key);
 870         return (null == result) ? defaultValue : result;
 871     }
 872 
 873     @SuppressWarnings("unchecked")
 874     @Override
 875     public synchronized void forEach(BiConsumer<? super K, ? super V> action) {
 876         Objects.requireNonNull(action);     // explicit check required in case
 877                                             // table is empty.
 878         final int expectedModCount = modCount;
 879 
 880         Entry<?, ?>[] tab = table;
 881         for (Entry<?, ?> entry : tab) {
 882             while (entry != null) {
 883                 action.accept((K)entry.key, (V)entry.value);
 884                 entry = entry.next;
 885 
 886                 if (expectedModCount != modCount) {
 887                     throw new ConcurrentModificationException();
 888                 }
 889             }
 890         }
 891     }
 892 
 893     @SuppressWarnings("unchecked")
 894     @Override
 895     public synchronized void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
 896         Objects.requireNonNull(function);     // explicit check required in case
 897                                               // table is empty.
 898         final int expectedModCount = modCount;
 899 
 900         Entry<K, V>[] tab = (Entry<K, V>[])table;
 901         for (Entry<K, V> entry : tab) {
 902             while (entry != null) {
 903                 entry.value = Objects.requireNonNull(
 904                     function.apply(entry.key, entry.value));
 905                 entry = entry.next;
 906 
 907                 if (expectedModCount != modCount) {
 908                     throw new ConcurrentModificationException();
 909                 }
 910             }
 911         }
 912     }
 913 
 914     @Override
 915     public synchronized V putIfAbsent(K key, V value) {
 916         Objects.requireNonNull(value);
 917 
 918         // Makes sure the key is not already in the hashtable.
 919         Entry<?,?> tab[] = table;
 920         int hash = key.hashCode();
 921         int index = (hash & 0x7FFFFFFF) % tab.length;
 922         @SuppressWarnings("unchecked")
 923         Entry<K,V> entry = (Entry<K,V>)tab[index];
 924         for (; entry != null; entry = entry.next) {
 925             if ((entry.hash == hash) && entry.key.equals(key)) {
 926                 V old = entry.value;
 927                 if (old == null) {
 928                     entry.value = value;
 929                 }
 930                 return old;
 931             }
 932         }
 933 
 934         addEntry(hash, key, value, index);
 935         return null;
 936     }
 937 
 938     @Override
 939     public synchronized boolean remove(Object key, Object value) {
 940         Objects.requireNonNull(value);
 941 
 942         Entry<?,?> tab[] = table;
 943         int hash = key.hashCode();
 944         int index = (hash & 0x7FFFFFFF) % tab.length;
 945         @SuppressWarnings("unchecked")
 946         Entry<K,V> e = (Entry<K,V>)tab[index];
 947         for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
 948             if ((e.hash == hash) && e.key.equals(key) && e.value.equals(value)) {
 949                 if (prev != null) {
 950                     prev.next = e.next;
 951                 } else {
 952                     tab[index] = e.next;
 953                 }
 954                 e.value = null; // clear for gc
 955                 modCount++;
 956                 count--;
 957                 return true;
 958             }
 959         }
 960         return false;
 961     }
 962 
 963     @Override
 964     public synchronized boolean replace(K key, V oldValue, V newValue) {
 965         Objects.requireNonNull(oldValue);
 966         Objects.requireNonNull(newValue);
 967         Entry<?,?> tab[] = table;
 968         int hash = key.hashCode();
 969         int index = (hash & 0x7FFFFFFF) % tab.length;
 970         @SuppressWarnings("unchecked")
 971         Entry<K,V> e = (Entry<K,V>)tab[index];
 972         for (; e != null; e = e.next) {
 973             if ((e.hash == hash) && e.key.equals(key)) {
 974                 if (e.value.equals(oldValue)) {
 975                     e.value = newValue;
 976                     return true;
 977                 } else {
 978                     return false;
 979                 }
 980             }
 981         }
 982         return false;
 983     }
 984 
 985     @Override
 986     public synchronized V replace(K key, V value) {
 987         Objects.requireNonNull(value);
 988         Entry<?,?> tab[] = table;
 989         int hash = key.hashCode();
 990         int index = (hash & 0x7FFFFFFF) % tab.length;
 991         @SuppressWarnings("unchecked")
 992         Entry<K,V> e = (Entry<K,V>)tab[index];
 993         for (; e != null; e = e.next) {
 994             if ((e.hash == hash) && e.key.equals(key)) {
 995                 V oldValue = e.value;
 996                 e.value = value;
 997                 return oldValue;
 998             }
 999         }
1000         return null;
1001     }
1002 
1003     @Override
1004     public synchronized V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1005         Objects.requireNonNull(mappingFunction);
1006 
1007         Entry<?,?> tab[] = table;
1008         int hash = key.hashCode();
1009         int index = (hash & 0x7FFFFFFF) % tab.length;
1010         @SuppressWarnings("unchecked")
1011         Entry<K,V> e = (Entry<K,V>)tab[index];
1012         for (; e != null; e = e.next) {
1013             if (e.hash == hash && e.key.equals(key)) {
1014                 // Hashtable not accept null value
1015                 return e.value;
1016             }
1017         }
1018 
1019         V newValue = mappingFunction.apply(key);
1020         if (newValue != null) {
1021             addEntry(hash, key, newValue, index);
1022         }
1023 
1024         return newValue;
1025     }
1026 
1027     @Override
1028     public synchronized V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1029         Objects.requireNonNull(remappingFunction);
1030 
1031         Entry<?,?> tab[] = table;
1032         int hash = key.hashCode();
1033         int index = (hash & 0x7FFFFFFF) % tab.length;
1034         @SuppressWarnings("unchecked")
1035         Entry<K,V> e = (Entry<K,V>)tab[index];
1036         for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1037             if (e.hash == hash && e.key.equals(key)) {
1038                 V newValue = remappingFunction.apply(key, e.value);
1039                 if (newValue == null) {
1040                     if (prev != null) {
1041                         prev.next = e.next;
1042                     } else {
1043                         tab[index] = e.next;
1044                     }
1045                     modCount++;
1046                     count--;
1047                 } else {
1048                     e.value = newValue;
1049                 }
1050                 return newValue;
1051             }
1052         }
1053         return null;
1054     }
1055 
1056     @Override
1057     public synchronized V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1058         Objects.requireNonNull(remappingFunction);
1059 
1060         Entry<?,?> tab[] = table;
1061         int hash = key.hashCode();
1062         int index = (hash & 0x7FFFFFFF) % tab.length;
1063         @SuppressWarnings("unchecked")
1064         Entry<K,V> e = (Entry<K,V>)tab[index];
1065         for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1066             if (e.hash == hash && Objects.equals(e.key, key)) {
1067                 V newValue = remappingFunction.apply(key, e.value);
1068                 if (newValue == null) {
1069                     if (prev != null) {
1070                         prev.next = e.next;
1071                     } else {
1072                         tab[index] = e.next;
1073                     }
1074                     modCount++;
1075                     count--;
1076                 } else {
1077                     e.value = newValue;
1078                 }
1079                 return newValue;
1080             }
1081         }
1082 
1083         V newValue = remappingFunction.apply(key, null);
1084         if (newValue != null) {
1085             addEntry(hash, key, newValue, index);
1086         }
1087 
1088         return newValue;
1089     }
1090 
1091     @Override
1092     public synchronized V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1093         Objects.requireNonNull(remappingFunction);
1094 
1095         Entry<?,?> tab[] = table;
1096         int hash = key.hashCode();
1097         int index = (hash & 0x7FFFFFFF) % tab.length;
1098         @SuppressWarnings("unchecked")
1099         Entry<K,V> e = (Entry<K,V>)tab[index];
1100         for (Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1101             if (e.hash == hash && e.key.equals(key)) {
1102                 V newValue = remappingFunction.apply(e.value, value);
1103                 if (newValue == null) {
1104                     if (prev != null) {
1105                         prev.next = e.next;
1106                     } else {
1107                         tab[index] = e.next;
1108                     }
1109                     modCount++;
1110                     count--;
1111                 } else {
1112                     e.value = newValue;
1113                 }
1114                 return newValue;
1115             }
1116         }
1117 
1118         if (value != null) {
1119             addEntry(hash, key, value, index);
1120         }
1121 
1122         return value;
1123     }
1124 
1125     /**
1126      * Save the state of the Hashtable to a stream (i.e., serialize it).
1127      *
1128      * @serialData The <i>capacity</i> of the Hashtable (the length of the
1129      *             bucket array) is emitted (int), followed by the
1130      *             <i>size</i> of the Hashtable (the number of key-value
1131      *             mappings), followed by the key (Object) and value (Object)
1132      *             for each key-value mapping represented by the Hashtable
1133      *             The key-value mappings are emitted in no particular order.
1134      */
1135     private void writeObject(java.io.ObjectOutputStream s)
1136             throws IOException {
1137         Entry<Object, Object> entryStack = null;
1138 
1139         synchronized (this) {
1140             // Write out the threshold and loadFactor
1141             s.defaultWriteObject();
1142 
1143             // Write out the length and count of elements
1144             s.writeInt(table.length);
1145             s.writeInt(count);
1146 
1147             // Stack copies of the entries in the table
1148             for (Entry<?, ?> entry : table) {
1149 
1150                 while (entry != null) {
1151                     entryStack =
1152                         new Entry<>(0, entry.key, entry.value, entryStack);
1153                     entry = entry.next;
1154                 }
1155             }
1156         }
1157 
1158         // Write out the key/value objects from the stacked entries
1159         while (entryStack != null) {
1160             s.writeObject(entryStack.key);
1161             s.writeObject(entryStack.value);
1162             entryStack = entryStack.next;
1163         }
1164     }
1165 
1166     /**
1167      * Reconstitute the Hashtable from a stream (i.e., deserialize it).
1168      */
1169     private void readObject(java.io.ObjectInputStream s)
1170          throws IOException, ClassNotFoundException
1171     {
1172         // Read in the threshold and loadFactor
1173         s.defaultReadObject();
1174 
1175         // Validate loadFactor (ignore threshold - it will be re-computed)
1176         if (loadFactor <= 0 || Float.isNaN(loadFactor))
1177             throw new StreamCorruptedException("Illegal Load: " + loadFactor);
1178 
1179         // Read the original length of the array and number of elements
1180         int origlength = s.readInt();
1181         int elements = s.readInt();
1182 
1183         // Validate # of elements
1184         if (elements < 0)
1185             throw new StreamCorruptedException("Illegal # of Elements: " + elements);
1186 
1187         // Clamp original length to be more than elements / loadFactor
1188         // (this is the invariant enforced with auto-growth)
1189         origlength = Math.max(origlength, (int)(elements / loadFactor) + 1);
1190 
1191         // Compute new length with a bit of room 5% + 3 to grow but
1192         // no larger than the clamped original length.  Make the length
1193         // odd if it's large enough, this helps distribute the entries.
1194         // Guard against the length ending up zero, that's not valid.
1195         int length = (int)((elements + elements / 20) / loadFactor) + 3;
1196         if (length > elements && (length & 1) == 0)
1197             length--;
1198         length = Math.min(length, origlength);
1199         table = new Entry<?,?>[length];
1200         threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
1201         count = 0;
1202 
1203         // Read the number of elements and then all the key/value objects
1204         for (; elements > 0; elements--) {
1205             @SuppressWarnings("unchecked")
1206                 K key = (K)s.readObject();
1207             @SuppressWarnings("unchecked")
1208                 V value = (V)s.readObject();
1209             // sync is eliminated for performance
1210             reconstitutionPut(table, key, value);
1211         }
1212     }
1213 
1214     /**
1215      * The put method used by readObject. This is provided because put
1216      * is overridable and should not be called in readObject since the
1217      * subclass will not yet be initialized.
1218      *
1219      * <p>This differs from the regular put method in several ways. No
1220      * checking for rehashing is necessary since the number of elements
1221      * initially in the table is known. The modCount is not incremented and
1222      * there's no synchronization because we are creating a new instance.
1223      * Also, no return value is needed.
1224      */
1225     private void reconstitutionPut(Entry<?,?>[] tab, K key, V value)
1226         throws StreamCorruptedException
1227     {
1228         if (value == null) {
1229             throw new java.io.StreamCorruptedException();
1230         }
1231         // Makes sure the key is not already in the hashtable.
1232         // This should not happen in deserialized version.
1233         int hash = key.hashCode();
1234         int index = (hash & 0x7FFFFFFF) % tab.length;
1235         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
1236             if ((e.hash == hash) && e.key.equals(key)) {
1237                 throw new java.io.StreamCorruptedException();
1238             }
1239         }
1240         // Creates the new entry.
1241         @SuppressWarnings("unchecked")
1242             Entry<K,V> e = (Entry<K,V>)tab[index];
1243         tab[index] = new Entry<>(hash, key, value, e);
1244         count++;
1245     }
1246 
1247     /**
1248      * Hashtable bucket collision list entry
1249      */
1250     private static class Entry<K,V> implements Map.Entry<K,V> {
1251         final int hash;
1252         final K key;
1253         V value;
1254         Entry<K,V> next;
1255 
1256         protected Entry(int hash, K key, V value, Entry<K,V> next) {
1257             this.hash = hash;
1258             this.key =  key;
1259             this.value = value;
1260             this.next = next;
1261         }
1262 
1263         @SuppressWarnings("unchecked")
1264         protected Object clone() {
1265             return new Entry<>(hash, key, value,
1266                                   (next==null ? null : (Entry<K,V>) next.clone()));
1267         }
1268 
1269         // Map.Entry Ops
1270 
1271         public K getKey() {
1272             return key;
1273         }
1274 
1275         public V getValue() {
1276             return value;
1277         }
1278 
1279         public V setValue(V value) {
1280             if (value == null)
1281                 throw new NullPointerException();
1282 
1283             V oldValue = this.value;
1284             this.value = value;
1285             return oldValue;
1286         }
1287 
1288         public boolean equals(Object o) {
1289             if (!(o instanceof Map.Entry))
1290                 return false;
1291             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1292 
1293             return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
1294                (value==null ? e.getValue()==null : value.equals(e.getValue()));
1295         }
1296 
1297         public int hashCode() {
1298             return hash ^ Objects.hashCode(value);
1299         }
1300 
1301         public String toString() {
1302             return key.toString()+"="+value.toString();
1303         }
1304     }
1305 
1306     // Types of Enumerations/Iterations
1307     private static final int KEYS = 0;
1308     private static final int VALUES = 1;
1309     private static final int ENTRIES = 2;
1310 
1311     /**
1312      * A hashtable enumerator class.  This class implements both the
1313      * Enumeration and Iterator interfaces, but individual instances
1314      * can be created with the Iterator methods disabled.  This is necessary
1315      * to avoid unintentionally increasing the capabilities granted a user
1316      * by passing an Enumeration.
1317      */
1318     private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1319         final Entry<?,?>[] table = Hashtable.this.table;
1320         int index = table.length;
1321         Entry<?,?> entry;
1322         Entry<?,?> lastReturned;
1323         final int type;
1324 
1325         /**
1326          * Indicates whether this Enumerator is serving as an Iterator
1327          * or an Enumeration.  (true -> Iterator).
1328          */
1329         final boolean iterator;
1330 
1331         /**
1332          * The modCount value that the iterator believes that the backing
1333          * Hashtable should have.  If this expectation is violated, the iterator
1334          * has detected concurrent modification.
1335          */
1336         protected int expectedModCount = Hashtable.this.modCount;
1337 
1338         Enumerator(int type, boolean iterator) {
1339             this.type = type;
1340             this.iterator = iterator;
1341         }
1342 
1343         public boolean hasMoreElements() {
1344             Entry<?,?> e = entry;
1345             int i = index;
1346             Entry<?,?>[] t = table;
1347             /* Use locals for faster loop iteration */
1348             while (e == null && i > 0) {
1349                 e = t[--i];
1350             }
1351             entry = e;
1352             index = i;
1353             return e != null;
1354         }
1355 
1356         @SuppressWarnings("unchecked")
1357         public T nextElement() {
1358             Entry<?,?> et = entry;
1359             int i = index;
1360             Entry<?,?>[] t = table;
1361             /* Use locals for faster loop iteration */
1362             while (et == null && i > 0) {
1363                 et = t[--i];
1364             }
1365             entry = et;
1366             index = i;
1367             if (et != null) {
1368                 Entry<?,?> e = lastReturned = entry;
1369                 entry = e.next;
1370                 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1371             }
1372             throw new NoSuchElementException("Hashtable Enumerator");
1373         }
1374 
1375         // Iterator methods
1376         public boolean hasNext() {
1377             return hasMoreElements();
1378         }
1379 
1380         public T next() {
1381             if (Hashtable.this.modCount != expectedModCount)
1382                 throw new ConcurrentModificationException();
1383             return nextElement();
1384         }
1385 
1386         public void remove() {
1387             if (!iterator)
1388                 throw new UnsupportedOperationException();
1389             if (lastReturned == null)
1390                 throw new IllegalStateException("Hashtable Enumerator");
1391             if (modCount != expectedModCount)
1392                 throw new ConcurrentModificationException();
1393 
1394             synchronized(Hashtable.this) {
1395                 Entry<?,?>[] tab = Hashtable.this.table;
1396                 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1397 
1398                 @SuppressWarnings("unchecked")
1399                 Entry<K,V> e = (Entry<K,V>)tab[index];
1400                 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1401                     if (e == lastReturned) {
1402                         if (prev == null)
1403                             tab[index] = e.next;
1404                         else
1405                             prev.next = e.next;
1406                         expectedModCount++;
1407                         lastReturned = null;
1408                         Hashtable.this.modCount++;
1409                         Hashtable.this.count--;
1410                         return;
1411                     }
1412                 }
1413                 throw new ConcurrentModificationException();
1414             }
1415         }
1416     }
1417 }