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