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