1 /* 2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.io.IOException; 29 import java.io.InvalidObjectException; 30 import java.io.Serializable; 31 import java.lang.ref.WeakReference; 32 import java.lang.reflect.ParameterizedType; 33 import java.lang.reflect.Type; 34 import java.util.function.BiConsumer; 35 import java.util.function.BiFunction; 36 import java.util.function.Consumer; 37 import java.util.function.Function; 38 39 /** 40 * Hash table based implementation of the <tt>Map</tt> interface. This 41 * implementation provides all of the optional map operations, and permits 42 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt> 43 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is 44 * unsynchronized and permits nulls.) This class makes no guarantees as to 45 * the order of the map; in particular, it does not guarantee that the order 46 * will remain constant over time. 47 * 48 * <p>This implementation provides constant-time performance for the basic 49 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function 50 * disperses the elements properly among the buckets. Iteration over 51 * collection views requires time proportional to the "capacity" of the 52 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number 53 * of key-value mappings). Thus, it's very important not to set the initial 54 * capacity too high (or the load factor too low) if iteration performance is 55 * important. 56 * 57 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its 58 * performance: <i>initial capacity</i> and <i>load factor</i>. The 59 * <i>capacity</i> is the number of buckets in the hash table, and the initial 60 * capacity is simply the capacity at the time the hash table is created. The 61 * <i>load factor</i> is a measure of how full the hash table is allowed to 62 * get before its capacity is automatically increased. When the number of 63 * entries in the hash table exceeds the product of the load factor and the 64 * current capacity, the hash table is <i>rehashed</i> (that is, internal data 65 * structures are rebuilt) so that the hash table has approximately twice the 66 * number of buckets. 67 * 68 * <p>As a general rule, the default load factor (.75) offers a good 69 * tradeoff between time and space costs. Higher values decrease the 70 * space overhead but increase the lookup cost (reflected in most of 71 * the operations of the <tt>HashMap</tt> class, including 72 * <tt>get</tt> and <tt>put</tt>). The expected number of entries in 73 * the map and its load factor should be taken into account when 74 * setting its initial capacity, so as to minimize the number of 75 * rehash operations. If the initial capacity is greater than the 76 * maximum number of entries divided by the load factor, no rehash 77 * operations will ever occur. 78 * 79 * <p>If many mappings are to be stored in a <tt>HashMap</tt> 80 * instance, creating it with a sufficiently large capacity will allow 81 * the mappings to be stored more efficiently than letting it perform 82 * automatic rehashing as needed to grow the table. Note that using 83 * many keys with the same {@code hashCode()} is a sure way to slow 84 * down performance of any hash table. To ameliorate impact, when keys 85 * are {@link Comparable}, this class may use comparison order among 86 * keys to help break ties. 87 * 88 * <p><strong>Note that this implementation is not synchronized.</strong> 89 * If multiple threads access a hash map concurrently, and at least one of 90 * the threads modifies the map structurally, it <i>must</i> be 91 * synchronized externally. (A structural modification is any operation 92 * that adds or deletes one or more mappings; merely changing the value 93 * associated with a key that an instance already contains is not a 94 * structural modification.) This is typically accomplished by 95 * synchronizing on some object that naturally encapsulates the map. 96 * 97 * If no such object exists, the map should be "wrapped" using the 98 * {@link Collections#synchronizedMap Collections.synchronizedMap} 99 * method. This is best done at creation time, to prevent accidental 100 * unsynchronized access to the map:<pre> 101 * Map m = Collections.synchronizedMap(new HashMap(...));</pre> 102 * 103 * <p>The iterators returned by all of this class's "collection view methods" 104 * are <i>fail-fast</i>: if the map is structurally modified at any time after 105 * the iterator is created, in any way except through the iterator's own 106 * <tt>remove</tt> method, the iterator will throw a 107 * {@link ConcurrentModificationException}. Thus, in the face of concurrent 108 * modification, the iterator fails quickly and cleanly, rather than risking 109 * arbitrary, non-deterministic behavior at an undetermined time in the 110 * future. 111 * 112 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 113 * as it is, generally speaking, impossible to make any hard guarantees in the 114 * presence of unsynchronized concurrent modification. Fail-fast iterators 115 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 116 * Therefore, it would be wrong to write a program that depended on this 117 * exception for its correctness: <i>the fail-fast behavior of iterators 118 * should be used only to detect bugs.</i> 119 * 120 * <p>This class is a member of the 121 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 122 * Java Collections Framework</a>. 123 * 124 * @param <K> the type of keys maintained by this map 125 * @param <V> the type of mapped values 126 * 127 * @author Doug Lea 128 * @author Josh Bloch 129 * @author Arthur van Hoff 130 * @author Neal Gafter 131 * @see Object#hashCode() 132 * @see Collection 133 * @see Map 134 * @see TreeMap 135 * @see Hashtable 136 * @since 1.2 137 */ 138 public class HashMap<K,V> extends AbstractMap<K,V> 139 implements Map<K,V>, Cloneable, Serializable { 140 141 private static final long serialVersionUID = 362498820763181265L; 142 143 /* 144 * Implementation notes. 145 * 146 * This map usually acts as a binned (bucketed) hash table, but 147 * when bins get too large, they are transformed into bins of 148 * TreeNodes, each structured similarly to those in 149 * java.util.TreeMap. Most methods try to use normal bins, but 150 * relay to TreeNode methods when applicable (simply by checking 151 * instanceof a node). Bins of TreeNodes may be traversed and 152 * used like any others, but additionally support faster lookup 153 * when overpopulated. However, since the vast majority of bins in 154 * normal use are not overpopulated, checking for existence of 155 * tree bins may be delayed in the course of table methods. 156 * 157 * Tree bins (i.e., bins whose elements are all TreeNodes) are 158 * ordered primarily by hashCode, but in the case of ties, if two 159 * elements are of the same "class C implements Comparable<C>", 160 * type then their compareTo method is used for ordering. (We 161 * conservatively check generic types via reflection to validate 162 * this -- see method comparableClassFor). The added complexity 163 * of tree bins is worthwhile in providing worst-case O(log n) 164 * operations when keys either have distinct hashes or are 165 * orderable, Thus, performance degrades gracefully under 166 * accidental or malicious usages in which hashCode() methods 167 * return values that are poorly distributed, as well as those in 168 * which many keys share a hashCode, so long as they are also 169 * Comparable. (If neither of these apply, we may waste about a 170 * factor of two in time and space compared to taking no 171 * precautions. But the only known cases stem from poor user 172 * programming practices that are already so slow that this makes 173 * little difference.) 174 * 175 * Because TreeNodes are about twice the size of regular nodes, we 176 * use them only when bins contain enough nodes to warrant use 177 * (see TREEIFY_THRESHOLD). And when they become too small (due to 178 * removal or resizing) they are converted back to plain bins. In 179 * usages with well-distributed user hashCodes, tree bins are 180 * rarely used. Ideally, under random hashCodes, the frequency of 181 * nodes in bins follows a Poisson distribution 182 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a 183 * parameter of about 0.5 on average for the default resizing 184 * threshold of 0.75, although with a large variance because of 185 * resizing granularity. Ignoring variance, the expected 186 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / 187 * factorial(k)). The first values are: 188 * 189 * 0: 0.60653066 190 * 1: 0.30326533 191 * 2: 0.07581633 192 * 3: 0.01263606 193 * 4: 0.00157952 194 * 5: 0.00015795 195 * 6: 0.00001316 196 * 7: 0.00000094 197 * 8: 0.00000006 198 * more: less than 1 in ten million 199 * 200 * The root of a tree bin is normally its first node. However, 201 * sometimes (currently only upon Iterator.remove), the root might 202 * be elsewhere, but can be recovered following parent links 203 * (method TreeNode.root()). 204 * 205 * All applicable internal methods accept a hash code as an 206 * argument (as normally supplied from a public method), allowing 207 * them to call each other without recomputing user hashCodes. 208 * Most internal methods also accept a "tab" argument, that is 209 * normally the current table, but may be a new or old one when 210 * resizing or converting. 211 * 212 * When bin lists are treeified, split, or untreeified, we keep 213 * them in the same relative access/traversal order (i.e., field 214 * Node.next) to better preserve locality, and to slightly 215 * simplify handling of splits and traversals that invoke 216 * iterator.remove. When using comparators on insertion, to keep a 217 * total ordering (or as close as is required here) across 218 * rebalancings, we compare classes and identityHashCodes as 219 * tie-breakers. 220 * 221 * The use and transitions among plain vs tree modes is 222 * complicated by the existence of subclass LinkedHashMap. See 223 * below for hook methods defined to be invoked upon insertion, 224 * removal and access that allow LinkedHashMap internals to 225 * otherwise remain independent of these mechanics. (This also 226 * requires that a map instance be passed to some utility methods 227 * that may create new nodes.) 228 * 229 * The concurrent-programming-like SSA-based coding style helps 230 * avoid aliasing errors amid all of the twisty pointer operations. 231 */ 232 233 /** 234 * The default initial capacity - MUST be a power of two. 235 */ 236 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 237 238 /** 239 * The maximum capacity, used if a higher value is implicitly specified 240 * by either of the constructors with arguments. 241 * MUST be a power of two <= 1<<30. 242 */ 243 static final int MAXIMUM_CAPACITY = 1 << 30; 244 245 /** 246 * The load factor used when none specified in constructor. 247 */ 248 static final float DEFAULT_LOAD_FACTOR = 0.75f; 249 250 /** 251 * The bin count threshold for using a tree rather than list for a 252 * bin. Bins are converted to trees when adding an element to a 253 * bin with at least this many nodes. The value must be greater 254 * than 2 and should be at least 8 to mesh with assumptions in 255 * tree removal about conversion back to plain bins upon 256 * shrinkage. 257 */ 258 static final int TREEIFY_THRESHOLD = 8; 259 260 /** 261 * The bin count threshold for untreeifying a (split) bin during a 262 * resize operation. Should be less than TREEIFY_THRESHOLD, and at 263 * most 6 to mesh with shrinkage detection under removal. 264 */ 265 static final int UNTREEIFY_THRESHOLD = 6; 266 267 /** 268 * The smallest table capacity for which bins may be treeified. 269 * (Otherwise the table is resized if too many nodes in a bin.) 270 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts 271 * between resizing and treeification thresholds. 272 */ 273 static final int MIN_TREEIFY_CAPACITY = 64; 274 275 /** 276 * Basic hash bin node, used for most entries. (See below for 277 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) 278 */ 279 static class Node<K,V> implements Map.Entry<K,V> { 280 final int hash; 281 final K key; 282 V value; 283 Node<K,V> next; 284 285 Node(int hash, K key, V value, Node<K,V> next) { 286 this.hash = hash; 287 this.key = key; 288 this.value = value; 289 this.next = next; 290 } 291 292 public final K getKey() { return key; } 293 public final V getValue() { return value; } 294 public final String toString() { return key + "=" + value; } 295 296 public final int hashCode() { 297 return Objects.hashCode(key) ^ Objects.hashCode(value); 298 } 299 300 public final V setValue(V newValue) { 301 V oldValue = value; 302 value = newValue; 303 return oldValue; 304 } 305 306 public final boolean equals(Object o) { 307 if (o == this) 308 return true; 309 if (o instanceof Map.Entry) { 310 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 311 if (Objects.equals(key, e.getKey()) && 312 Objects.equals(value, e.getValue())) 313 return true; 314 } 315 return false; 316 } 317 } 318 319 /* ---------------- Static utilities -------------- */ 320 321 /** 322 * Computes key.hashCode() and spreads (XORs) higher bits of hash 323 * to lower. Because the table uses power-of-two masking, sets of 324 * hashes that vary only in bits above the current mask will 325 * always collide. (Among known examples are sets of Float keys 326 * holding consecutive whole numbers in small tables.) So we 327 * apply a transform that spreads the impact of higher bits 328 * downward. There is a tradeoff between speed, utility, and 329 * quality of bit-spreading. Because many common sets of hashes 330 * are already reasonably distributed (so don't benefit from 331 * spreading), and because we use trees to handle large sets of 332 * collisions in bins, we just XOR some shifted bits in the 333 * cheapest possible way to reduce systematic lossage, as well as 334 * to incorporate impact of the highest bits that would otherwise 335 * never be used in index calculations because of table bounds. 336 */ 337 static final int hash(Object key) { 338 int h; 339 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 340 } 341 342 /** Cache of 1st encountered Class implementing Comparable */ 343 private static final class ClassRef extends WeakReference<Class<?>> { 344 final boolean selfComparable; 345 346 ClassRef(Class<?> cc, boolean selfComparable) { 347 super(cc); 348 this.selfComparable = selfComparable; 349 } 350 } 351 352 private transient ClassRef comparableClassRef; 353 354 /** 355 * Returns x's Class if it is of the form "class C implements 356 * Comparable<C>", else null. 357 */ 358 Class<?> comparableClassFor(Object x) { 359 if (x instanceof Comparable) { 360 Class<?> c, cc = null; 361 Type[] ts, as; 362 ParameterizedType p; 363 ClassRef ccRef; 364 if ((c = x.getClass()) == String.class) { // bypass checks 365 return c; 366 } 367 if ((ccRef = comparableClassRef) != null && 368 (cc = ccRef.get()) == c) { // cached 369 return ccRef.selfComparable ? c : null; 370 } 371 if ((ts = c.getGenericInterfaces()) != null) { 372 for (Type t : ts) { 373 if ((t instanceof ParameterizedType) && 374 ((p = (ParameterizedType) t).getRawType() == 375 Comparable.class) && 376 (as = p.getActualTypeArguments()) != null && 377 as.length == 1 && as[0] == c) { // type arg is c 378 if (cc == null) { 379 // not yet cached or already cleared 380 comparableClassRef = new ClassRef(c, true); 381 } 382 return c; 383 } 384 } 385 } 386 if (cc == null) { 387 // not yet cached or already cleared 388 comparableClassRef = new ClassRef(c, false); 389 } 390 } 391 return null; 392 } 393 394 /** 395 * Returns k.compareTo(x) if x matches kc (k's screened comparable 396 * class), else 0. 397 */ 398 @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable 399 static int compareComparables(Class<?> kc, Object k, Object x) { 400 return (x == null || x.getClass() != kc ? 0 : 401 ((Comparable)k).compareTo(x)); 402 } 403 404 /** 405 * Returns a power of two size for the given target capacity. 406 */ 407 static final int tableSizeFor(int cap) { 408 int n = cap - 1; 409 n |= n >>> 1; 410 n |= n >>> 2; 411 n |= n >>> 4; 412 n |= n >>> 8; 413 n |= n >>> 16; 414 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 415 } 416 417 /* ---------------- Fields -------------- */ 418 419 /** 420 * The table, initialized on first use, and resized as 421 * necessary. When allocated, length is always a power of two. 422 * (We also tolerate length zero in some operations to allow 423 * bootstrapping mechanics that are currently not needed.) 424 */ 425 transient Node<K,V>[] table; 426 427 /** 428 * Holds cached entrySet(). Note that AbstractMap fields are used 429 * for keySet() and values(). 430 */ 431 transient Set<Map.Entry<K,V>> entrySet; 432 433 /** 434 * The number of key-value mappings contained in this map. 435 */ 436 transient int size; 437 438 /** 439 * The number of times this HashMap has been structurally modified 440 * Structural modifications are those that change the number of mappings in 441 * the HashMap or otherwise modify its internal structure (e.g., 442 * rehash). This field is used to make iterators on Collection-views of 443 * the HashMap fail-fast. (See ConcurrentModificationException). 444 */ 445 transient int modCount; 446 447 /** 448 * The next size value at which to resize (capacity * load factor). 449 * 450 * @serial 451 */ 452 // (The javadoc description is true upon serialization. 453 // Additionally, if the table array has not been allocated, this 454 // field holds the initial array capacity, or zero signifying 455 // DEFAULT_INITIAL_CAPACITY.) 456 int threshold; 457 458 /** 459 * The load factor for the hash table. 460 * 461 * @serial 462 */ 463 final float loadFactor; 464 465 /* ---------------- Public operations -------------- */ 466 467 /** 468 * Constructs an empty <tt>HashMap</tt> with the specified initial 469 * capacity and load factor. 470 * 471 * @param initialCapacity the initial capacity 472 * @param loadFactor the load factor 473 * @throws IllegalArgumentException if the initial capacity is negative 474 * or the load factor is nonpositive 475 */ 476 public HashMap(int initialCapacity, float loadFactor) { 477 if (initialCapacity < 0) 478 throw new IllegalArgumentException("Illegal initial capacity: " + 479 initialCapacity); 480 if (initialCapacity > MAXIMUM_CAPACITY) 481 initialCapacity = MAXIMUM_CAPACITY; 482 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 483 throw new IllegalArgumentException("Illegal load factor: " + 484 loadFactor); 485 this.loadFactor = loadFactor; 486 this.threshold = tableSizeFor(initialCapacity); 487 } 488 489 /** 490 * Constructs an empty <tt>HashMap</tt> with the specified initial 491 * capacity and the default load factor (0.75). 492 * 493 * @param initialCapacity the initial capacity. 494 * @throws IllegalArgumentException if the initial capacity is negative. 495 */ 496 public HashMap(int initialCapacity) { 497 this(initialCapacity, DEFAULT_LOAD_FACTOR); 498 } 499 500 /** 501 * Constructs an empty <tt>HashMap</tt> with the default initial capacity 502 * (16) and the default load factor (0.75). 503 */ 504 public HashMap() { 505 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 506 } 507 508 /** 509 * Constructs a new <tt>HashMap</tt> with the same mappings as the 510 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with 511 * default load factor (0.75) and an initial capacity sufficient to 512 * hold the mappings in the specified <tt>Map</tt>. 513 * 514 * @param m the map whose mappings are to be placed in this map 515 * @throws NullPointerException if the specified map is null 516 */ 517 public HashMap(Map<? extends K, ? extends V> m) { 518 this.loadFactor = DEFAULT_LOAD_FACTOR; 519 putMapEntries(m, false); 520 } 521 522 /** 523 * Implements Map.putAll and Map constructor 524 * 525 * @param m the map 526 * @param evict false when initially constructing this map, else 527 * true (relayed to method afterNodeInsertion). 528 */ 529 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 530 int s = m.size(); 531 if (s > 0) { 532 if (table == null) { // pre-size 533 float ft = ((float)s / loadFactor) + 1.0F; 534 int t = ((ft < (float)MAXIMUM_CAPACITY) ? 535 (int)ft : MAXIMUM_CAPACITY); 536 if (t > threshold) 537 threshold = tableSizeFor(t); 538 } 539 else if (s > threshold) 540 resize(); 541 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 542 K key = e.getKey(); 543 V value = e.getValue(); 544 putVal(hash(key), key, value, false, evict); 545 } 546 } 547 } 548 549 /** 550 * Returns the number of key-value mappings in this map. 551 * 552 * @return the number of key-value mappings in this map 553 */ 554 public int size() { 555 return size; 556 } 557 558 /** 559 * Returns <tt>true</tt> if this map contains no key-value mappings. 560 * 561 * @return <tt>true</tt> if this map contains no key-value mappings 562 */ 563 public boolean isEmpty() { 564 return size == 0; 565 } 566 567 /** 568 * Returns the value to which the specified key is mapped, 569 * or {@code null} if this map contains no mapping for the key. 570 * 571 * <p>More formally, if this map contains a mapping from a key 572 * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 573 * key.equals(k))}, then this method returns {@code v}; otherwise 574 * it returns {@code null}. (There can be at most one such mapping.) 575 * 576 * <p>A return value of {@code null} does not <i>necessarily</i> 577 * indicate that the map contains no mapping for the key; it's also 578 * possible that the map explicitly maps the key to {@code null}. 579 * The {@link #containsKey containsKey} operation may be used to 580 * distinguish these two cases. 581 * 582 * @see #put(Object, Object) 583 */ 584 public V get(Object key) { 585 Node<K,V> e; 586 return (e = getNode(hash(key), key)) == null ? null : e.value; 587 } 588 589 /** 590 * Implements Map.get and related methods 591 * 592 * @param hash hash for key 593 * @param key the key 594 * @return the node, or null if none 595 */ 596 final Node<K,V> getNode(int hash, Object key) { 597 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 598 if ((tab = table) != null && (n = tab.length) > 0 && 599 (first = tab[(n - 1) & hash]) != null) { 600 if (first.hash == hash && // always check first node 601 ((k = first.key) == key || (key != null && key.equals(k)))) 602 return first; 603 if ((e = first.next) != null) { 604 if (first instanceof TreeNode) 605 return ((TreeNode<K,V>)first).getTreeNode(this, hash, key); 606 do { 607 if (e.hash == hash && 608 ((k = e.key) == key || (key != null && key.equals(k)))) 609 return e; 610 } while ((e = e.next) != null); 611 } 612 } 613 return null; 614 } 615 616 /** 617 * Returns <tt>true</tt> if this map contains a mapping for the 618 * specified key. 619 * 620 * @param key The key whose presence in this map is to be tested 621 * @return <tt>true</tt> if this map contains a mapping for the specified 622 * key. 623 */ 624 public boolean containsKey(Object key) { 625 return getNode(hash(key), key) != null; 626 } 627 628 /** 629 * Associates the specified value with the specified key in this map. 630 * If the map previously contained a mapping for the key, the old 631 * value is replaced. 632 * 633 * @param key key with which the specified value is to be associated 634 * @param value value to be associated with the specified key 635 * @return the previous value associated with <tt>key</tt>, or 636 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 637 * (A <tt>null</tt> return can also indicate that the map 638 * previously associated <tt>null</tt> with <tt>key</tt>.) 639 */ 640 public V put(K key, V value) { 641 return putVal(hash(key), key, value, false, true); 642 } 643 644 /** 645 * Implements Map.put and related methods 646 * 647 * @param hash hash for key 648 * @param key the key 649 * @param value the value to put 650 * @param onlyIfAbsent if true, don't change existing value 651 * @param evict if false, the table is in creation mode. 652 * @return previous value, or null if none 653 */ 654 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 655 boolean evict) { 656 Node<K,V>[] tab; Node<K,V> p; int n, i; 657 if ((tab = table) == null || (n = tab.length) == 0) 658 n = (tab = resize()).length; 659 if ((p = tab[i = (n - 1) & hash]) == null) 660 tab[i] = newNode(hash, key, value, null); 661 else { 662 Node<K,V> e; K k; 663 if (p.hash == hash && 664 ((k = p.key) == key || (key != null && key.equals(k)))) 665 e = p; 666 else if (p instanceof TreeNode) 667 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 668 else { 669 for (int binCount = 0; ; ++binCount) { 670 if ((e = p.next) == null) { 671 p.next = newNode(hash, key, value, null); 672 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 673 treeifyBin(tab, hash); 674 break; 675 } 676 if (e.hash == hash && 677 ((k = e.key) == key || (key != null && key.equals(k)))) 678 break; 679 p = e; 680 } 681 } 682 if (e != null) { // existing mapping for key 683 V oldValue = e.value; 684 if (!onlyIfAbsent || oldValue == null) 685 e.value = value; 686 afterNodeAccess(e); 687 return oldValue; 688 } 689 } 690 ++modCount; 691 if (++size > threshold) 692 resize(); 693 afterNodeInsertion(evict); 694 return null; 695 } 696 697 /** 698 * Initializes or doubles table size. If null, allocates in 699 * accord with initial capacity target held in field threshold. 700 * Otherwise, because we are using power-of-two expansion, the 701 * elements from each bin must either stay at same index, or move 702 * with a power of two offset in the new table. 703 * 704 * @return the table 705 */ 706 final Node<K,V>[] resize() { 707 Node<K,V>[] oldTab = table; 708 int oldCap = (oldTab == null) ? 0 : oldTab.length; 709 int oldThr = threshold; 710 int newCap, newThr = 0; 711 if (oldCap > 0) { 712 if (oldCap >= MAXIMUM_CAPACITY) { 713 threshold = Integer.MAX_VALUE; 714 return oldTab; 715 } 716 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 717 oldCap >= DEFAULT_INITIAL_CAPACITY) 718 newThr = oldThr << 1; // double threshold 719 } 720 else if (oldThr > 0) // initial capacity was placed in threshold 721 newCap = oldThr; 722 else { // zero initial threshold signifies using defaults 723 newCap = DEFAULT_INITIAL_CAPACITY; 724 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 725 } 726 if (newThr == 0) { 727 float ft = (float)newCap * loadFactor; 728 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 729 (int)ft : Integer.MAX_VALUE); 730 } 731 threshold = newThr; 732 @SuppressWarnings({"rawtypes","unchecked"}) 733 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 734 table = newTab; 735 if (oldTab != null) { 736 for (int j = 0; j < oldCap; ++j) { 737 Node<K,V> e; 738 if ((e = oldTab[j]) != null) { 739 oldTab[j] = null; 740 if (e.next == null) 741 newTab[e.hash & (newCap - 1)] = e; 742 else if (e instanceof TreeNode) 743 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 744 else { // preserve order 745 Node<K,V> loHead = null, loTail = null; 746 Node<K,V> hiHead = null, hiTail = null; 747 Node<K,V> next; 748 do { 749 next = e.next; 750 if ((e.hash & oldCap) == 0) { 751 if (loTail == null) 752 loHead = e; 753 else 754 loTail.next = e; 755 loTail = e; 756 } 757 else { 758 if (hiTail == null) 759 hiHead = e; 760 else 761 hiTail.next = e; 762 hiTail = e; 763 } 764 } while ((e = next) != null); 765 if (loTail != null) { 766 loTail.next = null; 767 newTab[j] = loHead; 768 } 769 if (hiTail != null) { 770 hiTail.next = null; 771 newTab[j + oldCap] = hiHead; 772 } 773 } 774 } 775 } 776 } 777 return newTab; 778 } 779 780 /** 781 * Replaces all linked nodes in bin at index for given hash unless 782 * table is too small, in which case resizes instead. 783 */ 784 final void treeifyBin(Node<K,V>[] tab, int hash) { 785 int n, index; Node<K,V> e; 786 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 787 resize(); 788 else if ((e = tab[index = (n - 1) & hash]) != null) { 789 TreeNode<K,V> hd = null, tl = null; 790 do { 791 TreeNode<K,V> p = replacementTreeNode(e, null); 792 if (tl == null) 793 hd = p; 794 else { 795 p.prev = tl; 796 tl.next = p; 797 } 798 tl = p; 799 } while ((e = e.next) != null); 800 if ((tab[index] = hd) != null) 801 hd.treeify(this, tab); 802 } 803 } 804 805 /** 806 * Copies all of the mappings from the specified map to this map. 807 * These mappings will replace any mappings that this map had for 808 * any of the keys currently in the specified map. 809 * 810 * @param m mappings to be stored in this map 811 * @throws NullPointerException if the specified map is null 812 */ 813 public void putAll(Map<? extends K, ? extends V> m) { 814 putMapEntries(m, true); 815 } 816 817 /** 818 * Removes the mapping for the specified key from this map if present. 819 * 820 * @param key key whose mapping is to be removed from the map 821 * @return the previous value associated with <tt>key</tt>, or 822 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 823 * (A <tt>null</tt> return can also indicate that the map 824 * previously associated <tt>null</tt> with <tt>key</tt>.) 825 */ 826 public V remove(Object key) { 827 Node<K,V> e; 828 return (e = removeNode(hash(key), key, null, false, true)) == null ? 829 null : e.value; 830 } 831 832 /** 833 * Implements Map.remove and related methods 834 * 835 * @param hash hash for key 836 * @param key the key 837 * @param value the value to match if matchValue, else ignored 838 * @param matchValue if true only remove if value is equal 839 * @param movable if false do not move other nodes while removing 840 * @return the node, or null if none 841 */ 842 final Node<K,V> removeNode(int hash, Object key, Object value, 843 boolean matchValue, boolean movable) { 844 Node<K,V>[] tab; Node<K,V> p; int n, index; 845 if ((tab = table) != null && (n = tab.length) > 0 && 846 (p = tab[index = (n - 1) & hash]) != null) { 847 Node<K,V> node = null, e; K k; V v; 848 if (p.hash == hash && 849 ((k = p.key) == key || (key != null && key.equals(k)))) 850 node = p; 851 else if ((e = p.next) != null) { 852 if (p instanceof TreeNode) 853 node = ((TreeNode<K,V>)p).getTreeNode(this, hash, key); 854 else { 855 do { 856 if (e.hash == hash && 857 ((k = e.key) == key || 858 (key != null && key.equals(k)))) { 859 node = e; 860 break; 861 } 862 p = e; 863 } while ((e = e.next) != null); 864 } 865 } 866 if (node != null && (!matchValue || (v = node.value) == value || 867 (value != null && value.equals(v)))) { 868 if (node instanceof TreeNode) 869 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); 870 else if (node == p) 871 tab[index] = node.next; 872 else 873 p.next = node.next; 874 ++modCount; 875 --size; 876 afterNodeRemoval(node); 877 return node; 878 } 879 } 880 return null; 881 } 882 883 /** 884 * Removes all of the mappings from this map. 885 * The map will be empty after this call returns. 886 */ 887 public void clear() { 888 Node<K,V>[] tab; 889 modCount++; 890 if ((tab = table) != null && size > 0) { 891 size = 0; 892 for (int i = 0; i < tab.length; ++i) 893 tab[i] = null; 894 } 895 } 896 897 /** 898 * Returns <tt>true</tt> if this map maps one or more keys to the 899 * specified value. 900 * 901 * @param value value whose presence in this map is to be tested 902 * @return <tt>true</tt> if this map maps one or more keys to the 903 * specified value 904 */ 905 public boolean containsValue(Object value) { 906 Node<K,V>[] tab; V v; 907 if ((tab = table) != null && size > 0) { 908 for (Node<K, V> e : tab) { 909 for (; e != null; e = e.next) { 910 if ((v = e.value) == value || 911 (value != null && value.equals(v))) 912 return true; 913 } 914 } 915 } 916 return false; 917 } 918 919 /** 920 * Returns a {@link Set} view of the keys contained in this map. 921 * The set is backed by the map, so changes to the map are 922 * reflected in the set, and vice-versa. If the map is modified 923 * while an iteration over the set is in progress (except through 924 * the iterator's own <tt>remove</tt> operation), the results of 925 * the iteration are undefined. The set supports element removal, 926 * which removes the corresponding mapping from the map, via the 927 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 928 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 929 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 930 * operations. 931 * 932 * @return a set view of the keys contained in this map 933 */ 934 public Set<K> keySet() { 935 Set<K> ks; 936 return (ks = keySet) == null ? (keySet = new KeySet()) : ks; 937 } 938 939 final class KeySet extends AbstractSet<K> { 940 public final int size() { return size; } 941 public final void clear() { HashMap.this.clear(); } 942 public final Iterator<K> iterator() { return new KeyIterator(); } 943 public final boolean contains(Object o) { return containsKey(o); } 944 public final boolean remove(Object key) { 945 return removeNode(hash(key), key, null, false, true) != null; 946 } 947 public final Spliterator<K> spliterator() { 948 return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0); 949 } 950 public final void forEach(Consumer<? super K> action) { 951 Node<K,V>[] tab; 952 if (action == null) 953 throw new NullPointerException(); 954 if (size > 0 && (tab = table) != null) { 955 int mc = modCount; 956 for (Node<K, V> e : tab) { 957 for (; e != null; e = e.next) 958 action.accept(e.key); 959 } 960 if (modCount != mc) 961 throw new ConcurrentModificationException(); 962 } 963 } 964 } 965 966 /** 967 * Returns a {@link Collection} view of the values contained in this map. 968 * The collection is backed by the map, so changes to the map are 969 * reflected in the collection, and vice-versa. If the map is 970 * modified while an iteration over the collection is in progress 971 * (except through the iterator's own <tt>remove</tt> operation), 972 * the results of the iteration are undefined. The collection 973 * supports element removal, which removes the corresponding 974 * mapping from the map, via the <tt>Iterator.remove</tt>, 975 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 976 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 977 * support the <tt>add</tt> or <tt>addAll</tt> operations. 978 * 979 * @return a view of the values contained in this map 980 */ 981 public Collection<V> values() { 982 Collection<V> vs; 983 return (vs = values) == null ? (values = new Values()) : vs; 984 } 985 986 final class Values extends AbstractCollection<V> { 987 public final int size() { return size; } 988 public final void clear() { HashMap.this.clear(); } 989 public final Iterator<V> iterator() { return new ValueIterator(); } 990 public final boolean contains(Object o) { return containsValue(o); } 991 public final Spliterator<V> spliterator() { 992 return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0); 993 } 994 public final void forEach(Consumer<? super V> action) { 995 Node<K,V>[] tab; 996 if (action == null) 997 throw new NullPointerException(); 998 if (size > 0 && (tab = table) != null) { 999 int mc = modCount; 1000 for (Node<K, V> e : tab) { 1001 for (; e != null; e = e.next) 1002 action.accept(e.value); 1003 } 1004 if (modCount != mc) 1005 throw new ConcurrentModificationException(); 1006 } 1007 } 1008 } 1009 1010 /** 1011 * Returns a {@link Set} view of the mappings contained in this map. 1012 * The set is backed by the map, so changes to the map are 1013 * reflected in the set, and vice-versa. If the map is modified 1014 * while an iteration over the set is in progress (except through 1015 * the iterator's own <tt>remove</tt> operation, or through the 1016 * <tt>setValue</tt> operation on a map entry returned by the 1017 * iterator) the results of the iteration are undefined. The set 1018 * supports element removal, which removes the corresponding 1019 * mapping from the map, via the <tt>Iterator.remove</tt>, 1020 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 1021 * <tt>clear</tt> operations. It does not support the 1022 * <tt>add</tt> or <tt>addAll</tt> operations. 1023 * 1024 * @return a set view of the mappings contained in this map 1025 */ 1026 public Set<Map.Entry<K,V>> entrySet() { 1027 Set<Map.Entry<K,V>> es; 1028 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; 1029 } 1030 1031 final class EntrySet extends AbstractSet<Map.Entry<K,V>> { 1032 public final int size() { return size; } 1033 public final void clear() { HashMap.this.clear(); } 1034 public final Iterator<Map.Entry<K,V>> iterator() { 1035 return new EntryIterator(); 1036 } 1037 public final boolean contains(Object o) { 1038 if (!(o instanceof Map.Entry)) 1039 return false; 1040 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 1041 Object key = e.getKey(); 1042 Node<K,V> candidate = getNode(hash(key), key); 1043 return candidate != null && candidate.equals(e); 1044 } 1045 public final boolean remove(Object o) { 1046 if (o instanceof Map.Entry) { 1047 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 1048 Object key = e.getKey(); 1049 Object value = e.getValue(); 1050 return removeNode(hash(key), key, value, true, true) != null; 1051 } 1052 return false; 1053 } 1054 public final Spliterator<Map.Entry<K,V>> spliterator() { 1055 return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); 1056 } 1057 public final void forEach(Consumer<? super Map.Entry<K,V>> action) { 1058 Node<K,V>[] tab; 1059 if (action == null) 1060 throw new NullPointerException(); 1061 if (size > 0 && (tab = table) != null) { 1062 int mc = modCount; 1063 for (Node<K, V> e : tab) { 1064 for (; e != null; e = e.next) 1065 action.accept(e); 1066 } 1067 if (modCount != mc) 1068 throw new ConcurrentModificationException(); 1069 } 1070 } 1071 } 1072 1073 // Overrides of JDK8 Map extension methods 1074 1075 @Override 1076 public V getOrDefault(Object key, V defaultValue) { 1077 Node<K,V> e; 1078 return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; 1079 } 1080 1081 @Override 1082 public V putIfAbsent(K key, V value) { 1083 return putVal(hash(key), key, value, true, true); 1084 } 1085 1086 @Override 1087 public boolean remove(Object key, Object value) { 1088 return removeNode(hash(key), key, value, true, true) != null; 1089 } 1090 1091 @Override 1092 public boolean replace(K key, V oldValue, V newValue) { 1093 Node<K,V> e; V v; 1094 if ((e = getNode(hash(key), key)) != null && 1095 ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { 1096 e.value = newValue; 1097 afterNodeAccess(e); 1098 return true; 1099 } 1100 return false; 1101 } 1102 1103 @Override 1104 public V replace(K key, V value) { 1105 Node<K,V> e; 1106 if ((e = getNode(hash(key), key)) != null) { 1107 V oldValue = e.value; 1108 e.value = value; 1109 afterNodeAccess(e); 1110 return oldValue; 1111 } 1112 return null; 1113 } 1114 1115 @Override 1116 public V computeIfAbsent(K key, 1117 Function<? super K, ? extends V> mappingFunction) { 1118 if (mappingFunction == null) 1119 throw new NullPointerException(); 1120 int hash = hash(key); 1121 Node<K,V>[] tab; Node<K,V> first; int n, i; 1122 int binCount = 0; 1123 TreeNode<K,V> t = null; 1124 Node<K,V> old = null; 1125 if (size > threshold || (tab = table) == null || 1126 (n = tab.length) == 0) 1127 n = (tab = resize()).length; 1128 if ((first = tab[i = (n - 1) & hash]) != null) { 1129 if (first instanceof TreeNode) 1130 old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key); 1131 else { 1132 Node<K,V> e = first; K k; 1133 do { 1134 if (e.hash == hash && 1135 ((k = e.key) == key || (key != null && key.equals(k)))) { 1136 old = e; 1137 break; 1138 } 1139 ++binCount; 1140 } while ((e = e.next) != null); 1141 } 1142 V oldValue; 1143 if (old != null && (oldValue = old.value) != null) { 1144 afterNodeAccess(old); 1145 return oldValue; 1146 } 1147 } 1148 V v = mappingFunction.apply(key); 1149 if (v == null) { 1150 return null; 1151 } else if (old != null) { 1152 old.value = v; 1153 afterNodeAccess(old); 1154 return v; 1155 } 1156 else if (t != null) 1157 t.putTreeVal(this, tab, hash, key, v); 1158 else { 1159 tab[i] = newNode(hash, key, v, first); 1160 if (binCount >= TREEIFY_THRESHOLD - 1) 1161 treeifyBin(tab, hash); 1162 } 1163 ++modCount; 1164 ++size; 1165 afterNodeInsertion(true); 1166 return v; 1167 } 1168 1169 public V computeIfPresent(K key, 1170 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1171 if (remappingFunction == null) 1172 throw new NullPointerException(); 1173 Node<K,V> e; V oldValue; 1174 int hash = hash(key); 1175 if ((e = getNode(hash, key)) != null && 1176 (oldValue = e.value) != null) { 1177 V v = remappingFunction.apply(key, oldValue); 1178 if (v != null) { 1179 e.value = v; 1180 afterNodeAccess(e); 1181 return v; 1182 } 1183 else 1184 removeNode(hash, key, null, false, true); 1185 } 1186 return null; 1187 } 1188 1189 @Override 1190 public V compute(K key, 1191 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1192 if (remappingFunction == null) 1193 throw new NullPointerException(); 1194 int hash = hash(key); 1195 Node<K,V>[] tab; Node<K,V> first; int n, i; 1196 int binCount = 0; 1197 TreeNode<K,V> t = null; 1198 Node<K,V> old = null; 1199 if (size > threshold || (tab = table) == null || 1200 (n = tab.length) == 0) 1201 n = (tab = resize()).length; 1202 if ((first = tab[i = (n - 1) & hash]) != null) { 1203 if (first instanceof TreeNode) 1204 old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key); 1205 else { 1206 Node<K,V> e = first; K k; 1207 do { 1208 if (e.hash == hash && 1209 ((k = e.key) == key || (key != null && key.equals(k)))) { 1210 old = e; 1211 break; 1212 } 1213 ++binCount; 1214 } while ((e = e.next) != null); 1215 } 1216 } 1217 V oldValue = (old == null) ? null : old.value; 1218 V v = remappingFunction.apply(key, oldValue); 1219 if (old != null) { 1220 if (v != null) { 1221 old.value = v; 1222 afterNodeAccess(old); 1223 } 1224 else 1225 removeNode(hash, key, null, false, true); 1226 } 1227 else if (v != null) { 1228 if (t != null) 1229 t.putTreeVal(this, tab, hash, key, v); 1230 else { 1231 tab[i] = newNode(hash, key, v, first); 1232 if (binCount >= TREEIFY_THRESHOLD - 1) 1233 treeifyBin(tab, hash); 1234 } 1235 ++modCount; 1236 ++size; 1237 afterNodeInsertion(true); 1238 } 1239 return v; 1240 } 1241 1242 @Override 1243 public V merge(K key, V value, 1244 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1245 if (value == null) 1246 throw new NullPointerException(); 1247 if (remappingFunction == null) 1248 throw new NullPointerException(); 1249 int hash = hash(key); 1250 Node<K,V>[] tab; Node<K,V> first; int n, i; 1251 int binCount = 0; 1252 TreeNode<K,V> t = null; 1253 Node<K,V> old = null; 1254 if (size > threshold || (tab = table) == null || 1255 (n = tab.length) == 0) 1256 n = (tab = resize()).length; 1257 if ((first = tab[i = (n - 1) & hash]) != null) { 1258 if (first instanceof TreeNode) 1259 old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key); 1260 else { 1261 Node<K,V> e = first; K k; 1262 do { 1263 if (e.hash == hash && 1264 ((k = e.key) == key || (key != null && key.equals(k)))) { 1265 old = e; 1266 break; 1267 } 1268 ++binCount; 1269 } while ((e = e.next) != null); 1270 } 1271 } 1272 if (old != null) { 1273 V v; 1274 if (old.value != null) 1275 v = remappingFunction.apply(old.value, value); 1276 else 1277 v = value; 1278 if (v != null) { 1279 old.value = v; 1280 afterNodeAccess(old); 1281 } 1282 else 1283 removeNode(hash, key, null, false, true); 1284 return v; 1285 } 1286 if (value != null) { 1287 if (t != null) 1288 t.putTreeVal(this, tab, hash, key, value); 1289 else { 1290 tab[i] = newNode(hash, key, value, first); 1291 if (binCount >= TREEIFY_THRESHOLD - 1) 1292 treeifyBin(tab, hash); 1293 } 1294 ++modCount; 1295 ++size; 1296 afterNodeInsertion(true); 1297 } 1298 return value; 1299 } 1300 1301 @Override 1302 public void forEach(BiConsumer<? super K, ? super V> action) { 1303 Node<K,V>[] tab; 1304 if (action == null) 1305 throw new NullPointerException(); 1306 if (size > 0 && (tab = table) != null) { 1307 int mc = modCount; 1308 for (Node<K, V> e : tab) { 1309 for (; e != null; e = e.next) 1310 action.accept(e.key, e.value); 1311 } 1312 if (modCount != mc) 1313 throw new ConcurrentModificationException(); 1314 } 1315 } 1316 1317 @Override 1318 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1319 Node<K,V>[] tab; 1320 if (function == null) 1321 throw new NullPointerException(); 1322 if (size > 0 && (tab = table) != null) { 1323 int mc = modCount; 1324 for (Node<K, V> e : tab) { 1325 for (; e != null; e = e.next) { 1326 e.value = function.apply(e.key, e.value); 1327 } 1328 } 1329 if (modCount != mc) 1330 throw new ConcurrentModificationException(); 1331 } 1332 } 1333 1334 /* ------------------------------------------------------------ */ 1335 // Cloning and serialization 1336 1337 /** 1338 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and 1339 * values themselves are not cloned. 1340 * 1341 * @return a shallow copy of this map 1342 */ 1343 @SuppressWarnings("unchecked") 1344 @Override 1345 public Object clone() { 1346 HashMap<K,V> result; 1347 try { 1348 result = (HashMap<K,V>)super.clone(); 1349 } catch (CloneNotSupportedException e) { 1350 // this shouldn't happen, since we are Cloneable 1351 throw new InternalError(e); 1352 } 1353 result.reinitialize(); 1354 result.putMapEntries(this, false); 1355 return result; 1356 } 1357 1358 // These methods are also used when serializing HashSets 1359 final float loadFactor() { return loadFactor; } 1360 final int capacity() { 1361 return (table != null) ? table.length : 1362 (threshold > 0) ? threshold : 1363 DEFAULT_INITIAL_CAPACITY; 1364 } 1365 1366 /** 1367 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e., 1368 * serialize it). 1369 * 1370 * @serialData The <i>capacity</i> of the HashMap (the length of the 1371 * bucket array) is emitted (int), followed by the 1372 * <i>size</i> (an int, the number of key-value 1373 * mappings), followed by the key (Object) and value (Object) 1374 * for each key-value mapping. The key-value mappings are 1375 * emitted in no particular order. 1376 */ 1377 private void writeObject(java.io.ObjectOutputStream s) 1378 throws IOException { 1379 int buckets = capacity(); 1380 // Write out the threshold, loadfactor, and any hidden stuff 1381 s.defaultWriteObject(); 1382 s.writeInt(buckets); 1383 s.writeInt(size); 1384 internalWriteEntries(s); 1385 } 1386 1387 /** 1388 * Reconstitute the {@code HashMap} instance from a stream (i.e., 1389 * deserialize it). 1390 */ 1391 private void readObject(java.io.ObjectInputStream s) 1392 throws IOException, ClassNotFoundException { 1393 // Read in the threshold (ignored), loadfactor, and any hidden stuff 1394 s.defaultReadObject(); 1395 reinitialize(); 1396 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 1397 throw new InvalidObjectException("Illegal load factor: " + 1398 loadFactor); 1399 s.readInt(); // Read and ignore number of buckets 1400 int mappings = s.readInt(); // Read number of mappings (size) 1401 if (mappings < 0) 1402 throw new InvalidObjectException("Illegal mappings count: " + 1403 mappings); 1404 else if (mappings > 0) { // (if zero, use defaults) 1405 // Size the table using given load factor only if within 1406 // range of 0.25...4.0 1407 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f); 1408 float fc = (float)mappings / lf + 1.0f; 1409 int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ? 1410 DEFAULT_INITIAL_CAPACITY : 1411 (fc >= MAXIMUM_CAPACITY) ? 1412 MAXIMUM_CAPACITY : 1413 tableSizeFor((int)fc)); 1414 float ft = (float)cap * lf; 1415 threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ? 1416 (int)ft : Integer.MAX_VALUE); 1417 @SuppressWarnings({"rawtypes","unchecked"}) 1418 Node<K,V>[] tab = (Node<K,V>[])new Node[cap]; 1419 table = tab; 1420 1421 // Read the keys and values, and put the mappings in the HashMap 1422 for (int i = 0; i < mappings; i++) { 1423 @SuppressWarnings("unchecked") 1424 K key = (K) s.readObject(); 1425 @SuppressWarnings("unchecked") 1426 V value = (V) s.readObject(); 1427 putVal(hash(key), key, value, false, false); 1428 } 1429 } 1430 } 1431 1432 /* ------------------------------------------------------------ */ 1433 // iterators 1434 1435 abstract class HashIterator { 1436 Node<K,V> next; // next entry to return 1437 Node<K,V> current; // current entry 1438 int expectedModCount; // for fast-fail 1439 int index; // current slot 1440 1441 HashIterator() { 1442 expectedModCount = modCount; 1443 Node<K,V>[] t = table; 1444 current = next = null; 1445 index = 0; 1446 if (t != null && size > 0) { // advance to first entry 1447 do {} while (index < t.length && (next = t[index++]) == null); 1448 } 1449 } 1450 1451 public final boolean hasNext() { 1452 return next != null; 1453 } 1454 1455 final Node<K,V> nextNode() { 1456 Node<K,V>[] t; 1457 Node<K,V> e = next; 1458 if (modCount != expectedModCount) 1459 throw new ConcurrentModificationException(); 1460 if (e == null) 1461 throw new NoSuchElementException(); 1462 if ((next = (current = e).next) == null && (t = table) != null) { 1463 do {} while (index < t.length && (next = t[index++]) == null); 1464 } 1465 return e; 1466 } 1467 1468 public final void remove() { 1469 Node<K,V> p = current; 1470 if (p == null) 1471 throw new IllegalStateException(); 1472 if (modCount != expectedModCount) 1473 throw new ConcurrentModificationException(); 1474 current = null; 1475 K key = p.key; 1476 removeNode(hash(key), key, null, false, false); 1477 expectedModCount = modCount; 1478 } 1479 } 1480 1481 final class KeyIterator extends HashIterator 1482 implements Iterator<K> { 1483 public final K next() { return nextNode().key; } 1484 } 1485 1486 final class ValueIterator extends HashIterator 1487 implements Iterator<V> { 1488 public final V next() { return nextNode().value; } 1489 } 1490 1491 final class EntryIterator extends HashIterator 1492 implements Iterator<Map.Entry<K,V>> { 1493 public final Map.Entry<K,V> next() { return nextNode(); } 1494 } 1495 1496 /* ------------------------------------------------------------ */ 1497 // spliterators 1498 1499 static class HashMapSpliterator<K,V> { 1500 final HashMap<K,V> map; 1501 Node<K,V> current; // current node 1502 int index; // current index, modified on advance/split 1503 int fence; // one past last index 1504 int est; // size estimate 1505 int expectedModCount; // for comodification checks 1506 1507 HashMapSpliterator(HashMap<K,V> m, int origin, 1508 int fence, int est, 1509 int expectedModCount) { 1510 this.map = m; 1511 this.index = origin; 1512 this.fence = fence; 1513 this.est = est; 1514 this.expectedModCount = expectedModCount; 1515 } 1516 1517 final int getFence() { // initialize fence and size on first use 1518 int hi; 1519 if ((hi = fence) < 0) { 1520 HashMap<K,V> m = map; 1521 est = m.size; 1522 expectedModCount = m.modCount; 1523 Node<K,V>[] tab = m.table; 1524 hi = fence = (tab == null) ? 0 : tab.length; 1525 } 1526 return hi; 1527 } 1528 1529 public final long estimateSize() { 1530 getFence(); // force init 1531 return (long) est; 1532 } 1533 } 1534 1535 static final class KeySpliterator<K,V> 1536 extends HashMapSpliterator<K,V> 1537 implements Spliterator<K> { 1538 KeySpliterator(HashMap<K,V> m, int origin, int fence, int est, 1539 int expectedModCount) { 1540 super(m, origin, fence, est, expectedModCount); 1541 } 1542 1543 public KeySpliterator<K,V> trySplit() { 1544 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1545 return (lo >= mid || current != null) ? null : 1546 new KeySpliterator<>(map, lo, index = mid, est >>>= 1, 1547 expectedModCount); 1548 } 1549 1550 public void forEachRemaining(Consumer<? super K> action) { 1551 int i, hi, mc; 1552 if (action == null) 1553 throw new NullPointerException(); 1554 HashMap<K,V> m = map; 1555 Node<K,V>[] tab = m.table; 1556 if ((hi = fence) < 0) { 1557 mc = expectedModCount = m.modCount; 1558 hi = fence = (tab == null) ? 0 : tab.length; 1559 } 1560 else 1561 mc = expectedModCount; 1562 if (tab != null && tab.length >= hi && 1563 (i = index) >= 0 && (i < (index = hi) || current != null)) { 1564 Node<K,V> p = current; 1565 current = null; 1566 do { 1567 if (p == null) 1568 p = tab[i++]; 1569 else { 1570 action.accept(p.key); 1571 p = p.next; 1572 } 1573 } while (p != null || i < hi); 1574 if (m.modCount != mc) 1575 throw new ConcurrentModificationException(); 1576 } 1577 } 1578 1579 public boolean tryAdvance(Consumer<? super K> action) { 1580 int hi; 1581 if (action == null) 1582 throw new NullPointerException(); 1583 Node<K,V>[] tab = map.table; 1584 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { 1585 while (current != null || index < hi) { 1586 if (current == null) 1587 current = tab[index++]; 1588 else { 1589 K k = current.key; 1590 current = current.next; 1591 action.accept(k); 1592 if (map.modCount != expectedModCount) 1593 throw new ConcurrentModificationException(); 1594 return true; 1595 } 1596 } 1597 } 1598 return false; 1599 } 1600 1601 public int characteristics() { 1602 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | 1603 Spliterator.DISTINCT; 1604 } 1605 } 1606 1607 static final class ValueSpliterator<K,V> 1608 extends HashMapSpliterator<K,V> 1609 implements Spliterator<V> { 1610 ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est, 1611 int expectedModCount) { 1612 super(m, origin, fence, est, expectedModCount); 1613 } 1614 1615 public ValueSpliterator<K,V> trySplit() { 1616 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1617 return (lo >= mid || current != null) ? null : 1618 new ValueSpliterator<>(map, lo, index = mid, est >>>= 1, 1619 expectedModCount); 1620 } 1621 1622 public void forEachRemaining(Consumer<? super V> action) { 1623 int i, hi, mc; 1624 if (action == null) 1625 throw new NullPointerException(); 1626 HashMap<K,V> m = map; 1627 Node<K,V>[] tab = m.table; 1628 if ((hi = fence) < 0) { 1629 mc = expectedModCount = m.modCount; 1630 hi = fence = (tab == null) ? 0 : tab.length; 1631 } 1632 else 1633 mc = expectedModCount; 1634 if (tab != null && tab.length >= hi && 1635 (i = index) >= 0 && (i < (index = hi) || current != null)) { 1636 Node<K,V> p = current; 1637 current = null; 1638 do { 1639 if (p == null) 1640 p = tab[i++]; 1641 else { 1642 action.accept(p.value); 1643 p = p.next; 1644 } 1645 } while (p != null || i < hi); 1646 if (m.modCount != mc) 1647 throw new ConcurrentModificationException(); 1648 } 1649 } 1650 1651 public boolean tryAdvance(Consumer<? super V> action) { 1652 int hi; 1653 if (action == null) 1654 throw new NullPointerException(); 1655 Node<K,V>[] tab = map.table; 1656 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { 1657 while (current != null || index < hi) { 1658 if (current == null) 1659 current = tab[index++]; 1660 else { 1661 V v = current.value; 1662 current = current.next; 1663 action.accept(v); 1664 if (map.modCount != expectedModCount) 1665 throw new ConcurrentModificationException(); 1666 return true; 1667 } 1668 } 1669 } 1670 return false; 1671 } 1672 1673 public int characteristics() { 1674 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0); 1675 } 1676 } 1677 1678 static final class EntrySpliterator<K,V> 1679 extends HashMapSpliterator<K,V> 1680 implements Spliterator<Map.Entry<K,V>> { 1681 EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est, 1682 int expectedModCount) { 1683 super(m, origin, fence, est, expectedModCount); 1684 } 1685 1686 public EntrySpliterator<K,V> trySplit() { 1687 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 1688 return (lo >= mid || current != null) ? null : 1689 new EntrySpliterator<>(map, lo, index = mid, est >>>= 1, 1690 expectedModCount); 1691 } 1692 1693 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) { 1694 int i, hi, mc; 1695 if (action == null) 1696 throw new NullPointerException(); 1697 HashMap<K,V> m = map; 1698 Node<K,V>[] tab = m.table; 1699 if ((hi = fence) < 0) { 1700 mc = expectedModCount = m.modCount; 1701 hi = fence = (tab == null) ? 0 : tab.length; 1702 } 1703 else 1704 mc = expectedModCount; 1705 if (tab != null && tab.length >= hi && 1706 (i = index) >= 0 && (i < (index = hi) || current != null)) { 1707 Node<K,V> p = current; 1708 current = null; 1709 do { 1710 if (p == null) 1711 p = tab[i++]; 1712 else { 1713 action.accept(p); 1714 p = p.next; 1715 } 1716 } while (p != null || i < hi); 1717 if (m.modCount != mc) 1718 throw new ConcurrentModificationException(); 1719 } 1720 } 1721 1722 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) { 1723 int hi; 1724 if (action == null) 1725 throw new NullPointerException(); 1726 Node<K,V>[] tab = map.table; 1727 if (tab != null && tab.length >= (hi = getFence()) && index >= 0) { 1728 while (current != null || index < hi) { 1729 if (current == null) 1730 current = tab[index++]; 1731 else { 1732 Node<K,V> e = current; 1733 current = current.next; 1734 action.accept(e); 1735 if (map.modCount != expectedModCount) 1736 throw new ConcurrentModificationException(); 1737 return true; 1738 } 1739 } 1740 } 1741 return false; 1742 } 1743 1744 public int characteristics() { 1745 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) | 1746 Spliterator.DISTINCT; 1747 } 1748 } 1749 1750 /* ------------------------------------------------------------ */ 1751 // LinkedHashMap support 1752 1753 1754 /* 1755 * The following package-protected methods are designed to be 1756 * overridden by LinkedHashMap, but not by any other subclass. 1757 * Nearly all other internal methods are also package-protected 1758 * but are declared final, so can be used by LinkedHashMap, view 1759 * classes, and HashSet. 1760 */ 1761 1762 // Create a regular (non-tree) node 1763 Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { 1764 return new Node<>(hash, key, value, next); 1765 } 1766 1767 // For conversion from TreeNodes to plain nodes 1768 Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { 1769 return new Node<>(p.hash, p.key, p.value, next); 1770 } 1771 1772 // Create a tree bin node 1773 TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { 1774 return new TreeNode<>(hash, key, value, next); 1775 } 1776 1777 // For treeifyBin 1778 TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { 1779 return new TreeNode<>(p.hash, p.key, p.value, next); 1780 } 1781 1782 /** 1783 * Reset to initial default state. Called by clone and readObject. 1784 */ 1785 void reinitialize() { 1786 table = null; 1787 entrySet = null; 1788 keySet = null; 1789 values = null; 1790 modCount = 0; 1791 threshold = 0; 1792 size = 0; 1793 } 1794 1795 // Callbacks to allow LinkedHashMap post-actions 1796 void afterNodeAccess(Node<K,V> p) { } 1797 void afterNodeInsertion(boolean evict) { } 1798 void afterNodeRemoval(Node<K,V> p) { } 1799 1800 // Called only from writeObject, to ensure compatible ordering. 1801 void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException { 1802 Node<K,V>[] tab; 1803 if (size > 0 && (tab = table) != null) { 1804 for (Node<K, V> e : tab) { 1805 for (; e != null; e = e.next) { 1806 s.writeObject(e.key); 1807 s.writeObject(e.value); 1808 } 1809 } 1810 } 1811 } 1812 1813 /* ------------------------------------------------------------ */ 1814 // Tree bins 1815 1816 /** 1817 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn 1818 * extends Node) so can be used as extension of either regular or 1819 * linked node. 1820 */ 1821 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 1822 TreeNode<K,V> parent; // red-black tree links 1823 TreeNode<K,V> left; 1824 TreeNode<K,V> right; 1825 TreeNode<K,V> prev; // needed to unlink next upon deletion 1826 boolean red; 1827 TreeNode(int hash, K key, V val, Node<K,V> next) { 1828 super(hash, key, val, next); 1829 } 1830 1831 /** 1832 * Returns root of tree containing this node. 1833 */ 1834 final TreeNode<K,V> root() { 1835 for (TreeNode<K,V> r = this, p;;) { 1836 if ((p = r.parent) == null) 1837 return r; 1838 r = p; 1839 } 1840 } 1841 1842 /** 1843 * Ensures that the given root is the first node of its bin. 1844 */ 1845 static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { 1846 int n; 1847 if (root != null && tab != null && (n = tab.length) > 0) { 1848 int index = (n - 1) & root.hash; 1849 TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; 1850 if (root != first) { 1851 Node<K,V> rn; 1852 tab[index] = root; 1853 TreeNode<K,V> rp = root.prev; 1854 if ((rn = root.next) != null) 1855 ((TreeNode<K,V>)rn).prev = rp; 1856 if (rp != null) 1857 rp.next = rn; 1858 if (first != null) 1859 first.prev = root; 1860 root.next = first; 1861 root.prev = null; 1862 } 1863 assert checkInvariants(root); 1864 } 1865 } 1866 1867 /** 1868 * Finds the node starting at root p with the given hash and key. 1869 * The kc argument caches comparableClassFor(key) upon first use 1870 * comparing keys. 1871 */ 1872 final TreeNode<K,V> find(HashMap<K,V> map, int h, Object k, Class<?> kc) { 1873 TreeNode<K,V> p = this; 1874 do { 1875 int ph, dir; K pk; 1876 TreeNode<K,V> pl = p.left, pr = p.right, q; 1877 if ((ph = p.hash) > h) 1878 p = pl; 1879 else if (ph < h) 1880 p = pr; 1881 else if ((pk = p.key) == k || (k != null && k.equals(pk))) 1882 return p; 1883 else if (pl == null) 1884 p = pr; 1885 else if (pr == null) 1886 p = pl; 1887 else if ((kc != null || 1888 (kc = map.comparableClassFor(k)) != null) && 1889 (dir = compareComparables(kc, k, pk)) != 0) 1890 p = (dir < 0) ? pl : pr; 1891 else if ((q = pr.find(map, h, k, kc)) != null) 1892 return q; 1893 else 1894 p = pl; 1895 } while (p != null); 1896 return null; 1897 } 1898 1899 /** 1900 * Calls find for root node. 1901 */ 1902 final TreeNode<K,V> getTreeNode(HashMap<K,V> map, int h, Object k) { 1903 return ((parent != null) ? root() : this).find(map, h, k, null); 1904 } 1905 1906 /** 1907 * Tie-breaking utility for ordering insertions when equal 1908 * hashCodes and non-comparable. We don't require a total 1909 * order, just a consistent insertion rule to maintain 1910 * equivalence across rebalancings. Tie-breaking further than 1911 * necessary simplifies testing a bit. 1912 */ 1913 static int tieBreakOrder(Object a, Object b) { 1914 int d; 1915 if (a == null || b == null || 1916 (d = a.getClass().getName(). 1917 compareTo(b.getClass().getName())) == 0) 1918 d = (System.identityHashCode(a) <= System.identityHashCode(b) ? 1919 -1 : 1); 1920 return d; 1921 } 1922 1923 /** 1924 * Forms tree of the nodes linked from this node. 1925 * @return root of tree 1926 */ 1927 final void treeify(HashMap<K,V> map, Node<K,V>[] tab) { 1928 TreeNode<K,V> root = null; 1929 for (TreeNode<K,V> x = this, next; x != null; x = next) { 1930 next = (TreeNode<K,V>)x.next; 1931 x.left = x.right = null; 1932 if (root == null) { 1933 x.parent = null; 1934 x.red = false; 1935 root = x; 1936 } 1937 else { 1938 K k = x.key; 1939 int h = x.hash; 1940 Class<?> kc = null; 1941 for (TreeNode<K,V> p = root;;) { 1942 int dir, ph; 1943 K pk = p.key; 1944 if ((ph = p.hash) > h) 1945 dir = -1; 1946 else if (ph < h) 1947 dir = 1; 1948 else if ((kc == null && 1949 (kc = map.comparableClassFor(k)) == null) || 1950 (dir = compareComparables(kc, k, pk)) == 0) 1951 dir = tieBreakOrder(k, pk); 1952 1953 TreeNode<K,V> xp = p; 1954 if ((p = (dir <= 0) ? p.left : p.right) == null) { 1955 x.parent = xp; 1956 if (dir <= 0) 1957 xp.left = x; 1958 else 1959 xp.right = x; 1960 root = balanceInsertion(root, x); 1961 break; 1962 } 1963 } 1964 } 1965 } 1966 moveRootToFront(tab, root); 1967 } 1968 1969 /** 1970 * Returns a list of non-TreeNodes replacing those linked from 1971 * this node. 1972 */ 1973 final Node<K,V> untreeify(HashMap<K,V> map) { 1974 Node<K,V> hd = null, tl = null; 1975 for (Node<K,V> q = this; q != null; q = q.next) { 1976 Node<K,V> p = map.replacementNode(q, null); 1977 if (tl == null) 1978 hd = p; 1979 else 1980 tl.next = p; 1981 tl = p; 1982 } 1983 return hd; 1984 } 1985 1986 /** 1987 * Tree version of putVal. 1988 */ 1989 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, 1990 int h, K k, V v) { 1991 Class<?> kc = null; 1992 boolean searched = false; 1993 TreeNode<K,V> root = (parent != null) ? root() : this; 1994 for (TreeNode<K,V> p = root;;) { 1995 int dir, ph; K pk; 1996 if ((ph = p.hash) > h) 1997 dir = -1; 1998 else if (ph < h) 1999 dir = 1; 2000 else if ((pk = p.key) == k || (k != null && k.equals(pk))) 2001 return p; 2002 else if ((kc == null && 2003 (kc = map.comparableClassFor(k)) == null) || 2004 (dir = compareComparables(kc, k, pk)) == 0) { 2005 if (!searched) { 2006 TreeNode<K,V> q, ch; 2007 searched = true; 2008 if (((ch = p.left) != null && 2009 (q = ch.find(map, h, k, kc)) != null) || 2010 ((ch = p.right) != null && 2011 (q = ch.find(map, h, k, kc)) != null)) 2012 return q; 2013 } 2014 dir = tieBreakOrder(k, pk); 2015 } 2016 2017 TreeNode<K,V> xp = p; 2018 if ((p = (dir <= 0) ? p.left : p.right) == null) { 2019 Node<K,V> xpn = xp.next; 2020 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); 2021 if (dir <= 0) 2022 xp.left = x; 2023 else 2024 xp.right = x; 2025 xp.next = x; 2026 x.parent = x.prev = xp; 2027 if (xpn != null) 2028 ((TreeNode<K,V>)xpn).prev = x; 2029 moveRootToFront(tab, balanceInsertion(root, x)); 2030 return null; 2031 } 2032 } 2033 } 2034 2035 /** 2036 * Removes the given node, that must be present before this call. 2037 * This is messier than typical red-black deletion code because we 2038 * cannot swap the contents of an interior node with a leaf 2039 * successor that is pinned by "next" pointers that are accessible 2040 * independently during traversal. So instead we swap the tree 2041 * linkages. If the current tree appears to have too few nodes, 2042 * the bin is converted back to a plain bin. (The test triggers 2043 * somewhere between 2 and 6 nodes, depending on tree structure). 2044 */ 2045 final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, 2046 boolean movable) { 2047 int n; 2048 if (tab == null || (n = tab.length) == 0) 2049 return; 2050 int index = (n - 1) & hash; 2051 TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; 2052 TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; 2053 if (pred == null) 2054 tab[index] = first = succ; 2055 else 2056 pred.next = succ; 2057 if (succ != null) 2058 succ.prev = pred; 2059 if (first == null) 2060 return; 2061 if (root.parent != null) 2062 root = root.root(); 2063 if (root == null || root.right == null || 2064 (rl = root.left) == null || rl.left == null) { 2065 tab[index] = first.untreeify(map); // too small 2066 return; 2067 } 2068 TreeNode<K,V> p = this, pl = left, pr = right, replacement; 2069 if (pl != null && pr != null) { 2070 TreeNode<K,V> s = pr, sl; 2071 while ((sl = s.left) != null) // find successor 2072 s = sl; 2073 boolean c = s.red; s.red = p.red; p.red = c; // swap colors 2074 TreeNode<K,V> sr = s.right; 2075 TreeNode<K,V> pp = p.parent; 2076 if (s == pr) { // p was s's direct parent 2077 p.parent = s; 2078 s.right = p; 2079 } 2080 else { 2081 TreeNode<K,V> sp = s.parent; 2082 if ((p.parent = sp) != null) { 2083 if (s == sp.left) 2084 sp.left = p; 2085 else 2086 sp.right = p; 2087 } 2088 if ((s.right = pr) != null) 2089 pr.parent = s; 2090 } 2091 p.left = null; 2092 if ((p.right = sr) != null) 2093 sr.parent = p; 2094 if ((s.left = pl) != null) 2095 pl.parent = s; 2096 if ((s.parent = pp) == null) 2097 root = s; 2098 else if (p == pp.left) 2099 pp.left = s; 2100 else 2101 pp.right = s; 2102 if (sr != null) 2103 replacement = sr; 2104 else 2105 replacement = p; 2106 } 2107 else if (pl != null) 2108 replacement = pl; 2109 else if (pr != null) 2110 replacement = pr; 2111 else 2112 replacement = p; 2113 if (replacement != p) { 2114 TreeNode<K,V> pp = replacement.parent = p.parent; 2115 if (pp == null) 2116 root = replacement; 2117 else if (p == pp.left) 2118 pp.left = replacement; 2119 else 2120 pp.right = replacement; 2121 p.left = p.right = p.parent = null; 2122 } 2123 2124 TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); 2125 2126 if (replacement == p) { // detach 2127 TreeNode<K,V> pp = p.parent; 2128 p.parent = null; 2129 if (pp != null) { 2130 if (p == pp.left) 2131 pp.left = null; 2132 else if (p == pp.right) 2133 pp.right = null; 2134 } 2135 } 2136 if (movable) 2137 moveRootToFront(tab, r); 2138 } 2139 2140 /** 2141 * Splits nodes in a tree bin into lower and upper tree bins, 2142 * or untreeifies if now too small. Called only from resize; 2143 * see above discussion about split bits and indices. 2144 * 2145 * @param map the map 2146 * @param tab the table for recording bin heads 2147 * @param index the index of the table being split 2148 * @param bit the bit of hash to split on 2149 */ 2150 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { 2151 TreeNode<K,V> b = this; 2152 // Relink into lo and hi lists, preserving order 2153 TreeNode<K,V> loHead = null, loTail = null; 2154 TreeNode<K,V> hiHead = null, hiTail = null; 2155 int lc = 0, hc = 0; 2156 for (TreeNode<K,V> e = b, next; e != null; e = next) { 2157 next = (TreeNode<K,V>)e.next; 2158 e.next = null; 2159 if ((e.hash & bit) == 0) { 2160 if ((e.prev = loTail) == null) 2161 loHead = e; 2162 else 2163 loTail.next = e; 2164 loTail = e; 2165 ++lc; 2166 } 2167 else { 2168 if ((e.prev = hiTail) == null) 2169 hiHead = e; 2170 else 2171 hiTail.next = e; 2172 hiTail = e; 2173 ++hc; 2174 } 2175 } 2176 2177 if (loHead != null) { 2178 if (lc <= UNTREEIFY_THRESHOLD) 2179 tab[index] = loHead.untreeify(map); 2180 else { 2181 tab[index] = loHead; 2182 if (hiHead != null) // (else is already treeified) 2183 loHead.treeify(map, tab); 2184 } 2185 } 2186 if (hiHead != null) { 2187 if (hc <= UNTREEIFY_THRESHOLD) 2188 tab[index + bit] = hiHead.untreeify(map); 2189 else { 2190 tab[index + bit] = hiHead; 2191 if (loHead != null) 2192 hiHead.treeify(map, tab); 2193 } 2194 } 2195 } 2196 2197 /* ------------------------------------------------------------ */ 2198 // Red-black tree methods, all adapted from CLR 2199 2200 static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, 2201 TreeNode<K,V> p) { 2202 TreeNode<K,V> r, pp, rl; 2203 if (p != null && (r = p.right) != null) { 2204 if ((rl = p.right = r.left) != null) 2205 rl.parent = p; 2206 if ((pp = r.parent = p.parent) == null) 2207 (root = r).red = false; 2208 else if (pp.left == p) 2209 pp.left = r; 2210 else 2211 pp.right = r; 2212 r.left = p; 2213 p.parent = r; 2214 } 2215 return root; 2216 } 2217 2218 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, 2219 TreeNode<K,V> p) { 2220 TreeNode<K,V> l, pp, lr; 2221 if (p != null && (l = p.left) != null) { 2222 if ((lr = p.left = l.right) != null) 2223 lr.parent = p; 2224 if ((pp = l.parent = p.parent) == null) 2225 (root = l).red = false; 2226 else if (pp.right == p) 2227 pp.right = l; 2228 else 2229 pp.left = l; 2230 l.right = p; 2231 p.parent = l; 2232 } 2233 return root; 2234 } 2235 2236 static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, 2237 TreeNode<K,V> x) { 2238 x.red = true; 2239 for (TreeNode<K,V> xp, xpp, xppl, xppr;;) { 2240 if ((xp = x.parent) == null) { 2241 x.red = false; 2242 return x; 2243 } 2244 else if (!xp.red || (xpp = xp.parent) == null) 2245 return root; 2246 if (xp == (xppl = xpp.left)) { 2247 if ((xppr = xpp.right) != null && xppr.red) { 2248 xppr.red = false; 2249 xp.red = false; 2250 xpp.red = true; 2251 x = xpp; 2252 } 2253 else { 2254 if (x == xp.right) { 2255 root = rotateLeft(root, x = xp); 2256 xpp = (xp = x.parent) == null ? null : xp.parent; 2257 } 2258 if (xp != null) { 2259 xp.red = false; 2260 if (xpp != null) { 2261 xpp.red = true; 2262 root = rotateRight(root, xpp); 2263 } 2264 } 2265 } 2266 } 2267 else { 2268 if (xppl != null && xppl.red) { 2269 xppl.red = false; 2270 xp.red = false; 2271 xpp.red = true; 2272 x = xpp; 2273 } 2274 else { 2275 if (x == xp.left) { 2276 root = rotateRight(root, x = xp); 2277 xpp = (xp = x.parent) == null ? null : xp.parent; 2278 } 2279 if (xp != null) { 2280 xp.red = false; 2281 if (xpp != null) { 2282 xpp.red = true; 2283 root = rotateLeft(root, xpp); 2284 } 2285 } 2286 } 2287 } 2288 } 2289 } 2290 2291 static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, 2292 TreeNode<K,V> x) { 2293 for (TreeNode<K,V> xp, xpl, xpr;;) { 2294 if (x == null || x == root) 2295 return root; 2296 else if ((xp = x.parent) == null) { 2297 x.red = false; 2298 return x; 2299 } 2300 else if (x.red) { 2301 x.red = false; 2302 return root; 2303 } 2304 else if ((xpl = xp.left) == x) { 2305 if ((xpr = xp.right) != null && xpr.red) { 2306 xpr.red = false; 2307 xp.red = true; 2308 root = rotateLeft(root, xp); 2309 xpr = (xp = x.parent) == null ? null : xp.right; 2310 } 2311 if (xpr == null) 2312 x = xp; 2313 else { 2314 TreeNode<K,V> sl = xpr.left, sr = xpr.right; 2315 if ((sr == null || !sr.red) && 2316 (sl == null || !sl.red)) { 2317 xpr.red = true; 2318 x = xp; 2319 } 2320 else { 2321 if (sr == null || !sr.red) { 2322 if (sl != null) 2323 sl.red = false; 2324 xpr.red = true; 2325 root = rotateRight(root, xpr); 2326 xpr = (xp = x.parent) == null ? 2327 null : xp.right; 2328 } 2329 if (xpr != null) { 2330 xpr.red = (xp == null) ? false : xp.red; 2331 if ((sr = xpr.right) != null) 2332 sr.red = false; 2333 } 2334 if (xp != null) { 2335 xp.red = false; 2336 root = rotateLeft(root, xp); 2337 } 2338 x = root; 2339 } 2340 } 2341 } 2342 else { // symmetric 2343 if (xpl != null && xpl.red) { 2344 xpl.red = false; 2345 xp.red = true; 2346 root = rotateRight(root, xp); 2347 xpl = (xp = x.parent) == null ? null : xp.left; 2348 } 2349 if (xpl == null) 2350 x = xp; 2351 else { 2352 TreeNode<K,V> sl = xpl.left, sr = xpl.right; 2353 if ((sl == null || !sl.red) && 2354 (sr == null || !sr.red)) { 2355 xpl.red = true; 2356 x = xp; 2357 } 2358 else { 2359 if (sl == null || !sl.red) { 2360 if (sr != null) 2361 sr.red = false; 2362 xpl.red = true; 2363 root = rotateLeft(root, xpl); 2364 xpl = (xp = x.parent) == null ? 2365 null : xp.left; 2366 } 2367 if (xpl != null) { 2368 xpl.red = (xp == null) ? false : xp.red; 2369 if ((sl = xpl.left) != null) 2370 sl.red = false; 2371 } 2372 if (xp != null) { 2373 xp.red = false; 2374 root = rotateRight(root, xp); 2375 } 2376 x = root; 2377 } 2378 } 2379 } 2380 } 2381 } 2382 2383 /** 2384 * Recursive invariant check 2385 */ 2386 static <K,V> boolean checkInvariants(TreeNode<K,V> t) { 2387 TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right, 2388 tb = t.prev, tn = (TreeNode<K,V>)t.next; 2389 if (tb != null && tb.next != t) 2390 return false; 2391 if (tn != null && tn.prev != t) 2392 return false; 2393 if (tp != null && t != tp.left && t != tp.right) 2394 return false; 2395 if (tl != null && (tl.parent != t || tl.hash > t.hash)) 2396 return false; 2397 if (tr != null && (tr.parent != t || tr.hash < t.hash)) 2398 return false; 2399 if (t.red && tl != null && tl.red && tr != null && tr.red) 2400 return false; 2401 if (tl != null && !checkInvariants(tl)) 2402 return false; 2403 if (tr != null && !checkInvariants(tr)) 2404 return false; 2405 return true; 2406 } 2407 } 2408 2409 }