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