1 /*
   2  * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 import java.io.*;
  28 
  29 /**
  30  * Hash table based implementation of the <tt>Map</tt> interface.  This
  31  * implementation provides all of the optional map operations, and permits
  32  * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
  33  * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
  34  * unsynchronized and permits nulls.)  This class makes no guarantees as to
  35  * the order of the map; in particular, it does not guarantee that the order
  36  * will remain constant over time.
  37  *
  38  * <p>This implementation provides constant-time performance for the basic
  39  * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
  40  * disperses the elements properly among the buckets.  Iteration over
  41  * collection views requires time proportional to the "capacity" of the
  42  * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
  43  * of key-value mappings).  Thus, it's very important not to set the initial
  44  * capacity too high (or the load factor too low) if iteration performance is
  45  * important.
  46  *
  47  * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
  48  * performance: <i>initial capacity</i> and <i>load factor</i>.  The
  49  * <i>capacity</i> is the number of buckets in the hash table, and the initial
  50  * capacity is simply the capacity at the time the hash table is created.  The
  51  * <i>load factor</i> is a measure of how full the hash table is allowed to
  52  * get before its capacity is automatically increased.  When the number of
  53  * entries in the hash table exceeds the product of the load factor and the
  54  * current capacity, the hash table is <i>rehashed</i> (that is, internal data
  55  * structures are rebuilt) so that the hash table has approximately twice the
  56  * number of buckets.
  57  *
  58  * <p>As a general rule, the default load factor (.75) offers a good tradeoff
  59  * between time and space costs.  Higher values decrease the space overhead
  60  * but increase the lookup cost (reflected in most of the operations of the
  61  * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The
  62  * expected number of entries in the map and its load factor should be taken
  63  * into account when setting its initial capacity, so as to minimize the
  64  * number of rehash operations.  If the initial capacity is greater
  65  * than the maximum number of entries divided by the load factor, no
  66  * rehash operations will ever occur.
  67  *
  68  * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
  69  * creating it with a sufficiently large capacity will allow the mappings to
  70  * be stored more efficiently than letting it perform automatic rehashing as
  71  * needed to grow the table.
  72  *
  73  * <p><strong>Note that this implementation is not synchronized.</strong>
  74  * If multiple threads access a hash map concurrently, and at least one of
  75  * the threads modifies the map structurally, it <i>must</i> be
  76  * synchronized externally.  (A structural modification is any operation
  77  * that adds or deletes one or more mappings; merely changing the value
  78  * associated with a key that an instance already contains is not a
  79  * structural modification.)  This is typically accomplished by
  80  * synchronizing on some object that naturally encapsulates the map.
  81  *
  82  * If no such object exists, the map should be "wrapped" using the
  83  * {@link Collections#synchronizedMap Collections.synchronizedMap}
  84  * method.  This is best done at creation time, to prevent accidental
  85  * unsynchronized access to the map:<pre>
  86  *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>
  87  *
  88  * <p>The iterators returned by all of this class's "collection view methods"
  89  * are <i>fail-fast</i>: if the map is structurally modified at any time after
  90  * the iterator is created, in any way except through the iterator's own
  91  * <tt>remove</tt> method, the iterator will throw a
  92  * {@link ConcurrentModificationException}.  Thus, in the face of concurrent
  93  * modification, the iterator fails quickly and cleanly, rather than risking
  94  * arbitrary, non-deterministic behavior at an undetermined time in the
  95  * future.
  96  *
  97  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
  98  * as it is, generally speaking, impossible to make any hard guarantees in the
  99  * presence of unsynchronized concurrent modification.  Fail-fast iterators
 100  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 101  * Therefore, it would be wrong to write a program that depended on this
 102  * exception for its correctness: <i>the fail-fast behavior of iterators
 103  * should be used only to detect bugs.</i>
 104  *
 105  * <p>This class is a member of the
 106  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 107  * Java Collections Framework</a>.
 108  *
 109  * @param <K> the type of keys maintained by this map
 110  * @param <V> the type of mapped values
 111  *
 112  * @author  Doug Lea
 113  * @author  Josh Bloch
 114  * @author  Arthur van Hoff
 115  * @author  Neal Gafter
 116  * @see     Object#hashCode()
 117  * @see     Collection
 118  * @see     Map
 119  * @see     TreeMap
 120  * @see     Hashtable
 121  * @since   1.2
 122  */
 123 
 124 public class HashMap<K,V>
 125     extends AbstractMap<K,V>
 126     implements Map<K,V>, Cloneable, Serializable
 127 {
 128 
 129     /**
 130      * The default initial capacity - MUST be a power of two.
 131      */
 132     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 133 
 134     /**
 135      * The maximum capacity, used if a higher value is implicitly specified
 136      * by either of the constructors with arguments.
 137      * MUST be a power of two <= 1<<30.
 138      */
 139     static final int MAXIMUM_CAPACITY = 1 << 30;
 140 
 141     /**
 142      * The load factor used when none specified in constructor.
 143      */
 144     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 145 
 146     /**
 147      * An empty table instance to share when the table is not inflated.
 148      */
 149     static final Entry<?,?>[] EMPTY_TABLE = {};
 150 
 151     /**
 152      * The table, resized as necessary. Length MUST Always be a power of two.
 153      */
 154     transient Entry<?,?>[] table = EMPTY_TABLE;
 155 
 156     /**
 157      * The number of key-value mappings contained in this map.
 158      */
 159     transient int size;
 160 
 161     /**
 162      * The next size value at which to resize (capacity * load factor). If
 163      * table == EMPTY_TABLE then this is the initial capacity at which the
 164      * table will be created when inflated.
 165      * @serial
 166      */
 167     int threshold;
 168 
 169     /**
 170      * The load factor for the hash table.
 171      *
 172      * @serial
 173      */
 174     final float loadFactor;
 175 
 176     /**
 177      * The number of times this HashMap has been structurally modified
 178      * Structural modifications are those that change the number of mappings in
 179      * the HashMap or otherwise modify its internal structure (e.g.,
 180      * rehash).  This field is used to make iterators on Collection-views of
 181      * the HashMap fail-fast.  (See ConcurrentModificationException).
 182      */
 183     transient int modCount;
 184 
 185     private static class Holder {
 186          /**
 187          *
 188          */
 189         static final sun.misc.Unsafe UNSAFE;
 190 
 191         /**
 192          * Offset of "final" hashSeed field we must set in
 193          * readObject() method.
 194          */
 195         static final long HASHSEED_OFFSET;
 196 
 197         static {
 198             try {
 199                 UNSAFE = sun.misc.Unsafe.getUnsafe();
 200                 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
 201                     HashMap.class.getDeclaredField("hashSeed"));
 202             } catch (NoSuchFieldException | SecurityException e) {
 203                 throw new InternalError("Failed to record hashSeed offset", e);
 204             }
 205         }
 206     }
 207 
 208     /**
 209      * A randomizing value associated with this instance that is applied to
 210      * hash code of keys to make hash collisions harder to find.
 211      */
 212     transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
 213 
 214     /**
 215      * Constructs an empty <tt>HashMap</tt> with the specified initial
 216      * capacity and load factor.
 217      *
 218      * @param  initialCapacity the initial capacity
 219      * @param  loadFactor      the load factor
 220      * @throws IllegalArgumentException if the initial capacity is negative
 221      *         or the load factor is nonpositive
 222      */
 223     public HashMap(int initialCapacity, float loadFactor) {
 224         if (initialCapacity < 0)
 225             throw new IllegalArgumentException("Illegal initial capacity: " +
 226                                                initialCapacity);
 227         if (initialCapacity > MAXIMUM_CAPACITY)
 228             initialCapacity = MAXIMUM_CAPACITY;
 229         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 230             throw new IllegalArgumentException("Illegal load factor: " +
 231                                                loadFactor);
 232 
 233         this.loadFactor = loadFactor;
 234         threshold = initialCapacity;
 235         init();
 236     }
 237 
 238     /**
 239      * Constructs an empty <tt>HashMap</tt> with the specified initial
 240      * capacity and the default load factor (0.75).
 241      *
 242      * @param  initialCapacity the initial capacity.
 243      * @throws IllegalArgumentException if the initial capacity is negative.
 244      */
 245     public HashMap(int initialCapacity) {
 246         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 247     }
 248 
 249     /**
 250      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 251      * (16) and the default load factor (0.75).
 252      */
 253     public HashMap() {
 254         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
 255     }
 256 
 257     /**
 258      * Constructs a new <tt>HashMap</tt> with the same mappings as the
 259      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 260      * default load factor (0.75) and an initial capacity sufficient to
 261      * hold the mappings in the specified <tt>Map</tt>.
 262      *
 263      * @param   m the map whose mappings are to be placed in this map
 264      * @throws  NullPointerException if the specified map is null
 265      */
 266     public HashMap(Map<? extends K, ? extends V> m) {
 267         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 268                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
 269         inflateTable(threshold);
 270 
 271         putAllForCreate(m);
 272     }
 273 
 274     private static int roundUpToPowerOf2(int number) {
 275         int rounded = number >= MAXIMUM_CAPACITY
 276                 ? MAXIMUM_CAPACITY
 277                 : (rounded = Integer.highestOneBit(number)) != 0
 278                     ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
 279                     : 1;
 280 
 281         return rounded;
 282     }
 283 
 284     /**
 285      * Inflate the table
 286      */
 287     private void inflateTable(int toSize) {
 288         // Find a power of 2 >= initialCapacity
 289         int capacity = roundUpToPowerOf2(toSize);
 290 
 291         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
 292         table = new Entry[capacity];
 293     }
 294 
 295     // internal utilities
 296 
 297     /**
 298      * Initialization hook for subclasses. This method is called
 299      * in all constructors and pseudo-constructors (clone, readObject)
 300      * after HashMap has been initialized but before any entries have
 301      * been inserted.  (In the absence of this method, readObject would
 302      * require explicit knowledge of subclasses.)
 303      */
 304     void init() {
 305     }
 306 
 307     /**
 308      * Retrieve object hash code and applies a supplemental hash function to the
 309      * result hash, which defends against poor quality hash functions.  This is
 310      * critical because HashMap uses power-of-two length hash tables, that
 311      * otherwise encounter collisions for hashCodes that do not differ
 312      * in lower bits.
 313      */
 314     final int hash(Object k) {
 315         if (k instanceof String) {
 316             return ((String) k).hash32();
 317         }
 318 
 319         int  h = hashSeed ^ k.hashCode();
 320 
 321         // This function ensures that hashCodes that differ only by
 322         // constant multiples at each bit position have a bounded
 323         // number of collisions (approximately 8 at default load factor).
 324         h ^= (h >>> 20) ^ (h >>> 12);
 325         return h ^ (h >>> 7) ^ (h >>> 4);
 326     }
 327 
 328     /**
 329      * Returns index for hash code h.
 330      */
 331     static int indexFor(int h, int length) {
 332         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
 333         return h & (length-1);
 334     }
 335 
 336     /**
 337      * Returns the number of key-value mappings in this map.
 338      *
 339      * @return the number of key-value mappings in this map
 340      */
 341     public int size() {
 342         return size;
 343     }
 344 
 345     /**
 346      * Returns <tt>true</tt> if this map contains no key-value mappings.
 347      *
 348      * @return <tt>true</tt> if this map contains no key-value mappings
 349      */
 350     public boolean isEmpty() {
 351         return size == 0;
 352     }
 353 
 354     /**
 355      * Returns the value to which the specified key is mapped,
 356      * or {@code null} if this map contains no mapping for the key.
 357      *
 358      * <p>More formally, if this map contains a mapping from a key
 359      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 360      * key.equals(k))}, then this method returns {@code v}; otherwise
 361      * it returns {@code null}.  (There can be at most one such mapping.)
 362      *
 363      * <p>A return value of {@code null} does not <i>necessarily</i>
 364      * indicate that the map contains no mapping for the key; it's also
 365      * possible that the map explicitly maps the key to {@code null}.
 366      * The {@link #containsKey containsKey} operation may be used to
 367      * distinguish these two cases.
 368      *
 369      * @see #put(Object, Object)
 370      */
 371     @SuppressWarnings("unchecked")
 372     public V get(Object key) {
 373         Entry<K,V> entry = getEntry(key);
 374 
 375         return null == entry ? null : entry.getValue();
 376     }
 377 
 378     /**
 379      * Returns <tt>true</tt> if this map contains a mapping for the
 380      * specified key.
 381      *
 382      * @param   key   The key whose presence in this map is to be tested
 383      * @return <tt>true</tt> if this map contains a mapping for the specified
 384      * key.
 385      */
 386     public boolean containsKey(Object key) {
 387         return getEntry(key) != null;
 388     }
 389 
 390     /**
 391      * Returns the entry associated with the specified key in the
 392      * HashMap.  Returns null if the HashMap contains no mapping
 393      * for the key.
 394      */
 395     @SuppressWarnings("unchecked")
 396     final Entry<K,V> getEntry(Object key) {
 397         if (isEmpty()) {
 398             return null;
 399         }
 400 
 401         int hash = (key == null) ? 0 : hash(key);
 402         for (Entry<?,?> e = table[indexFor(hash, table.length)];
 403              e != null;
 404              e = e.next) {
 405             Object k;
 406             if (e.hash == hash &&
 407                 ((k = e.key) == key || (key != null && key.equals(k))))
 408                 return (Entry<K,V>)e;
 409         }
 410         return null;
 411     }
 412 
 413     /**
 414      * Associates the specified value with the specified key in this map.
 415      * If the map previously contained a mapping for the key, the old
 416      * value is replaced.
 417      *
 418      * @param key key with which the specified value is to be associated
 419      * @param value value to be associated with the specified key
 420      * @return the previous value associated with <tt>key</tt>, or
 421      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 422      *         (A <tt>null</tt> return can also indicate that the map
 423      *         previously associated <tt>null</tt> with <tt>key</tt>.)
 424      */
 425     public V put(K key, V value) {
 426         if (table == EMPTY_TABLE) {
 427             inflateTable(threshold);
 428         }
 429         if (key == null)
 430             return putForNullKey(value);
 431         int hash = hash(key);
 432         int i = indexFor(hash, table.length);
 433         @SuppressWarnings("unchecked")
 434         Entry<K,V> e = (Entry<K,V>)table[i];
 435         for(; e != null; e = e.next) {
 436             Object k;
 437             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
 438                 V oldValue = e.value;
 439                 e.value = value;
 440                 e.recordAccess(this);
 441                 return oldValue;
 442             }
 443         }
 444 
 445         modCount++;
 446         addEntry(hash, key, value, i);
 447         return null;
 448     }
 449 
 450     /**
 451      * Offloaded version of put for null keys
 452      */
 453     private V putForNullKey(V value) {
 454         @SuppressWarnings("unchecked")
 455         Entry<K,V> e = (Entry<K,V>)table[0];
 456         for(; e != null; e = e.next) {
 457             if (e.key == null) {
 458                 V oldValue = e.value;
 459                 e.value = value;
 460                 e.recordAccess(this);
 461                 return oldValue;
 462             }
 463         }
 464         modCount++;
 465         addEntry(0, null, value, 0);
 466         return null;
 467     }
 468 
 469     /**
 470      * This method is used instead of put by constructors and
 471      * pseudoconstructors (clone, readObject).  It does not resize the table,
 472      * check for comodification, etc.  It calls createEntry rather than
 473      * addEntry.
 474      */
 475     private void putForCreate(K key, V value) {
 476         int hash = null == key ? 0 : hash(key);
 477         int i = indexFor(hash, table.length);
 478 
 479         /**
 480          * Look for preexisting entry for key.  This will never happen for
 481          * clone or deserialize.  It will only happen for construction if the
 482          * input Map is a sorted map whose ordering is inconsistent w/ equals.
 483          */
 484         for (@SuppressWarnings("unchecked")
 485              Entry<?,V> e = (Entry<?,V>)table[i]; e != null; e = e.next) {
 486             Object k;
 487             if (e.hash == hash &&
 488                 ((k = e.key) == key || (key != null && key.equals(k)))) {
 489                 e.value = value;
 490                 return;
 491             }
 492         }
 493 
 494         createEntry(hash, key, value, i);
 495     }
 496 
 497     private void putAllForCreate(Map<? extends K, ? extends V> m) {
 498         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 499             putForCreate(e.getKey(), e.getValue());
 500     }
 501 
 502     /**
 503      * Rehashes the contents of this map into a new array with a
 504      * larger capacity.  This method is called automatically when the
 505      * number of keys in this map reaches its threshold.
 506      *
 507      * If current capacity is MAXIMUM_CAPACITY, this method does not
 508      * resize the map, but sets threshold to Integer.MAX_VALUE.
 509      * This has the effect of preventing future calls.
 510      *
 511      * @param newCapacity the new capacity, MUST be a power of two;
 512      *        must be greater than current capacity unless current
 513      *        capacity is MAXIMUM_CAPACITY (in which case value
 514      *        is irrelevant).
 515      */
 516     void resize(int newCapacity) {
 517         Entry<?,?>[] oldTable = table;
 518         int oldCapacity = oldTable.length;
 519         if (oldCapacity == MAXIMUM_CAPACITY) {
 520             threshold = Integer.MAX_VALUE;
 521             return;
 522         }
 523 
 524         Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
 525         transfer(newTable);
 526         table = newTable;
 527         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
 528     }
 529 
 530     /**
 531      * Transfers all entries from current table to newTable.
 532      */
 533     @SuppressWarnings("unchecked")
 534     void transfer(Entry<?,?>[] newTable) {
 535         Entry<?,?>[] src = table;
 536         int newCapacity = newTable.length;
 537         for (int j = 0; j < src.length; j++ ) {
 538             Entry<K,V> e = (Entry<K,V>) src[j];
 539             while(null != e) {
 540                 Entry<K,V> next = e.next;
 541                 int i = indexFor(e.hash, newCapacity);
 542                 e.next = (Entry<K,V>) newTable[i];
 543                 newTable[i] = e;
 544                 e = next;
 545             }
 546         }
 547         Arrays.fill(table, null);
 548     }
 549 
 550     /**
 551      * Copies all of the mappings from the specified map to this map.
 552      * These mappings will replace any mappings that this map had for
 553      * any of the keys currently in the specified map.
 554      *
 555      * @param m mappings to be stored in this map
 556      * @throws NullPointerException if the specified map is null
 557      */
 558     public void putAll(Map<? extends K, ? extends V> m) {
 559         int numKeysToBeAdded = m.size();
 560         if (numKeysToBeAdded == 0)
 561             return;
 562 
 563         if (table == EMPTY_TABLE) {
 564             inflateTable(Math.max((int) (numKeysToBeAdded * loadFactor), threshold));
 565         }
 566 
 567         /*
 568          * Expand the map if the map if the number of mappings to be added
 569          * is greater than or equal to threshold.  This is conservative; the
 570          * obvious condition is (m.size() + size) >= threshold, but this
 571          * condition could result in a map with twice the appropriate capacity,
 572          * if the keys to be added overlap with the keys already in this map.
 573          * By using the conservative calculation, we subject ourself
 574          * to at most one extra resize.
 575          */
 576         if (numKeysToBeAdded > threshold) {
 577             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
 578             if (targetCapacity > MAXIMUM_CAPACITY)
 579                 targetCapacity = MAXIMUM_CAPACITY;
 580             int newCapacity = table.length;
 581             while (newCapacity < targetCapacity)
 582                 newCapacity <<= 1;
 583             if (newCapacity > table.length)
 584                 resize(newCapacity);
 585         }
 586 
 587         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 588             put(e.getKey(), e.getValue());
 589     }
 590 
 591     /**
 592      * Removes the mapping for the specified key from this map if present.
 593      *
 594      * @param  key key whose mapping is to be removed from the map
 595      * @return the previous value associated with <tt>key</tt>, or
 596      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 597      *         (A <tt>null</tt> return can also indicate that the map
 598      *         previously associated <tt>null</tt> with <tt>key</tt>.)
 599      */
 600     public V remove(Object key) {
 601         Entry<K,V> e = removeEntryForKey(key);
 602         return (e == null ? null : e.value);
 603     }
 604 
 605     /**
 606      * Removes and returns the entry associated with the specified key
 607      * in the HashMap.  Returns null if the HashMap contains no mapping
 608      * for this key.
 609      */
 610     final Entry<K,V> removeEntryForKey(Object key) {
 611         if (isEmpty()) {
 612             return null;
 613         }
 614         int hash = (key == null) ? 0 : hash(key);
 615         int i = indexFor(hash, table.length);
 616         @SuppressWarnings("unchecked")
 617             Entry<K,V> prev = (Entry<K,V>)table[i];
 618         Entry<K,V> e = prev;
 619 
 620         while (e != null) {
 621             Entry<K,V> next = e.next;
 622             Object k;
 623             if (e.hash == hash &&
 624                 ((k = e.key) == key || (key != null && key.equals(k)))) {
 625                 modCount++;
 626                 size--;
 627                 if (prev == e)
 628                     table[i] = next;
 629                 else
 630                     prev.next = next;
 631                 e.recordRemoval(this);
 632                 return e;
 633             }
 634             prev = e;
 635             e = next;
 636         }
 637 
 638         return e;
 639     }
 640 
 641     /**
 642      * Special version of remove for EntrySet using {@code Map.Entry.equals()}
 643      * for matching.
 644      */
 645     final Entry<K,V> removeMapping(Object o) {
 646         if (isEmpty() || !(o instanceof Map.Entry))
 647             return null;
 648 
 649         Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
 650         Object key = entry.getKey();
 651         int hash = (key == null) ? 0 : hash(key);
 652         int i = indexFor(hash, table.length);
 653         @SuppressWarnings("unchecked")
 654             Entry<K,V> prev = (Entry<K,V>)table[i];
 655         Entry<K,V> e = prev;
 656 
 657         while (e != null) {
 658             Entry<K,V> next = e.next;
 659             if (e.hash == hash && e.equals(entry)) {
 660                 modCount++;
 661                 size--;
 662                 if (prev == e)
 663                     table[i] = next;
 664                 else
 665                     prev.next = next;
 666                 e.recordRemoval(this);
 667                 return e;
 668             }
 669             prev = e;
 670             e = next;
 671         }
 672 
 673         return e;
 674     }
 675 
 676     /**
 677      * Removes all of the mappings from this map.
 678      * The map will be empty after this call returns.
 679      */
 680     public void clear() {
 681         modCount++;
 682         Arrays.fill(table, null);
 683         size = 0;
 684     }
 685 
 686     /**
 687      * Returns <tt>true</tt> if this map maps one or more keys to the
 688      * specified value.
 689      *
 690      * @param value value whose presence in this map is to be tested
 691      * @return <tt>true</tt> if this map maps one or more keys to the
 692      *         specified value
 693      */
 694     public boolean containsValue(Object value) {
 695         if (isEmpty()) {
 696             return false;
 697         }
 698 
 699         if (value == null)
 700             return containsNullValue();
 701 
 702         Entry<?,?>[] tab = table;
 703         for (int i = 0; i < tab.length ; i++)
 704             for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
 705                 if (value.equals(e.value))
 706                     return true;
 707         return false;
 708     }
 709 
 710     /**
 711      * Special-case code for containsValue with null argument
 712      */
 713     private boolean containsNullValue() {
 714         Entry<?,?>[] tab = table;
 715         for (int i = 0; i < tab.length ; i++)
 716             for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
 717                 if (e.value == null)
 718                     return true;
 719         return false;
 720     }
 721 
 722     /**
 723      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
 724      * values themselves are not cloned.
 725      *
 726      * @return a shallow copy of this map
 727      */
 728     @SuppressWarnings("unchecked")
 729     public Object clone() {
 730         HashMap<K,V> result = null;
 731         try {
 732             result = (HashMap<K,V>)super.clone();
 733         } catch (CloneNotSupportedException e) {
 734             // assert false;
 735         }
 736         result.table = (table == EMPTY_TABLE)
 737             ? EMPTY_TABLE
 738             : new Entry<?,?>[table.length];
 739         result.entrySet = null;
 740         result.modCount = 0;
 741         result.size = 0;
 742         result.init();
 743         result.putAllForCreate(this);
 744 
 745         return result;
 746     }
 747 
 748     static class Entry<K,V> implements Map.Entry<K,V> {
 749         final K key;
 750         V value;
 751         Entry<K,V> next;
 752         final int hash;
 753 
 754         /**
 755          * Creates new entry.
 756          */
 757         Entry(int h, K k, V v, Entry<K,V> n) {
 758             value = v;
 759             next = n;
 760             key = k;
 761             hash = h;
 762         }
 763 
 764         public final K getKey() {
 765             return key;
 766         }
 767 
 768         public final V getValue() {
 769             return value;
 770         }
 771 
 772         public final V setValue(V newValue) {
 773             V oldValue = value;
 774             value = newValue;
 775             return oldValue;
 776         }
 777 
 778         public final boolean equals(Object o) {
 779             if (!(o instanceof Map.Entry))
 780                 return false;
 781             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 782             Object k1 = getKey();
 783             Object k2 = e.getKey();
 784             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
 785                 Object v1 = getValue();
 786                 Object v2 = e.getValue();
 787                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
 788                     return true;
 789             }
 790             return false;
 791         }
 792 
 793         public final int hashCode() {
 794             return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
 795         }
 796 
 797         public final String toString() {
 798             return getKey() + "=" + getValue();
 799         }
 800 
 801         /**
 802          * This method is invoked whenever the value in an entry is
 803          * overwritten by an invocation of put(k,v) for a key k that's already
 804          * in the HashMap.
 805          */
 806         void recordAccess(HashMap<K,V> m) {
 807         }
 808 
 809         /**
 810          * This method is invoked whenever the entry is
 811          * removed from the table.
 812          */
 813         void recordRemoval(HashMap<K,V> m) {
 814         }
 815     }
 816 
 817     /**
 818      * Adds a new entry with the specified key, value and hash code to
 819      * the specified bucket.  It is the responsibility of this
 820      * method to resize the table if appropriate.
 821      *
 822      * Subclass overrides this to alter the behavior of put method.
 823      */
 824     void addEntry(int hash, K key, V value, int bucketIndex) {
 825         if ((size >= threshold) && (null != table[bucketIndex])) {
 826             resize(2 * table.length);
 827             hash = (null != key) ? hash(key) : 0;
 828             bucketIndex = indexFor(hash, table.length);
 829         }
 830 
 831         createEntry(hash, key, value, bucketIndex);
 832     }
 833 
 834     /**
 835      * Like addEntry except that this version is used when creating entries
 836      * as part of Map construction or "pseudo-construction" (cloning,
 837      * deserialization).  This version needn't worry about resizing the table.
 838      *
 839      * Subclass overrides this to alter the behavior of HashMap(Map),
 840      * clone, and readObject.
 841      */
 842     void createEntry(int hash, K key, V value, int bucketIndex) {
 843         @SuppressWarnings("unchecked")
 844             Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
 845         table[bucketIndex] = new Entry<>(hash, key, value, e);
 846         size++;
 847     }
 848 
 849     private abstract class HashIterator<E> implements Iterator<E> {
 850         Entry<?,?> next;        // next entry to return
 851         int expectedModCount;   // For fast-fail
 852         int index;              // current slot
 853         Entry<?,?> current;     // current entry
 854 
 855         HashIterator() {
 856             expectedModCount = modCount;
 857             if (size > 0) { // advance to first entry
 858                 Entry<?,?>[] t = table;
 859                 while (index < t.length && (next = t[index++]) == null)
 860                     ;
 861             }
 862         }
 863 
 864         public final boolean hasNext() {
 865             return next != null;
 866         }
 867 
 868         @SuppressWarnings("unchecked")
 869         final Entry<K,V> nextEntry() {
 870             if (modCount != expectedModCount)
 871                 throw new ConcurrentModificationException();
 872             Entry<?,?> e = next;
 873             if (e == null)
 874                 throw new NoSuchElementException();
 875 
 876             if ((next = e.next) == null) {
 877                 Entry<?,?>[] t = table;
 878                 while (index < t.length && (next = t[index++]) == null)
 879                     ;
 880             }
 881             current = e;
 882             return (Entry<K,V>)e;
 883         }
 884 
 885         public void remove() {
 886             if (current == null)
 887                 throw new IllegalStateException();
 888             if (modCount != expectedModCount)
 889                 throw new ConcurrentModificationException();
 890             Object k = current.key;
 891             current = null;
 892             HashMap.this.removeEntryForKey(k);
 893             expectedModCount = modCount;
 894         }
 895     }
 896 
 897     private final class ValueIterator extends HashIterator<V> {
 898         public V next() {
 899             return nextEntry().value;
 900         }
 901     }
 902 
 903     private final class KeyIterator extends HashIterator<K> {
 904         public K next() {
 905             return nextEntry().getKey();
 906         }
 907     }
 908 
 909     private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
 910         public Map.Entry<K,V> next() {
 911             return nextEntry();
 912         }
 913     }
 914 
 915     // Subclass overrides these to alter behavior of views' iterator() method
 916     Iterator<K> newKeyIterator()   {
 917         return new KeyIterator();
 918     }
 919     Iterator<V> newValueIterator()   {
 920         return new ValueIterator();
 921     }
 922     Iterator<Map.Entry<K,V>> newEntryIterator()   {
 923         return new EntryIterator();
 924     }
 925 
 926 
 927     // Views
 928 
 929     private transient Set<Map.Entry<K,V>> entrySet = null;
 930 
 931     /**
 932      * Returns a {@link Set} view of the keys contained in this map.
 933      * The set is backed by the map, so changes to the map are
 934      * reflected in the set, and vice-versa.  If the map is modified
 935      * while an iteration over the set is in progress (except through
 936      * the iterator's own <tt>remove</tt> operation), the results of
 937      * the iteration are undefined.  The set supports element removal,
 938      * which removes the corresponding mapping from the map, via the
 939      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 940      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 941      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
 942      * operations.
 943      */
 944     public Set<K> keySet() {
 945         Set<K> ks = keySet;
 946         return (ks != null ? ks : (keySet = new KeySet()));
 947     }
 948 
 949     private final class KeySet extends AbstractSet<K> {
 950         public Iterator<K> iterator() {
 951             return newKeyIterator();
 952         }
 953         public int size() {
 954             return size;
 955         }
 956         public boolean contains(Object o) {
 957             return containsKey(o);
 958         }
 959         public boolean remove(Object o) {
 960             return HashMap.this.removeEntryForKey(o) != null;
 961         }
 962         public void clear() {
 963             HashMap.this.clear();
 964         }
 965     }
 966 
 967     /**
 968      * Returns a {@link Collection} view of the values contained in this map.
 969      * The collection is backed by the map, so changes to the map are
 970      * reflected in the collection, and vice-versa.  If the map is
 971      * modified while an iteration over the collection is in progress
 972      * (except through the iterator's own <tt>remove</tt> operation),
 973      * the results of the iteration are undefined.  The collection
 974      * supports element removal, which removes the corresponding
 975      * mapping from the map, via the <tt>Iterator.remove</tt>,
 976      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 977      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
 978      * support the <tt>add</tt> or <tt>addAll</tt> operations.
 979      */
 980     public Collection<V> values() {
 981         Collection<V> vs = values;
 982         return (vs != null ? vs : (values = new Values()));
 983     }
 984 
 985     private final class Values extends AbstractCollection<V> {
 986         public Iterator<V> iterator() {
 987             return newValueIterator();
 988         }
 989         public int size() {
 990             return size;
 991         }
 992         public boolean contains(Object o) {
 993             return containsValue(o);
 994         }
 995         public void clear() {
 996             HashMap.this.clear();
 997         }
 998     }
 999 
1000     /**
1001      * Returns a {@link Set} view of the mappings contained in this map.
1002      * The set is backed by the map, so changes to the map are
1003      * reflected in the set, and vice-versa.  If the map is modified
1004      * while an iteration over the set is in progress (except through
1005      * the iterator's own <tt>remove</tt> operation, or through the
1006      * <tt>setValue</tt> operation on a map entry returned by the
1007      * iterator) the results of the iteration are undefined.  The set
1008      * supports element removal, which removes the corresponding
1009      * mapping from the map, via the <tt>Iterator.remove</tt>,
1010      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1011      * <tt>clear</tt> operations.  It does not support the
1012      * <tt>add</tt> or <tt>addAll</tt> operations.
1013      *
1014      * @return a set view of the mappings contained in this map
1015      */
1016     public Set<Map.Entry<K,V>> entrySet() {
1017         return entrySet0();
1018     }
1019 
1020     private Set<Map.Entry<K,V>> entrySet0() {
1021         Set<Map.Entry<K,V>> es = entrySet;
1022         return es != null ? es : (entrySet = new EntrySet());
1023     }
1024 
1025     private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1026         public Iterator<Map.Entry<K,V>> iterator() {
1027             return newEntryIterator();
1028         }
1029         public boolean contains(Object o) {
1030             if (!(o instanceof Map.Entry))
1031                 return false;
1032             Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1033             Entry<K,V> candidate = getEntry(e.getKey());
1034             return candidate != null && candidate.equals(e);
1035         }
1036         public boolean remove(Object o) {
1037             return removeMapping(o) != null;
1038         }
1039         public int size() {
1040             return size;
1041         }
1042         public void clear() {
1043             HashMap.this.clear();
1044         }
1045     }
1046 
1047     /**
1048      * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1049      * serialize it).
1050      *
1051      * @serialData The <i>capacity</i> of the HashMap (the length of the
1052      *             bucket array) is emitted (int), followed by the
1053      *             <i>size</i> (an int, the number of key-value
1054      *             mappings), followed by the key (Object) and value (Object)
1055      *             for each key-value mapping.  The key-value mappings are
1056      *             emitted in no particular order.
1057      */
1058     private void writeObject(java.io.ObjectOutputStream s)
1059         throws IOException
1060     {
1061         // Write out the threshold, loadfactor, and any hidden stuff
1062         s.defaultWriteObject();
1063 
1064         // Write out number of buckets
1065         if (table==EMPTY_TABLE) {
1066             s.writeInt(roundUpToPowerOf2(threshold));
1067         } else {
1068            s.writeInt(table.length);
1069         }
1070 
1071         // Write out size (number of Mappings)
1072         s.writeInt(size);
1073 
1074         // Write out keys and values (alternating)
1075         if (size > 0) {
1076             for(Map.Entry<K,V> e : entrySet0()) {
1077                 s.writeObject(e.getKey());
1078                 s.writeObject(e.getValue());
1079             }
1080         }
1081     }
1082 
1083     private static final long serialVersionUID = 362498820763181265L;
1084 
1085     /**
1086      * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1087      * deserialize it).
1088      */
1089     private void readObject(java.io.ObjectInputStream s)
1090          throws IOException, ClassNotFoundException
1091     {
1092         // Read in the threshold (ignored), loadfactor, and any hidden stuff
1093         s.defaultReadObject();
1094         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
1095             throw new InvalidObjectException("Illegal load factor: " +
1096                                                loadFactor);
1097         }
1098 
1099         // set other fields that need values
1100         Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1101                 sun.misc.Hashing.randomHashSeed(this));
1102         table = EMPTY_TABLE;
1103 
1104         // Read in number of buckets
1105         int bucketsCapacity = s.readInt();
1106 
1107         if (bucketsCapacity < 0) {
1108             throw new InvalidObjectException("Illegal capacity: " + bucketsCapacity);
1109         }
1110 
1111         bucketsCapacity = roundUpToPowerOf2(bucketsCapacity);
1112 
1113         // Read number of mappings
1114         int mappings = s.readInt();
1115         if (mappings < 0)
1116             throw new InvalidObjectException("Illegal mappings count: " +
1117                                                mappings);
1118 
1119         // capacity chosen by number of mappings and desired load (if >= 0.25)
1120         int mappingsCapacity = (int) Math.min(
1121                     mappings * Math.min(1 / loadFactor, 4.0f),
1122                     // we have limits...
1123                     HashMap.MAXIMUM_CAPACITY);
1124 
1125         // capacity is greater of that suggested by loading and buckets
1126         int capacity = Math.max(mappingsCapacity, bucketsCapacity);
1127 
1128         // allocate the bucket array;
1129         if (mappings > 0) {
1130             inflateTable(capacity);
1131         } else {
1132             threshold = capacity;
1133         }
1134 
1135         init();  // Give subclass a chance to do its thing.
1136 
1137         // Read the keys and values, and put the mappings in the HashMap
1138         for (int i=0; i<mappings; i++) {
1139             @SuppressWarnings("unchecked")
1140                 K key = (K) s.readObject();
1141             @SuppressWarnings("unchecked")
1142                 V value = (V) s.readObject();
1143             putForCreate(key, value);
1144         }
1145     }
1146 
1147     // These methods are used when serializing HashSets
1148     int   capacity()     { return table.length; }
1149     float loadFactor()   { return loadFactor;   }
1150 }