1 /* 2 * Copyright (c) 1997, 2024, 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 org.openjdk.bench.valhalla.sandbox.corelibs.corelibs.mapprotos; 27 28 import java.io.IOException; 29 import java.io.InvalidObjectException; 30 import java.io.PrintStream; 31 import java.io.Serializable; 32 import java.lang.Boolean; 33 import java.lang.reflect.Field; 34 import java.lang.reflect.InvocationTargetException; 35 import java.lang.reflect.Method; 36 import java.util.AbstractCollection; 37 import java.util.AbstractMap; 38 import java.util.AbstractSet; 39 import java.util.Arrays; 40 import java.util.Collection; 41 import java.util.Collections; 42 import java.util.ConcurrentModificationException; 43 import java.util.Hashtable; 44 import java.util.Iterator; 45 import java.util.Map; 46 import java.util.Objects; 47 import java.util.Optional; 48 import java.util.TreeMap; 49 import java.util.NoSuchElementException; 50 import java.util.Set; 51 import java.util.Spliterator; 52 import java.util.function.BiConsumer; 53 import java.util.function.BiFunction; 54 import java.util.function.Consumer; 55 import java.util.function.Function; 56 57 /** 58 * HashMap using hashing and "open addressing". 59 * Hash entries are inline class instances. 60 * As described in <em>Introduction to Algorithms, 3rd Edition (The MIT Press)</em>, 61 * Section 11 Hash tables and Section 11.4 Open addressing. 62 * 63 * Open addressing is used to locate other entries for keys with the same hash. 64 * If multiple keys have the same hashcode, a rehashing mechanism 65 * is used to place the 2nd and subsequent 66 * key/value pairs at a non-optimal index in the table. Therefore, 67 * finding the entry for a desired key must rehash and examine subsequent 68 * entries until the value is value or it encounters an empty entry. 69 * When an entry is removed, the entry is marked as deleted, (not empty) 70 * to allow the search algorithm to keep looking; otherwise it would terminate 71 * the scan on the deleted entry, when it might be the case for some (other) key 72 * would have that same entry as part of its chain of possible locations for its hash. 73 * The default load factor (.75) should be re-evaluated in light of the open addressing 74 * computations. A higher number would reduce unused (wasted) space at the cost of 75 * increased search times, a lower number would increase unused (wasted) space but 76 * improve search times (assuming even hashcode distributions). 77 * Badly distributed hash values will result in incremental table growth and 78 * linear search performance. 79 * <p> 80 * During insertion the Robin Hood hash algorithm does a small optimization 81 * to reduce worst case rehash lengths. 82 * Removal of entries, does a compaction of the following entries to fill 83 * in free entries and reduce entry rehashling lengths based on 84 * "On Deletions in Open Addressing Hashing", by Rosa M. Jimenez and Conrado Martinz. 85 * 86 * <p> 87 * The only allocation that occurs during put operations is for the resizing of the entry table. 88 * 89 * <P> 90 * Hash table based implementation of the {@code Map} interface. This 91 * implementation provides all of the optional map operations, and permits 92 * {@code null} values and the {@code null} key. (The {@code HashMap} 93 * class is roughly equivalent to {@code Hashtable}, except that it is 94 * unsynchronized and permits nulls.) This class makes no guarantees as to 95 * the order of the map; in particular, it does not guarantee that the order 96 * will remain constant over time. 97 * 98 * <p>This implementation provides constant-time performance for the basic 99 * operations ({@code get} and {@code put}), assuming the hash function 100 * disperses the elements properly among the buckets. Iteration over 101 * collection views requires time proportional to the "capacity" of the 102 * {@code HashMap} instance (the number of buckets) plus its size (the number 103 * of key-value mappings). Thus, it's very important not to set the initial 104 * capacity too high (or the load factor too low) if iteration performance is 105 * important. 106 * 107 * <p>An instance of {@code HashMap} has two parameters that affect its 108 * performance: <i>initial capacity</i> and <i>load factor</i>. The 109 * <i>capacity</i> is the number of buckets in the hash table, and the initial 110 * capacity is simply the capacity at the time the hash table is created. The 111 * <i>load factor</i> is a measure of how full the hash table is allowed to 112 * get before its capacity is automatically increased. When the number of 113 * entries in the hash table exceeds the product of the load factor and the 114 * current capacity, the hash table is <i>rehashed</i> (that is, internal data 115 * structures are rebuilt) so that the hash table has approximately twice the 116 * number of buckets. 117 * 118 * <p>As a general rule, the default load factor (.75) offers a good 119 * tradeoff between time and space costs. Higher values decrease the 120 * space overhead but increase the lookup cost (reflected in most of 121 * the operations of the {@code HashMap} class, including 122 * {@code get} and {@code put}). The expected number of entries in 123 * the map and its load factor should be taken into account when 124 * setting its initial capacity, so as to minimize the number of 125 * rehash operations. If the initial capacity is greater than the 126 * maximum number of entries divided by the load factor, no rehash 127 * operations will ever occur. 128 * 129 * <p>If many mappings are to be stored in a {@code HashMap} 130 * instance, creating it with a sufficiently large capacity will allow 131 * the mappings to be stored more efficiently than letting it perform 132 * automatic rehashing as needed to grow the table. Note that using 133 * many keys with the same {@code hashCode()} is a sure way to slow 134 * down performance of any hash table. 135 * TBD: To ameliorate impact, when keys 136 * are {@link Comparable}, this class may use comparison order among 137 * keys to help break ties. 138 * 139 * <p><strong>Note that this implementation is not synchronized.</strong> 140 * If multiple threads access a hash map concurrently, and at least one of 141 * the threads modifies the map structurally, it <i>must</i> be 142 * synchronized externally. (A structural modification is any operation 143 * that adds or deletes one or more mappings; merely changing the value 144 * associated with a key that an instance already contains is not a 145 * structural modification.) This is typically accomplished by 146 * synchronizing on some object that naturally encapsulates the map. 147 * 148 * If no such object exists, the map should be "wrapped" using the 149 * {@link Collections#synchronizedMap Collections.synchronizedMap} 150 * method. This is best done at creation time, to prevent accidental 151 * unsynchronized access to the map:<pre> 152 * Map m = Collections.synchronizedMap(new HashMap(...));</pre> 153 * 154 * <p>The iterators returned by all of this class's "collection view methods" 155 * are <i>fail-fast</i>: if the map is structurally modified at any time after 156 * the iterator is created, in any way except through the iterator's own 157 * {@code remove} method, the iterator will throw a 158 * {@link ConcurrentModificationException}. Thus, in the face of concurrent 159 * modification, the iterator fails quickly and cleanly, rather than risking 160 * arbitrary, non-deterministic behavior at an undetermined time in the 161 * future. 162 * 163 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 164 * as it is, generally speaking, impossible to make any hard guarantees in the 165 * presence of unsynchronized concurrent modification. Fail-fast iterators 166 * throw {@code ConcurrentModificationException} on a best-effort basis. 167 * Therefore, it would be wrong to write a program that depended on this 168 * exception for its correctness: <i>the fail-fast behavior of iterators 169 * should be used only to detect bugs.</i> 170 * 171 * <p>This class is a member of the 172 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 173 * Java Collections Framework</a>. 174 * 175 * @param <K> the type of keys maintained by this map 176 * @param <V> the type of mapped values 177 * 178 * @author Doug Lea 179 * @author Josh Bloch 180 * @author Arthur van Hoff 181 * @author Neal Gafter 182 * @see Object#hashCode() 183 * @see Collection 184 * @see Map 185 * @see TreeMap 186 * @see Hashtable 187 * @since 1.2 188 */ 189 public class HashMap<K,V> extends XAbstractMap<K,V> 190 implements Map<K,V>, Cloneable, Serializable { 191 192 private static final long serialVersionUID = 362498820763181265L; 193 194 private static final boolean DEBUG = Boolean.getBoolean("DEBUG"); 195 private static final boolean VERIFYTABLEOK = Boolean.getBoolean("VERIFYTABLEOK"); 196 197 /* 198 * Implementation notes. 199 * 200 * This map usually acts as a binned (bucketed) hash table. 201 * The concurrent-programming-like SSA-based coding style helps 202 * avoid aliasing errors amid all of the twisty pointer operations. 203 */ 204 205 /** 206 * The default initial capacity - MUST be a power of two. 207 */ 208 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 209 210 /** 211 * The maximum capacity, used if a higher value is implicitly specified 212 * by either of the constructors with arguments. 213 * MUST be a power of two <= 1<<30. 214 */ 215 static final int MAXIMUM_CAPACITY = 1 << 30; 216 217 /** 218 * The load factor used when none specified in constructor. 219 */ 220 static final float DEFAULT_LOAD_FACTOR = 0.75f; 221 222 private final int REHASH_HASH = 2003; // Odd and small (a medium-small prime) 223 224 /** 225 * Basic hash bin node, used for most entries. 226 */ 227 static value class YNode<K,V> implements Map.Entry<K,V> { 228 final int hash; 229 final short probes; // maybe only a byte 230 final K key; 231 final V value; 232 233 YNode() { 234 this.hash = 0; 235 this.probes = 0; 236 this.key = null; 237 this.value = null; 238 } 239 240 YNode(int hash, K key, V value, int probes) { 241 this.hash = hash; 242 this.key = key; 243 this.value = value; 244 this.probes = (short)probes; 245 } 246 247 boolean isEmpty() { 248 return probes == 0; 249 } 250 251 boolean isValue() { 252 return probes > 0; 253 } 254 255 public final K getKey() { return key; } 256 public final V getValue() { return value; } 257 public final String toString() { return key + "=" + value + ", probes: " + probes 258 + ", hash: " + Integer.toString(hash, 16) 259 + ", hashCode: " + hashCode(); } 260 public final int hashCode() { 261 return Objects.hashCode(key) ^ Objects.hashCode(value); 262 } 263 264 public final V setValue(V newValue) { 265 throw new IllegalStateException("YNode cannot set a value"); 266 } 267 268 public final boolean equals(Object o) { 269 if (o == this) 270 return true; 271 if (o instanceof Map.Entry) { 272 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 273 if (Objects.equals(key, e.getKey()) && 274 Objects.equals(value, e.getValue())) 275 return true; 276 } 277 return false; 278 } 279 } 280 281 value class YNodeWrapper implements Map.Entry<K,V> { 282 final int index; 283 final YNode<K,V> entry; 284 285 YNodeWrapper(int index) { 286 this.index = index; 287 this.entry = table[index]; 288 } 289 290 public K getKey() { 291 return entry.key; 292 } 293 294 public V getValue() { 295 return entry.value; 296 } 297 298 public String toString() { 299 return entry.toString(); 300 } 301 302 public int hashCode() { 303 return entry.hashCode(); 304 } 305 306 public boolean equals(Object o) { 307 return entry.equals(o); 308 } 309 /** 310 * Replaces the value corresponding to this entry with the specified 311 * value (optional operation). (Writes through to the map.) The 312 * behavior of this call is undefined if the mapping has already been 313 * removed from the map (by the iterator's {@code remove} operation). 314 * 315 * @param value new value to be stored in this entry 316 * @return old value corresponding to the entry 317 * @throws UnsupportedOperationException if the {@code put} operation 318 * is not supported by the backing map 319 * @throws ClassCastException if the class of the specified value 320 * prevents it from being stored in the backing map 321 * @throws NullPointerException if the backing map does not permit 322 * null values, and the specified value is null 323 * @throws IllegalArgumentException if some property of this value 324 * prevents it from being stored in the backing map 325 * @throws IllegalStateException implementations may, but are not 326 * required to, throw this exception if the entry has been 327 * removed from the backing map. 328 */ 329 public V setValue(V value) { 330 table[index] = new YNode<>(entry.hash, entry.key, value, entry.probes); 331 return entry.value; 332 } 333 } 334 /* ---------------- Static utilities -------------- */ 335 336 /** 337 * Computes key.hashCode() and spreads (XORs) higher bits of hash 338 * to lower. Because the table uses power-of-two masking, sets of 339 * hashes that vary only in bits above the current mask will 340 * always collide. (Among known examples are sets of Float keys 341 * holding consecutive whole numbers in small tables.) So we 342 * apply a transform that spreads the impact of higher bits 343 * downward. There is a tradeoff between speed, utility, and 344 * quality of bit-spreading. Because many common sets of hashes 345 * are already reasonably distributed (so don't benefit from 346 * spreading), and because we use trees to handle large sets of 347 * collisions in bins, we just XOR some shifted bits in the 348 * cheapest possible way to reduce systematic lossage, as well as 349 * to incorporate impact of the highest bits that would otherwise 350 * never be used in index calculations because of table bounds. 351 */ 352 static final int hash(Object key) { 353 int h; 354 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 355 } 356 357 /** 358 * Returns a power of two size for the given target capacity. 359 */ 360 static final int tableSizeFor(int cap) { 361 int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); 362 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 363 } 364 365 /* ---------------- Fields -------------- */ 366 367 /** 368 * The table, initialized on first use, and resized as 369 * necessary. When allocated, length is always a power of two. 370 * (We also tolerate length zero in some operations to allow 371 * bootstrapping mechanics that are currently not needed.) 372 */ 373 transient YNode<K,V>[] table; 374 375 /** 376 * Holds cached entrySet(). Note that AbstractMap fields are used 377 * for keySet() and values(). 378 */ 379 transient Set<Map.Entry<K,V>> entrySet; 380 381 /** 382 * The number of key-value mappings contained in this map. 383 */ 384 transient int size; 385 386 /** 387 * The number of times this HashMap has been structurally modified 388 * Structural modifications are those that change the number of mappings in 389 * the HashMap or otherwise modify its internal structure (e.g., 390 * rehash). This field is used to make iterators on Collection-views of 391 * the HashMap fail-fast. (See ConcurrentModificationException). 392 */ 393 transient int modCount; 394 395 /** 396 * The next size value at which to resize (capacity * load factor). 397 * 398 * @serial 399 */ 400 // (The javadoc description is true upon serialization. 401 // Additionally, if the table array has not been allocated, this 402 // field holds the initial array capacity, or zero signifying 403 // DEFAULT_INITIAL_CAPACITY.) 404 int threshold; 405 406 /** 407 * The load factor for the hash table. 408 * 409 * @serial 410 */ 411 final float loadFactor; 412 413 private transient int[] getProbes = new int[16]; 414 private transient int[] putProbes = new int[16]; 415 private transient int[] notFoundProbes = new int[16]; 416 417 418 /* ---------------- Public operations -------------- */ 419 420 /** 421 * Constructs an empty {@code HashMap} with the specified initial 422 * capacity and load factor. 423 * 424 * @param initialCapacity the initial capacity 425 * @param loadFactor the load factor 426 * @throws IllegalArgumentException if the initial capacity is negative 427 * or the load factor is nonpositive 428 */ 429 public HashMap(int initialCapacity, float loadFactor) { 430 if (initialCapacity < 0) 431 throw new IllegalArgumentException("Illegal initial capacity: " + 432 initialCapacity); 433 if (initialCapacity > MAXIMUM_CAPACITY) 434 initialCapacity = MAXIMUM_CAPACITY; 435 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 436 throw new IllegalArgumentException("Illegal load factor: " + 437 loadFactor); 438 this.loadFactor = loadFactor; 439 this.threshold = tableSizeFor(initialCapacity); 440 } 441 442 /** 443 * Constructs an empty {@code HashMap} with the specified initial 444 * capacity and the default load factor (0.75). 445 * 446 * @param initialCapacity the initial capacity. 447 * @throws IllegalArgumentException if the initial capacity is negative. 448 */ 449 public HashMap(int initialCapacity) { 450 this(initialCapacity, DEFAULT_LOAD_FACTOR); 451 } 452 453 /** 454 * Constructs an empty {@code HashMap} with the default initial capacity 455 * (16) and the default load factor (0.75). 456 */ 457 public HashMap() { 458 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted 459 } 460 461 /** 462 * Constructs a new {@code HashMap} with the same mappings as the 463 * specified {@code Map}. The {@code HashMap} is created with 464 * default load factor (0.75) and an initial capacity sufficient to 465 * hold the mappings in the specified {@code Map}. 466 * 467 * @param m the map whose mappings are to be placed in this map 468 * @throws NullPointerException if the specified map is null 469 */ 470 public HashMap(Map<? extends K, ? extends V> m) { 471 this.loadFactor = DEFAULT_LOAD_FACTOR; 472 putMapEntries(m, false); 473 } 474 475 /** 476 * Implements Map.putAll and Map constructor. 477 * 478 * @param m the map 479 * @param evict false when initially constructing this map, else true. 480 */ 481 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 482 int s = m.size(); 483 if (s > 0) { 484 if (table == null) { // pre-size 485 float ft = ((float)s / loadFactor) + 1.0F; 486 int t = ((ft < (float)MAXIMUM_CAPACITY) ? 487 (int)ft : MAXIMUM_CAPACITY); 488 if (t > threshold) 489 threshold = tableSizeFor(t); 490 } else { 491 // Because of linked-list bucket constraints, we cannot 492 // expand all at once, but can reduce total resize 493 // effort by repeated doubling now vs later 494 while (s > threshold && table.length < MAXIMUM_CAPACITY) 495 resize(); 496 } 497 498 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 499 K key = e.getKey(); 500 V value = e.getValue(); 501 putVal(hash(key), key, value, false); 502 } 503 } 504 } 505 506 /** 507 * Returns the number of key-value mappings in this map. 508 * 509 * @return the number of key-value mappings in this map 510 */ 511 public int size() { 512 return size; 513 } 514 515 /** 516 * Returns {@code true} if this map contains no key-value mappings. 517 * 518 * @return {@code true} if this map contains no key-value mappings 519 */ 520 public boolean isEmpty() { 521 return size == 0; 522 } 523 524 /** 525 * Returns the value to which the specified key is mapped, 526 * or {@code null} if this map contains no mapping for the key. 527 * 528 * <p>More formally, if this map contains a mapping from a key 529 * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 530 * key.equals(k))}, then this method returns {@code v}; otherwise 531 * it returns {@code null}. (There can be at most one such mapping.) 532 * 533 * <p>A return value of {@code null} does not <i>necessarily</i> 534 * indicate that the map contains no mapping for the key; it's also 535 * possible that the map explicitly maps the key to {@code null}. 536 * The {@link #containsKey containsKey} operation may be used to 537 * distinguish these two cases. 538 * 539 * @see #put(Object, Object) 540 */ 541 public V get(Object key) { 542 final YNode<K, V>[] tab; 543 final int mask; 544 // int probes = 0; 545 if ((tab = table) != null && (mask = tab.length - 1) >= 0) { 546 final int hash = hash(key); 547 int h = hash; 548 YNode<K, V> entry; 549 while ((entry = tab[(mask & h)]).isValue()) { 550 // probes++; 551 K k; 552 if (entry.hash == hash && 553 ((k = entry.key) == key || (key != null && key.equals(k)))) { 554 // getProbes = incProbeCount(getProbes, probes); 555 return entry.value; 556 } else { 557 h += REHASH_HASH; 558 } 559 } 560 } 561 // notFoundProbes = incProbeCount(notFoundProbes, 0); 562 return null; // not found; empty table 563 } 564 565 /** 566 * Same as Get caching the entry. 567 * @param key the key 568 * @return a value, or null 569 */ 570 public V get1(Object key) { 571 final int hash = hash(key); 572 final YNode<K, V>[] tab; 573 int n; 574 if ((tab = table) != null && (n = tab.length) > 0) { 575 int h = hash; 576 int index = (n - 1) & h; 577 YNode<K, V> entry = tab[index]; 578 for (; //int probes = 1 579 entry.isValue(); 580 h += REHASH_HASH, index = (n - 1) & h, entry = tab[index]) { //, probes++ 581 K k; 582 if (entry.hash == hash && 583 ((k = entry.key) == key || (key != null && key.equals(k)))) { 584 // getProbes = incProbeCount(getProbes, probes); 585 return entry.value; 586 } 587 } 588 } 589 // notFoundProbes = incProbeCount(notFoundProbes, 0); 590 return null; // not found; empty table 591 } 592 593 /** 594 * Implements Map.get and related methods. 595 * 596 * @param hash hash for key 597 * @param key the key 598 * @return the index of a matching node or -1 599 */ 600 private final int getNode(final int hash, Object key) { 601 YNode<K, V>[] tab; 602 int n; 603 if ((tab = table) != null && (n = tab.length) > 0) { 604 final YNode<K, V> first; 605 final int i = (n - 1) & hash; 606 K k; 607 if ((first = tab[i]).isValue() && 608 first.hash == hash && 609 ((k = first.key) == key || (key != null && key.equals(k)))) { 610 // getProbes = incProbeCount(getProbes, 1); 611 return i; 612 } 613 // non-empty table and not first entry 614 int h = hash; 615 for (int probes = 1; probes <= tab.length; probes++, h += REHASH_HASH) { 616 final int index = (n - 1) & h; 617 final YNode<K, V> entry = tab[index]; 618 if (!entry.isValue()) { 619 // notFoundProbes = incProbeCount(notFoundProbes, probes); 620 return -1; // search ended without finding the key 621 } else if (entry.hash == hash && 622 ((k = entry.key) == key || (key != null && key.equals(k)))) { 623 // getProbes = incProbeCount(getProbes, probes); 624 return index; 625 } 626 } 627 } 628 // notFoundProbes = incProbeCount(notFoundProbes, 0); 629 return -1; // not found; empty table 630 } 631 632 /** 633 * Returns {@code true} if this map contains a mapping for the 634 * specified key. 635 * 636 * @param key The key whose presence in this map is to be tested 637 * @return {@code true} if this map contains a mapping for the specified 638 * key. 639 */ 640 public boolean containsKey(Object key) { 641 return getNode(hash(key), key) >= 0; 642 } 643 644 /** 645 * Associates the specified value with the specified key in this map. 646 * If the map previously contained a mapping for the key, the old 647 * value is replaced. 648 * 649 * @param key key with which the specified value is to be associated 650 * @param value value to be associated with the specified key 651 * @return the previous value associated with {@code key}, or 652 * {@code null} if there was no mapping for {@code key}. 653 * (A {@code null} return can also indicate that the map 654 * previously associated {@code null} with {@code key}.) 655 */ 656 public V put(K key, V value) { 657 return putVal(hash(key), key, value, false); 658 } 659 660 /** 661 * Implements Map.put and related methods. 662 * 663 * @param hash hash for key 664 * @param key the key 665 * @param value the value to put 666 * @param onlyIfAbsent if true, don't change existing value 667 * @return previous value, or null if none 668 */ 669 private final V putVal(final int hash, final K key, final V value, boolean onlyIfAbsent) { 670 YNode<K, V>[] tab; 671 YNode<K, V> tp; 672 int n, i; 673 if ((tab = table) == null || (n = tab.length) == 0) 674 n = (tab = resize()).length; 675 debug(" putval", -1, new YNode<K,V>(hash, key, value, -1)); 676 677 int h = hash; 678 int insert = -1; // insertion point if not already present 679 int insertProbes = -1; 680 for (int probes = 1; ; probes++, h += REHASH_HASH) { 681 if (probes > tab.length) 682 throw new IllegalStateException("No empty entries in table"); 683 final int index; 684 final YNode<K, V> entry = tab[(index = ((n - 1) & h))]; 685 // debug(" looking at", index, entry); 686 if (entry.isEmpty()) { 687 // Absent; insert in the first place it could be added 688 // TBD: should it check onlyIfAbsent? 689 if (insert < 0) { 690 // no better place to insert than here 691 tab[index] = new YNode<>(hash, key, value, probes); 692 debug(" setting", index, tab[index]); 693 // putProbes = incProbeCount(putProbes, probes); 694 } else { 695 // The new entry is more needy than the current one 696 final YNode<K,V> tmp = tab[insert]; 697 tab[insert] = new YNode<>(hash, key, value, insertProbes); 698 debug(" robin-hood inserted", index, tab[index]); 699 // putProbes = incProbeCount(putProbes, insertProbes); 700 putReinsert(insert, tmp); 701 } 702 break; // break to update modCount and size 703 } 704 705 if (entry.isValue() && entry.hash == hash && 706 (entry.key == key || (key != null && key.equals(entry.key)))) { 707 // TBD: consider if updated entry should be moved closer to the front 708 if (!onlyIfAbsent || entry.value == null) { 709 tab[index] = new YNode<>(hash, key, value, entry.probes); 710 } 711 debug(" oldvalue", index, entry); 712 debug(" updating", index, tab[index]); 713 // putProbes = incProbeCount(putProbes, probes); 714 return entry.value; 715 } 716 717 // Save first possible insert index 718 if (insert < 0 && probes > entry.probes) { 719 insert = index; 720 insertProbes = probes; 721 } 722 } 723 ++modCount; 724 ++size; 725 isTableOk(tab, "table not ok, putval"); 726 if (size >= threshold) 727 resize(); // Ensure there is at least 1 empty available 728 return null; 729 } 730 731 /** 732 * Re-insert the entry in the table starting at the entry beyond the index. 733 * Insert it at an empty slot. 734 * Replace an entry with a lower probe count and repeat to reinsert that entry. 735 * @param oldIndex the index just replaced 736 * @param rEntry the entry to be replaced 737 */ 738 private void putReinsert(final int oldIndex, YNode<K,V> rEntry) { 739 final YNode<K, V>[] tab = table; 740 final int n = tab.length; 741 742 int h = oldIndex + REHASH_HASH; 743 for (int probes = rEntry.probes + 1; probes <= n; probes++, h += REHASH_HASH) { 744 isTableOk(tab, "bubble down loop"); 745 final int index = (n - 1) & h; 746 final YNode<K,V> entry = tab[index]; 747 if (entry.isEmpty()) { 748 // Insert in the empty slot 749 tab[index] = new YNode<>(rEntry.hash, rEntry.key, rEntry.value, probes); 750 debug(" reinserted", index, tab[index]); 751 return; 752 } else if (probes > entry.probes) { 753 // Replace a less deserving entry 754 tab[index] = new YNode<>(rEntry.hash, rEntry.key, rEntry.value, probes); 755 debug(" robin-hood bubble down", index, tab[index]); 756 rEntry = entry; 757 probes = rEntry.probes; 758 debug(" robin-hood moving", index, rEntry); 759 } else { 760 debug(" robin-hood skipping", index, entry); 761 } 762 } 763 throw new RuntimeException("bubble down failed"); 764 } 765 766 private void debug(String msg, int index, YNode<K,V> entry) { 767 if (DEBUG && System.out != null) { 768 System.out.println(System.identityHashCode(this) + ": " + msg + ": index: " + index + ", node: " + Objects.toString(entry)); 769 } 770 } 771 private void debug2(String msg, int index, YNode<K,V> entry) { 772 if (System.out != null) { 773 System.out.println(System.identityHashCode(this) + ": " + msg + ": index: " + index + 774 ", " + "node: " + entry); 775 } 776 } 777 778 /** 779 * Initializes or doubles table size. If null, allocates in 780 * accord with initial capacity target held in field threshold. 781 * Otherwise, because we are using power-of-two expansion, the 782 * elements from each bin must either stay at same index, or move 783 * with a power of two offset in the new table. 784 * 785 * @return the table 786 */ 787 final YNode<K,V>[] resize() { 788 YNode<K,V>[] oldTab = table; 789 int oldCap = (oldTab == null) ? 0 : oldTab.length; 790 int oldThr = threshold; 791 int newCap, newThr = 0; 792 if (oldCap > 0) { 793 if (oldCap >= MAXIMUM_CAPACITY) { 794 threshold = Integer.MAX_VALUE; 795 return oldTab; 796 } 797 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 798 oldCap >= DEFAULT_INITIAL_CAPACITY) 799 newThr = oldThr << 1; // double threshold 800 } 801 else if (oldThr > 0) // initial capacity was placed in threshold 802 newCap = oldThr; 803 else { // zero initial threshold signifies using defaults 804 newCap = DEFAULT_INITIAL_CAPACITY; 805 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 806 } 807 if (newThr == 0) { 808 float ft = (float)newCap * loadFactor; 809 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 810 (int)ft : Integer.MAX_VALUE); 811 } 812 isTableOk(oldTab, "oldTab bad before resize"); 813 if (getProbes != null) 814 Arrays.fill(getProbes, 0); 815 if (putProbes != null) 816 Arrays.fill(putProbes, 0); 817 if (notFoundProbes != null) 818 Arrays.fill(notFoundProbes, 0); 819 820 // There must always be an empty entry, resize when it gets to capacity. 821 threshold = (newThr > newCap) ? newCap : newThr; 822 @SuppressWarnings({"rawtypes","unchecked"}) 823 YNode<K,V>[] newTab = (YNode<K,V>[])new YNode[newCap]; 824 table = newTab; 825 if (oldTab != null) { 826 for (int i = 0; i < oldCap; ++i) { 827 YNode<K,V> e; 828 if ((e = oldTab[i]).isValue()) { 829 final int ii; 830 if (newTab[ii = (newCap - 1) & e.hash].isEmpty()) { 831 newTab[ii] = new YNode<>(e.hash, e.key, e.value, 1); 832 putProbes = incProbeCount(putProbes, 1); 833 } else { 834 int h = e.hash + REHASH_HASH; 835 for (int probes = 2; ; probes++, h += REHASH_HASH) { 836 final int index; 837 if (newTab[(index = ((newCap - 1) & h))].isEmpty()) { 838 newTab[index] = new YNode<>(e.hash, e.key, e.value, probes); 839 putProbes = incProbeCount(putProbes, probes); 840 break; 841 } 842 // TBD: Consider Robin-hood insert 843 if (probes > newTab.length) 844 throw new IllegalStateException("NYI resize: no support for overflow"); 845 } 846 } 847 } 848 } 849 } 850 851 debug("resized", newTab.length, new YNode<K,V>()); 852 isTableOk(newTab, "newTab bad after resize"); 853 return newTab; 854 } 855 856 /** 857 * Dump the hashtable. 858 */ 859 public void dumpTable() { 860 dumpTable(table, "dumpTable"); 861 } 862 863 /** 864 * Dump the hashtable 865 * @param table the table 866 * @param msg a message 867 */ 868 private void dumpTable(YNode<K, V>[] table, String msg) { 869 if (System.out == null || table == null) 870 return; 871 System.out.println(msg + ", size: " + size + ", len: " + table.length); 872 for (int i = 0; i < table.length; ++i) { 873 if (table[i].isValue()) 874 System.out.println(" [" + i + "] " + table[i]); 875 } 876 } 877 878 /** 879 * Copies all of the mappings from the specified map to this map. 880 * These mappings will replace any mappings that this map had for 881 * any of the keys currently in the specified map. 882 * 883 * @param m mappings to be stored in this map 884 * @throws NullPointerException if the specified map is null 885 */ 886 public void putAll(Map<? extends K, ? extends V> m) { 887 putMapEntries(m, true); 888 } 889 890 /** 891 * Removes the mapping for the specified key from this map if present. 892 * 893 * @param key key whose mapping is to be removed from the map 894 * @return the previous value associated with {@code key}, or 895 * {@code null} if there was no mapping for {@code key}. 896 * (A {@code null} return can also indicate that the map 897 * previously associated {@code null} with {@code key}.) 898 */ 899 public V remove(Object key) { 900 YNode<K,V> entry = removeNode(hash(key), key, null, false, true); 901 return entry.isValue() ? entry.value : null; 902 } 903 904 /** 905 * Implements Map.remove and related methods. 906 * 907 * @param hash hash for key 908 * @param key the key 909 * @param value the value to match if matchValue, else ignored 910 * @param matchValue if true only remove if value is equal 911 * @param movable if false do not move other nodes while removing 912 * @return the node, or null if none 913 */ 914 @SuppressWarnings("unchecked") 915 private final YNode<K,V> removeNode(final int hash, final Object key, final Object value, 916 boolean matchValue, boolean movable) { 917 YNode<K, V>[] tab; 918 YNode<K, V> entry; 919 V v = null; 920 int curr; 921 int n; 922 debug(" removeNode", -2, new YNode<K,V>(hash, (K)key, (V)value, -2)); 923 924 if ((tab = table) != null && (n = tab.length) > 0 && 925 (curr = getNode(hash, key)) >= 0 && 926 (entry = tab[curr]).isValue() && 927 ((!matchValue || (v = entry.value) == value || 928 (value != null && value.equals(v))))) { 929 // found entry; free and compress 930 removeNode(curr); 931 return entry; 932 } 933 return new YNode(); 934 } 935 936 @SuppressWarnings("unchecked") 937 private void removeNode(final int curr) { 938 final YNode<K, V>[] tab = table;; 939 final int n = tab.length; 940 941 ++modCount; 942 --size; 943 int free = curr; // The entry to be cleared, if not replaced 944 int h = curr; 945 int probes = 0; 946 do { 947 probes++; 948 h += REHASH_HASH; 949 final int index = (n - 1) & h; 950 final YNode<K, V> entry = tab[index]; 951 if (entry.probes == 0) { 952 // Search ended at empty entry, clear the free entry 953 debug(" clearing", index, entry); 954 tab[free] = new YNode<>(); 955 return; 956 } 957 if (entry.probes > probes) { 958 // move up the entry, skip if it is already in the best spot 959 debug(" replacing", free, entry); 960 tab[free] = new YNode<>(entry.hash, entry.key, entry.value, entry.probes - probes); 961 debug(" with", free, tab[free]); 962 free = index; 963 probes = 0; 964 } 965 } while (((n - 1) & h) != curr); 966 isTableOk(tab, "table not ok, not found"); 967 throw new RuntimeException("removeNode too many probes"); 968 } 969 970 /** 971 * Removes all of the mappings from this map. 972 * The map will be empty after this call returns. 973 */ 974 @SuppressWarnings({"rawtypes","unchecked"}) 975 public void clear() { 976 YNode<K,V>[] tab; 977 modCount++; 978 if ((tab = table) != null && size > 0) { 979 size = 0; 980 for (int i = 0; i < tab.length; i++) 981 tab[i] = new YNode(); 982 } 983 } 984 985 /** 986 * Returns {@code true} if this map maps one or more keys to the 987 * specified value. 988 * 989 * @param value value whose presence in this map is to be tested 990 * @return {@code true} if this map maps one or more keys to the 991 * specified value 992 */ 993 public boolean containsValue(Object value) { 994 YNode<K,V>[] tab; V v; 995 if ((tab = table) != null && size > 0) { 996 for (YNode<K,V> te : tab) { 997 if (te.isValue()) { 998 if ((v = te.value) == value || 999 (value != null && value.equals(v))) 1000 return true; 1001 } 1002 } 1003 } 1004 return false; 1005 } 1006 1007 /** 1008 * Returns a {@link Set} view of the keys contained in this map. 1009 * The set is backed by the map, so changes to the map are 1010 * reflected in the set, and vice-versa. If the map is modified 1011 * while an iteration over the set is in progress (except through 1012 * the iterator's own {@code remove} operation), the results of 1013 * the iteration are undefined. The set supports element removal, 1014 * which removes the corresponding mapping from the map, via the 1015 * {@code Iterator.remove}, {@code Set.remove}, 1016 * {@code removeAll}, {@code retainAll}, and {@code clear} 1017 * operations. It does not support the {@code add} or {@code addAll} 1018 * operations. 1019 * 1020 * @return a set view of the keys contained in this map 1021 */ 1022 public Set<K> keySet() { 1023 Set<K> ks = keySet; 1024 if (ks == null) { 1025 ks = new KeySet(); 1026 keySet = ks; 1027 } 1028 return ks; 1029 } 1030 1031 /** 1032 * Prepares the array for {@link Collection#toArray(Object[])} implementation. 1033 * If supplied array is smaller than this map size, a new array is allocated. 1034 * If supplied array is bigger than this map size, a null is written at size index. 1035 * 1036 * @param a an original array passed to {@code toArray()} method 1037 * @param <T> type of array elements 1038 * @return an array ready to be filled and returned from {@code toArray()} method. 1039 */ 1040 @SuppressWarnings("unchecked") 1041 final <T> T[] prepareArray(T[] a) { 1042 int size = this.size; 1043 if (a.length < size) { 1044 return (T[]) java.lang.reflect.Array 1045 .newInstance(a.getClass().getComponentType(), size); 1046 } 1047 if (a.length > size) { 1048 a[size] = null; 1049 } 1050 return a; 1051 } 1052 1053 /** 1054 * Fills an array with this map keys and returns it. This method assumes 1055 * that input array is big enough to fit all the keys. Use 1056 * {@link #prepareArray(Object[])} to ensure this. 1057 * 1058 * @param a an array to fill 1059 * @param <T> type of array elements 1060 * @return supplied array 1061 */ 1062 <T> T[] keysToArray(T[] a) { 1063 Object[] r = a; 1064 YNode<K,V>[] tab; 1065 int idx = 0; 1066 if (size > 0 && (tab = table) != null) { 1067 for (YNode<K,V> te : tab) { 1068 if (te.isValue()) { 1069 r[idx++] = te.key; 1070 } 1071 } 1072 } 1073 return a; 1074 } 1075 1076 /** 1077 * Fills an array with this map values and returns it. This method assumes 1078 * that input array is big enough to fit all the values. Use 1079 * {@link #prepareArray(Object[])} to ensure this. 1080 * 1081 * @param a an array to fill 1082 * @param <T> type of array elements 1083 * @return supplied array 1084 */ 1085 <T> T[] valuesToArray(T[] a) { 1086 Object[] r = a; 1087 YNode<K,V>[] tab; 1088 int idx = 0; 1089 if (size > 0 && (tab = table) != null) { 1090 for (YNode<K,V> te : tab) { 1091 if (te.isValue()) { 1092 r[idx++] = te.value; 1093 } 1094 } 1095 } 1096 return a; 1097 } 1098 1099 final class KeySet extends AbstractSet<K> { 1100 public final int size() { return size; } 1101 public final void clear() { HashMap.this.clear(); } 1102 public final Iterator<K> iterator() { return new KeyIterator(); } 1103 public final boolean contains(Object o) { return containsKey(o); } 1104 public final boolean remove(Object key) { 1105 return removeNode(hash(key), key, null, false, true).isValue(); 1106 } 1107 1108 public Object[] toArray() { 1109 return keysToArray(new Object[size]); 1110 } 1111 1112 public <T> T[] toArray(T[] a) { 1113 return keysToArray(prepareArray(a)); 1114 } 1115 1116 public final void forEach(Consumer<? super K> action) { 1117 YNode<K,V>[] tab; 1118 if (action == null) 1119 throw new NullPointerException(); 1120 if (size > 0 && (tab = table) != null) { 1121 int mc = modCount; 1122 for (YNode<K,V> te : tab) { 1123 if (te.isValue()) { 1124 action.accept(te.key); 1125 } 1126 } 1127 if (modCount != mc) 1128 throw new ConcurrentModificationException(); 1129 } 1130 } 1131 } 1132 1133 /** 1134 * Returns a {@link Collection} view of the values contained in this map. 1135 * The collection is backed by the map, so changes to the map are 1136 * reflected in the collection, and vice-versa. If the map is 1137 * modified while an iteration over the collection is in progress 1138 * (except through the iterator's own {@code remove} operation), 1139 * the results of the iteration are undefined. The collection 1140 * supports element removal, which removes the corresponding 1141 * mapping from the map, via the {@code Iterator.remove}, 1142 * {@code Collection.remove}, {@code removeAll}, 1143 * {@code retainAll} and {@code clear} operations. It does not 1144 * support the {@code add} or {@code addAll} operations. 1145 * 1146 * @return a view of the values contained in this map 1147 */ 1148 public Collection<V> values() { 1149 Collection<V> vs = values; 1150 if (vs == null) { 1151 vs = new Values(); 1152 values = vs; 1153 } 1154 return vs; 1155 } 1156 1157 final class Values extends AbstractCollection<V> { 1158 public final int size() { return size; } 1159 public final void clear() { HashMap.this.clear(); } 1160 public final Iterator<V> iterator() { return new ValueIterator(); } 1161 public final boolean contains(Object o) { return containsValue(o); } 1162 1163 public Object[] toArray() { 1164 return valuesToArray(new Object[size]); 1165 } 1166 1167 public <T> T[] toArray(T[] a) { 1168 return valuesToArray(prepareArray(a)); 1169 } 1170 1171 public final void forEach(Consumer<? super V> action) { 1172 YNode<K,V>[] tab; 1173 if (action == null) 1174 throw new NullPointerException(); 1175 if (size > 0 && (tab = table) != null) { 1176 int mc = modCount; 1177 for (YNode<K,V> te : tab) { 1178 if (te.isValue()) { 1179 action.accept(te.value); 1180 } 1181 } 1182 if (modCount != mc) 1183 throw new ConcurrentModificationException(); 1184 } 1185 } 1186 } 1187 1188 /** 1189 * Returns a {@link Set} view of the mappings contained in this map. 1190 * The set is backed by the map, so changes to the map are 1191 * reflected in the set, and vice-versa. If the map is modified 1192 * while an iteration over the set is in progress (except through 1193 * the iterator's own {@code remove} operation, or through the 1194 * {@code setValue} operation on a map entry returned by the 1195 * iterator) the results of the iteration are undefined. The set 1196 * supports element removal, which removes the corresponding 1197 * mapping from the map, via the {@code Iterator.remove}, 1198 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and 1199 * {@code clear} operations. It does not support the 1200 * {@code add} or {@code addAll} operations. 1201 * 1202 * @return a set view of the mappings contained in this map 1203 */ 1204 public Set<Map.Entry<K,V>> entrySet() { 1205 Set<Map.Entry<K,V>> es; 1206 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; 1207 } 1208 1209 final class EntrySet extends AbstractSet<Map.Entry<K,V>> { 1210 public final int size() { return size; } 1211 public final void clear() { HashMap.this.clear(); } 1212 public final Iterator<Map.Entry<K,V>> iterator() { 1213 return new EntryIterator(); 1214 } 1215 public final boolean contains(Object o) { 1216 if (!(o instanceof Map.Entry)) 1217 return false; 1218 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 1219 Object key = e.getKey(); 1220 int index = getNode(hash(key), key); 1221 return index >= 0 && table[index].equals(e); 1222 } 1223 public final boolean remove(Object o) { 1224 if (o instanceof Map.Entry) { 1225 Map.Entry<?,?> e = (Map.Entry<?,?>) o; 1226 Object key = e.getKey(); 1227 Object value = e.getValue(); 1228 return removeNode(hash(key), key, value, true, true).isValue(); 1229 } 1230 return false; 1231 } 1232 1233 public final void forEach(Consumer<? super Map.Entry<K,V>> action) { 1234 YNode<K,V>[] tab; 1235 if (action == null) 1236 throw new NullPointerException(); 1237 if (size > 0 && (tab = table) != null) { 1238 int mc = modCount; 1239 for (YNode<K,V> te : tab) { 1240 if (te.isValue()) { 1241 action.accept(new YNodeWrapper(te.hash & (tab.length - 1))); 1242 } 1243 } 1244 if (modCount != mc) 1245 throw new ConcurrentModificationException(); 1246 } 1247 } 1248 } 1249 1250 // Overrides of JDK8 Map extension methods 1251 1252 @Override 1253 public V getOrDefault(Object key, V defaultValue) { 1254 final int index; 1255 return (index = getNode(hash(key), key)) < 0 ? defaultValue : table[index].value; 1256 } 1257 1258 @Override 1259 public V putIfAbsent(K key, V value) { 1260 return putVal(hash(key), key, value, true); 1261 } 1262 1263 @Override 1264 public boolean remove(Object key, Object value) { 1265 return removeNode(hash(key), key, value, true, true).isValue(); 1266 } 1267 1268 @Override 1269 public boolean replace(K key, V oldValue, V newValue) { 1270 int hash, index; 1271 V v; 1272 if ((index = getNode((hash = hash(key)), key)) >= 0 && 1273 ((v = table[index].value) == oldValue || (v != null && v.equals(oldValue)))) { 1274 table[index] = new YNode<>(hash, key, newValue, table[index].probes); 1275 return true; 1276 } 1277 return false; 1278 } 1279 1280 @Override 1281 public V replace(K key, V value) { 1282 int hash, index; 1283 V v; 1284 if ((index = getNode((hash = hash(key)), key)) >= 0) { 1285 V oldValue = table[index].value; 1286 table[index] = new YNode<>(hash, key, value, table[index].probes); 1287 return oldValue; 1288 } 1289 return null; 1290 } 1291 1292 /** 1293 * {@inheritDoc} 1294 * 1295 * <p>This method will, on a best-effort basis, throw a 1296 * {@link ConcurrentModificationException} if it is detected that the 1297 * mapping function modifies this map during computation. 1298 * 1299 * @throws ConcurrentModificationException if it is detected that the 1300 * mapping function modified this map 1301 */ 1302 @Override 1303 public V computeIfAbsent(K key, 1304 Function<? super K, ? extends V> mappingFunction) { 1305 if (mappingFunction == null) 1306 throw new NullPointerException(); 1307 int hash = hash(key); 1308 YNode<K,V>[] tab = table; 1309 YNode<K,V> entry; 1310 int index; 1311 1312 index = getNode(hash, key); 1313 if (index >= 0 && (entry = tab[index]).value != null) { 1314 return entry.value; 1315 } 1316 int mc = modCount; 1317 V v = mappingFunction.apply(key); 1318 if (mc != modCount) { throw new ConcurrentModificationException(); } 1319 if (v == null) { 1320 return null; 1321 } 1322 putVal(hash, key, v, false); 1323 return v; 1324 } 1325 1326 /** 1327 * {@inheritDoc} 1328 * 1329 * <p>This method will, on a best-effort basis, throw a 1330 * {@link ConcurrentModificationException} if it is detected that the 1331 * remapping function modifies this map during computation. 1332 * 1333 * @throws ConcurrentModificationException if it is detected that the 1334 * remapping function modified this map 1335 */ 1336 @Override 1337 public V computeIfPresent(K key, 1338 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1339 if (remappingFunction == null) 1340 throw new NullPointerException(); 1341 YNode<K,V> oldValue; 1342 int hash = hash(key); 1343 int index = getNode(hash, key); 1344 if (index >= 0 && (oldValue = table[index]).value != null) { 1345 int mc = modCount; 1346 V v = remappingFunction.apply(key, oldValue.value); 1347 if (mc != modCount) { throw new ConcurrentModificationException(); } 1348 if (v != null) { 1349 table[index] = new YNode<>(hash, key, v, oldValue.probes); 1350 return v; 1351 } else 1352 removeNode(hash, key, null, false, true); 1353 } 1354 return null; 1355 } 1356 1357 /** 1358 * {@inheritDoc} 1359 * 1360 * <p>This method will, on a best-effort basis, throw a 1361 * {@link ConcurrentModificationException} if it is detected that the 1362 * remapping function modifies this map during computation. 1363 * 1364 * @throws ConcurrentModificationException if it is detected that the 1365 * remapping function modified this map 1366 */ 1367 @Override 1368 @SuppressWarnings("unchecked") 1369 public V compute(K key, 1370 BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 1371 if (remappingFunction == null) 1372 throw new NullPointerException(); 1373 1374 int hash = hash(key); 1375 int index = getNode(hash, key); 1376 YNode<K,V> oldValue = (index >= 0) ? table[index] : new YNode(); 1377 1378 int mc = modCount; 1379 V v = remappingFunction.apply(key, oldValue.value); 1380 if (mc != modCount) { throw new ConcurrentModificationException(); } 1381 if (v != null) { 1382 if (index >= 0) { 1383 table[index] = new YNode<>(hash, key, v, oldValue.probes); 1384 // modCount++; 1385 } else 1386 putVal(hash, key, v, false); 1387 } else 1388 // TBD: 2nd lookup to remove even though we have index 1389 removeNode(hash, key, null, false, true); 1390 return v; 1391 } 1392 1393 /** 1394 * {@inheritDoc} 1395 * 1396 * <p>This method will, on a best-effort basis, throw a 1397 * {@link ConcurrentModificationException} if it is detected that the 1398 * remapping function modifies this map during computation. 1399 * 1400 * @throws ConcurrentModificationException if it is detected that the 1401 * remapping function modified this map 1402 */ 1403 @Override 1404 public V merge(K key, V value, 1405 BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 1406 if (remappingFunction == null) 1407 throw new NullPointerException(); 1408 1409 final int hash = hash(key); 1410 final int index = getNode(hash, key); 1411 if (index >= 0) { 1412 int mc = modCount; 1413 V v = remappingFunction.apply(table[index].value, value); 1414 if (mc != modCount) { throw new ConcurrentModificationException(); } 1415 if (v != null) { 1416 if (index >= 0) { 1417 table[index] = new YNode<>(hash, key, v, table[index].probes); 1418 // modCount++; 1419 } else 1420 putVal(hash, key, v, false); 1421 } else { 1422 // TBD: 2nd lookup to remove even though we have index 1423 removeNode(hash, key, null, false, true); 1424 } 1425 return v; 1426 } else { 1427 // put new key/value (even if null) 1428 putVal(hash, key, value, false); 1429 } 1430 return value; 1431 } 1432 1433 @Override 1434 public void forEach(BiConsumer<? super K, ? super V> action) { 1435 YNode<K,V>[] tab; 1436 if (action == null) 1437 throw new NullPointerException(); 1438 if (size > 0 && (tab = table) != null) { 1439 int mc = modCount; 1440 for (YNode<K,V> te : tab) { 1441 if (te.isValue()) { 1442 action.accept(te.key, te.value); 1443 } 1444 } 1445 if (modCount != mc) 1446 throw new ConcurrentModificationException(); 1447 } 1448 } 1449 1450 @Override 1451 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 1452 super.replaceAll(function); 1453 } 1454 1455 /* ------------------------------------------------------------ */ 1456 // Cloning and serialization 1457 1458 /** 1459 * Returns a shallow copy of this {@code HashMap} instance: the keys and 1460 * values themselves are not cloned. 1461 * 1462 * @return a shallow copy of this map 1463 */ 1464 @SuppressWarnings("unchecked") 1465 @Override 1466 public Object clone() { 1467 HashMap<K,V> result; 1468 try { 1469 result = (HashMap<K,V>)super.clone(); 1470 } catch (CloneNotSupportedException e) { 1471 // this shouldn't happen, since we are Cloneable 1472 throw new InternalError(e); 1473 } 1474 result.reinitialize(); 1475 result.putMapEntries(this, false); 1476 return result; 1477 } 1478 1479 // These methods are also used when serializing HashSets 1480 final float loadFactor() { return loadFactor; } 1481 final int capacity() { 1482 return (table != null) ? table.length : 1483 (threshold > 0) ? threshold : 1484 DEFAULT_INITIAL_CAPACITY; 1485 } 1486 1487 /** 1488 * Saves this map to a stream (that is, serializes it). 1489 * 1490 * @param s the stream 1491 * @throws IOException if an I/O error occurs 1492 * @serialData The <i>capacity</i> of the HashMap (the length of the 1493 * bucket array) is emitted (int), followed by the 1494 * <i>size</i> (an int, the number of key-value 1495 * mappings), followed by the key (Object) and value (Object) 1496 * for each key-value mapping. The key-value mappings are 1497 * emitted in no particular order. 1498 */ 1499 private void writeObject(java.io.ObjectOutputStream s) 1500 throws IOException { 1501 int buckets = capacity(); 1502 // Write out the threshold, loadfactor, and any hidden stuff 1503 s.defaultWriteObject(); 1504 s.writeInt(buckets); 1505 s.writeInt(size); 1506 internalWriteEntries(s); 1507 } 1508 1509 /** 1510 * Reconstitutes this map from a stream (that is, deserializes it). 1511 * @param s the stream 1512 * @throws ClassNotFoundException if the class of a serialized object 1513 * could not be found 1514 * @throws IOException if an I/O error occurs 1515 */ 1516 private void readObject(java.io.ObjectInputStream s) 1517 throws IOException, ClassNotFoundException { 1518 // Read in the threshold (ignored), loadfactor, and any hidden stuff 1519 s.defaultReadObject(); 1520 reinitialize(); 1521 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 1522 throw new InvalidObjectException("Illegal load factor: " + 1523 loadFactor); 1524 s.readInt(); // Read and ignore number of buckets 1525 int mappings = s.readInt(); // Read number of mappings (size) 1526 if (mappings < 0) 1527 throw new InvalidObjectException("Illegal mappings count: " + 1528 mappings); 1529 else if (mappings > 0) { // (if zero, use defaults) 1530 // Size the table using given load factor only if within 1531 // range of 0.25...4.0 1532 float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f); 1533 float fc = (float)mappings / lf + 1.0f; 1534 int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ? 1535 DEFAULT_INITIAL_CAPACITY : 1536 (fc >= MAXIMUM_CAPACITY) ? 1537 MAXIMUM_CAPACITY : 1538 tableSizeFor((int)fc)); 1539 float ft = (float)cap * lf; 1540 threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ? 1541 (int)ft : Integer.MAX_VALUE); 1542 1543 // Check Map.Entry[].class since it's the nearest public type to 1544 // what we're actually creating. 1545 // SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Map.Entry[].class, cap); 1546 @SuppressWarnings({"rawtypes","unchecked"}) 1547 YNode<K,V>[] tab = (YNode<K,V>[])new YNode[cap]; 1548 table = tab; 1549 1550 // Read the keys and values, and put the mappings in the HashMap 1551 for (int i = 0; i < mappings; i++) { 1552 @SuppressWarnings("unchecked") 1553 K key = (K) s.readObject(); 1554 @SuppressWarnings("unchecked") 1555 V value = (V) s.readObject(); 1556 putVal(hash(key), key, value, false); 1557 } 1558 } 1559 } 1560 1561 /* ------------------------------------------------------------ */ 1562 // iterators 1563 1564 abstract class HashIterator { 1565 int next; // next entry to return 1566 int current; // current entry 1567 int expectedModCount; // for fast-fail 1568 int count; 1569 1570 HashIterator() { 1571 expectedModCount = modCount; 1572 current = -1; 1573 next = (size > 0 && table != null) ? findNext(0) : -1; 1574 count = 0; 1575 } 1576 1577 public final boolean hasNext() { 1578 return next >= 0; 1579 } 1580 1581 final Entry<K,V> nextNode() { 1582 if (modCount != expectedModCount) 1583 throw new ConcurrentModificationException("ex: " + expectedModCount + " != " + modCount); 1584 if (!hasNext()) 1585 throw new NoSuchElementException(); 1586 current = next; 1587 assert current >= 0; 1588 1589 next = (current + REHASH_HASH) & (table.length - 1); 1590 next = (next == 0) ? -1 : findNext(next); 1591 return new YNodeWrapper(current); 1592 } 1593 1594 public final void remove() { 1595 if (current < 0 || current > table.length) 1596 throw new IllegalStateException(); 1597 if (modCount != expectedModCount) 1598 throw new ConcurrentModificationException(); 1599 YNode<K, V> p = table[current]; 1600 removeNode(p.hash, p.key, null, false, false); 1601 if (table[current].isValue()) { 1602 // a node was moved into current 1603 next = current; 1604 } 1605 current = -1; 1606 expectedModCount = modCount; 1607 } 1608 1609 /** 1610 * Find the next value entry in the rehash sequence. 1611 */ 1612 private final int findNext(int index) { 1613 final YNode<K,V>[] t = table; 1614 final int lowbitmask = table.length - 1; 1615 index = index & lowbitmask; 1616 int count = 0; 1617 while (!t[index].isValue()) { 1618 count ++; 1619 index = (index + REHASH_HASH) & lowbitmask; 1620 if (index == 0) 1621 return -1; 1622 } 1623 return index; 1624 } 1625 } 1626 1627 final class KeyIterator extends HashIterator 1628 implements Iterator<K> { 1629 public final K next() { return nextNode().getKey(); } 1630 } 1631 1632 final class ValueIterator extends HashIterator 1633 implements Iterator<V> { 1634 public final V next() { return nextNode().getValue(); } 1635 } 1636 1637 final class EntryIterator extends HashIterator 1638 implements Iterator<Map.Entry<K,V>> { 1639 public final Map.Entry<K,V> next() { return nextNode(); } 1640 } 1641 1642 /** 1643 * Reset to initial default state. Called by clone and readObject. 1644 */ 1645 void reinitialize() { 1646 table = null; 1647 entrySet = null; 1648 keySet = null; 1649 values = null; 1650 modCount = 0; 1651 threshold = 0; 1652 size = 0; 1653 } 1654 1655 // Called only from writeObject, to ensure compatible ordering. 1656 void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException { 1657 YNode<K,V>[] tab; 1658 if (size > 0 && (tab = table) != null) { 1659 for (YNode<K,V> te : tab) { 1660 if (te.isValue()) { 1661 s.writeObject(te.key); 1662 s.writeObject(te.value); 1663 } 1664 } 1665 } 1666 } 1667 1668 1669 /** 1670 * Check each entry in the table. 1671 * - FindNode will find it from the key. 1672 * - the probes value is correct. 1673 */ 1674 boolean isTableOk(final YNode<K,V>[] tab, String msg) { 1675 int n; 1676 if (!VERIFYTABLEOK || tab == null || (n = tab.length) == 0) 1677 return true; 1678 boolean ok = true; 1679 int valueEntries = 0; 1680 for (int index = 0; index < tab.length; index++) { 1681 final YNode<K,V> te = tab[index]; 1682 if (te.isValue()) { 1683 valueEntries++; 1684 if (te.key == this || te.value == this) 1685 continue; // skip self referential entries 1686 int hash = hash(te.key); 1687 int th = hash(te.key); 1688 if (th != te.hash) { 1689 ok = false; 1690 debug2("ERROR: computed hash not equal stored hash: th: " + th, index, te); 1691 } 1692 1693 int findex = getNode(hash, te.key); 1694 if (findex < index) { 1695 ok = false; 1696 debug2("ERROR: getNode entry not found/found at wrong index: " + findex, 1697 index , te); 1698 } 1699 if (findex >= 0) { 1700 int h = hash; 1701 for (int probes = 1; probes <= tab.length; probes++, h += REHASH_HASH) { 1702 int i = (n - 1) & h; 1703 if (i == findex) { 1704 if (probes != te.probes) { 1705 ok = false; 1706 debug2("ERROR: computed probes not equal recorded " + 1707 "probes: " + probes, findex, te); 1708 } 1709 break; 1710 } 1711 if (probes == 500) { 1712 debug2("probes > 500: " + probes, findex, te); 1713 } 1714 } 1715 } 1716 // Check for duplicate entry 1717 for (int j = index + 1; j < tab.length; j++) { 1718 if (te.hash == tab[j].hash && 1719 te.key.equals(tab[j].key)) { 1720 debug2("ERROR: YNode at index ", index, te); 1721 debug2("ERROR: duplicate YNode", j, tab[j]); 1722 } 1723 } 1724 } 1725 } 1726 if (valueEntries != size()) { 1727 debug2("ERROR: size wrong: " + valueEntries, size(), new YNode<K,V>()); 1728 ok = false; 1729 } 1730 if (!ok) { 1731 if (System.out != null) { 1732 Thread.dumpStack(); 1733 dumpTable(table, msg); 1734 } 1735 } 1736 return ok; 1737 } 1738 1739 /** 1740 * Print stats of the table to the a stream. 1741 * @param out a stream 1742 */ 1743 public void dumpStats(PrintStream out) { 1744 out.printf("%s instance: size: %d%n", this.getClass().getName(), this.size()); 1745 long size = heapSize(); 1746 long bytesPer = (this.size != 0) ? size / this.size() : 0; 1747 out.printf(" heap size: %d(bytes), avg bytes per entry: %d, table len: %d%n", 1748 size, bytesPer, (table != null) ? table.length : 0); 1749 long[] types = entryTypes(); 1750 out.printf(" values: %d, empty: %d%n", 1751 types[0], types[1]); 1752 printStats(out, "hash collisions", entryRehashes()); 1753 printStats(out, "getProbes ", minCounts(getProbes)); 1754 printStats(out, "putProbes ", minCounts(putProbes)); 1755 printStats(out, "notFoundProbes ", minCounts(notFoundProbes)); 1756 1757 isTableOk(table, "dumpStats"); 1758 } 1759 1760 private void printStats(PrintStream out, String label, int[] hist) { 1761 if (hist.length > 1) { 1762 out.printf(" %s: max: %d, mean: %3.2f, stddev: %3.2f, %s%n", 1763 label, hist.length - 1, 1764 computeMean(hist), computeStdDev(hist), 1765 Arrays.toString(hist)); 1766 } else if (hist.length > 0) { 1767 out.printf(" %s: max: %d, %s%n", 1768 label, hist.length - 1, 1769 Arrays.toString(hist)); 1770 } else { 1771 out.printf(" %s: n/a%n", label); 1772 } 1773 } 1774 1775 private double computeStdDev(int[] hist) { 1776 double mean = computeMean(hist); 1777 double sum = 0.0f; 1778 long count = 0L; 1779 for (int i = 1; i < hist.length; i++) { 1780 count += hist[i]; 1781 sum += (i - mean) * (i - mean) * hist[i]; 1782 } 1783 return Math.sqrt(sum / (count - 1)); 1784 } 1785 1786 private double computeMean(int[] hist) { 1787 long sum = 0L; 1788 long count = 0; 1789 for (int i = 1; i < hist.length; i++) { 1790 count += hist[i]; 1791 sum += i * hist[i]; 1792 } 1793 return (double)sum / (double)count; 1794 } 1795 1796 private long[] entryTypes() { 1797 long[] counts = new long[2]; 1798 if (table == null) 1799 return counts; 1800 for (YNode<K,V> te : table) { 1801 if (te.isEmpty()) 1802 counts[1]++; 1803 else 1804 counts[0]++; 1805 } 1806 return counts; 1807 } 1808 1809 private int[] incProbeCount(int[] counters, int probes) { 1810 if (counters == null) 1811 counters = new int[Math.max(probes + 1, 16)]; 1812 else if (probes >= counters.length) 1813 counters = Arrays.copyOf(counters, Math.max(probes + 1, counters.length * 2)); 1814 counters[probes]++; 1815 return counters; 1816 } 1817 1818 1819 // Returns a histogram array of the number of rehashs needed to find each key. 1820 private int[] entryRehashes() { 1821 if (table == null) 1822 return new int[0]; 1823 int[] counts = new int[table.length + 1]; 1824 YNode<K,V>[] tab = table; 1825 int n = tab.length; 1826 for (YNode<K,V> te : tab) { 1827 1828 if (!te.isValue()) 1829 continue; 1830 int h = te.hash; 1831 int count; 1832 final K key = te.key; 1833 K k; 1834 for (count = 1; count < tab.length; count++, h += REHASH_HASH) { 1835 final YNode<K, V> entry; 1836 if ((entry = tab[(n - 1) & h]).isValue() && 1837 entry.hash == te.hash && 1838 ((k = entry.key) == key || (k != null && k.equals(key)))) { 1839 break; 1840 } 1841 } 1842 1843 counts[count]++; 1844 } 1845 1846 int i; 1847 for (i = counts.length - 1; i >= 0 && counts[i] == 0; i--) { 1848 } 1849 counts = Arrays.copyOf(counts, i + 1); 1850 return counts; 1851 } 1852 1853 private int[] minCounts(int[] counts) { 1854 int i; 1855 for (i = counts.length - 1; i >= 0 && counts[i] == 0; i--) { 1856 } 1857 counts = Arrays.copyOf(counts, i + 1); 1858 return counts; 1859 } 1860 1861 private long heapSize() { 1862 long acc = objectSizeMaybe(this); 1863 return acc + objectSizeMaybe(table); 1864 } 1865 1866 private long objectSizeMaybe(Object o) { 1867 try { 1868 return (mObjectSize != null) 1869 ? (long)mObjectSize.invoke(null, o) 1870 : 0L; 1871 } catch (IllegalAccessException | InvocationTargetException e) { 1872 return 0L; 1873 } 1874 } 1875 1876 private static boolean hasObjectSize = false; 1877 private static Method mObjectSize = getObjectSizeMethod(); 1878 1879 private static Method getObjectSizeMethod() { 1880 try { 1881 Method m = Objects.class.getDeclaredMethod("getObjectSize", Object.class); 1882 hasObjectSize = true; 1883 return m; 1884 } catch (NoSuchMethodException nsme) { 1885 return null; 1886 } 1887 } 1888 1889 }