src/share/classes/java/util/Hashtable.java

Print this page
rev 5382 : 7126277: Alternative hashing implementation


 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      * Constructs a new, empty hashtable with the specified initial
 168      * capacity and the specified load factor.
 169      *
 170      * @param      initialCapacity   the initial capacity of the hashtable.
 171      * @param      loadFactor        the load factor of the hashtable.
 172      * @exception  IllegalArgumentException  if the initial capacity is less
 173      *             than zero, or if the load factor is nonpositive.
 174      */
 175     public Hashtable(int initialCapacity, float loadFactor) {
 176         if (initialCapacity < 0)
 177             throw new IllegalArgumentException("Illegal Capacity: "+
 178                                                initialCapacity);
 179         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 180             throw new IllegalArgumentException("Illegal Load: "+loadFactor);
 181 
 182         if (initialCapacity==0)
 183             initialCapacity = 1;
 184         this.loadFactor = loadFactor;
 185         table = new Entry<?,?>[initialCapacity];
 186         threshold = (int)(initialCapacity * loadFactor);
 187     }
 188 
 189     /**
 190      * Constructs a new, empty hashtable with the specified initial capacity
 191      * and default load factor (0.75).
 192      *
 193      * @param     initialCapacity   the initial capacity of the hashtable.
 194      * @exception IllegalArgumentException if the initial capacity is less
 195      *              than zero.
 196      */
 197     public Hashtable(int initialCapacity) {
 198         this(initialCapacity, 0.75f);
 199     }
 200 
 201     /**
 202      * Constructs a new, empty hashtable with a default initial capacity (11)
 203      * and load factor (0.75).
 204      */
 205     public Hashtable() {
 206         this(11, 0.75f);


 310      *         specified value
 311      * @throws NullPointerException  if the value is <code>null</code>
 312      * @since 1.2
 313      */
 314     public boolean containsValue(Object value) {
 315         return contains(value);
 316     }
 317 
 318     /**
 319      * Tests if the specified object is a key in this hashtable.
 320      *
 321      * @param   key   possible key
 322      * @return  <code>true</code> if and only if the specified object
 323      *          is a key in this hashtable, as determined by the
 324      *          <tt>equals</tt> method; <code>false</code> otherwise.
 325      * @throws  NullPointerException  if the key is <code>null</code>
 326      * @see     #contains(Object)
 327      */
 328     public synchronized boolean containsKey(Object key) {
 329         Entry<?,?> tab[] = table;
 330         int hash = key.hashCode();
 331         int index = (hash & 0x7FFFFFFF) % tab.length;
 332         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 333             if ((e.hash == hash) && e.key.equals(key)) {
 334                 return true;
 335             }
 336         }
 337         return false;
 338     }
 339 
 340     /**
 341      * Returns the value to which the specified key is mapped,
 342      * or {@code null} if this map contains no mapping for the key.
 343      *
 344      * <p>More formally, if this map contains a mapping from a key
 345      * {@code k} to a value {@code v} such that {@code (key.equals(k))},
 346      * then this method returns {@code v}; otherwise it returns
 347      * {@code null}.  (There can be at most one such mapping.)
 348      *
 349      * @param key the key whose associated value is to be returned
 350      * @return the value to which the specified key is mapped, or
 351      *         {@code null} if this map contains no mapping for the key
 352      * @throws NullPointerException if the specified key is null
 353      * @see     #put(Object, Object)
 354      */
 355     @SuppressWarnings("unchecked")
 356     public synchronized V get(Object key) {
 357         Entry<?,?> tab[] = table;
 358         int hash = key.hashCode();
 359         int index = (hash & 0x7FFFFFFF) % tab.length;
 360         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 361             if ((e.hash == hash) && e.key.equals(key)) {
 362                 return (V)e.value;
 363             }
 364         }
 365         return null;
 366     }
 367 
 368     /**
 369      * The maximum size of array to allocate.
 370      * Some VMs reserve some header words in an array.
 371      * Attempts to allocate larger arrays may result in
 372      * OutOfMemoryError: Requested array size exceeds VM limit
 373      */
 374     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 375 
 376     /**
 377      * Increases the capacity of and internally reorganizes this
 378      * hashtable, in order to accommodate and access its entries more
 379      * efficiently.  This method is called automatically when the
 380      * number of keys in the hashtable exceeds this hashtable's capacity
 381      * and load factor.
 382      */
 383     @SuppressWarnings("unchecked")
 384     protected void rehash() {
 385         int oldCapacity = table.length;
 386         Entry<?,?>[] oldMap = table;
 387 
 388         // overflow-conscious code
 389         int newCapacity = (oldCapacity << 1) + 1;
 390         if (newCapacity - MAX_ARRAY_SIZE > 0) {
 391             if (oldCapacity == MAX_ARRAY_SIZE)
 392                 // Keep running with MAX_ARRAY_SIZE buckets
 393                 return;
 394             newCapacity = MAX_ARRAY_SIZE;
 395         }
 396         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
 397 
 398         modCount++;
 399         threshold = (int)(newCapacity * loadFactor);
 400         table = newMap;
 401 
 402         for (int i = oldCapacity ; i-- > 0 ;) {
 403             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
 404                 Entry<K,V> e = old;
 405                 old = old.next;
 406 
 407                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
 408                 e.next = (Entry<K,V>)newMap[index];
 409                 newMap[index] = e;
 410             }
 411         }
 412     }
 413 
 414     /**
 415      * Maps the specified <code>key</code> to the specified
 416      * <code>value</code> in this hashtable. Neither the key nor the
 417      * value can be <code>null</code>. <p>
 418      *
 419      * The value can be retrieved by calling the <code>get</code> method
 420      * with a key that is equal to the original key.
 421      *
 422      * @param      key     the hashtable key
 423      * @param      value   the value
 424      * @return     the previous value of the specified key in this hashtable,
 425      *             or <code>null</code> if it did not have one
 426      * @exception  NullPointerException  if the key or value is
 427      *               <code>null</code>
 428      * @see     Object#equals(Object)
 429      * @see     #get(Object)
 430      */
 431     public synchronized V put(K key, V value) {
 432         // Make sure the value is not null
 433         if (value == null) {
 434             throw new NullPointerException();
 435         }
 436 
 437         // Makes sure the key is not already in the hashtable.
 438         Entry<?,?> tab[] = table;
 439         int hash = key.hashCode();
 440         int index = (hash & 0x7FFFFFFF) % tab.length;
 441         @SuppressWarnings("unchecked")
 442         Entry<K,V> entry = (Entry<K,V>)tab[index];
 443         for(; entry != null ; entry = entry.next) {
 444             if ((entry.hash == hash) && entry.key.equals(key)) {
 445                 V old = entry.value;
 446                 entry.value = value;
 447                 return old;
 448             }
 449         }
 450 
 451         modCount++;
 452         if (count >= threshold) {
 453             // Rehash the table if the threshold is exceeded
 454             rehash();
 455 
 456             tab = table;

 457             index = (hash & 0x7FFFFFFF) % tab.length;
 458         }
 459 
 460         // Creates the new entry.
 461         @SuppressWarnings("unchecked")
 462         Entry<K,V> e = (Entry<K,V>)tab[index];
 463         tab[index] = new Entry<>(hash, key, value, e);
 464         count++;
 465         return null;
 466     }
 467 
 468     /**
 469      * Removes the key (and its corresponding value) from this
 470      * hashtable. This method does nothing if the key is not in the hashtable.
 471      *
 472      * @param   key   the key that needs to be removed
 473      * @return  the value to which the key had been mapped in this hashtable,
 474      *          or <code>null</code> if the key did not have a mapping
 475      * @throws  NullPointerException  if the key is <code>null</code>
 476      */
 477     public synchronized V remove(Object key) {
 478         Entry<?,?> tab[] = table;
 479         int hash = key.hashCode();
 480         int index = (hash & 0x7FFFFFFF) % tab.length;
 481         @SuppressWarnings("unchecked")
 482         Entry<K,V> e = (Entry<K,V>)tab[index];
 483         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
 484             if ((e.hash == hash) && e.key.equals(key)) {
 485                 modCount++;
 486                 if (prev != null) {
 487                     prev.next = e.next;
 488                 } else {
 489                     tab[index] = e.next;
 490                 }
 491                 count--;
 492                 V oldValue = e.value;
 493                 e.value = null;
 494                 return oldValue;
 495             }
 496         }
 497         return null;
 498     }
 499 


 668         if (entrySet==null)
 669             entrySet = Collections.synchronizedSet(new EntrySet(), this);
 670         return entrySet;
 671     }
 672 
 673     private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 674         public Iterator<Map.Entry<K,V>> iterator() {
 675             return getIterator(ENTRIES);
 676         }
 677 
 678         public boolean add(Map.Entry<K,V> o) {
 679             return super.add(o);
 680         }
 681 
 682         public boolean contains(Object o) {
 683             if (!(o instanceof Map.Entry))
 684                 return false;
 685             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
 686             Object key = entry.getKey();
 687             Entry<?,?>[] tab = table;
 688             int hash = key.hashCode();
 689             int index = (hash & 0x7FFFFFFF) % tab.length;
 690 
 691             for (Entry<?,?> e = tab[index]; e != null; e = e.next)
 692                 if (e.hash==hash && e.equals(entry))
 693                     return true;
 694             return false;
 695         }
 696 
 697         public boolean remove(Object o) {
 698             if (!(o instanceof Map.Entry))
 699                 return false;
 700             Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
 701             Object key = entry.getKey();
 702             Entry<?,?>[] tab = table;
 703             int hash = key.hashCode();
 704             int index = (hash & 0x7FFFFFFF) % tab.length;
 705 
 706             @SuppressWarnings("unchecked")
 707             Entry<K,V> e = (Entry<K,V>)tab[index];
 708             for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
 709                 if (e.hash==hash && e.equals(entry)) {
 710                     modCount++;
 711                     if (prev != null)
 712                         prev.next = e.next;
 713                     else
 714                         tab[index] = e.next;
 715 
 716                     count--;
 717                     e.value = null;
 718                     return true;
 719                 }
 720             }
 721             return false;
 722         }
 723 


 818      * @see Map#hashCode()
 819      * @since 1.2
 820      */
 821     public synchronized int hashCode() {
 822         /*
 823          * This code detects the recursion caused by computing the hash code
 824          * of a self-referential hash table and prevents the stack overflow
 825          * that would otherwise result.  This allows certain 1.1-era
 826          * applets with self-referential hash tables to work.  This code
 827          * abuses the loadFactor field to do double-duty as a hashCode
 828          * in progress flag, so as not to worsen the space performance.
 829          * A negative load factor indicates that hash code computation is
 830          * in progress.
 831          */
 832         int h = 0;
 833         if (count == 0 || loadFactor < 0)
 834             return h;  // Returns zero
 835 
 836         loadFactor = -loadFactor;  // Mark hashCode computation in progress
 837         Entry<?,?>[] tab = table;
 838         for (int i = 0; i < tab.length; i++)
 839             for (Entry<?,?> e = tab[i]; e != null; e = e.next)
 840                 h += e.key.hashCode() ^ e.value.hashCode();




 841         loadFactor = -loadFactor;  // Mark hashCode computation complete
 842 
 843         return h;
 844     }
 845 
 846     /**
 847      * Save the state of the Hashtable to a stream (i.e., serialize it).
 848      *
 849      * @serialData The <i>capacity</i> of the Hashtable (the length of the
 850      *             bucket array) is emitted (int), followed by the
 851      *             <i>size</i> of the Hashtable (the number of key-value
 852      *             mappings), followed by the key (Object) and value (Object)
 853      *             for each key-value mapping represented by the Hashtable
 854      *             The key-value mappings are emitted in no particular order.
 855      */
 856     private void writeObject(java.io.ObjectOutputStream s)
 857             throws IOException {
 858         Entry<Object, Object> entryStack = null;
 859 
 860         synchronized (this) {


 877             }
 878         }
 879 
 880         // Write out the key/value objects from the stacked entries
 881         while (entryStack != null) {
 882             s.writeObject(entryStack.key);
 883             s.writeObject(entryStack.value);
 884             entryStack = entryStack.next;
 885         }
 886     }
 887 
 888     /**
 889      * Reconstitute the Hashtable from a stream (i.e., deserialize it).
 890      */
 891     private void readObject(java.io.ObjectInputStream s)
 892          throws IOException, ClassNotFoundException
 893     {
 894         // Read in the length, threshold, and loadfactor
 895         s.defaultReadObject();
 896 




 897         // Read the original length of the array and number of elements
 898         int origlength = s.readInt();
 899         int elements = s.readInt();
 900 
 901         // Compute new size with a bit of room 5% to grow but
 902         // no larger than the original size.  Make the length
 903         // odd if it's large enough, this helps distribute the entries.
 904         // Guard against the length ending up zero, that's not valid.
 905         int length = (int)(elements * loadFactor) + (elements / 20) + 3;
 906         if (length > elements && (length & 1) == 0)
 907             length--;
 908         if (origlength > 0 && length > origlength)
 909             length = origlength;
 910         Entry<?,?>[] table = new Entry<?,?>[length];

 911         count = 0;
 912 
 913         // Read the number of elements and then all the key/value objects
 914         for (; elements > 0; elements--) {
 915             @SuppressWarnings("unchecked")
 916                 K key = (K)s.readObject();
 917             @SuppressWarnings("unchecked")
 918                 V value = (V)s.readObject();
 919             // synch could be eliminated for performance
 920             reconstitutionPut(table, key, value);
 921         }
 922         this.table = table;
 923     }
 924 
 925     /**
 926      * The put method used by readObject. This is provided because put
 927      * is overridable and should not be called in readObject since the
 928      * subclass will not yet be initialized.
 929      *
 930      * <p>This differs from the regular put method in several ways. No
 931      * checking for rehashing is necessary since the number of elements
 932      * initially in the table is known. The modCount is not incremented
 933      * because we are creating a new instance. Also, no return value
 934      * is needed.
 935      */
 936     private void reconstitutionPut(Entry<?,?>[] tab, K key, V value)
 937         throws StreamCorruptedException
 938     {
 939         if (value == null) {
 940             throw new java.io.StreamCorruptedException();
 941         }
 942         // Makes sure the key is not already in the hashtable.
 943         // This should not happen in deserialized version.
 944         int hash = key.hashCode();
 945         int index = (hash & 0x7FFFFFFF) % tab.length;
 946         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
 947             if ((e.hash == hash) && e.key.equals(key)) {
 948                 throw new java.io.StreamCorruptedException();
 949             }
 950         }
 951         // Creates the new entry.
 952         @SuppressWarnings("unchecked")
 953             Entry<K,V> e = (Entry<K,V>)tab[index];
 954         tab[index] = new Entry<>(hash, key, value, e);
 955         count++;
 956     }
 957 
 958     /**
 959      * Hashtable collision list.
 960      */
 961     private static class Entry<K,V> implements Map.Entry<K,V> {
 962         int hash;
 963         K key;
 964         V value;
 965         Entry<K,V> next;
 966 
 967         protected Entry(int hash, K key, V value, Entry<K,V> next) {
 968             this.hash = hash;
 969             this.key = key;
 970             this.value = value;
 971             this.next = next;
 972         }
 973 
 974         @SuppressWarnings("unchecked")
 975         protected Object clone() {
 976             return new Entry<>(hash, key, value,
 977                                   (next==null ? null : (Entry<K,V>) next.clone()));
 978         }
 979 
 980         // Map.Entry Ops
 981 
 982         public K getKey() {




 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 h ^ ((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);


 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 


 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 


 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) {


 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() {