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