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