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