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