1 /* 2 * Copyright (C) 2014 The Android Open Source Project 3 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. Oracle designates this 9 * particular file as subject to the "Classpath" exception as provided 10 * by Oracle in the LICENSE file that accompanied this code. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 23 * or visit www.oracle.com if you need additional information or have any 24 * questions. 25 */ 26 27 package java.util; 28 29 import java.io.*; 30 import java.util.function.BiFunction; 31 import java.util.function.Consumer; 32 import java.util.function.BiConsumer; 33 34 /** 35 * Hash table based implementation of the <tt>Map</tt> interface. This 36 * implementation provides all of the optional map operations, and permits 37 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt> 38 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is 39 * unsynchronized and permits nulls.) This class makes no guarantees as to 40 * the order of the map; in particular, it does not guarantee that the order 41 * will remain constant over time. 42 * 43 * <p>This implementation provides constant-time performance for the basic 44 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function 45 * disperses the elements properly among the buckets. Iteration over 46 * collection views requires time proportional to the "capacity" of the 47 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number 48 * of key-value mappings). Thus, it's very important not to set the initial 49 * capacity too high (or the load factor too low) if iteration performance is 50 * important. 51 * 52 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its 53 * performance: <i>initial capacity</i> and <i>load factor</i>. The 54 * <i>capacity</i> is the number of buckets in the hash table, and the initial 55 * capacity is simply the capacity at the time the hash table is created. The 56 * <i>load factor</i> is a measure of how full the hash table is allowed to 57 * get before its capacity is automatically increased. When the number of 58 * entries in the hash table exceeds the product of the load factor and the 59 * current capacity, the hash table is <i>rehashed</i> (that is, internal data 60 * structures are rebuilt) so that the hash table has approximately twice the 61 * number of buckets. 62 * 63 * <p>As a general rule, the default load factor (.75) offers a good tradeoff 64 * between time and space costs. Higher values decrease the space overhead 65 * but increase the lookup cost (reflected in most of the operations of the 66 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The 67 * expected number of entries in the map and its load factor should be taken 68 * into account when setting its initial capacity, so as to minimize the 69 * number of rehash operations. If the initial capacity is greater 70 * than the maximum number of entries divided by the load factor, no 71 * rehash operations will ever occur. 72 * 73 * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance, 74 * creating it with a sufficiently large capacity will allow the mappings to 75 * be stored more efficiently than letting it perform automatic rehashing as 76 * needed to grow the table. 77 * 78 * <p><strong>Note that this implementation is not synchronized.</strong> 79 * If multiple threads access a hash map concurrently, and at least one of 80 * the threads modifies the map structurally, it <i>must</i> be 81 * synchronized externally. (A structural modification is any operation 82 * that adds or deletes one or more mappings; merely changing the value 83 * associated with a key that an instance already contains is not a 84 * structural modification.) This is typically accomplished by 85 * synchronizing on some object that naturally encapsulates the map. 86 * 87 * If no such object exists, the map should be "wrapped" using the 88 * {@link Collections#synchronizedMap Collections.synchronizedMap} 89 * method. This is best done at creation time, to prevent accidental 90 * unsynchronized access to the map:<pre> 91 * Map m = Collections.synchronizedMap(new HashMap(...));</pre> 92 * 93 * <p>The iterators returned by all of this class's "collection view methods" 94 * are <i>fail-fast</i>: if the map is structurally modified at any time after 95 * the iterator is created, in any way except through the iterator's own 96 * <tt>remove</tt> method, the iterator will throw a 97 * {@link ConcurrentModificationException}. Thus, in the face of concurrent 98 * modification, the iterator fails quickly and cleanly, rather than risking 99 * arbitrary, non-deterministic behavior at an undetermined time in the 100 * future. 101 * 102 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 103 * as it is, generally speaking, impossible to make any hard guarantees in the 104 * presence of unsynchronized concurrent modification. Fail-fast iterators 105 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 106 * Therefore, it would be wrong to write a program that depended on this 107 * exception for its correctness: <i>the fail-fast behavior of iterators 108 * should be used only to detect bugs.</i> 109 * 110 * <p>This class is a member of the 111 * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 112 * Java Collections Framework</a>. 113 * 114 * @param <K> the type of keys maintained by this map 115 * @param <V> the type of mapped values 116 * 117 * @author Doug Lea 118 * @author Josh Bloch 119 * @author Arthur van Hoff 120 * @author Neal Gafter 121 * @see Object#hashCode() 122 * @see Collection 123 * @see Map 124 * @see TreeMap 125 * @see Hashtable 126 * @since 1.2 127 */ 128 129 public class HashMap<K,V> 130 extends AbstractMap<K,V> 131 implements Map<K,V>, Cloneable, Serializable 132 { 133 134 /** 135 * The default initial capacity - MUST be a power of two. 136 */ 137 static final int DEFAULT_INITIAL_CAPACITY = 4; 138 139 /** 140 * The maximum capacity, used if a higher value is implicitly specified 141 * by either of the constructors with arguments. 142 * MUST be a power of two <= 1<<30. 143 */ 144 static final int MAXIMUM_CAPACITY = 1 << 30; 145 146 /** 147 * The load factor used when none specified in constructor. 148 */ 149 static final float DEFAULT_LOAD_FACTOR = 0.75f; 150 151 /** 152 * An empty table instance to share when the table is not inflated. 153 */ 154 static final HashMapEntry<?,?>[] EMPTY_TABLE = {}; 155 156 /** 157 * The table, resized as necessary. Length MUST Always be a power of two. 158 */ 159 transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE; 160 161 /** 162 * The number of key-value mappings contained in this map. 163 */ 164 transient int size; 165 166 /** 167 * The next size value at which to resize (capacity * load factor). 168 * @serial 169 */ 170 // If table == EMPTY_TABLE then this is the initial capacity at which the 171 // table will be created when inflated. 172 int threshold; 173 174 /** 175 * The load factor for the hash table. 176 * 177 * @serial 178 */ 179 // Android-Note: We always use a load factor of 0.75 and ignore any explicitly 180 // selected values. 181 final float loadFactor = DEFAULT_LOAD_FACTOR; 182 183 /** 184 * The number of times this HashMap has been structurally modified 185 * Structural modifications are those that change the number of mappings in 186 * the HashMap or otherwise modify its internal structure (e.g., 187 * rehash). This field is used to make iterators on Collection-views of 188 * the HashMap fail-fast. (See ConcurrentModificationException). 189 */ 190 transient int modCount; 191 192 /** 193 * Constructs an empty <tt>HashMap</tt> with the specified initial 194 * capacity and load factor. 195 * 196 * @param initialCapacity the initial capacity 197 * @param loadFactor the load factor 198 * @throws IllegalArgumentException if the initial capacity is negative 199 * or the load factor is nonpositive 200 */ HashMap(int initialCapacity, float loadFactor)201 public HashMap(int initialCapacity, float loadFactor) { 202 if (initialCapacity < 0) 203 throw new IllegalArgumentException("Illegal initial capacity: " + 204 initialCapacity); 205 if (initialCapacity > MAXIMUM_CAPACITY) { 206 initialCapacity = MAXIMUM_CAPACITY; 207 } else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) { 208 initialCapacity = DEFAULT_INITIAL_CAPACITY; 209 } 210 211 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 212 throw new IllegalArgumentException("Illegal load factor: " + 213 loadFactor); 214 // Android-Note: We always use the default load factor of 0.75f. 215 216 // This might appear wrong but it's just awkward design. We always call 217 // inflateTable() when table == EMPTY_TABLE. That method will take "threshold" 218 // to mean "capacity" and then replace it with the real threshold (i.e, multiplied with 219 // the load factor). 220 threshold = initialCapacity; 221 init(); 222 } 223 224 /** 225 * Constructs an empty <tt>HashMap</tt> with the specified initial 226 * capacity and the default load factor (0.75). 227 * 228 * @param initialCapacity the initial capacity. 229 * @throws IllegalArgumentException if the initial capacity is negative. 230 */ HashMap(int initialCapacity)231 public HashMap(int initialCapacity) { 232 this(initialCapacity, DEFAULT_LOAD_FACTOR); 233 } 234 235 /** 236 * Constructs an empty <tt>HashMap</tt> with the default initial capacity 237 * (16) and the default load factor (0.75). 238 */ HashMap()239 public HashMap() { 240 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 241 } 242 243 /** 244 * Constructs a new <tt>HashMap</tt> with the same mappings as the 245 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with 246 * default load factor (0.75) and an initial capacity sufficient to 247 * hold the mappings in the specified <tt>Map</tt>. 248 * 249 * @param m the map whose mappings are to be placed in this map 250 * @throws NullPointerException if the specified map is null 251 */ HashMap(Map<? extends K, ? extends V> m)252 public HashMap(Map<? extends K, ? extends V> m) { 253 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 254 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); 255 inflateTable(threshold); 256 257 putAllForCreate(m); 258 } 259 roundUpToPowerOf2(int number)260 private static int roundUpToPowerOf2(int number) { 261 // assert number >= 0 : "number must be non-negative"; 262 int rounded = number >= MAXIMUM_CAPACITY 263 ? MAXIMUM_CAPACITY 264 : (rounded = Integer.highestOneBit(number)) != 0 265 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded 266 : 1; 267 268 return rounded; 269 } 270 271 /** 272 * Inflates the table. 273 */ inflateTable(int toSize)274 private void inflateTable(int toSize) { 275 // Find a power of 2 >= toSize 276 int capacity = roundUpToPowerOf2(toSize); 277 278 // Android-changed: Replace usage of Math.min() here because this method is 279 // called from the <clinit> of runtime, at which point the native libraries 280 // needed by Float.* might not be loaded. 281 float thresholdFloat = capacity * loadFactor; 282 if (thresholdFloat > MAXIMUM_CAPACITY + 1) { 283 thresholdFloat = MAXIMUM_CAPACITY + 1; 284 } 285 286 threshold = (int) thresholdFloat; 287 table = new HashMapEntry[capacity]; 288 } 289 290 // internal utilities 291 292 /** 293 * Initialization hook for subclasses. This method is called 294 * in all constructors and pseudo-constructors (clone, readObject) 295 * after HashMap has been initialized but before any entries have 296 * been inserted. (In the absence of this method, readObject would 297 * require explicit knowledge of subclasses.) 298 */ init()299 void init() { 300 } 301 302 /** 303 * Returns index for hash code h. 304 */ indexFor(int h, int length)305 static int indexFor(int h, int length) { 306 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; 307 return h & (length-1); 308 } 309 310 /** 311 * Returns the number of key-value mappings in this map. 312 * 313 * @return the number of key-value mappings in this map 314 */ size()315 public int size() { 316 return size; 317 } 318 319 /** 320 * Returns <tt>true</tt> if this map contains no key-value mappings. 321 * 322 * @return <tt>true</tt> if this map contains no key-value mappings 323 */ isEmpty()324 public boolean isEmpty() { 325 return size == 0; 326 } 327 328 /** 329 * Returns the value to which the specified key is mapped, 330 * or {@code null} if this map contains no mapping for the key. 331 * 332 * <p>More formally, if this map contains a mapping from a key 333 * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 334 * key.equals(k))}, then this method returns {@code v}; otherwise 335 * it returns {@code null}. (There can be at most one such mapping.) 336 * 337 * <p>A return value of {@code null} does not <i>necessarily</i> 338 * indicate that the map contains no mapping for the key; it's also 339 * possible that the map explicitly maps the key to {@code null}. 340 * The {@link #containsKey containsKey} operation may be used to 341 * distinguish these two cases. 342 * 343 * @see #put(Object, Object) 344 */ get(Object key)345 public V get(Object key) { 346 if (key == null) 347 return getForNullKey(); 348 Entry<K,V> entry = getEntry(key); 349 350 return null == entry ? null : entry.getValue(); 351 } 352 353 /** 354 * Offloaded version of get() to look up null keys. Null keys map 355 * to index 0. This null case is split out into separate methods 356 * for the sake of performance in the two most commonly used 357 * operations (get and put), but incorporated with conditionals in 358 * others. 359 */ getForNullKey()360 private V getForNullKey() { 361 if (size == 0) { 362 return null; 363 } 364 for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) { 365 if (e.key == null) 366 return e.value; 367 } 368 return null; 369 } 370 371 /** 372 * Returns <tt>true</tt> if this map contains a mapping for the 373 * specified key. 374 * 375 * @param key The key whose presence in this map is to be tested 376 * @return <tt>true</tt> if this map contains a mapping for the specified 377 * key. 378 */ containsKey(Object key)379 public boolean containsKey(Object key) { 380 return getEntry(key) != null; 381 } 382 383 /** 384 * Returns the entry associated with the specified key in the 385 * HashMap. Returns null if the HashMap contains no mapping 386 * for the key. 387 */ getEntry(Object key)388 final Entry<K,V> getEntry(Object key) { 389 if (size == 0) { 390 return null; 391 } 392 393 int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); 394 for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)]; 395 e != null; 396 e = e.next) { 397 Object k; 398 if (e.hash == hash && 399 ((k = e.key) == key || (key != null && key.equals(k)))) 400 return e; 401 } 402 return null; 403 } 404 405 /** 406 * Associates the specified value with the specified key in this map. 407 * If the map previously contained a mapping for the key, the old 408 * value is replaced. 409 * 410 * @param key key with which the specified value is to be associated 411 * @param value value to be associated with the specified key 412 * @return the previous value associated with <tt>key</tt>, or 413 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 414 * (A <tt>null</tt> return can also indicate that the map 415 * previously associated <tt>null</tt> with <tt>key</tt>.) 416 */ put(K key, V value)417 public V put(K key, V value) { 418 if (table == EMPTY_TABLE) { 419 inflateTable(threshold); 420 } 421 if (key == null) 422 return putForNullKey(value); 423 int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key); 424 int i = indexFor(hash, table.length); 425 for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) { 426 Object k; 427 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 428 V oldValue = e.value; 429 e.value = value; 430 e.recordAccess(this); 431 return oldValue; 432 } 433 } 434 435 modCount++; 436 addEntry(hash, key, value, i); 437 return null; 438 } 439 440 /** 441 * Offloaded version of put for null keys 442 */ putForNullKey(V value)443 private V putForNullKey(V value) { 444 for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) { 445 if (e.key == null) { 446 V oldValue = e.value; 447 e.value = value; 448 e.recordAccess(this); 449 return oldValue; 450 } 451 } 452 modCount++; 453 addEntry(0, null, value, 0); 454 return null; 455 } 456 457 /** 458 * This method is used instead of put by constructors and 459 * pseudoconstructors (clone, readObject). It does not resize the table, 460 * check for comodification, etc. It calls createEntry rather than 461 * addEntry. 462 */ putForCreate(K key, V value)463 private void putForCreate(K key, V value) { 464 int hash = null == key ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); 465 int i = indexFor(hash, table.length); 466 467 /** 468 * Look for preexisting entry for key. This will never happen for 469 * clone or deserialize. It will only happen for construction if the 470 * input Map is a sorted map whose ordering is inconsistent w/ equals. 471 */ 472 for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) { 473 Object k; 474 if (e.hash == hash && 475 ((k = e.key) == key || (key != null && key.equals(k)))) { 476 e.value = value; 477 return; 478 } 479 } 480 481 createEntry(hash, key, value, i); 482 } 483 putAllForCreate(Map<? extends K, ? extends V> m)484 private void putAllForCreate(Map<? extends K, ? extends V> m) { 485 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 486 putForCreate(e.getKey(), e.getValue()); 487 } 488 489 /** 490 * Rehashes the contents of this map into a new array with a 491 * larger capacity. This method is called automatically when the 492 * number of keys in this map reaches its threshold. 493 * 494 * If current capacity is MAXIMUM_CAPACITY, this method does not 495 * resize the map, but sets threshold to Integer.MAX_VALUE. 496 * This has the effect of preventing future calls. 497 * 498 * @param newCapacity the new capacity, MUST be a power of two; 499 * must be greater than current capacity unless current 500 * capacity is MAXIMUM_CAPACITY (in which case value 501 * is irrelevant). 502 */ resize(int newCapacity)503 void resize(int newCapacity) { 504 HashMapEntry[] oldTable = table; 505 int oldCapacity = oldTable.length; 506 if (oldCapacity == MAXIMUM_CAPACITY) { 507 threshold = Integer.MAX_VALUE; 508 return; 509 } 510 511 HashMapEntry[] newTable = new HashMapEntry[newCapacity]; 512 transfer(newTable); 513 table = newTable; 514 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); 515 } 516 517 /** 518 * Transfers all entries from current table to newTable. 519 */ transfer(HashMapEntry[] newTable)520 void transfer(HashMapEntry[] newTable) { 521 int newCapacity = newTable.length; 522 for (HashMapEntry<K,V> e : table) { 523 while(null != e) { 524 HashMapEntry<K,V> next = e.next; 525 int i = indexFor(e.hash, newCapacity); 526 e.next = newTable[i]; 527 newTable[i] = e; 528 e = next; 529 } 530 } 531 } 532 533 /** 534 * Copies all of the mappings from the specified map to this map. 535 * These mappings will replace any mappings that this map had for 536 * any of the keys currently in the specified map. 537 * 538 * @param m mappings to be stored in this map 539 * @throws NullPointerException if the specified map is null 540 */ putAll(Map<? extends K, ? extends V> m)541 public void putAll(Map<? extends K, ? extends V> m) { 542 int numKeysToBeAdded = m.size(); 543 if (numKeysToBeAdded == 0) 544 return; 545 546 if (table == EMPTY_TABLE) { 547 inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); 548 } 549 550 /* 551 * Expand the map if the map if the number of mappings to be added 552 * is greater than or equal to threshold. This is conservative; the 553 * obvious condition is (m.size() + size) >= threshold, but this 554 * condition could result in a map with twice the appropriate capacity, 555 * if the keys to be added overlap with the keys already in this map. 556 * By using the conservative calculation, we subject ourself 557 * to at most one extra resize. 558 */ 559 if (numKeysToBeAdded > threshold) { 560 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); 561 if (targetCapacity > MAXIMUM_CAPACITY) 562 targetCapacity = MAXIMUM_CAPACITY; 563 int newCapacity = table.length; 564 while (newCapacity < targetCapacity) 565 newCapacity <<= 1; 566 if (newCapacity > table.length) 567 resize(newCapacity); 568 } 569 570 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 571 put(e.getKey(), e.getValue()); 572 } 573 574 /** 575 * Removes the mapping for the specified key from this map if present. 576 * 577 * @param key key whose mapping is to be removed from the map 578 * @return the previous value associated with <tt>key</tt>, or 579 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 580 * (A <tt>null</tt> return can also indicate that the map 581 * previously associated <tt>null</tt> with <tt>key</tt>.) 582 */ remove(Object key)583 public V remove(Object key) { 584 Entry<K,V> e = removeEntryForKey(key); 585 return (e == null ? null : e.getValue()); 586 } 587 588 /** 589 * Removes and returns the entry associated with the specified key 590 * in the HashMap. Returns null if the HashMap contains no mapping 591 * for this key. 592 */ removeEntryForKey(Object key)593 final Entry<K,V> removeEntryForKey(Object key) { 594 if (size == 0) { 595 return null; 596 } 597 int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); 598 int i = indexFor(hash, table.length); 599 HashMapEntry<K,V> prev = table[i]; 600 HashMapEntry<K,V> e = prev; 601 602 while (e != null) { 603 HashMapEntry<K,V> next = e.next; 604 Object k; 605 if (e.hash == hash && 606 ((k = e.key) == key || (key != null && key.equals(k)))) { 607 modCount++; 608 size--; 609 if (prev == e) 610 table[i] = next; 611 else 612 prev.next = next; 613 e.recordRemoval(this); 614 return e; 615 } 616 prev = e; 617 e = next; 618 } 619 620 return e; 621 } 622 623 /** 624 * Special version of remove for EntrySet using {@code Map.Entry.equals()} 625 * for matching. 626 */ removeMapping(Object o)627 final Entry<K,V> removeMapping(Object o) { 628 if (size == 0 || !(o instanceof Map.Entry)) 629 return null; 630 631 Map.Entry<K,V> entry = (Map.Entry<K,V>) o; 632 Object key = entry.getKey(); 633 int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key); 634 int i = indexFor(hash, table.length); 635 HashMapEntry<K,V> prev = table[i]; 636 HashMapEntry<K,V> e = prev; 637 638 while (e != null) { 639 HashMapEntry<K,V> next = e.next; 640 if (e.hash == hash && e.equals(entry)) { 641 modCount++; 642 size--; 643 if (prev == e) 644 table[i] = next; 645 else 646 prev.next = next; 647 e.recordRemoval(this); 648 return e; 649 } 650 prev = e; 651 e = next; 652 } 653 654 return e; 655 } 656 657 /** 658 * Removes all of the mappings from this map. 659 * The map will be empty after this call returns. 660 */ clear()661 public void clear() { 662 modCount++; 663 Arrays.fill(table, null); 664 size = 0; 665 } 666 667 /** 668 * Returns <tt>true</tt> if this map maps one or more keys to the 669 * specified value. 670 * 671 * @param value value whose presence in this map is to be tested 672 * @return <tt>true</tt> if this map maps one or more keys to the 673 * specified value 674 */ containsValue(Object value)675 public boolean containsValue(Object value) { 676 if (value == null) 677 return containsNullValue(); 678 679 HashMapEntry[] tab = table; 680 for (int i = 0; i < tab.length ; i++) 681 for (HashMapEntry e = tab[i] ; e != null ; e = e.next) 682 if (value.equals(e.value)) 683 return true; 684 return false; 685 } 686 687 /** 688 * Special-case code for containsValue with null argument 689 */ containsNullValue()690 private boolean containsNullValue() { 691 HashMapEntry[] tab = table; 692 for (int i = 0; i < tab.length ; i++) 693 for (HashMapEntry e = tab[i] ; e != null ; e = e.next) 694 if (e.value == null) 695 return true; 696 return false; 697 } 698 699 /** 700 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and 701 * values themselves are not cloned. 702 * 703 * @return a shallow copy of this map 704 */ clone()705 public Object clone() { 706 HashMap<K,V> result = null; 707 try { 708 result = (HashMap<K,V>)super.clone(); 709 } catch (CloneNotSupportedException e) { 710 // assert false; 711 } 712 if (result.table != EMPTY_TABLE) { 713 result.inflateTable(Math.min( 714 (int) Math.min( 715 size * Math.min(1 / loadFactor, 4.0f), 716 // we have limits... 717 HashMap.MAXIMUM_CAPACITY), 718 table.length)); 719 } 720 result.entrySet = null; 721 result.modCount = 0; 722 result.size = 0; 723 result.init(); 724 result.putAllForCreate(this); 725 726 return result; 727 } 728 729 /** @hide */ // Android added. 730 static class HashMapEntry<K,V> implements Map.Entry<K,V> { 731 final K key; 732 V value; 733 HashMapEntry<K,V> next; 734 int hash; 735 736 /** 737 * Creates new entry. 738 */ HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n)739 HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) { 740 value = v; 741 next = n; 742 key = k; 743 hash = h; 744 } 745 getKey()746 public final K getKey() { 747 return key; 748 } 749 getValue()750 public final V getValue() { 751 return value; 752 } 753 setValue(V newValue)754 public final V setValue(V newValue) { 755 V oldValue = value; 756 value = newValue; 757 return oldValue; 758 } 759 equals(Object o)760 public final boolean equals(Object o) { 761 if (!(o instanceof Map.Entry)) 762 return false; 763 Map.Entry e = (Map.Entry)o; 764 Object k1 = getKey(); 765 Object k2 = e.getKey(); 766 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 767 Object v1 = getValue(); 768 Object v2 = e.getValue(); 769 if (v1 == v2 || (v1 != null && v1.equals(v2))) 770 return true; 771 } 772 return false; 773 } 774 hashCode()775 public final int hashCode() { 776 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); 777 } 778 toString()779 public final String toString() { 780 return getKey() + "=" + getValue(); 781 } 782 783 /** 784 * This method is invoked whenever the value in an entry is 785 * overwritten by an invocation of put(k,v) for a key k that's already 786 * in the HashMap. 787 */ recordAccess(HashMap<K,V> m)788 void recordAccess(HashMap<K,V> m) { 789 } 790 791 /** 792 * This method is invoked whenever the entry is 793 * removed from the table. 794 */ recordRemoval(HashMap<K,V> m)795 void recordRemoval(HashMap<K,V> m) { 796 } 797 } 798 799 /** 800 * Adds a new entry with the specified key, value and hash code to 801 * the specified bucket. It is the responsibility of this 802 * method to resize the table if appropriate. 803 * 804 * Subclass overrides this to alter the behavior of put method. 805 */ addEntry(int hash, K key, V value, int bucketIndex)806 void addEntry(int hash, K key, V value, int bucketIndex) { 807 if ((size >= threshold) && (null != table[bucketIndex])) { 808 resize(2 * table.length); 809 hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0; 810 bucketIndex = indexFor(hash, table.length); 811 } 812 813 createEntry(hash, key, value, bucketIndex); 814 } 815 816 /** 817 * Like addEntry except that this version is used when creating entries 818 * as part of Map construction or "pseudo-construction" (cloning, 819 * deserialization). This version needn't worry about resizing the table. 820 * 821 * Subclass overrides this to alter the behavior of HashMap(Map), 822 * clone, and readObject. 823 */ createEntry(int hash, K key, V value, int bucketIndex)824 void createEntry(int hash, K key, V value, int bucketIndex) { 825 HashMapEntry<K,V> e = table[bucketIndex]; 826 table[bucketIndex] = new HashMapEntry<>(hash, key, value, e); 827 size++; 828 } 829 830 private abstract class HashIterator<E> implements Iterator<E> { 831 HashMapEntry<K,V> next; // next entry to return 832 int expectedModCount; // For fast-fail 833 int index; // current slot 834 HashMapEntry<K,V> current; // current entry 835 HashIterator()836 HashIterator() { 837 expectedModCount = modCount; 838 if (size > 0) { // advance to first entry 839 HashMapEntry[] t = table; 840 while (index < t.length && (next = t[index++]) == null) 841 ; 842 } 843 } 844 hasNext()845 public final boolean hasNext() { 846 return next != null; 847 } 848 nextEntry()849 final Entry<K,V> nextEntry() { 850 if (modCount != expectedModCount) 851 throw new ConcurrentModificationException(); 852 HashMapEntry<K,V> e = next; 853 if (e == null) 854 throw new NoSuchElementException(); 855 856 if ((next = e.next) == null) { 857 HashMapEntry[] t = table; 858 while (index < t.length && (next = t[index++]) == null) 859 ; 860 } 861 current = e; 862 return e; 863 } 864 remove()865 public void remove() { 866 if (current == null) 867 throw new IllegalStateException(); 868 if (modCount != expectedModCount) 869 throw new ConcurrentModificationException(); 870 Object k = current.key; 871 current = null; 872 HashMap.this.removeEntryForKey(k); 873 expectedModCount = modCount; 874 } 875 } 876 877 private final class ValueIterator extends HashIterator<V> { next()878 public V next() { 879 return nextEntry().getValue(); 880 } 881 } 882 883 private final class KeyIterator extends HashIterator<K> { next()884 public K next() { 885 return nextEntry().getKey(); 886 } 887 } 888 889 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { next()890 public Map.Entry<K,V> next() { 891 return nextEntry(); 892 } 893 } 894 895 /* ------------------------------------------------------------ */ 896 // spliterators 897 898 static class HashMapSpliterator<K,V> { 899 final HashMap<K,V> map; 900 HashMapEntry<K,V> current; // current entry 901 int index; // current index, modified on advance/split 902 int fence; // one past last index 903 int est; // size estimate 904 int expectedModCount; // for comodification checks 905 HashMapSpliterator(HashMap<K,V> m, int origin, int fence, int est, int expectedModCount)906 HashMapSpliterator(HashMap<K,V> m, int origin, 907 int fence, int est, 908 int expectedModCount) { 909 this.map = m; 910 this.index = origin; 911 this.fence = fence; 912 this.est = est; 913 this.expectedModCount = expectedModCount; 914 } 915 getFence()916 final int getFence() { // initialize fence and size on first use 917 int hi; 918 if ((hi = fence) < 0) { 919 HashMap<K,V> m = map; 920 est = m.size; 921 expectedModCount = m.modCount; 922 HashMapEntry<K,V>[] tab = m.table; 923 hi = fence = (tab == null) ? 0 : tab.length; 924 } 925 return hi; 926 } 927 estimateSize()928 public final long estimateSize() { 929 getFence(); // force init 930 return (long) est; 931 } 932 } 933 934 static final class KeySpliterator<K,V> 935 extends HashMapSpliterator<K,V> 936 implements Spliterator<K> { KeySpliterator(HashMap<K,V> m, int origin, int fence, int est, int expectedModCount)937 KeySpliterator(HashMap<K,V> m, int origin, int fence, int est, 938 int expectedModCount) { 939 super(m, origin, fence, est, expectedModCount); 940 } 941 trySplit()942 public KeySpliterator<K,V> trySplit() { 943 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 944 return (lo >= mid || current != null) ? null : 945 new KeySpliterator<>(map, lo, index = mid, est >>>= 1, 946 expectedModCount); 947 } 948 forEachRemaining(Consumer<? super K> action)949 public void forEachRemaining(Consumer<? super K> action) { 950 int i, hi, mc; 951 if (action == null) 952 throw new NullPointerException(); 953 HashMap<K,V> m = map; 954 HashMapEntry<K,V>[] tab = m.table; 955 if ((hi = fence) < 0) { 956 mc = expectedModCount = m.modCount; 957 hi = fence = (tab == null) ? 0 : tab.length; 958 } 959 else 960 mc = expectedModCount; 961 if (tab != null && tab.length >= hi && 962 (i = index) >= 0 && (i < (index = hi) || current != null)) { 963 HashMapEntry<K,V> p = current; 964 current = null; 965 do { 966 if (p == null) 967 p = tab[i++]; 968 else { 969 action.accept(p.key); 970 p = p.next; 971 } 972 } while (p != null || i < hi); 973 if (m.modCount != mc) 974 throw new ConcurrentModificationException(); 975 } 976 } 977 tryAdvance(Consumer<? super K> action)978 public boolean tryAdvance(Consumer<? super K> action) { 979 int hi; 980 if (action == null) 981 throw new NullPointerException(); 982 HashMapEntry<K,V>[] tab = map.table; 983 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { 984 while (current != null || index < hi) { 985 if (current == null) 986 current = tab[index++]; 987 else { 988 K k = current.key; 989 current = current.next; 990 action.accept(k); 991 if (map.modCount != expectedModCount) 992 throw new ConcurrentModificationException(); 993 return true; 994 } 995 } 996 } 997 return false; 998 } 999 characteristics()1000 public int characteristics() { 1001 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | 1002 Spliterator.DISTINCT | 1003 ((map instanceof LinkedHashMap) ? Spliterator.ORDERED : 0); 1004 } 1005 } 1006 1007 static final class ValueSpliterator<K,V> 1008 extends HashMapSpliterator<K,V> 1009 implements Spliterator<V> { ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est, int expectedModCount)1010 ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est, 1011 int expectedModCount) { 1012 super(m, origin, fence, est, expectedModCount); 1013 } 1014 trySplit()1015 public ValueSpliterator<K,V> trySplit() { 1016 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1017 return (lo >= mid || current != null) ? null : 1018 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1, 1019 expectedModCount); 1020 } 1021 forEachRemaining(Consumer<? super V> action)1022 public void forEachRemaining(Consumer<? super V> action) { 1023 int i, hi, mc; 1024 if (action == null) 1025 throw new NullPointerException(); 1026 HashMap<K,V> m = map; 1027 HashMapEntry<K,V>[] tab = m.table; 1028 if ((hi = fence) < 0) { 1029 mc = expectedModCount = m.modCount; 1030 hi = fence = (tab == null) ? 0 : tab.length; 1031 } 1032 else 1033 mc = expectedModCount; 1034 if (tab != null && tab.length >= hi && 1035 (i = index) >= 0 && (i < (index = hi) || current != null)) { 1036 HashMapEntry<K,V> p = current; 1037 current = null; 1038 do { 1039 if (p == null) 1040 p = tab[i++]; 1041 else { 1042 action.accept(p.value); 1043 p = p.next; 1044 } 1045 } while (p != null || i < hi); 1046 if (m.modCount != mc) 1047 throw new ConcurrentModificationException(); 1048 } 1049 } 1050 tryAdvance(Consumer<? super V> action)1051 public boolean tryAdvance(Consumer<? super V> action) { 1052 int hi; 1053 if (action == null) 1054 throw new NullPointerException(); 1055 HashMapEntry<K,V>[] tab = map.table; 1056 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { 1057 while (current != null || index < hi) { 1058 if (current == null) 1059 current = tab[index++]; 1060 else { 1061 V v = current.value; 1062 current = current.next; 1063 action.accept(v); 1064 if (map.modCount != expectedModCount) 1065 throw new ConcurrentModificationException(); 1066 return true; 1067 } 1068 } 1069 } 1070 return false; 1071 } 1072 characteristics()1073 public int characteristics() { 1074 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | 1075 ((map instanceof LinkedHashMap) ? Spliterator.ORDERED : 0); 1076 } 1077 } 1078 1079 static final class EntrySpliterator<K,V> 1080 extends HashMapSpliterator<K,V> 1081 implements Spliterator<Map.Entry<K,V>> { EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est, int expectedModCount)1082 EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est, 1083 int expectedModCount) { 1084 super(m, origin, fence, est, expectedModCount); 1085 } 1086 trySplit()1087 public EntrySpliterator<K,V> trySplit() { 1088 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1089 return (lo >= mid || current != null) ? null : 1090 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1, 1091 expectedModCount); 1092 } 1093 forEachRemaining(Consumer<? super Map.Entry<K,V>> action)1094 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) { 1095 int i, hi, mc; 1096 if (action == null) 1097 throw new NullPointerException(); 1098 HashMap<K,V> m = map; 1099 HashMapEntry<K,V>[] tab = m.table; 1100 if ((hi = fence) < 0) { 1101 mc = expectedModCount = m.modCount; 1102 hi = fence = (tab == null) ? 0 : tab.length; 1103 } 1104 else 1105 mc = expectedModCount; 1106 if (tab != null && tab.length >= hi && 1107 (i = index) >= 0 && (i < (index = hi) || current != null)) { 1108 HashMapEntry<K,V> p = current; 1109 current = null; 1110 do { 1111 if (p == null) 1112 p = tab[i++]; 1113 else { 1114 action.accept(p); 1115 p = p.next; 1116 } 1117 } while (p != null || i < hi); 1118 if (m.modCount != mc) 1119 throw new ConcurrentModificationException(); 1120 } 1121 } 1122 tryAdvance(Consumer<? super Map.Entry<K,V>> action)1123 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 1124 int hi; 1125 if (action == null) 1126 throw new NullPointerException(); 1127 HashMapEntry<K,V>[] tab = map.table; 1128 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { 1129 while (current != null || index < hi) { 1130 if (current == null) 1131 current = tab[index++]; 1132 else { 1133 HashMapEntry<K,V> e = current; 1134 current = current.next; 1135 action.accept(e); 1136 if (map.modCount != expectedModCount) 1137 throw new ConcurrentModificationException(); 1138 return true; 1139 } 1140 } 1141 } 1142 return false; 1143 } 1144 characteristics()1145 public int characteristics() { 1146 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | 1147 Spliterator.DISTINCT | 1148 ((map instanceof LinkedHashMap) ? Spliterator.ORDERED : 0); 1149 } 1150 } 1151 1152 // Subclass overrides these to alter behavior of views' iterator() method newKeyIterator()1153 Iterator<K> newKeyIterator() { 1154 return new KeyIterator(); 1155 } newValueIterator()1156 Iterator<V> newValueIterator() { 1157 return new ValueIterator(); 1158 } newEntryIterator()1159 Iterator<Map.Entry<K,V>> newEntryIterator() { 1160 return new EntryIterator(); 1161 } 1162 1163 1164 // Views 1165 1166 private transient Set<Map.Entry<K,V>> entrySet = null; 1167 1168 /** 1169 * Returns a {@link Set} view of the keys contained in this map. 1170 * The set is backed by the map, so changes to the map are 1171 * reflected in the set, and vice-versa. If the map is modified 1172 * while an iteration over the set is in progress (except through 1173 * the iterator's own <tt>remove</tt> operation), the results of 1174 * the iteration are undefined. The set supports element removal, 1175 * which removes the corresponding mapping from the map, via the 1176 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 1177 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 1178 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 1179 * operations. 1180 */ keySet()1181 public Set<K> keySet() { 1182 Set<K> ks = keySet; 1183 return (ks != null ? ks : (keySet = new KeySet())); 1184 } 1185 1186 private final class KeySet extends AbstractSet<K> { iterator()1187 public Iterator<K> iterator() { 1188 return newKeyIterator(); 1189 } size()1190 public int size() { 1191 return size; 1192 } contains(Object o)1193 public boolean contains(Object o) { 1194 return containsKey(o); 1195 } remove(Object o)1196 public boolean remove(Object o) { 1197 return HashMap.this.removeEntryForKey(o) != null; 1198 } clear()1199 public void clear() { 1200 HashMap.this.clear(); 1201 } spliterator()1202 public final Spliterator<K> spliterator() { 1203 return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0); 1204 } forEach(Consumer<? super K> action)1205 public final void forEach(Consumer<? super K> action) { 1206 HashMapEntry<K,V>[] tab; 1207 if (action == null) 1208 throw new NullPointerException(); 1209 if (size > 0 && (tab = table) != null) { 1210 int mc = modCount; 1211 for (int i = 0; i < tab.length; ++i) { 1212 for (HashMapEntry<K,V> e = tab[i]; e != null; e = e.next) { 1213 action.accept(e.key); 1214 // Android-modified - this was outside of the loop, inconsistent with other 1215 // collections 1216 if (modCount != mc) { 1217 throw new ConcurrentModificationException(); 1218 } 1219 } 1220 } 1221 1222 } 1223 } 1224 } 1225 1226 /** 1227 * Returns a {@link Collection} view of the values contained in this map. 1228 * The collection is backed by the map, so changes to the map are 1229 * reflected in the collection, and vice-versa. If the map is 1230 * modified while an iteration over the collection is in progress 1231 * (except through the iterator's own <tt>remove</tt> operation), 1232 * the results of the iteration are undefined. The collection 1233 * supports element removal, which removes the corresponding 1234 * mapping from the map, via the <tt>Iterator.remove</tt>, 1235 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 1236 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 1237 * support the <tt>add</tt> or <tt>addAll</tt> operations. 1238 */ values()1239 public Collection<V> values() { 1240 Collection<V> vs = values; 1241 return (vs != null ? vs : (values = new Values())); 1242 } 1243 1244 private final class Values extends AbstractCollection<V> { iterator()1245 public Iterator<V> iterator() { 1246 return newValueIterator(); 1247 } size()1248 public int size() { 1249 return size; 1250 } contains(Object o)1251 public boolean contains(Object o) { 1252 return containsValue(o); 1253 } clear()1254 public void clear() { 1255 HashMap.this.clear(); 1256 } spliterator()1257 public final Spliterator<V> spliterator() { 1258 return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0); 1259 } forEach(Consumer<? super V> action)1260 public final void forEach(Consumer<? super V> action) { 1261 HashMapEntry<K,V>[] tab; 1262 if (action == null) 1263 throw new NullPointerException(); 1264 if (size > 0 && (tab = table) != null) { 1265 int mc = modCount; 1266 for (int i = 0; i < tab.length; ++i) { 1267 for (HashMapEntry<K,V> e = tab[i]; e != null; e = e.next) { 1268 action.accept(e.value); 1269 // Android-modified - this was outside of the loop, inconsistent with other 1270 // collections 1271 if (modCount != mc) { 1272 throw new ConcurrentModificationException(); 1273 } 1274 } 1275 } 1276 } 1277 } 1278 } 1279 1280 /** 1281 * Returns a {@link Set} view of the mappings contained in this map. 1282 * The set is backed by the map, so changes to the map are 1283 * reflected in the set, and vice-versa. If the map is modified 1284 * while an iteration over the set is in progress (except through 1285 * the iterator's own <tt>remove</tt> operation, or through the 1286 * <tt>setValue</tt> operation on a map entry returned by the 1287 * iterator) the results of the iteration are undefined. The set 1288 * supports element removal, which removes the corresponding 1289 * mapping from the map, via the <tt>Iterator.remove</tt>, 1290 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 1291 * <tt>clear</tt> operations. It does not support the 1292 * <tt>add</tt> or <tt>addAll</tt> operations. 1293 * 1294 * @return a set view of the mappings contained in this map 1295 */ 1296 // Android-changed: Changed type parameter from <? extends Entry<K, V> 1297 // to a Map.Entry<K, V>. entrySet()1298 public Set<Map.Entry<K,V>> entrySet() { 1299 return entrySet0(); 1300 } 1301 entrySet0()1302 private Set<Map.Entry<K,V>> entrySet0() { 1303 Set<Map.Entry<K,V>> es = entrySet; 1304 return es != null ? es : (entrySet = new EntrySet()); 1305 } 1306 1307 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { iterator()1308 public Iterator<Map.Entry<K,V>> iterator() { 1309 return newEntryIterator(); 1310 } contains(Object o)1311 public boolean contains(Object o) { 1312 if (!(o instanceof Map.Entry)) 1313 return false; 1314 Map.Entry<K,V> e = (Map.Entry<K,V>) o; 1315 Entry<K,V> candidate = getEntry(e.getKey()); 1316 return candidate != null && candidate.equals(e); 1317 } remove(Object o)1318 public boolean remove(Object o) { 1319 return removeMapping(o) != null; 1320 } size()1321 public int size() { 1322 return size; 1323 } clear()1324 public void clear() { 1325 HashMap.this.clear(); 1326 } spliterator()1327 public final Spliterator<Map.Entry<K,V>> spliterator() { 1328 return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); 1329 } forEach(Consumer<? super Map.Entry<K,V>> action)1330 public final void forEach(Consumer<? super Map.Entry<K,V>> action) { 1331 HashMapEntry<K,V>[] tab; 1332 if (action == null) 1333 throw new NullPointerException(); 1334 if (size > 0 && (tab = table) != null) { 1335 int mc = modCount; 1336 for (int i = 0; i < tab.length; ++i) { 1337 for (HashMapEntry<K,V> e = tab[i]; e != null; e = e.next) { 1338 action.accept(e); 1339 // Android-modified - this was outside of the loop, inconsistent with other 1340 // collections 1341 if (modCount != mc) { 1342 throw new ConcurrentModificationException(); 1343 } 1344 } 1345 } 1346 } 1347 } 1348 } 1349 1350 @Override forEach(BiConsumer<? super K, ? super V> action)1351 public void forEach(BiConsumer<? super K, ? super V> action) { 1352 HashMapEntry<K,V>[] tab; 1353 if (action == null) 1354 throw new NullPointerException(); 1355 if (size > 0 && (tab = table) != null) { 1356 int mc = modCount; 1357 for (int i = 0; i < tab.length; ++i) { 1358 for (HashMapEntry<K,V> e = tab[i]; e != null; e = e.next) { 1359 action.accept(e.key, e.value); 1360 // Android-modified - this was outside of the loop, inconsistent with other 1361 // collections 1362 if (modCount != mc) { 1363 throw new ConcurrentModificationException(); 1364 } 1365 } 1366 } 1367 } 1368 } 1369 1370 @Override replaceAll(BiFunction<? super K, ? super V, ? extends V> function)1371 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1372 HashMapEntry<K,V>[] tab; 1373 if (function == null) 1374 throw new NullPointerException(); 1375 if (size > 0 && (tab = table) != null) { 1376 int mc = modCount; 1377 for (int i = 0; i < tab.length; ++i) { 1378 for (HashMapEntry<K,V> e = tab[i]; e != null; e = e.next) { 1379 e.value = function.apply(e.key, e.value); 1380 } 1381 } 1382 if (modCount != mc) 1383 throw new ConcurrentModificationException(); 1384 } 1385 } 1386 1387 /** 1388 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e., 1389 * serialize it). 1390 * 1391 * @serialData The <i>capacity</i> of the HashMap (the length of the 1392 * bucket array) is emitted (int), followed by the 1393 * <i>size</i> (an int, the number of key-value 1394 * mappings), followed by the key (Object) and value (Object) 1395 * for each key-value mapping. The key-value mappings are 1396 * emitted in no particular order. 1397 */ writeObject(java.io.ObjectOutputStream s)1398 private void writeObject(java.io.ObjectOutputStream s) 1399 throws IOException 1400 { 1401 // Write out the threshold, loadfactor, and any hidden stuff 1402 s.defaultWriteObject(); 1403 1404 // Write out number of buckets 1405 if (table==EMPTY_TABLE) { 1406 s.writeInt(roundUpToPowerOf2(threshold)); 1407 } else { 1408 s.writeInt(table.length); 1409 } 1410 1411 // Write out size (number of Mappings) 1412 s.writeInt(size); 1413 1414 // Write out keys and values (alternating) 1415 if (size > 0) { 1416 for(Map.Entry<K,V> e : entrySet0()) { 1417 s.writeObject(e.getKey()); 1418 s.writeObject(e.getValue()); 1419 } 1420 } 1421 } 1422 1423 private static final long serialVersionUID = 362498820763181265L; 1424 1425 /** 1426 * Reconstitute the {@code HashMap} instance from a stream (i.e., 1427 * deserialize it). 1428 */ readObject(java.io.ObjectInputStream s)1429 private void readObject(java.io.ObjectInputStream s) 1430 throws IOException, ClassNotFoundException 1431 { 1432 // Read in the threshold (ignored), loadfactor, and any hidden stuff 1433 s.defaultReadObject(); 1434 if (loadFactor <= 0 || Float.isNaN(loadFactor)) { 1435 throw new InvalidObjectException("Illegal load factor: " + 1436 loadFactor); 1437 } 1438 1439 // set other fields that need values 1440 table = (HashMapEntry<K,V>[]) EMPTY_TABLE; 1441 1442 // Read in number of buckets 1443 s.readInt(); // ignored. 1444 1445 // Read number of mappings 1446 int mappings = s.readInt(); 1447 if (mappings < 0) 1448 throw new InvalidObjectException("Illegal mappings count: " + 1449 mappings); 1450 1451 // capacity chosen by number of mappings and desired load (if >= 0.25) 1452 int capacity = (int) Math.min( 1453 mappings * Math.min(1 / loadFactor, 4.0f), 1454 // we have limits... 1455 HashMap.MAXIMUM_CAPACITY); 1456 1457 // allocate the bucket array; 1458 if (mappings > 0) { 1459 inflateTable(capacity); 1460 } else { 1461 threshold = capacity; 1462 } 1463 1464 init(); // Give subclass a chance to do its thing. 1465 1466 // Read the keys and values, and put the mappings in the HashMap 1467 for (int i = 0; i < mappings; i++) { 1468 K key = (K) s.readObject(); 1469 V value = (V) s.readObject(); 1470 putForCreate(key, value); 1471 } 1472 } 1473 1474 @Override replace(K key, V oldValue, V newValue)1475 public boolean replace(K key, V oldValue, V newValue) { 1476 HashMapEntry<K,V> e; V v; 1477 if ((e = (HashMapEntry)getEntry(key)) != null && 1478 ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { 1479 e.value = newValue; 1480 e.recordAccess(this); 1481 return true; 1482 } 1483 return false; 1484 } 1485 1486 // These methods are used when serializing HashSets capacity()1487 int capacity() { return table.length; } loadFactor()1488 float loadFactor() { return loadFactor; } 1489 } 1490