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