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