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<?,?>[] 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     private static class Holder {
 167             // Unsafe mechanics
 168         /**
 169          * 
 170          */
 171         static final sun.misc.Unsafe UNSAFE;
 172         
 173         /**
 174          * Offset of "final" hashSeed field we must set in
 175          * readObject() method.
 176          */
 177         static final long HASHSEED_OFFSET;
 178                 
 179         static {           
 180             try {
 181                 UNSAFE = sun.misc.Unsafe.getUnsafe();
 182                 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
 183                     Hashtable.class.getDeclaredField("hashSeed"));                        
 184             } catch (NoSuchFieldException | SecurityException e) {
 185                 throw new InternalError("Failed to record hashSeed offset", e);
 186             }
 187         }
 188     }
 189     
 190     /**
 191      * A randomizing value associated with this instance that is applied to  
 192      * hash code of keys to make hash collisions harder to find.
 193      */
 194     transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
 195 
 196     private int hash(Object k) {
 197         int h = hashSeed;
 198 
 199         if (k instanceof String) {
 200             return ((String)k).hash32();
 201         } else {
 202             h ^= k.hashCode();
 203 
 204             // This function ensures that hashCodes that differ only by
 205             // constant multiples at each bit position have a bounded
 206             // number of collisions (approximately 8 at default load factor).
 207             h ^= (h >>> 20) ^ (h >>> 12);
 208             return h ^ (h >>> 7) ^ (h >>> 4);
 209         }
 210     }
 211 
 212     /**
 213      * Constructs a new, empty hashtable with the specified initial
 214      * capacity and the specified load factor.
 215      *
 216      * @param      initialCapacity   the initial capacity of the hashtable.
 217      * @param      loadFactor        the load factor of the hashtable.
 218      * @exception  IllegalArgumentException  if the initial capacity is less
 219      *             than zero, or if the load factor is nonpositive.
 220      */
 221     public Hashtable(int initialCapacity, float loadFactor) {
 222         if (initialCapacity < 0)
 223             throw new IllegalArgumentException("Illegal Capacity: "+
 224                                                initialCapacity);
 225         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 226             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
 227 
 228         if (initialCapacity==0)
 229             initialCapacity = 1;
 230         this.loadFactor = loadFactor;
 231         table = new Entry<?,?>[initialCapacity];
 232         threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
 233     }
 234 
 235     /**
 236      * Constructs a new, empty hashtable with the specified initial capacity
 237      * and default load factor (0.75).
 238      *
 239      * @param     initialCapacity   the initial capacity of the hashtable.
 240      * @exception IllegalArgumentException if the initial capacity is less
 241      *              than zero.
 242      */
 243     public Hashtable(int initialCapacity) {
 244         this(initialCapacity, 0.75f);
 245     }
 246 
 247     /**
 248      * Constructs a new, empty hashtable with a default initial capacity (11)
 249      * and load factor (0.75).
 250      */
 251     public Hashtable() {
 252         this(11, 0.75f);
 253     }
 254 
 255     /**
 256      * Constructs a new hashtable with the same mappings as the given
 257      * Map.  The hashtable is created with an initial capacity sufficient to
 258      * hold the mappings in the given Map and a default load factor (0.75).
 259      *
 260      * @param t the map whose mappings are to be placed in this map.
 261      * @throws NullPointerException if the specified map is null.
 262      * @since   1.2
 263      */
 264     public Hashtable(Map<? extends K, ? extends V> t) {
 265         this(Math.max(2*t.size(), 11), 0.75f);
 266         putAll(t);
 267     }
 268 
 269     /**
 270      * Returns the number of keys in this hashtable.
 271      *
 272      * @return  the number of keys in this hashtable.
 273      */
 274     public synchronized int size() {
 275         return count;
 276     }
 277 
 278     /**
 279      * Tests if this hashtable maps no keys to values.
 280      *
 281      * @return  <code>true</code> if this hashtable maps no keys to values;
 282      *          <code>false</code> otherwise.
 283      */
 284     public synchronized boolean isEmpty() {
 285         return count == 0;
 286     }
 287 
 288     /**
 289      * Returns an enumeration of the keys in this hashtable.
 290      *
 291      * @return  an enumeration of the keys in this hashtable.
 292      * @see     Enumeration
 293      * @see     #elements()
 294      * @see     #keySet()
 295      * @see     Map
 296      */
 297     public synchronized Enumeration<K> keys() {
 298         return this.<K>getEnumeration(KEYS);
 299     }
 300 
 301     /**
 302      * Returns an enumeration of the values in this hashtable.
 303      * Use the Enumeration methods on the returned object to fetch the elements
 304      * sequentially.
 305      *
 306      * @return  an enumeration of the values in this hashtable.
 307      * @see     java.util.Enumeration
 308      * @see     #keys()
 309      * @see     #values()
 310      * @see     Map
 311      */
 312     public synchronized Enumeration<V> elements() {
 313         return this.<V>getEnumeration(VALUES);
 314     }
 315 
 316     /**
 317      * Tests if some key maps into the specified value in this hashtable.
 318      * This operation is more expensive than the {@link #containsKey
 319      * containsKey} method.
 320      *
 321      * <p>Note that this method is identical in functionality to
 322      * {@link #containsValue containsValue}, (which is part of the
 323      * {@link Map} interface in the collections framework).
 324      *
 325      * @param      value   a value to search for
 326      * @return     <code>true</code> if and only if some key maps to the
 327      *             <code>value</code> argument in this hashtable as
 328      *             determined by the <tt>equals</tt> method;
 329      *             <code>false</code> otherwise.
 330      * @exception  NullPointerException  if the value is <code>null</code>
 331      */
 332     public synchronized boolean contains(Object value) {
 333         if (value == null) {
 334             throw new NullPointerException();
 335         }
 336 
 337         Entry<?,?> tab[] = table;
 338         for (int i = tab.length ; i-- > 0 ;) {
 339             for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
 340                 if (e.value.equals(value)) {
 341                     return true;
 342                 }
 343             }
 344         }
 345         return false;
 346     }
 347 
 348     /**
 349      * Returns true if this hashtable maps one or more keys to this value.
 350      *
 351      * <p>Note that this method is identical in functionality to {@link
 352      * #contains contains} (which predates the {@link Map} interface).
 353      *
 354      * @param value value whose presence in this hashtable is to be tested
 355      * @return <tt>true</tt> if this map maps one or more keys to the
 356      *         specified value
 357      * @throws NullPointerException  if the value is <code>null</code>
 358      * @since 1.2
 359      */
 360     public boolean containsValue(Object value) {
 361         return contains(value);
 362     }
 363 
 364     /**
 365      * Tests if the specified object is a key in this hashtable.
 366      *
 367      * @param   key   possible key
 368      * @return  <code>true</code> if and only if the specified object
 369      *          is a key in this hashtable, as determined by the
 370      *          <tt>equals</tt> method; <code>false</code> otherwise.
 371      * @throws  NullPointerException  if the key is <code>null</code>
 372      * @see     #contains(Object)
 373      */
 374     public synchronized boolean containsKey(Object key) {
 375         Entry<?,?> tab[] = table;
 376         int hash = hash(key);
 377         int index = (hash & 0x7FFFFFFF) % tab.length;
 378         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 379             if ((e.hash == hash) && e.key.equals(key)) {
 380                 return true;
 381             }
 382         }
 383         return false;
 384     }
 385 
 386     /**
 387      * Returns the value to which the specified key is mapped,
 388      * or {@code null} if this map contains no mapping for the key.
 389      *
 390      * <p>More formally, if this map contains a mapping from a key
 391      * {@code k} to a value {@code v} such that {@code (key.equals(k))},
 392      * then this method returns {@code v}; otherwise it returns
 393      * {@code null}.  (There can be at most one such mapping.)
 394      *
 395      * @param key the key whose associated value is to be returned
 396      * @return the value to which the specified key is mapped, or
 397      *         {@code null} if this map contains no mapping for the key
 398      * @throws NullPointerException if the specified key is null
 399      * @see     #put(Object, Object)
 400      */
 401     @SuppressWarnings("unchecked")
 402     public synchronized V get(Object key) {
 403         Entry<?,?> tab[] = table;
 404         int hash = hash(key);
 405         int index = (hash & 0x7FFFFFFF) % tab.length;
 406         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 407             if ((e.hash == hash) && e.key.equals(key)) {
 408                 return (V)e.value;
 409             }
 410         }
 411         return null;
 412     }
 413 
 414     /**
 415      * The maximum size of array to allocate.
 416      * Some VMs reserve some header words in an array.
 417      * Attempts to allocate larger arrays may result in
 418      * OutOfMemoryError: Requested array size exceeds VM limit
 419      */
 420     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 421 
 422     /**
 423      * Increases the capacity of and internally reorganizes this
 424      * hashtable, in order to accommodate and access its entries more
 425      * efficiently.  This method is called automatically when the
 426      * number of keys in the hashtable exceeds this hashtable's capacity
 427      * and load factor.
 428      */
 429     @SuppressWarnings("unchecked")
 430     protected void rehash() {
 431         int oldCapacity = table.length;
 432         Entry<?,?>[] oldMap = table;
 433 
 434         // overflow-conscious code
 435         int newCapacity = (oldCapacity << 1) + 1;
 436         if (newCapacity - MAX_ARRAY_SIZE > 0) {
 437             if (oldCapacity == MAX_ARRAY_SIZE)
 438                 // Keep running with MAX_ARRAY_SIZE buckets
 439                 return;
 440             newCapacity = MAX_ARRAY_SIZE;
 441         }
 442         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
 443 
 444         modCount++;
 445         threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
 446         table = newMap;
 447 
 448         for (int i = oldCapacity ; i-- > 0 ;) {
 449             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
 450                 Entry<K,V> e = old;
 451                 old = old.next;
 452 
 453                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
 454                 e.next = (Entry<K,V>)newMap[index];
 455                 newMap[index] = e;
 456             }
 457         }
 458     }
 459 
 460     /**
 461      * Maps the specified <code>key</code> to the specified
 462      * <code>value</code> in this hashtable. Neither the key nor the
 463      * value can be <code>null</code>. <p>
 464      *
 465      * The value can be retrieved by calling the <code>get</code> method
 466      * with a key that is equal to the original key.
 467      *
 468      * @param      key     the hashtable key
 469      * @param      value   the value
 470      * @return     the previous value of the specified key in this hashtable,
 471      *             or <code>null</code> if it did not have one
 472      * @exception  NullPointerException  if the key or value is
 473      *               <code>null</code>
 474      * @see     Object#equals(Object)
 475      * @see     #get(Object)
 476      */
 477     public synchronized V put(K key, V value) {
 478         // Make sure the value is not null
 479         if (value == null) {
 480             throw new NullPointerException();
 481         }
 482 
 483         // Makes sure the key is not already in the hashtable.
 484         Entry<?,?> tab[] = table;
 485         int hash = hash(key);
 486         int index = (hash & 0x7FFFFFFF) % tab.length;
 487         @SuppressWarnings("unchecked")
 488         Entry<K,V> entry = (Entry<K,V>)tab[index];
 489         for(; entry != null ; entry = entry.next) {
 490             if ((entry.hash == hash) && entry.key.equals(key)) {
 491                 V old = entry.value;
 492                 entry.value = value;
 493                 return old;
 494             }
 495         }
 496 
 497         modCount++;
 498         if (count >= threshold) {
 499             // Rehash the table if the threshold is exceeded
 500             rehash();
 501 
 502             tab = table;
 503             hash = hash(key);
 504             index = (hash & 0x7FFFFFFF) % tab.length;
 505         }
 506 
 507         // Creates the new entry.
 508         @SuppressWarnings("unchecked")
 509         Entry<K,V> e = (Entry<K,V>)tab[index];
 510         tab[index] = new Entry<>(hash, key, value, e);
 511         count++;
 512         return null;
 513     }
 514 
 515     /**
 516      * Removes the key (and its corresponding value) from this
 517      * hashtable. This method does nothing if the key is not in the hashtable.
 518      *
 519      * @param   key   the key that needs to be removed
 520      * @return  the value to which the key had been mapped in this hashtable,
 521      *          or <code>null</code> if the key did not have a mapping
 522      * @throws  NullPointerException  if the key is <code>null</code>
 523      */
 524     public synchronized V remove(Object key) {
 525         Entry<?,?> tab[] = table;
 526         int hash = hash(key);
 527         int index = (hash & 0x7FFFFFFF) % tab.length;
 528         @SuppressWarnings("unchecked")
 529         Entry<K,V> e = (Entry<K,V>)tab[index];
 530         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
 531             if ((e.hash == hash) && e.key.equals(key)) {
 532                 modCount++;
 533                 if (prev != null) {
 534                     prev.next = e.next;
 535                 } else {
 536                     tab[index] = e.next;
 537                 }
 538                 count--;
 539                 V oldValue = e.value;
 540                 e.value = null;
 541                 return oldValue;
 542             }
 543         }
 544         return null;
 545     }
 546 
 547     /**
 548      * Copies all of the mappings from the specified map to this hashtable.
 549      * These mappings will replace any mappings that this hashtable had for any
 550      * of the keys currently in the specified map.
 551      *
 552      * @param t mappings to be stored in this map
 553      * @throws NullPointerException if the specified map is null
 554      * @since 1.2
 555      */
 556     public synchronized void putAll(Map<? extends K, ? extends V> t) {
 557         for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
 558             put(e.getKey(), e.getValue());
 559     }
 560 
 561     /**
 562      * Clears this hashtable so that it contains no keys.
 563      */
 564     public synchronized void clear() {
 565         Entry<?,?> tab[] = table;
 566         modCount++;
 567         for (int index = tab.length; --index >= 0; )
 568             tab[index] = null;
 569         count = 0;
 570     }
 571 
 572     /**
 573      * Creates a shallow copy of this hashtable. All the structure of the
 574      * hashtable itself is copied, but the keys and values are not cloned.
 575      * This is a relatively expensive operation.
 576      *
 577      * @return  a clone of the hashtable
 578      */
 579     public synchronized Object clone() {
 580         try {
 581             Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
 582             t.table = new Entry<?,?>[table.length];
 583             for (int i = table.length ; i-- > 0 ; ) {
 584                 t.table[i] = (table[i] != null)
 585                     ? (Entry<?,?>) table[i].clone() : null;
 586             }
 587             t.keySet = null;
 588             t.entrySet = null;
 589             t.values = null;
 590             t.modCount = 0;
 591             return t;
 592         } catch (CloneNotSupportedException e) {
 593             // this shouldn't happen, since we are Cloneable
 594             throw new InternalError(e);
 595         }
 596     }
 597 
 598     /**
 599      * Returns a string representation of this <tt>Hashtable</tt> object
 600      * in the form of a set of entries, enclosed in braces and separated
 601      * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each
 602      * entry is rendered as the key, an equals sign <tt>=</tt>, and the
 603      * associated element, where the <tt>toString</tt> method is used to
 604      * convert the key and element to strings.
 605      *
 606      * @return  a string representation of this hashtable
 607      */
 608     public synchronized String toString() {
 609         int max = size() - 1;
 610         if (max == -1)
 611             return "{}";
 612 
 613         StringBuilder sb = new StringBuilder();
 614         Iterator<Map.Entry<K,V>> it = entrySet().iterator();
 615 
 616         sb.append('{');
 617         for (int i = 0; ; i++) {
 618             Map.Entry<K,V> e = it.next();
 619             K key = e.getKey();
 620             V value = e.getValue();
 621             sb.append(key   == this ? "(this Map)" : key.toString());
 622             sb.append('=');
 623             sb.append(value == this ? "(this Map)" : value.toString());
 624 
 625             if (i == max)
 626                 return sb.append('}').toString();
 627             sb.append(", ");
 628         }
 629     }
 630 
 631 
 632     private <T> Enumeration<T> getEnumeration(int type) {
 633         if (count == 0) {
 634             return Collections.emptyEnumeration();
 635         } else {
 636             return new Enumerator<>(type, false);
 637         }
 638     }
 639 
 640     private <T> Iterator<T> getIterator(int type) {
 641         if (count == 0) {
 642             return Collections.emptyIterator();
 643         } else {
 644             return new Enumerator<>(type, true);
 645         }
 646     }
 647 
 648     // Views
 649 
 650     /**
 651      * Each of these fields are initialized to contain an instance of the
 652      * appropriate view the first time this view is requested.  The views are
 653      * stateless, so there's no reason to create more than one of each.
 654      */
 655     private transient volatile Set<K> keySet = null;
 656     private transient volatile Set<Map.Entry<K,V>> entrySet = null;
 657     private transient volatile Collection<V> values = null;
 658 
 659     /**
 660      * Returns a {@link Set} view of the keys contained in this map.
 661      * The set is backed by the map, so changes to the map are
 662      * reflected in the set, and vice-versa.  If the map is modified
 663      * while an iteration over the set is in progress (except through
 664      * the iterator's own <tt>remove</tt> operation), the results of
 665      * the iteration are undefined.  The set supports element removal,
 666      * which removes the corresponding mapping from the map, via the
 667      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 668      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 669      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
 670      * operations.
 671      *
 672      * @since 1.2
 673      */
 674     public Set<K> keySet() {
 675         if (keySet == null)
 676             keySet = Collections.synchronizedSet(new KeySet(), this);
 677         return keySet;
 678     }
 679 
 680     private class KeySet extends AbstractSet<K> {
 681         public Iterator<K> iterator() {
 682             return getIterator(KEYS);
 683         }
 684         public int size() {
 685             return count;
 686         }
 687         public boolean contains(Object o) {
 688             return containsKey(o);
 689         }
 690         public boolean remove(Object o) {
 691             return Hashtable.this.remove(o) != null;
 692         }
 693         public void clear() {
 694             Hashtable.this.clear();
 695         }
 696     }
 697 
 698     /**
 699      * Returns a {@link Set} view of the mappings contained in this map.
 700      * The set is backed by the map, so changes to the map are
 701      * reflected in the set, and vice-versa.  If the map is modified
 702      * while an iteration over the set is in progress (except through
 703      * the iterator's own <tt>remove</tt> operation, or through the
 704      * <tt>setValue</tt> operation on a map entry returned by the
 705      * iterator) the results of the iteration are undefined.  The set
 706      * supports element removal, which removes the corresponding
 707      * mapping from the map, via the <tt>Iterator.remove</tt>,
 708      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
 709      * <tt>clear</tt> operations.  It does not support the
 710      * <tt>add</tt> or <tt>addAll</tt> operations.
 711      *
 712      * @since 1.2
 713      */
 714     public Set<Map.Entry<K,V>> entrySet() {
 715         if (entrySet==null)
 716             entrySet = Collections.synchronizedSet(new EntrySet(), this);
 717         return entrySet;
 718     }
 719 
 720     private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 721         public Iterator<Map.Entry<K,V>> iterator() {
 722             return getIterator(ENTRIES);
 723         }
 724 
 725         public boolean add(Map.Entry<K,V> o) {
 726             return super.add(o);
 727         }
 728 
 729         public boolean contains(Object o) {
 730             if (!(o instanceof Map.Entry))
 731                 return false;
 732             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
 733             Object key = entry.getKey();
 734             Entry<?,?>[] tab = table;
 735             int hash = hash(key);
 736             int index = (hash & 0x7FFFFFFF) % tab.length;
 737 
 738             for (Entry<?,?> e = tab[index]; e != null; e = e.next)
 739                 if (e.hash==hash && e.equals(entry))
 740                     return true;
 741             return false;
 742         }
 743 
 744         public boolean remove(Object o) {
 745             if (!(o instanceof Map.Entry))
 746                 return false;
 747             Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
 748             Object key = entry.getKey();
 749             Entry<?,?>[] tab = table;
 750             int hash = hash(key);
 751             int index = (hash & 0x7FFFFFFF) % tab.length;
 752 
 753             @SuppressWarnings("unchecked")
 754             Entry<K,V> e = (Entry<K,V>)tab[index];
 755             for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
 756                 if (e.hash==hash && e.equals(entry)) {
 757                     modCount++;
 758                     if (prev != null)
 759                         prev.next = e.next;
 760                     else
 761                         tab[index] = e.next;
 762 
 763                     count--;
 764                     e.value = null;
 765                     return true;
 766                 }
 767             }
 768             return false;
 769         }
 770 
 771         public int size() {
 772             return count;
 773         }
 774 
 775         public void clear() {
 776             Hashtable.this.clear();
 777         }
 778     }
 779 
 780     /**
 781      * Returns a {@link Collection} view of the values contained in this map.
 782      * The collection is backed by the map, so changes to the map are
 783      * reflected in the collection, and vice-versa.  If the map is
 784      * modified while an iteration over the collection is in progress
 785      * (except through the iterator's own <tt>remove</tt> operation),
 786      * the results of the iteration are undefined.  The collection
 787      * supports element removal, which removes the corresponding
 788      * mapping from the map, via the <tt>Iterator.remove</tt>,
 789      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 790      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
 791      * support the <tt>add</tt> or <tt>addAll</tt> operations.
 792      *
 793      * @since 1.2
 794      */
 795     public Collection<V> values() {
 796         if (values==null)
 797             values = Collections.synchronizedCollection(new ValueCollection(),
 798                                                         this);
 799         return values;
 800     }
 801 
 802     private class ValueCollection extends AbstractCollection<V> {
 803         public Iterator<V> iterator() {
 804             return getIterator(VALUES);
 805         }
 806         public int size() {
 807             return count;
 808         }
 809         public boolean contains(Object o) {
 810             return containsValue(o);
 811         }
 812         public void clear() {
 813             Hashtable.this.clear();
 814         }
 815     }
 816 
 817     // Comparison and hashing
 818 
 819     /**
 820      * Compares the specified Object with this Map for equality,
 821      * as per the definition in the Map interface.
 822      *
 823      * @param  o object to be compared for equality with this hashtable
 824      * @return true if the specified Object is equal to this Map
 825      * @see Map#equals(Object)
 826      * @since 1.2
 827      */
 828     public synchronized boolean equals(Object o) {
 829         if (o == this)
 830             return true;
 831 
 832         if (!(o instanceof Map))
 833             return false;
 834         Map<?,?> t = (Map<?,?>) o;
 835         if (t.size() != size())
 836             return false;
 837 
 838         try {
 839             Iterator<Map.Entry<K,V>> i = entrySet().iterator();
 840             while (i.hasNext()) {
 841                 Map.Entry<K,V> e = i.next();
 842                 K key = e.getKey();
 843                 V value = e.getValue();
 844                 if (value == null) {
 845                     if (!(t.get(key)==null && t.containsKey(key)))
 846                         return false;
 847                 } else {
 848                     if (!value.equals(t.get(key)))
 849                         return false;
 850                 }
 851             }
 852         } catch (ClassCastException unused)   {
 853             return false;
 854         } catch (NullPointerException unused) {
 855             return false;
 856         }
 857 
 858         return true;
 859     }
 860 
 861     /**
 862      * Returns the hash code value for this Map as per the definition in the
 863      * Map interface.
 864      *
 865      * @see Map#hashCode()
 866      * @since 1.2
 867      */
 868     public synchronized int hashCode() {
 869         /*
 870          * This code detects the recursion caused by computing the hash code
 871          * of a self-referential hash table and prevents the stack overflow
 872          * that would otherwise result.  This allows certain 1.1-era
 873          * applets with self-referential hash tables to work.  This code
 874          * abuses the loadFactor field to do double-duty as a hashCode
 875          * in progress flag, so as not to worsen the space performance.
 876          * A negative load factor indicates that hash code computation is
 877          * in progress.
 878          */
 879         int h = 0;
 880         if (count == 0 || loadFactor < 0)
 881             return h;  // Returns zero
 882 
 883         loadFactor = -loadFactor;  // Mark hashCode computation in progress
 884         Entry<?,?>[] tab = table;
 885         for (Entry<?,?> entry : tab) {
 886             while (entry != null) {
 887                 h += entry.hashCode();
 888                 entry = entry.next;
 889             }
 890         }
 891 
 892         loadFactor = -loadFactor;  // Mark hashCode computation complete
 893 
 894         return h;
 895     }
 896 
 897     /**
 898      * Save the state of the Hashtable to a stream (i.e., serialize it).
 899      *
 900      * @serialData The <i>capacity</i> of the Hashtable (the length of the
 901      *             bucket array) is emitted (int), followed by the
 902      *             <i>size</i> of the Hashtable (the number of key-value
 903      *             mappings), followed by the key (Object) and value (Object)
 904      *             for each key-value mapping represented by the Hashtable
 905      *             The key-value mappings are emitted in no particular order.
 906      */
 907     private void writeObject(java.io.ObjectOutputStream s)
 908             throws IOException {
 909         Entry<Object, Object> entryStack = null;
 910 
 911         synchronized (this) {
 912             // Write out the length, threshold, loadfactor
 913             s.defaultWriteObject();
 914 
 915             // Write out length, count of elements
 916             s.writeInt(table.length);
 917             s.writeInt(count);
 918 
 919             // Stack copies of the entries in the table
 920             for (int index = 0; index < table.length; index++) {
 921                 Entry<?,?> entry = table[index];
 922 
 923                 while (entry != null) {
 924                     entryStack =
 925                         new Entry<>(0, entry.key, entry.value, entryStack);
 926                     entry = entry.next;
 927                 }
 928             }
 929         }
 930 
 931         // Write out the key/value objects from the stacked entries
 932         while (entryStack != null) {
 933             s.writeObject(entryStack.key);
 934             s.writeObject(entryStack.value);
 935             entryStack = entryStack.next;
 936         }
 937     }
 938 
 939     /**
 940      * Reconstitute the Hashtable from a stream (i.e., deserialize it).
 941      */
 942     private void readObject(java.io.ObjectInputStream s)
 943          throws IOException, ClassNotFoundException
 944     {
 945         // Read in the length, threshold, and loadfactor
 946         s.defaultReadObject();
 947         
 948         // set hashMask
 949         Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET, 
 950                 sun.misc.Hashing.randomHashSeed(this));
 951 
 952         // Read the original length of the array and number of elements
 953         int origlength = s.readInt();
 954         int elements = s.readInt();
 955 
 956         // Compute new size with a bit of room 5% to grow but
 957         // no larger than the original size.  Make the length
 958         // odd if it's large enough, this helps distribute the entries.
 959         // Guard against the length ending up zero, that's not valid.
 960         int length = (int)(elements * loadFactor) + (elements / 20) + 3;
 961         if (length > elements && (length & 1) == 0)
 962             length--;
 963         if (origlength > 0 && length > origlength)
 964             length = origlength;
 965         table = new Entry<?,?>[length];
 966         threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
 967         count = 0;
 968 
 969         // Read the number of elements and then all the key/value objects
 970         for (; elements > 0; elements--) {
 971             @SuppressWarnings("unchecked")
 972                 K key = (K)s.readObject();
 973             @SuppressWarnings("unchecked")
 974                 V value = (V)s.readObject();
 975             // synch could be eliminated for performance
 976             reconstitutionPut(table, key, value);
 977         }
 978     }
 979 
 980     /**
 981      * The put method used by readObject. This is provided because put
 982      * is overridable and should not be called in readObject since the
 983      * subclass will not yet be initialized.
 984      *
 985      * <p>This differs from the regular put method in several ways. No
 986      * checking for rehashing is necessary since the number of elements
 987      * initially in the table is known. The modCount is not incremented
 988      * because we are creating a new instance. Also, no return value
 989      * is needed.
 990      */
 991     private void reconstitutionPut(Entry<?,?>[] tab, K key, V value)
 992         throws StreamCorruptedException
 993     {
 994         if (value == null) {
 995             throw new java.io.StreamCorruptedException();
 996         }
 997         // Makes sure the key is not already in the hashtable.
 998         // This should not happen in deserialized version.
 999         int hash = hash(key);
1000         int index = (hash & 0x7FFFFFFF) % tab.length;
1001         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
1002             if ((e.hash == hash) && e.key.equals(key)) {
1003                 throw new java.io.StreamCorruptedException();
1004             }
1005         }
1006         // Creates the new entry.
1007         @SuppressWarnings("unchecked")
1008             Entry<K,V> e = (Entry<K,V>)tab[index];
1009         tab[index] = new Entry<>(hash, key, value, e);
1010         count++;
1011     }
1012 
1013     /**
1014      * Hashtable bucket collision list entry
1015      */
1016     private static class Entry<K,V> implements Map.Entry<K,V> {
1017         final int hash;
1018         K key;
1019         V value;
1020         Entry<K,V> next;
1021 
1022         protected Entry(int hash, K key, V value, Entry<K,V> next) {
1023             this.hash = hash;
1024             this.key =  key;
1025             this.value = value;
1026             this.next = next;
1027         }
1028 
1029         @SuppressWarnings("unchecked")
1030         protected Object clone() {
1031             return new Entry<>(hash, key, value,
1032                                   (next==null ? null : (Entry<K,V>) next.clone()));
1033         }
1034 
1035         // Map.Entry Ops
1036 
1037         public K getKey() {
1038             return key;
1039         }
1040 
1041         public V getValue() {
1042             return value;
1043         }
1044 
1045         public V setValue(V value) {
1046             if (value == null)
1047                 throw new NullPointerException();
1048 
1049             V oldValue = this.value;
1050             this.value = value;
1051             return oldValue;
1052         }
1053 
1054         public boolean equals(Object o) {
1055             if (!(o instanceof Map.Entry))
1056                 return false;
1057             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1058 
1059             return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
1060                (value==null ? e.getValue()==null : value.equals(e.getValue()));
1061         }
1062 
1063         public int hashCode() {
1064             return hash ^ (value==null ? 0 : value.hashCode());
1065         }
1066 
1067         public String toString() {
1068             return key.toString()+"="+value.toString();
1069         }
1070     }
1071 
1072     // Types of Enumerations/Iterations
1073     private static final int KEYS = 0;
1074     private static final int VALUES = 1;
1075     private static final int ENTRIES = 2;
1076 
1077     /**
1078      * A hashtable enumerator class.  This class implements both the
1079      * Enumeration and Iterator interfaces, but individual instances
1080      * can be created with the Iterator methods disabled.  This is necessary
1081      * to avoid unintentionally increasing the capabilities granted a user
1082      * by passing an Enumeration.
1083      */
1084     private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1085         Entry<?,?>[] table = Hashtable.this.table;
1086         int index = table.length;
1087         Entry<?,?> entry = null;
1088         Entry<?,?> lastReturned = null;
1089         int type;
1090 
1091         /**
1092          * Indicates whether this Enumerator is serving as an Iterator
1093          * or an Enumeration.  (true -> Iterator).
1094          */
1095         boolean iterator;
1096 
1097         /**
1098          * The modCount value that the iterator believes that the backing
1099          * Hashtable should have.  If this expectation is violated, the iterator
1100          * has detected concurrent modification.
1101          */
1102         protected int expectedModCount = modCount;
1103 
1104         Enumerator(int type, boolean iterator) {
1105             this.type = type;
1106             this.iterator = iterator;
1107         }
1108 
1109         public boolean hasMoreElements() {
1110             Entry<?,?> e = entry;
1111             int i = index;
1112             Entry<?,?>[] t = table;
1113             /* Use locals for faster loop iteration */
1114             while (e == null && i > 0) {
1115                 e = t[--i];
1116             }
1117             entry = e;
1118             index = i;
1119             return e != null;
1120         }
1121 
1122         @SuppressWarnings("unchecked")
1123         public T nextElement() {
1124             Entry<?,?> et = entry;
1125             int i = index;
1126             Entry<?,?>[] t = table;
1127             /* Use locals for faster loop iteration */
1128             while (et == null && i > 0) {
1129                 et = t[--i];
1130             }
1131             entry = et;
1132             index = i;
1133             if (et != null) {
1134                 Entry<?,?> e = lastReturned = entry;
1135                 entry = e.next;
1136                 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1137             }
1138             throw new NoSuchElementException("Hashtable Enumerator");
1139         }
1140 
1141         // Iterator methods
1142         public boolean hasNext() {
1143             return hasMoreElements();
1144         }
1145 
1146         public T next() {
1147             if (modCount != expectedModCount)
1148                 throw new ConcurrentModificationException();
1149             return nextElement();
1150         }
1151 
1152         public void remove() {
1153             if (!iterator)
1154                 throw new UnsupportedOperationException();
1155             if (lastReturned == null)
1156                 throw new IllegalStateException("Hashtable Enumerator");
1157             if (modCount != expectedModCount)
1158                 throw new ConcurrentModificationException();
1159 
1160             synchronized(Hashtable.this) {
1161                 Entry<?,?>[] tab = Hashtable.this.table;
1162                 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1163 
1164                 @SuppressWarnings("unchecked")
1165                 Entry<K,V> e = (Entry<K,V>)tab[index];
1166                 for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
1167                     if (e == lastReturned) {
1168                         modCount++;
1169                         expectedModCount++;
1170                         if (prev == null)
1171                             tab[index] = e.next;
1172                         else
1173                             prev.next = e.next;
1174                         count--;
1175                         lastReturned = null;
1176                         return;
1177                     }
1178                 }
1179                 throw new ConcurrentModificationException();
1180             }
1181         }
1182     }
1183 }