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