libcore/luni/src/main/java/java/util/HashMap.java

   1 /*
   2  *  Licensed to the Apache Software Foundation (ASF) under one or more
   3  *  contributor license agreements. See the NOTICE file distributed with
   4  *  this work for additional information regarding copyright ownership.
   5  *  The ASF licenses this file to You under the Apache License, Version 2.0
   6  *  (the "License"); you may not use this file except in compliance with
   7  *  the License. You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  *  Unless required by applicable law or agreed to in writing, software
  12  *  distributed under the License is distributed on an "AS IS" BASIS,
  13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  *  See the License for the specific language governing permissions and
  15  *  limitations under the License.
  16  */
  17
  18 // BEGIN android-note
  19 // Completely different implementation from harmony.  Runs much faster.
  20 // BEGIN android-note
  21
  22 package java.util;
  23
  24 import java.io.IOException;
  25 import java.io.InvalidObjectException;
  26 import java.io.ObjectInputStream;
  27 import java.io.ObjectOutputStream;
  28 import java.io.ObjectStreamField;
  29 import java.io.Serializable;
  30 import libcore.base.Objects;
  31
  32 /**
  33  * HashMap is an implementation of {@link Map}. All optional operations are supported.
  34  *
  35  * <p>All elements are permitted as keys or values, including null.
  36  *
  37  * <p>Note that the iteration order for HashMap is non-deterministic. If you want
  38  * deterministic iteration, use {@link LinkedHashMap}.
  39  *
  40  * <p>Note: the implementation of {@code HashMap} is not synchronized.
  41  * If one thread of several threads accessing an instance modifies the map
  42  * structurally, access to the map needs to be synchronized. A structural
  43  * modification is an operation that adds or removes an entry. Changes in
  44  * the value of an entry are not structural changes.
  45  *
  46  * <p>The {@code Iterator} created by calling the {@code iterator} method
  47  * may throw a {@code ConcurrentModificationException} if the map is structurally
  48  * changed while an iterator is used to iterate over the elements. Only the
  49  * {@code remove} method that is provided by the iterator allows for removal of
  50  * elements during iteration. It is not possible to guarantee that this
  51  * mechanism works in all cases of unsynchronized concurrent modification. It
  52  * should only be used for debugging purposes.
  53  *
  54  * @param <K> the type of keys maintained by this map
  55  * @param <V> the type of mapped values
  56  */
  57 public class HashMap<K, V> extends AbstractMap<K, V> implements Cloneable, Serializable {
  58     /**
  59      * Min capacity (other than zero) for a HashMap. Must be a power of two
  60      * greater than 1 (and less than 1 << 30).
  61      */
  62     private static final int MINIMUM_CAPACITY = 4;
  63
  64     /**
  65      * Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY.
  66      */
  67     private static final int MAXIMUM_CAPACITY = 1 << 30;
  68
  69     /**
  70      * An empty table shared by all zero-capacity maps (typically from default
  71      * constructor). It is never written to, and replaced on first put. Its size
  72      * is set to half the minimum, so that the first resize will create a
  73      * minimum-sized table.
  74      */
  75     private static final Entry[] EMPTY_TABLE
  76             = new HashMapEntry[MINIMUM_CAPACITY >>> 1];
  77
  78     /**
  79      * The default load factor. Note that this implementation ignores the
  80      * load factor, but cannot do away with it entirely because it's
  81      * mentioned in the API.
  82      *
  83      * <p>Note that this constant has no impact on the behavior of the program,
  84      * but it is emitted as part of the serialized form. The load factor of
  85      * .75 is hardwired into the program, which uses cheap shifts in place of
  86      * expensive division.
  87      */
  88     static final float DEFAULT_LOAD_FACTOR = .75F;
  89
  90     /**
  91      * The hash table. If this hash map contains a mapping for null, it is
  92      * not represented this hash table.
  93      */
  94     transient HashMapEntry<K, V>[] table;
  95
  96     /**
  97      * The entry representing the null key, or null if there's no such mapping.
  98      */
  99     transient HashMapEntry<K, V> entryForNullKey;
 100
 101     /**
 102      * The number of mappings in this hash map.
 103      */
 104     transient int size;
 105
 106     /**
 107      * Incremented by "structural modifications" to allow (best effort)
 108      * detection of concurrent modification.
 109      */
 110     transient int modCount;
 111
 112     /**
 113      * The table is rehashed when its size exceeds this threshold.
 114      * The value of this field is generally .75 * capacity, except when
 115      * the capacity is zero, as described in the EMPTY_TABLE declaration
 116      * above.
 117      */
 118     private transient int threshold;
 119
 120     // Views - lazily initialized
 121     private transient Set<K> keySet;
 122     private transient Set<Entry<K, V>> entrySet;
 123     private transient Collection<V> values;
 124
 125     /**
 126      * Constructs a new empty {@code HashMap} instance.
 127      */
 128     @SuppressWarnings("unchecked")
 129     public HashMap() {
 130         table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
 131         threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
 132     }
 133
 134     /**
 135      * Constructs a new {@code HashMap} instance with the specified capacity.
 136      *
 137      * @param capacity
 138      *            the initial capacity of this hash map.
 139      * @throws IllegalArgumentException
 140      *                when the capacity is less than zero.
 141      */
 142     public HashMap(int capacity) {
 143         if (capacity < 0) {
 144             throw new IllegalArgumentException("Capacity: " + capacity);
 145         }
 146
 147         if (capacity == 0) {
 148             @SuppressWarnings("unchecked")
 149             HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
 150             table = tab;
 151             threshold = -1; // Forces first put() to replace EMPTY_TABLE
 152             return;
 153         }
 154
 155         if (capacity < MINIMUM_CAPACITY) {
 156             capacity = MINIMUM_CAPACITY;
 157         } else if (capacity > MAXIMUM_CAPACITY) {
 158             capacity = MAXIMUM_CAPACITY;
 159         } else {
 160             capacity = roundUpToPowerOfTwo(capacity);
 161         }
 162         makeTable(capacity);
 163     }
 164
 165     /**
 166      * Constructs a new {@code HashMap} instance with the specified capacity and
 167      * load factor.
 168      *
 169      * @param capacity
 170      *            the initial capacity of this hash map.
 171      * @param loadFactor
 172      *            the initial load factor.
 173      * @throws IllegalArgumentException
 174      *                when the capacity is less than zero or the load factor is
 175      *                less or equal to zero or NaN.
 176      */
 177     public HashMap(int capacity, float loadFactor) {
 178         this(capacity);
 179
 180         if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
 181             throw new IllegalArgumentException("Load factor: " + loadFactor);
 182         }
 183
 184         /*
 185          * Note that this implementation ignores loadFactor; it always uses
 186          * a load factor of 3/4. This simplifies the code and generally
 187          * improves performance.
 188          */
 189     }
 190
 191     /**
 192      * Constructs a new {@code HashMap} instance containing the mappings from
 193      * the specified map.
 194      *
 195      * @param map
 196      *            the mappings to add.
 197      */
 198     public HashMap(Map<? extends K, ? extends V> map) {
 199         this(capacityForInitSize(map.size()));
 200         constructorPutAll(map);
 201     }
 202
 203     /**
 204      * Inserts all of the elements of map into this HashMap in a manner
 205      * suitable for use by constructors and pseudo-constructors (i.e., clone,
 206      * readObject). Also used by LinkedHashMap.
 207      */
 208     final void constructorPutAll(Map<? extends K, ? extends V> map) {
 209         for (Entry<? extends K, ? extends V> e : map.entrySet()) {
 210             constructorPut(e.getKey(), e.getValue());
 211         }
 212     }
 213
 214     /**
 215      * Returns an appropriate capacity for the specified initial size. Does
 216      * not round the result up to a power of two; the caller must do this!
 217      * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive).
 218      */
 219     static int capacityForInitSize(int size) {
 220         int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth
 221
 222         // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY
 223         return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY;
 224     }
 225
 226     /**
 227      * Returns a shallow copy of this map.
 228      *
 229      * @return a shallow copy of this map.
 230      */
 231     @SuppressWarnings("unchecked")
 232     @Override public Object clone() {
 233         /*
 234          * This could be made more efficient. It unnecessarily hashes all of
 235          * the elements in the map.
 236          */
 237         HashMap<K, V> result;
 238         try {
 239             result = (HashMap<K, V>) super.clone();
 240         } catch (CloneNotSupportedException e) {
 241             throw new AssertionError(e);
 242         }
 243
 244         // Restore clone to empty state, retaining our capacity and threshold
 245         result.makeTable(table.length);
 246         result.entryForNullKey = null;
 247         result.size = 0;
 248         result.keySet = null;
 249         result.entrySet = null;
 250         result.values = null;
 251
 252         result.init(); // Give subclass a chance to initialize itself
 253         result.constructorPutAll(this); // Calls method overridden in subclass!!
 254         return result;
 255     }
 256
 257     /**
 258      * This method is called from the pseudo-constructors (clone and readObject)
 259      * prior to invoking constructorPut/constructorPutAll, which invoke the
 260      * overridden constructorNewEntry method. Normally it is a VERY bad idea to
 261      * invoke an overridden method from a pseudo-constructor (Effective Java
 262      * Item 17). In this case it is unavoidable, and the init method provides a
 263      * workaround.
 264      */
 265     void init() { }
 266
 267     /**
 268      * Returns whether this map is empty.
 269      *
 270      * @return {@code true} if this map has no elements, {@code false}
 271      *         otherwise.
 272      * @see #size()
 273      */
 274     @Override public boolean isEmpty() {
 275         return size == 0;
 276     }
 277
 278     /**
 279      * Returns the number of elements in this map.
 280      *
 281      * @return the number of elements in this map.
 282      */
 283     @Override public int size() {
 284         return size;
 285     }
 286
 287     /**
 288      * Returns the value of the mapping with the specified key.
 289      *
 290      * @param key
 291      *            the key.
 292      * @return the value of the mapping with the specified key, or {@code null}
 293      *         if no mapping for the specified key is found.
 294      */
 295     public V get(Object key) {
 296         if (key == null) {
 297             HashMapEntry<K, V> e = entryForNullKey;
 298             return e == null ? null : e.value;
 299         }
 300
 301         // Doug Lea's supplemental secondaryHash function (inlined)
 302         int hash = key.hashCode();
 303         hash ^= (hash >>> 20) ^ (hash >>> 12);
 304         hash ^= (hash >>> 7) ^ (hash >>> 4);
 305
 306         HashMapEntry<K, V>[] tab = table;
 307         for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
 308                 e != null; e = e.next) {
 309             K eKey = e.key;
 310             if (eKey == key || (e.hash == hash && key.equals(eKey))) {
 311                 return e.value;
 312             }
 313         }
 314         return null;
 315     }
 316
 317     /**
 318      * Returns whether this map contains the specified key.
 319      *
 320      * @param key
 321      *            the key to search for.
 322      * @return {@code true} if this map contains the specified key,
 323      *         {@code false} otherwise.
 324      */
 325     @Override public boolean containsKey(Object key) {
 326         if (key == null) {
 327             return entryForNullKey != null;
 328         }
 329
 330         // Doug Lea's supplemental secondaryHash function (inlined)
 331         int hash = key.hashCode();
 332         hash ^= (hash >>> 20) ^ (hash >>> 12);
 333         hash ^= (hash >>> 7) ^ (hash >>> 4);
 334
 335         HashMapEntry<K, V>[] tab = table;
 336         for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
 337                 e != null; e = e.next) {
 338             K eKey = e.key;
 339             if (eKey == key || (e.hash == hash && key.equals(eKey))) {
 340                 return true;
 341             }
 342         }
 343         return false;
 344     }
 345
 346     /**
 347      * Returns whether this map contains the specified value.
 348      *
 349      * @param value
 350      *            the value to search for.
 351      * @return {@code true} if this map contains the specified value,
 352      *         {@code false} otherwise.
 353      */
 354     @Override public boolean containsValue(Object value) {
 355         HashMapEntry[] tab = table;
 356         int len = tab.length;
 357         if (value == null) {
 358             for (int i = 0; i < len; i++) {
 359                 for (HashMapEntry e = tab[i]; e != null; e = e.next) {
 360                     if (e.value == null) {
 361                         return true;
 362                     }
 363                 }
 364             }
 365             return entryForNullKey != null && entryForNullKey.value == null;
 366         }
 367
 368         // value is non-null
 369         for (int i = 0; i < len; i++) {
 370             for (HashMapEntry e = tab[i]; e != null; e = e.next) {
 371                 if (value.equals(e.value)) {
 372                     return true;
 373                 }
 374             }
 375         }
 376         return entryForNullKey != null && value.equals(entryForNullKey.value);
 377     }
 378
 379     /**
 380      * Maps the specified key to the specified value.
 381      *
 382      * @param key
 383      *            the key.
 384      * @param value
 385      *            the value.
 386      * @return the value of any previous mapping with the specified key or
 387      *         {@code null} if there was no such mapping.
 388      */
 389     @Override public V put(K key, V value) {
 390         if (key == null) {
 391             return putValueForNullKey(value);
 392         }
 393
 394         int hash = secondaryHash(key.hashCode());
 395         HashMapEntry<K, V>[] tab = table;
 396         int index = hash & (tab.length - 1);
 397         for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
 398             if (e.hash == hash && key.equals(e.key)) {
 399                 preModify(e);
 400                 V oldValue = e.value;
 401                 e.value = value;
 402                 return oldValue;
 403             }
 404         }
 405
 406         // No entry for (non-null) key is present; create one
 407         modCount++;
 408         if (size++ > threshold) {
 409             tab = doubleCapacity();
 410             index = hash & (tab.length - 1);
 411         }
 412         addNewEntry(key, value, hash, index);
 413         return null;
 414     }
 415
 416     private V putValueForNullKey(V value) {
 417         HashMapEntry<K, V> entry = entryForNullKey;
 418         if (entry == null) {
 419             addNewEntryForNullKey(value);
 420             size++;
 421             modCount++;
 422             return null;
 423         } else {
 424             preModify(entry);
 425             V oldValue = entry.value;
 426             entry.value = value;
 427             return oldValue;
 428         }
 429     }
 430
 431     /**
 432      * Give LinkedHashMap a chance to take action when we modify an existing
 433      * entry.
 434      *
 435      * @param e the entry we're about to modify.
 436      */
 437     void preModify(HashMapEntry<K, V> e) { }
 438
 439     /**
 440      * This method is just like put, except that it doesn't do things that
 441      * are inappropriate or unnecessary for constructors and pseudo-constructors
 442      * (i.e., clone, readObject). In particular, this method does not check to
 443      * ensure that capacity is sufficient, and does not increment modCount.
 444      */
 445     private void constructorPut(K key, V value) {
 446         if (key == null) {
 447             HashMapEntry<K, V> entry = entryForNullKey;
 448             if (entry == null) {
 449                 entryForNullKey = constructorNewEntry(null, value, 0, null);
 450                 size++;
 451             } else {
 452                 entry.value = value;
 453             }
 454             return;
 455         }
 456
 457         int hash = secondaryHash(key.hashCode());
 458         HashMapEntry<K, V>[] tab = table;
 459         int index = hash & (tab.length - 1);
 460         HashMapEntry<K, V> first = tab[index];
 461         for (HashMapEntry<K, V> e = first; e != null; e = e.next) {
 462             if (e.hash == hash && key.equals(e.key)) {
 463                 e.value = value;
 464                 return;
 465             }
 466         }
 467
 468         // No entry for (non-null) key is present; create one
 469         tab[index] = constructorNewEntry(key, value, hash, first);
 470         size++;
 471     }
 472
 473     /**
 474      * Creates a new entry for the given key, value, hash, and index and
 475      * inserts it into the hash table. This method is called by put
 476      * (and indirectly, putAll), and overridden by LinkedHashMap. The hash
 477      * must incorporate the secondary hash function.
 478      */
 479     void addNewEntry(K key, V value, int hash, int index) {
 480         table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
 481     }
 482
 483     /**
 484      * Creates a new entry for the null key, and the given value and
 485      * inserts it into the hash table. This method is called by put
 486      * (and indirectly, putAll), and overridden by LinkedHashMap.
 487      */
 488     void addNewEntryForNullKey(V value) {
 489         entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
 490     }
 491
 492     /**
 493      * Like newEntry, but does not perform any activity that would be
 494      * unnecessary or inappropriate for constructors. In this class, the
 495      * two methods behave identically; in LinkedHashMap, they differ.
 496      */
 497     HashMapEntry<K, V> constructorNewEntry(
 498             K key, V value, int hash, HashMapEntry<K, V> first) {
 499         return new HashMapEntry<K, V>(key, value, hash, first);
 500     }
 501
 502     /**
 503      * Copies all the mappings in the specified map to this map. These mappings
 504      * will replace all mappings that this map had for any of the keys currently
 505      * in the given map.
 506      *
 507      * @param map
 508      *            the map to copy mappings from.
 509      */
 510     @Override public void putAll(Map<? extends K, ? extends V> map) {
 511         ensureCapacity(map.size());
 512         super.putAll(map);
 513     }
 514
 515     /**
 516      * Ensures that the hash table has sufficient capacity to store the
 517      * specified number of mappings, with room to grow. If not, it increases the
 518      * capacity as appropriate. Like doubleCapacity, this method moves existing
 519      * entries to new buckets as appropriate. Unlike doubleCapacity, this method
 520      * can grow the table by factors of 2^n for n > 1. Hopefully, a single call
 521      * to this method will be faster than multiple calls to doubleCapacity.
 522      *
 523      *  <p>This method is called only by putAll.
 524      */
 525     private void ensureCapacity(int numMappings) {
 526         int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings));
 527         HashMapEntry<K, V>[] oldTable = table;
 528         int oldCapacity = oldTable.length;
 529         if (newCapacity <= oldCapacity) {
 530             return;
 531         }
 532         if (newCapacity == oldCapacity << 1) {
 533             doubleCapacity();
 534             return;
 535         }
 536
 537         // We're growing by at least 4x, rehash in the obvious way
 538         HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
 539         if (size != 0) {
 540             int newMask = newCapacity - 1;
 541             for (int i = 0; i < oldCapacity; i++) {
 542                 for (HashMapEntry<K, V> e = oldTable[i]; e != null;) {
 543                     HashMapEntry<K, V> oldNext = e.next;
 544                     int newIndex = e.hash & newMask;
 545                     HashMapEntry<K, V> newNext = newTable[newIndex];
 546                     newTable[newIndex] = e;
 547                     e.next = newNext;
 548                     e = oldNext;
 549                 }
 550             }
 551         }
 552     }
 553
 554     /**
 555      * Allocate a table of the given capacity and set the threshold accordingly.
 556      * @param newCapacity must be a power of two
 557      */
 558     private HashMapEntry<K, V>[] makeTable(int newCapacity) {
 559         @SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
 560                 = (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];
 561         table = newTable;
 562         threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
 563         return newTable;
 564     }
 565
 566     /**
 567      * Doubles the capacity of the hash table. Existing entries are placed in
 568      * the correct bucket on the enlarged table. If the current capacity is,
 569      * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which
 570      * will be new unless we were already at MAXIMUM_CAPACITY.
 571      */
 572     private HashMapEntry<K, V>[] doubleCapacity() {
 573         HashMapEntry<K, V>[] oldTable = table;
 574         int oldCapacity = oldTable.length;
 575         if (oldCapacity == MAXIMUM_CAPACITY) {
 576             return oldTable;
 577         }
 578         int newCapacity = oldCapacity << 1;
 579         HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
 580         if (size == 0) {
 581             return newTable;
 582         }
 583
 584         for (int j = 0; j < oldCapacity; j++) {
 585             /*
 586              * Rehash the bucket using the minimum number of field writes.
 587              * This is the most subtle and delicate code in the class.
 588              */
 589             HashMapEntry<K, V> e = oldTable[j];
 590             if (e == null) {
 591                 continue;
 592             }
 593             int highBit = e.hash & oldCapacity;
 594             HashMapEntry<K, V> broken = null;
 595             newTable[j | highBit] = e;
 596             for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
 597                 int nextHighBit = n.hash & oldCapacity;
 598                 if (nextHighBit != highBit) {
 599                     if (broken == null)
 600                         newTable[j | nextHighBit] = n;
 601                     else
 602                         broken.next = n;
 603                     broken = e;
 604                     highBit = nextHighBit;
 605                 }
 606             }
 607             if (broken != null)
 608                 broken.next = null;
 609         }
 610         return newTable;
 611     }
 612
 613     /**
 614      * Removes the mapping with the specified key from this map.
 615      *
 616      * @param key
 617      *            the key of the mapping to remove.
 618      * @return the value of the removed mapping or {@code null} if no mapping
 619      *         for the specified key was found.
 620      */
 621     @Override public V remove(Object key) {
 622         if (key == null) {
 623             return removeNullKey();
 624         }
 625         int hash = secondaryHash(key.hashCode());
 626         HashMapEntry<K, V>[] tab = table;
 627         int index = hash & (tab.length - 1);
 628         for (HashMapEntry<K, V> e = tab[index], prev = null;
 629                 e != null; prev = e, e = e.next) {
 630             if (e.hash == hash && key.equals(e.key)) {
 631                 if (prev == null) {
 632                     tab[index] = e.next;
 633                 } else {
 634                     prev.next = e.next;
 635                 }
 636                 modCount++;
 637                 size--;
 638                 postRemove(e);
 639                 return e.value;
 640             }
 641         }
 642         return null;
 643     }
 644
 645     private V removeNullKey() {
 646         HashMapEntry<K, V> e = entryForNullKey;
 647         if (e == null) {
 648             return null;
 649         }
 650         entryForNullKey = null;
 651         modCount++;
 652         size--;
 653         postRemove(e);
 654         return e.value;
 655     }
 656
 657     /**
 658      * Subclass overrides this method to unlink entry.
 659      */
 660     void postRemove(HashMapEntry<K, V> e) { }
 661
 662     /**
 663      * Removes all mappings from this hash map, leaving it empty.
 664      *
 665      * @see #isEmpty
 666      * @see #size
 667      */
 668     @Override public void clear() {
 669         if (size != 0) {
 670             Arrays.fill(table, null);
 671             entryForNullKey = null;
 672             modCount++;
 673             size = 0;
 674         }
 675     }
 676
 677     /**
 678      * Returns a set of the keys contained in this map. The set is backed by
 679      * this map so changes to one are reflected by the other. The set does not
 680      * support adding.
 681      *
 682      * @return a set of the keys.
 683      */
 684     @Override public Set<K> keySet() {
 685         Set<K> ks = keySet;
 686         return (ks != null) ? ks : (keySet = new KeySet());
 687     }
 688
 689     /**
 690      * Returns a collection of the values contained in this map. The collection
 691      * is backed by this map so changes to one are reflected by the other. The
 692      * collection supports remove, removeAll, retainAll and clear operations,
 693      * and it does not support add or addAll operations.
 694      * <p>
 695      * This method returns a collection which is the subclass of
 696      * AbstractCollection. The iterator method of this subclass returns a
 697      * "wrapper object" over the iterator of map's entrySet(). The {@code size}
 698      * method wraps the map's size method and the {@code contains} method wraps
 699      * the map's containsValue method.
 700      * </p>
 701      * <p>
 702      * The collection is created when this method is called for the first time
 703      * and returned in response to all subsequent calls. This method may return
 704      * different collections when multiple concurrent calls occur, since no
 705      * synchronization is performed.
 706      * </p>
 707      *
 708      * @return a collection of the values contained in this map.
 709      */
 710     @Override public Collection<V> values() {
 711         Collection<V> vs = values;
 712         return (vs != null) ? vs : (values = new Values());
 713     }
 714
 715     /**
 716      * Returns a set containing all of the mappings in this map. Each mapping is
 717      * an instance of {@link Map.Entry}. As the set is backed by this map,
 718      * changes in one will be reflected in the other.
 719      *
 720      * @return a set of the mappings.
 721      */
 722     public Set<Entry<K, V>> entrySet() {
 723         Set<Entry<K, V>> es = entrySet;
 724         return (es != null) ? es : (entrySet = new EntrySet());
 725     }
 726
 727     static class HashMapEntry<K, V> implements Entry<K, V> {
 728         final K key;
 729         V value;
 730         final int hash;
 731         HashMapEntry<K, V> next;
 732
 733         HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
 734             this.key = key;
 735             this.value = value;
 736             this.hash = hash;
 737             this.next = next;
 738         }
 739
 740         public final K getKey() {
 741             return key;
 742         }
 743
 744         public final V getValue() {
 745             return value;
 746         }
 747
 748         public final V setValue(V value) {
 749             V oldValue = this.value;
 750             this.value = value;
 751             return oldValue;
 752         }
 753
 754         @Override public final boolean equals(Object o) {
 755             if (!(o instanceof Entry)) {
 756                 return false;
 757             }
 758             Entry<?, ?> e = (Entry<?, ?>) o;
 759             return Objects.equal(e.getKey(), key)
 760                     && Objects.equal(e.getValue(), value);
 761         }
 762
 763         @Override public final int hashCode() {
 764             return (key == null ? 0 : key.hashCode()) ^
 765                     (value == null ? 0 : value.hashCode());
 766         }
 767
 768         @Override public final String toString() {
 769             return key + "=" + value;
 770         }
 771     }
 772
 773     private abstract class HashIterator {
 774         int nextIndex;
 775         HashMapEntry<K, V> nextEntry = entryForNullKey;
 776         HashMapEntry<K, V> lastEntryReturned;
 777         int expectedModCount = modCount;
 778
 779         HashIterator() {
 780             if (nextEntry == null) {
 781                 HashMapEntry<K, V>[] tab = table;
 782                 HashMapEntry<K, V> next = null;
 783                 while (next == null && nextIndex < tab.length) {
 784                     next = tab[nextIndex++];
 785                 }
 786                 nextEntry = next;
 787             }
 788         }
 789
 790         public boolean hasNext() {
 791             return nextEntry != null;
 792         }
 793
 794         HashMapEntry<K, V> nextEntry() {
 795             if (modCount != expectedModCount)
 796                 throw new ConcurrentModificationException();
 797             if (nextEntry == null)
 798                 throw new NoSuchElementException();
 799
 800             HashMapEntry<K, V> entryToReturn = nextEntry;
 801             HashMapEntry<K, V>[] tab = table;
 802             HashMapEntry<K, V> next = entryToReturn.next;
 803             while (next == null && nextIndex < tab.length) {
 804                 next = tab[nextIndex++];
 805             }
 806             nextEntry = next;
 807             return lastEntryReturned = entryToReturn;
 808         }
 809
 810         public void remove() {
 811             if (lastEntryReturned == null)
 812                 throw new IllegalStateException();
 813             if (modCount != expectedModCount)
 814                 throw new ConcurrentModificationException();
 815             HashMap.this.remove(lastEntryReturned.key);
 816             lastEntryReturned = null;
 817             expectedModCount = modCount;
 818         }
 819     }
 820
 821     private final class KeyIterator extends HashIterator
 822             implements Iterator<K> {
 823         public K next() { return nextEntry().key; }
 824     }
 825
 826     private final class ValueIterator extends HashIterator
 827             implements Iterator<V> {
 828         public V next() { return nextEntry().value; }
 829     }
 830
 831     private final class EntryIterator extends HashIterator
 832             implements Iterator<Entry<K, V>> {
 833         public Entry<K, V> next() { return nextEntry(); }
 834     }
 835
 836     /**
 837      * Returns true if this map contains the specified mapping.
 838      */
 839     private boolean containsMapping(Object key, Object value) {
 840         if (key == null) {
 841             HashMapEntry<K, V> e = entryForNullKey;
 842             return e != null && Objects.equal(value, e.value);
 843         }
 844
 845         int hash = secondaryHash(key.hashCode());
 846         HashMapEntry<K, V>[] tab = table;
 847         int index = hash & (tab.length - 1);
 848         for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
 849             if (e.hash == hash && key.equals(e.key)) {
 850                 return Objects.equal(value, e.value);
 851             }
 852         }
 853         return false; // No entry for key
 854     }
 855
 856     /**
 857      * Removes the mapping from key to value and returns true if this mapping
 858      * exists; otherwise, returns does nothing and returns false.
 859      */
 860     private boolean removeMapping(Object key, Object value) {
 861         if (key == null) {
 862             HashMapEntry<K, V> e = entryForNullKey;
 863             if (e == null || !Objects.equal(value, e.value)) {
 864                 return false;
 865             }
 866             entryForNullKey = null;
 867             modCount++;
 868             size--;
 869             postRemove(e);
 870             return true;
 871         }
 872
 873         int hash = secondaryHash(key.hashCode());
 874         HashMapEntry<K, V>[] tab = table;
 875         int index = hash & (tab.length - 1);
 876         for (HashMapEntry<K, V> e = tab[index], prev = null;
 877                 e != null; prev = e, e = e.next) {
 878             if (e.hash == hash && key.equals(e.key)) {
 879                 if (!Objects.equal(value, e.value)) {
 880                     return false;  // Map has wrong value for key
 881                 }
 882                 if (prev == null) {
 883                     tab[index] = e.next;
 884                 } else {
 885                     prev.next = e.next;
 886                 }
 887                 modCount++;
 888                 size--;
 889                 postRemove(e);
 890                 return true;
 891             }
 892         }
 893         return false; // No entry for key
 894     }
 895
 896     // Subclass (LinkedHashMap) overrides these for correct iteration order
 897     Iterator<K> newKeyIterator() { return new KeyIterator();   }
 898     Iterator<V> newValueIterator() { return new ValueIterator(); }
 899     Iterator<Entry<K, V>> newEntryIterator() { return new EntryIterator(); }
 900
 901     private final class KeySet extends AbstractSet<K> {
 902         public Iterator<K> iterator() {
 903             return newKeyIterator();
 904         }
 905         public int size() {
 906             return size;
 907         }
 908         public boolean isEmpty() {
 909             return size == 0;
 910         }
 911         public boolean contains(Object o) {
 912             return containsKey(o);
 913         }
 914         public boolean remove(Object o) {
 915             int oldSize = size;
 916             HashMap.this.remove(o);
 917             return size != oldSize;
 918         }
 919         public void clear() {
 920             HashMap.this.clear();
 921         }
 922     }
 923
 924     private final class Values extends AbstractCollection<V> {
 925         public Iterator<V> iterator() {
 926             return newValueIterator();
 927         }
 928         public int size() {
 929             return size;
 930         }
 931         public boolean isEmpty() {
 932             return size == 0;
 933         }
 934         public boolean contains(Object o) {
 935             return containsValue(o);
 936         }
 937         public void clear() {
 938             HashMap.this.clear();
 939         }
 940     }
 941
 942     private final class EntrySet extends AbstractSet<Entry<K, V>> {
 943         public Iterator<Entry<K, V>> iterator() {
 944             return newEntryIterator();
 945         }
 946         public boolean contains(Object o) {
 947             if (!(o instanceof Entry))
 948                 return false;
 949             Entry<?, ?> e = (Entry<?, ?>) o;
 950             return containsMapping(e.getKey(), e.getValue());
 951         }
 952         public boolean remove(Object o) {
 953             if (!(o instanceof Entry))
 954                 return false;
 955             Entry<?, ?> e = (Entry<?, ?>)o;
 956             return removeMapping(e.getKey(), e.getValue());
 957         }
 958         public int size() {
 959             return size;
 960         }
 961         public boolean isEmpty() {
 962             return size == 0;
 963         }
 964         public void clear() {
 965             HashMap.this.clear();
 966         }
 967     }
 968
 969     /**
 970      * Applies a supplemental hash function to a given hashCode, which defends
 971      * against poor quality hash functions. This is critical because HashMap
 972      * uses power-of-two length hash tables, that otherwise encounter collisions
 973      * for hashCodes that do not differ in lower or upper bits.
 974      */
 975     private static int secondaryHash(int h) {
 976         // Doug Lea's supplemental hash function
 977         h ^= (h >>> 20) ^ (h >>> 12);
 978         return h ^ (h >>> 7) ^ (h >>> 4);
 979     }
 980
 981     /**
 982      * Returns the smallest power of two >= its argument, with several caveats:
 983      * If the argument is negative but not Integer.MIN_VALUE, the method returns
 984      * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method
 985      * returns Integer.MIN_VALUE. If the argument is zero, the method returns
 986      * zero.
 987      */
 988     private static int roundUpToPowerOfTwo(int i) {
 989         i--; // If input is a power of two, shift its high-order bit right
 990
 991         // "Smear" the high-order bit all the way to the right
 992         i |= i >>>  1;
 993         i |= i >>>  2;
 994         i |= i >>>  4;
 995         i |= i >>>  8;
 996         i |= i >>> 16;
 997
 998         return i + 1;
 999     }
1000
1001     private static final long serialVersionUID = 362498820763181265L;
1002
1003     /**
1004      * Serializable fields.
1005      *
1006      * @serialField loadFactor float
1007      *              load factor for this HashMap
1008      */
1009     private static final ObjectStreamField[] serialPersistentFields = {
1010         new ObjectStreamField("loadFactor", Float.TYPE)
1011     };
1012
1013     private void writeObject(ObjectOutputStream stream) throws IOException {
1014         // Emulate loadFactor field for other implementations to read
1015         ObjectOutputStream.PutField fields = stream.putFields();
1016         fields.put("loadFactor", DEFAULT_LOAD_FACTOR);
1017         stream.writeFields();
1018
1019         stream.writeInt(table.length); // Capacity
1020         stream.writeInt(size);
1021         for (Entry<K, V> e : entrySet()) {
1022             stream.writeObject(e.getKey());
1023             stream.writeObject(e.getValue());
1024         }
1025     }
1026
1027     private void readObject(ObjectInputStream stream) throws IOException,
1028             ClassNotFoundException {
1029         stream.defaultReadObject();
1030         int capacity = stream.readInt();
1031         if (capacity < 0) {
1032             throw new InvalidObjectException("Capacity: " + capacity);
1033         }
1034         if (capacity < MINIMUM_CAPACITY) {
1035             capacity = MINIMUM_CAPACITY;
1036         } else if (capacity > MAXIMUM_CAPACITY) {
1037             capacity = MAXIMUM_CAPACITY;
1038         } else {
1039             capacity = roundUpToPowerOfTwo(capacity);
1040         }
1041         makeTable(capacity);
1042
1043         int size = stream.readInt();
1044         if (size < 0) {
1045             throw new InvalidObjectException("Size: " + size);
1046         }
1047
1048         init(); // Give subclass (LinkedHashMap) a chance to initialize itself
1049         for (int i = 0; i < size; i++) {
1050             @SuppressWarnings("unchecked") K key = (K) stream.readObject();
1051             @SuppressWarnings("unchecked") V val = (V) stream.readObject();
1052             constructorPut(key, val);
1053         }
1054     }
1055 }