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