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 }