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 = 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).
 163      * @serial
 164      */
 165     int threshold;
 166 
 167     /**
 168      * The load factor for the hash table.
 169      *
 170      * @serial
 171      */
 172     final float loadFactor;
 173 
 174     /**
 175      * The number of times this HashMap has been structurally modified
 176      * Structural modifications are those that change the number of mappings in
 177      * the HashMap or otherwise modify its internal structure (e.g.,
 178      * rehash).  This field is used to make iterators on Collection-views of
 179      * the HashMap fail-fast.  (See ConcurrentModificationException).
 180      */
 181     transient int modCount;
 182 
 183     private static class Holder {
 184          /**
 185          *
 186          */
 187         static final sun.misc.Unsafe UNSAFE;
 188 
 189         /**
 190          * Offset of "final" hashSeed field we must set in
 191          * readObject() method.
 192          */
 193         static final long HASHSEED_OFFSET;
 194 
 195         static {
 196             try {
 197                 UNSAFE = sun.misc.Unsafe.getUnsafe();
 198                 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
 199                     HashMap.class.getDeclaredField("hashSeed"));
 200             } catch (NoSuchFieldException | SecurityException e) {
 201                 throw new InternalError("Failed to record hashSeed offset", e);
 202             }
 203         }
 204     }
 205 
 206     /**
 207      * A randomizing value associated with this instance that is applied to
 208      * hash code of keys to make hash collisions harder to find.
 209      */
 210     transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
 211 
 212     /**
 213      * Constructs an empty <tt>HashMap</tt> with the specified initial
 214      * capacity and load factor.
 215      *
 216      * @param  initialCapacity the initial capacity
 217      * @param  loadFactor      the load factor
 218      * @throws IllegalArgumentException if the initial capacity is negative
 219      *         or the load factor is nonpositive
 220      */
 221     public HashMap(int initialCapacity, float loadFactor) {
 222         if (initialCapacity < 0)
 223             throw new IllegalArgumentException("Illegal initial capacity: " +
 224                                                initialCapacity);
 225         if (initialCapacity > MAXIMUM_CAPACITY)
 226             initialCapacity = MAXIMUM_CAPACITY;
 227         if (loadFactor <= 0 || Float.isNaN(loadFactor))
 228             throw new IllegalArgumentException("Illegal load factor: " +
 229                                                loadFactor);
 230 
 231         this.loadFactor = loadFactor;
 232         threshold = initialCapacity;
 233         init();
 234     }
 235 
 236     /**
 237      * Constructs an empty <tt>HashMap</tt> with the specified initial
 238      * capacity and the default load factor (0.75).
 239      *
 240      * @param  initialCapacity the initial capacity.
 241      * @throws IllegalArgumentException if the initial capacity is negative.
 242      */
 243     public HashMap(int initialCapacity) {
 244         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 245     }
 246 
 247     /**
 248      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 249      * (16) and the default load factor (0.75).
 250      */
 251     public HashMap() {
 252         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
 253     }
 254 
 255     /**
 256      * Constructs a new <tt>HashMap</tt> with the same mappings as the
 257      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
 258      * default load factor (0.75) and an initial capacity sufficient to
 259      * hold the mappings in the specified <tt>Map</tt>.
 260      *
 261      * @param   m the map whose mappings are to be placed in this map
 262      * @throws  NullPointerException if the specified map is null
 263      */
 264     public HashMap(Map<? extends K, ? extends V> m) {
 265         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 266                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
 267         inflateTable(threshold);
 268 
 269         putAllForCreate(m);
 270     }
 271 
 272     private static int roundUpToPowerOf2(int number) {
 273         int rounded = (rounded = Integer.highestOneBit(number)) != 0
 274             ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
 275             : 1;
 276 
 277         return rounded;
 278     }
 279 
 280     /**
 281      * Inflate the table
 282      */
 283     private void inflateTable(int toSize) {
 284         // Find a power of 2 >= initialCapacity
 285         int capacity = roundUpToPowerOf2(toSize);
 286 
 287         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
 288         table = new Entry[capacity];
 289     }
 290 
 291     // internal utilities
 292 
 293     /**
 294      * Initialization hook for subclasses. This method is called
 295      * in all constructors and pseudo-constructors (clone, readObject)
 296      * after HashMap has been initialized but before any entries have
 297      * been inserted.  (In the absence of this method, readObject would
 298      * require explicit knowledge of subclasses.)
 299      */
 300     void init() {
 301     }
 302 
 303     /**
 304      * Retrieve object hash code and applies a supplemental hash function to the
 305      * result hash, which defends against poor quality hash functions.  This is
 306      * critical because HashMap uses power-of-two length hash tables, that
 307      * otherwise encounter collisions for hashCodes that do not differ
 308      * in lower bits.
 309      */
 310     final int hash(Object k) {
 311         if (k instanceof String) {
 312             return ((String) k).hash32();
 313         }
 314 
 315         int  h = hashSeed ^ k.hashCode();
 316 
 317         // This function ensures that hashCodes that differ only by
 318         // constant multiples at each bit position have a bounded
 319         // number of collisions (approximately 8 at default load factor).
 320         h ^= (h >>> 20) ^ (h >>> 12);
 321         return h ^ (h >>> 7) ^ (h >>> 4);
 322     }
 323 
 324     /**
 325      * Returns index for hash code h.
 326      */
 327     static int indexFor(int h, int length) {
 328         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
 329         return h & (length-1);
 330     }
 331 
 332     /**
 333      * Returns the number of key-value mappings in this map.
 334      *
 335      * @return the number of key-value mappings in this map
 336      */
 337     public int size() {
 338         return size;
 339     }
 340 
 341     /**
 342      * Returns <tt>true</tt> if this map contains no key-value mappings.
 343      *
 344      * @return <tt>true</tt> if this map contains no key-value mappings
 345      */
 346     public boolean isEmpty() {
 347         return size == 0;
 348     }
 349 
 350     /**
 351      * Returns the value to which the specified key is mapped,
 352      * or {@code null} if this map contains no mapping for the key.
 353      *
 354      * <p>More formally, if this map contains a mapping from a key
 355      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 356      * key.equals(k))}, then this method returns {@code v}; otherwise
 357      * it returns {@code null}.  (There can be at most one such mapping.)
 358      *
 359      * <p>A return value of {@code null} does not <i>necessarily</i>
 360      * indicate that the map contains no mapping for the key; it's also
 361      * possible that the map explicitly maps the key to {@code null}.
 362      * The {@link #containsKey containsKey} operation may be used to
 363      * distinguish these two cases.
 364      *
 365      * @see #put(Object, Object)
 366      */
 367     @SuppressWarnings("unchecked")
 368     public V get(Object key) {
 369         Entry<K,V> entry = getEntry(key);
 370 
 371         return null == entry ? null : entry.getValue();
 372     }
 373 
 374     /**
 375      * Returns <tt>true</tt> if this map contains a mapping for the
 376      * specified key.
 377      *
 378      * @param   key   The key whose presence in this map is to be tested
 379      * @return <tt>true</tt> if this map contains a mapping for the specified
 380      * key.
 381      */
 382     public boolean containsKey(Object key) {
 383         return getEntry(key) != null;
 384     }
 385 
 386     /**
 387      * Returns the entry associated with the specified key in the
 388      * HashMap.  Returns null if the HashMap contains no mapping
 389      * for the key.
 390      */
 391     @SuppressWarnings("unchecked")
 392     final Entry<K,V> getEntry(Object key) {
 393         if (isEmpty()) {
 394             return null;
 395         }
 396 
 397         int hash = (key == null) ? 0 : hash(key);
 398         for (Entry<?,?> e = table[indexFor(hash, table.length)];
 399              e != null;
 400              e = e.next) {
 401             Object k;
 402             if (e.hash == hash &&
 403                 ((k = e.key) == key || (key != null && key.equals(k))))
 404                 return (Entry<K,V>)e;
 405         }
 406         return null;
 407     }
 408 
 409     /**
 410      * Associates the specified value with the specified key in this map.
 411      * If the map previously contained a mapping for the key, the old
 412      * value is replaced.
 413      *
 414      * @param key key with which the specified value is to be associated
 415      * @param value value to be associated with the specified key
 416      * @return the previous value associated with <tt>key</tt>, or
 417      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 418      *         (A <tt>null</tt> return can also indicate that the map
 419      *         previously associated <tt>null</tt> with <tt>key</tt>.)
 420      */
 421     public V put(K key, V value) {
 422         if (table == EMPTY_TABLE) {
 423             inflateTable(threshold);
 424         }
 425         if (key == null)
 426             return putForNullKey(value);
 427         int hash = hash(key);
 428         int i = indexFor(hash, table.length);
 429         @SuppressWarnings("unchecked")
 430         Entry<K,V> e = (Entry<K,V>)table[i];
 431         for(; e != null; e = e.next) {
 432             Object k;
 433             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
 434                 V oldValue = e.value;
 435                 e.value = value;
 436                 e.recordAccess(this);
 437                 return oldValue;
 438             }
 439         }
 440 
 441         modCount++;
 442         addEntry(hash, key, value, i);
 443         return null;
 444     }
 445 
 446     /**
 447      * Offloaded version of put for null keys
 448      */
 449     private V putForNullKey(V value) {
 450         @SuppressWarnings("unchecked")
 451         Entry<K,V> e = (Entry<K,V>)table[0];
 452         for(; e != null; e = e.next) {
 453             if (e.key == null) {
 454                 V oldValue = e.value;
 455                 e.value = value;
 456                 e.recordAccess(this);
 457                 return oldValue;
 458             }
 459         }
 460         modCount++;
 461         addEntry(0, null, value, 0);
 462         return null;
 463     }
 464 
 465     /**
 466      * This method is used instead of put by constructors and
 467      * pseudoconstructors (clone, readObject).  It does not resize the table,
 468      * check for comodification, etc.  It calls createEntry rather than
 469      * addEntry.
 470      */
 471     private void putForCreate(K key, V value) {
 472         int hash = null == key ? 0 : hash(key);
 473         int i = indexFor(hash, table.length);
 474 
 475         /**
 476          * Look for preexisting entry for key.  This will never happen for
 477          * clone or deserialize.  It will only happen for construction if the
 478          * input Map is a sorted map whose ordering is inconsistent w/ equals.
 479          */
 480         for (@SuppressWarnings("unchecked")
 481              Entry<?,V> e = (Entry<?,V>)table[i]; e != null; e = e.next) {
 482             Object k;
 483             if (e.hash == hash &&
 484                 ((k = e.key) == key || (key != null && key.equals(k)))) {
 485                 e.value = value;
 486                 return;
 487             }
 488         }
 489 
 490         createEntry(hash, key, value, i);
 491     }
 492 
 493     private void putAllForCreate(Map<? extends K, ? extends V> m) {
 494         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 495             putForCreate(e.getKey(), e.getValue());
 496     }
 497 
 498     /**
 499      * Rehashes the contents of this map into a new array with a
 500      * larger capacity.  This method is called automatically when the
 501      * number of keys in this map reaches its threshold.
 502      *
 503      * If current capacity is MAXIMUM_CAPACITY, this method does not
 504      * resize the map, but sets threshold to Integer.MAX_VALUE.
 505      * This has the effect of preventing future calls.
 506      *
 507      * @param newCapacity the new capacity, MUST be a power of two;
 508      *        must be greater than current capacity unless current
 509      *        capacity is MAXIMUM_CAPACITY (in which case value
 510      *        is irrelevant).
 511      */
 512     void resize(int newCapacity) {
 513         Entry<?,?>[] oldTable = table;
 514         int oldCapacity = oldTable.length;
 515         if (oldCapacity == MAXIMUM_CAPACITY) {
 516             threshold = Integer.MAX_VALUE;
 517             return;
 518         }
 519 
 520         Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
 521         transfer(newTable);
 522         table = newTable;
 523         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
 524     }
 525 
 526     /**
 527      * Transfers all entries from current table to newTable.
 528      */
 529     @SuppressWarnings("unchecked")
 530     void transfer(Entry<?,?>[] newTable) {
 531         Entry<?,?>[] src = table;
 532         int newCapacity = newTable.length;
 533         for (int j = 0; j < src.length; j++ ) {
 534             Entry<K,V> e = (Entry<K,V>) src[j];
 535             while(null != e) {
 536                 Entry<K,V> next = e.next;
 537                 int i = indexFor(e.hash, newCapacity);
 538                 e.next = (Entry<K,V>) newTable[i];
 539                 newTable[i] = e;
 540                 e = next;
 541             }
 542         }
 543         Arrays.fill(table, null);
 544     }
 545 
 546     /**
 547      * Copies all of the mappings from the specified map to this map.
 548      * These mappings will replace any mappings that this map had for
 549      * any of the keys currently in the specified map.
 550      *
 551      * @param m mappings to be stored in this map
 552      * @throws NullPointerException if the specified map is null
 553      */
 554     public void putAll(Map<? extends K, ? extends V> m) {
 555         int numKeysToBeAdded = m.size();
 556         if (numKeysToBeAdded == 0)
 557             return;
 558 
 559         if (table == EMPTY_TABLE) {
 560             inflateTable(Math.max((int) (numKeysToBeAdded * loadFactor), threshold));
 561         }
 562 
 563         /*
 564          * Expand the map if the map if the number of mappings to be added
 565          * is greater than or equal to threshold.  This is conservative; the
 566          * obvious condition is (m.size() + size) >= threshold, but this
 567          * condition could result in a map with twice the appropriate capacity,
 568          * if the keys to be added overlap with the keys already in this map.
 569          * By using the conservative calculation, we subject ourself
 570          * to at most one extra resize.
 571          */
 572         if (numKeysToBeAdded > threshold) {
 573             int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
 574             if (targetCapacity > MAXIMUM_CAPACITY)
 575                 targetCapacity = MAXIMUM_CAPACITY;
 576             int newCapacity = table.length;
 577             while (newCapacity < targetCapacity)
 578                 newCapacity <<= 1;
 579             if (newCapacity > table.length)
 580                 resize(newCapacity);
 581         }
 582 
 583         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 584             put(e.getKey(), e.getValue());
 585     }
 586 
 587     /**
 588      * Removes the mapping for the specified key from this map if present.
 589      *
 590      * @param  key key whose mapping is to be removed from the map
 591      * @return the previous value associated with <tt>key</tt>, or
 592      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 593      *         (A <tt>null</tt> return can also indicate that the map
 594      *         previously associated <tt>null</tt> with <tt>key</tt>.)
 595      */
 596     public V remove(Object key) {
 597         Entry<K,V> e = removeEntryForKey(key);
 598         return (e == null ? null : e.value);
 599     }
 600 
 601     /**
 602      * Removes and returns the entry associated with the specified key
 603      * in the HashMap.  Returns null if the HashMap contains no mapping
 604      * for this key.
 605      */
 606     final Entry<K,V> removeEntryForKey(Object key) {
 607         if (isEmpty()) {
 608             return null;
 609         }
 610         int hash = (key == null) ? 0 : hash(key);
 611         int i = indexFor(hash, table.length);
 612         @SuppressWarnings("unchecked")
 613             Entry<K,V> prev = (Entry<K,V>)table[i];
 614         Entry<K,V> e = prev;
 615 
 616         while (e != null) {
 617             Entry<K,V> next = e.next;
 618             Object k;
 619             if (e.hash == hash &&
 620                 ((k = e.key) == key || (key != null && key.equals(k)))) {
 621                 modCount++;
 622                 size--;
 623                 if (prev == e)
 624                     table[i] = next;
 625                 else
 626                     prev.next = next;
 627                 e.recordRemoval(this);
 628                 return e;
 629             }
 630             prev = e;
 631             e = next;
 632         }
 633 
 634         return e;
 635     }
 636 
 637     /**
 638      * Special version of remove for EntrySet using {@code Map.Entry.equals()}
 639      * for matching.
 640      */
 641     final Entry<K,V> removeMapping(Object o) {
 642         if (isEmpty() || !(o instanceof Map.Entry))
 643             return null;
 644 
 645         Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
 646         Object key = entry.getKey();
 647         int hash = (key == null) ? 0 : hash(key);
 648         int i = indexFor(hash, table.length);
 649         @SuppressWarnings("unchecked")
 650             Entry<K,V> prev = (Entry<K,V>)table[i];
 651         Entry<K,V> e = prev;
 652 
 653         while (e != null) {
 654             Entry<K,V> next = e.next;
 655             if (e.hash == hash && e.equals(entry)) {
 656                 modCount++;
 657                 size--;
 658                 if (prev == e)
 659                     table[i] = next;
 660                 else
 661                     prev.next = next;
 662                 e.recordRemoval(this);
 663                 return e;
 664             }
 665             prev = e;
 666             e = next;
 667         }
 668 
 669         return e;
 670     }
 671 
 672     /**
 673      * Removes all of the mappings from this map.
 674      * The map will be empty after this call returns.
 675      */
 676     public void clear() {
 677         modCount++;
 678         Arrays.fill(table, null);
 679         size = 0;
 680     }
 681 
 682     /**
 683      * Returns <tt>true</tt> if this map maps one or more keys to the
 684      * specified value.
 685      *
 686      * @param value value whose presence in this map is to be tested
 687      * @return <tt>true</tt> if this map maps one or more keys to the
 688      *         specified value
 689      */
 690     public boolean containsValue(Object value) {
 691         if (isEmpty()) {
 692             return false;
 693         }
 694 
 695         if (value == null)
 696             return containsNullValue();
 697 
 698         Entry<?,?>[] tab = table;
 699         for (int i = 0; i < tab.length ; i++)
 700             for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
 701                 if (value.equals(e.value))
 702                     return true;
 703         return false;
 704     }
 705 
 706     /**
 707      * Special-case code for containsValue with null argument
 708      */
 709     private boolean containsNullValue() {
 710         Entry<?,?>[] tab = table;
 711         for (int i = 0; i < tab.length ; i++)
 712             for (Entry<?,?> e = tab[i] ; e != null ; e = e.next)
 713                 if (e.value == null)
 714                     return true;
 715         return false;
 716     }
 717 
 718     /**
 719      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
 720      * values themselves are not cloned.
 721      *
 722      * @return a shallow copy of this map
 723      */
 724     @SuppressWarnings("unchecked")
 725     public Object clone() {
 726         HashMap<K,V> result = null;
 727         try {
 728             result = (HashMap<K,V>)super.clone();
 729         } catch (CloneNotSupportedException e) {
 730             // assert false;
 731         }
 732         result.table = (table == EMPTY_TABLE)
 733             ? EMPTY_TABLE
 734             : new Entry<?,?>[table.length];
 735         result.entrySet = null;
 736         result.modCount = 0;
 737         result.size = 0;
 738         result.init();
 739         result.putAllForCreate(this);
 740 
 741         return result;
 742     }
 743 
 744     static class Entry<K,V> implements Map.Entry<K,V> {
 745         final K key;
 746         V value;
 747         Entry<K,V> next;
 748         final int hash;
 749 
 750         /**
 751          * Creates new entry.
 752          */
 753         Entry(int h, K k, V v, Entry<K,V> n) {
 754             value = v;
 755             next = n;
 756             key = k;
 757             hash = h;
 758         }
 759 
 760         public final K getKey() {
 761             return key;
 762         }
 763 
 764         public final V getValue() {
 765             return value;
 766         }
 767 
 768         public final V setValue(V newValue) {
 769             V oldValue = value;
 770             value = newValue;
 771             return oldValue;
 772         }
 773 
 774         public final boolean equals(Object o) {
 775             if (!(o instanceof Map.Entry))
 776                 return false;
 777             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
 778             Object k1 = getKey();
 779             Object k2 = e.getKey();
 780             if (k1 == k2 || (k1 != null && k1.equals(k2))) {
 781                 Object v1 = getValue();
 782                 Object v2 = e.getValue();
 783                 if (v1 == v2 || (v1 != null && v1.equals(v2)))
 784                     return true;
 785             }
 786             return false;
 787         }
 788 
 789         public final int hashCode() {
 790             return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
 791         }
 792 
 793         public final String toString() {
 794             return getKey() + "=" + getValue();
 795         }
 796 
 797         /**
 798          * This method is invoked whenever the value in an entry is
 799          * overwritten by an invocation of put(k,v) for a key k that's already
 800          * in the HashMap.
 801          */
 802         void recordAccess(HashMap<K,V> m) {
 803         }
 804 
 805         /**
 806          * This method is invoked whenever the entry is
 807          * removed from the table.
 808          */
 809         void recordRemoval(HashMap<K,V> m) {
 810         }
 811     }
 812 
 813     /**
 814      * Adds a new entry with the specified key, value and hash code to
 815      * the specified bucket.  It is the responsibility of this
 816      * method to resize the table if appropriate.
 817      *
 818      * Subclass overrides this to alter the behavior of put method.
 819      */
 820     void addEntry(int hash, K key, V value, int bucketIndex) {
 821         if ((size >= threshold) && (null != table[bucketIndex])) {
 822             resize(2 * table.length);
 823             hash = (null != key) ? hash(key) : 0;
 824             bucketIndex = indexFor(hash, table.length);
 825         }
 826 
 827         createEntry(hash, key, value, bucketIndex);
 828     }
 829 
 830     /**
 831      * Like addEntry except that this version is used when creating entries
 832      * as part of Map construction or "pseudo-construction" (cloning,
 833      * deserialization).  This version needn't worry about resizing the table.
 834      *
 835      * Subclass overrides this to alter the behavior of HashMap(Map),
 836      * clone, and readObject.
 837      */
 838     void createEntry(int hash, K key, V value, int bucketIndex) {
 839         @SuppressWarnings("unchecked")
 840             Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
 841         table[bucketIndex] = new Entry<>(hash, key, value, e);
 842         size++;
 843     }
 844 
 845     private abstract class HashIterator<E> implements Iterator<E> {
 846         Entry<?,?> next;        // next entry to return
 847         int expectedModCount;   // For fast-fail
 848         int index;              // current slot
 849         Entry<?,?> current;     // current entry
 850 
 851         HashIterator() {
 852             expectedModCount = modCount;
 853             if (size > 0) { // advance to first entry
 854                 Entry<?,?>[] t = table;
 855                 while (index < t.length && (next = t[index++]) == null)
 856                     ;
 857             }
 858         }
 859 
 860         public final boolean hasNext() {
 861             return next != null;
 862         }
 863 
 864         @SuppressWarnings("unchecked")
 865         final Entry<K,V> nextEntry() {
 866             if (modCount != expectedModCount)
 867                 throw new ConcurrentModificationException();
 868             Entry<?,?> e = next;
 869             if (e == null)
 870                 throw new NoSuchElementException();
 871 
 872             if ((next = e.next) == null) {
 873                 Entry<?,?>[] t = table;
 874                 while (index < t.length && (next = t[index++]) == null)
 875                     ;
 876             }
 877             current = e;
 878             return (Entry<K,V>)e;
 879         }
 880 
 881         public void remove() {
 882             if (current == null)
 883                 throw new IllegalStateException();
 884             if (modCount != expectedModCount)
 885                 throw new ConcurrentModificationException();
 886             Object k = current.key;
 887             current = null;
 888             HashMap.this.removeEntryForKey(k);
 889             expectedModCount = modCount;
 890         }
 891     }
 892 
 893     private final class ValueIterator extends HashIterator<V> {
 894         public V next() {
 895             return nextEntry().value;
 896         }
 897     }
 898 
 899     private final class KeyIterator extends HashIterator<K> {
 900         public K next() {
 901             return nextEntry().getKey();
 902         }
 903     }
 904 
 905     private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
 906         public Map.Entry<K,V> next() {
 907             return nextEntry();
 908         }
 909     }
 910 
 911     // Subclass overrides these to alter behavior of views' iterator() method
 912     Iterator<K> newKeyIterator()   {
 913         return new KeyIterator();
 914     }
 915     Iterator<V> newValueIterator()   {
 916         return new ValueIterator();
 917     }
 918     Iterator<Map.Entry<K,V>> newEntryIterator()   {
 919         return new EntryIterator();
 920     }
 921 
 922 
 923     // Views
 924 
 925     private transient Set<Map.Entry<K,V>> entrySet = null;
 926 
 927     /**
 928      * Returns a {@link Set} view of the keys contained in this map.
 929      * The set is backed by the map, so changes to the map are
 930      * reflected in the set, and vice-versa.  If the map is modified
 931      * while an iteration over the set is in progress (except through
 932      * the iterator's own <tt>remove</tt> operation), the results of
 933      * the iteration are undefined.  The set supports element removal,
 934      * which removes the corresponding mapping from the map, via the
 935      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 936      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 937      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
 938      * operations.
 939      */
 940     public Set<K> keySet() {
 941         Set<K> ks = keySet;
 942         return (ks != null ? ks : (keySet = new KeySet()));
 943     }
 944 
 945     private final class KeySet extends AbstractSet<K> {
 946         public Iterator<K> iterator() {
 947             return newKeyIterator();
 948         }
 949         public int size() {
 950             return size;
 951         }
 952         public boolean contains(Object o) {
 953             return containsKey(o);
 954         }
 955         public boolean remove(Object o) {
 956             return HashMap.this.removeEntryForKey(o) != null;
 957         }
 958         public void clear() {
 959             HashMap.this.clear();
 960         }
 961     }
 962 
 963     /**
 964      * Returns a {@link Collection} view of the values contained in this map.
 965      * The collection is backed by the map, so changes to the map are
 966      * reflected in the collection, and vice-versa.  If the map is
 967      * modified while an iteration over the collection is in progress
 968      * (except through the iterator's own <tt>remove</tt> operation),
 969      * the results of the iteration are undefined.  The collection
 970      * supports element removal, which removes the corresponding
 971      * mapping from the map, via the <tt>Iterator.remove</tt>,
 972      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 973      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
 974      * support the <tt>add</tt> or <tt>addAll</tt> operations.
 975      */
 976     public Collection<V> values() {
 977         Collection<V> vs = values;
 978         return (vs != null ? vs : (values = new Values()));
 979     }
 980 
 981     private final class Values extends AbstractCollection<V> {
 982         public Iterator<V> iterator() {
 983             return newValueIterator();
 984         }
 985         public int size() {
 986             return size;
 987         }
 988         public boolean contains(Object o) {
 989             return containsValue(o);
 990         }
 991         public void clear() {
 992             HashMap.this.clear();
 993         }
 994     }
 995 
 996     /**
 997      * Returns a {@link Set} view of the mappings contained in this map.
 998      * The set is backed by the map, so changes to the map are
 999      * reflected in the set, and vice-versa.  If the map is modified
1000      * while an iteration over the set is in progress (except through
1001      * the iterator's own <tt>remove</tt> operation, or through the
1002      * <tt>setValue</tt> operation on a map entry returned by the
1003      * iterator) the results of the iteration are undefined.  The set
1004      * supports element removal, which removes the corresponding
1005      * mapping from the map, via the <tt>Iterator.remove</tt>,
1006      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
1007      * <tt>clear</tt> operations.  It does not support the
1008      * <tt>add</tt> or <tt>addAll</tt> operations.
1009      *
1010      * @return a set view of the mappings contained in this map
1011      */
1012     public Set<Map.Entry<K,V>> entrySet() {
1013         return entrySet0();
1014     }
1015 
1016     private Set<Map.Entry<K,V>> entrySet0() {
1017         Set<Map.Entry<K,V>> es = entrySet;
1018         return es != null ? es : (entrySet = new EntrySet());
1019     }
1020 
1021     private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1022         public Iterator<Map.Entry<K,V>> iterator() {
1023             return newEntryIterator();
1024         }
1025         public boolean contains(Object o) {
1026             if (!(o instanceof Map.Entry))
1027                 return false;
1028             Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1029             Entry<K,V> candidate = getEntry(e.getKey());
1030             return candidate != null && candidate.equals(e);
1031         }
1032         public boolean remove(Object o) {
1033             return removeMapping(o) != null;
1034         }
1035         public int size() {
1036             return size;
1037         }
1038         public void clear() {
1039             HashMap.this.clear();
1040         }
1041     }
1042 
1043     /**
1044      * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1045      * serialize it).
1046      *
1047      * @serialData The <i>capacity</i> of the HashMap (the length of the
1048      *             bucket array, a power of 2) is emitted (int), followed by the
1049      *             <i>size</i> (an int, the number of key-value
1050      *             mappings), followed by the key (Object) and value (Object)
1051      *             for each key-value mapping.  The key-value mappings are
1052      *             emitted in no particular order.
1053      */
1054     private void writeObject(java.io.ObjectOutputStream s)
1055         throws IOException
1056     {
1057         // Write out the threshold, loadfactor, and any hidden stuff
1058         s.defaultWriteObject();
1059 
1060         // Write out number of buckets
1061         if (table==EMPTY_TABLE) {
1062             s.writeInt(roundUpToPowerOf2(threshold));
1063         } else {
1064            s.writeInt(table.length);
1065         }
1066 
1067         // Write out size (number of Mappings)
1068         s.writeInt(size);
1069 
1070         // Write out keys and values (alternating)
1071         if (size > 0) {
1072             for(Map.Entry<K,V> e : entrySet0()) {
1073                 s.writeObject(e.getKey());
1074                 s.writeObject(e.getValue());
1075             }
1076         }
1077     }
1078 
1079     private static final long serialVersionUID = 362498820763181265L;
1080 
1081     /**
1082      * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1083      * deserialize it).
1084      */
1085     private void readObject(java.io.ObjectInputStream s)
1086          throws IOException, ClassNotFoundException
1087     {
1088         // Read in the threshold (ignored), loadfactor, and any hidden stuff
1089         s.defaultReadObject();
1090         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
1091             throw new InvalidObjectException("Illegal load factor: " +
1092                                                loadFactor);
1093         }
1094 
1095         // set hashMask
1096         Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1097                 sun.misc.Hashing.randomHashSeed(this));
1098 
1099         // Read in number of buckets and allocate the bucket array;
1100         table = EMPTY_TABLE;
1101 
1102         int buckets = s.readInt();
1103 
1104         if ((buckets < 0) || // negative
1105             (buckets > HashMap.MAXIMUM_CAPACITY) || // too big
1106             (Integer.bitCount(buckets) > 1)) /* not power of 2 or zero */ {
1107             throw new InvalidObjectException("Illegal capacity: " + buckets);
1108         }
1109 
1110         // Read number of mappings
1111         int mappings = s.readInt();
1112         if (mappings < 0)
1113             throw new InvalidObjectException("Illegal mappings count: " +
1114                                                mappings);
1115 
1116         int mappingsCapacity = Math.max(
1117                 (int) Math.min(
1118                     // capacity chosen by number of mappings
1119                     // and desired load (if >= 0.25)
1120                     mappings * Math.min(1 / loadFactor, 4.0f),
1121                     // we have limits...
1122                     HashMap.MAXIMUM_CAPACITY),
1123                 // maybe they want extra buckets.
1124                 buckets);
1125 
1126         if (mappings > 0) {
1127             inflateTable(mappingsCapacity);
1128         } else {
1129             threshold = mappingsCapacity;
1130         }
1131 
1132         init();  // Give subclass a chance to do its thing.
1133 
1134         // Read the keys and values, and put the mappings in the HashMap
1135         for (int i=0; i<mappings; i++) {
1136             @SuppressWarnings("unchecked")
1137                 K key = (K) s.readObject();
1138             @SuppressWarnings("unchecked")
1139                 V value = (V) s.readObject();
1140             putForCreate(key, value);
1141         }
1142     }
1143 
1144     // These methods are used when serializing HashSets
1145     int   capacity()     { return table.length; }
1146     float loadFactor()   { return loadFactor;   }
1147 }