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