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