1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.io.*;
29 import java.lang.reflect.ParameterizedType;
30 import java.lang.reflect.Type;
31 import java.util.concurrent.ThreadLocalRandom;
32 import java.util.function.BiConsumer;
33 import java.util.function.Consumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Function;
36
37 /**
38 * Hash table based implementation of the <tt>Map</tt> interface. This
39 * implementation provides all of the optional map operations, and permits
40 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
41 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
42 * unsynchronized and permits nulls.) This class makes no guarantees as to
43 * the order of the map; in particular, it does not guarantee that the order
44 * will remain constant over time.
45 *
46 * <p>This implementation provides constant-time performance for the basic
47 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
48 * disperses the elements properly among the buckets. Iteration over
49 * collection views requires time proportional to the "capacity" of the
50 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
51 * of key-value mappings). Thus, it's very important not to set the initial
52 * capacity too high (or the load factor too low) if iteration performance is
53 * important.
54 *
55 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
56 * performance: <i>initial capacity</i> and <i>load factor</i>. The
57 * <i>capacity</i> is the number of buckets in the hash table, and the initial
58 * capacity is simply the capacity at the time the hash table is created. The
59 * <i>load factor</i> is a measure of how full the hash table is allowed to
60 * get before its capacity is automatically increased. When the number of
61 * entries in the hash table exceeds the product of the load factor and the
62 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
63 * structures are rebuilt) so that the hash table has approximately twice the
64 * number of buckets.
65 *
66 * <p>As a general rule, the default load factor (.75) offers a good tradeoff
67 * between time and space costs. Higher values decrease the space overhead
68 * but increase the lookup cost (reflected in most of the operations of the
69 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
70 * expected number of entries in the map and its load factor should be taken
71 * into account when setting its initial capacity, so as to minimize the
72 * number of rehash operations. If the initial capacity is greater
73 * than the maximum number of entries divided by the load factor, no
74 * rehash operations will ever occur.
75 *
76 * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,
77 * creating it with a sufficiently large capacity will allow the mappings to
78 * be stored more efficiently than letting it perform automatic rehashing as
79 * needed to grow the table.
80 *
81 * <p><strong>Note that this implementation is not synchronized.</strong>
82 * If multiple threads access a hash map concurrently, and at least one of
83 * the threads modifies the map structurally, it <i>must</i> be
84 * synchronized externally. (A structural modification is any operation
85 * that adds or deletes one or more mappings; merely changing the value
86 * associated with a key that an instance already contains is not a
87 * structural modification.) This is typically accomplished by
88 * synchronizing on some object that naturally encapsulates the map.
89 *
90 * If no such object exists, the map should be "wrapped" using the
91 * {@link Collections#synchronizedMap Collections.synchronizedMap}
92 * method. This is best done at creation time, to prevent accidental
93 * unsynchronized access to the map:<pre>
94 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
95 *
96 * <p>The iterators returned by all of this class's "collection view methods"
97 * are <i>fail-fast</i>: if the map is structurally modified at any time after
98 * the iterator is created, in any way except through the iterator's own
99 * <tt>remove</tt> method, the iterator will throw a
100 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
101 * modification, the iterator fails quickly and cleanly, rather than risking
102 * arbitrary, non-deterministic behavior at an undetermined time in the
103 * future.
104 *
105 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
106 * as it is, generally speaking, impossible to make any hard guarantees in the
107 * presence of unsynchronized concurrent modification. Fail-fast iterators
108 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
109 * Therefore, it would be wrong to write a program that depended on this
110 * exception for its correctness: <i>the fail-fast behavior of iterators
111 * should be used only to detect bugs.</i>
112 *
113 * <p>This class is a member of the
114 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
115 * Java Collections Framework</a>.
116 *
117 * @param <K> the type of keys maintained by this map
118 * @param <V> the type of mapped values
119 *
120 * @author Doug Lea
121 * @author Josh Bloch
122 * @author Arthur van Hoff
123 * @author Neal Gafter
124 * @see Object#hashCode()
125 * @see Collection
126 * @see Map
127 * @see TreeMap
128 * @see Hashtable
129 * @since 1.2
130 */
131
132 public class HashMap<K,V>
133 extends AbstractMap<K,V>
134 implements Map<K,V>, Cloneable, Serializable
135 {
136
137 /**
138 * The default initial capacity - MUST be a power of two.
139 */
140 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
141
142 /**
143 * The maximum capacity, used if a higher value is implicitly specified
144 * by either of the constructors with arguments.
145 * MUST be a power of two <= 1<<30.
146 */
147 static final int MAXIMUM_CAPACITY = 1 << 30;
148
149 /**
150 * The load factor used when none specified in constructor.
151 */
152 static final float DEFAULT_LOAD_FACTOR = 0.75f;
153
154 /**
155 * An empty table instance to share when the table is not inflated.
156 */
157 static final Object[] EMPTY_TABLE = {};
158
159 /**
160 * The table, resized as necessary. Length MUST Always be a power of two.
161 */
162 transient Object[] table = EMPTY_TABLE;
163
164 /**
165 * The number of key-value mappings contained in this map.
166 */
167 transient int size;
168
169 /**
170 * The next size value at which to resize (capacity * load factor).
171 * @serial
172 */
173 // If table == EMPTY_TABLE then this is the initial capacity at which the
174 // table will be created when inflated.
175 int threshold;
176
177 /**
178 * The load factor for the hash table.
179 *
180 * @serial
181 */
182 final float loadFactor;
183
184 /**
185 * The number of times this HashMap has been structurally modified
186 * Structural modifications are those that change the number of mappings in
187 * the HashMap or otherwise modify its internal structure (e.g.,
188 * rehash). This field is used to make iterators on Collection-views of
189 * the HashMap fail-fast. (See ConcurrentModificationException).
190 */
191 transient int modCount;
192
193 /**
194 * Holds values which can't be initialized until after VM is booted.
195 */
196 private static class Holder {
197 static final sun.misc.Unsafe UNSAFE;
198
199 /**
200 * Offset of "final" hashSeed field we must set in
201 * readObject() method.
202 */
203 static final long HASHSEED_OFFSET;
204
205 static final boolean USE_HASHSEED;
206
207 static {
208 String hashSeedProp = java.security.AccessController.doPrivileged(
209 new sun.security.action.GetPropertyAction(
210 "jdk.map.useRandomSeed"));
211 boolean localBool = (null != hashSeedProp)
212 ? Boolean.parseBoolean(hashSeedProp) : false;
213 USE_HASHSEED = localBool;
214
215 if (USE_HASHSEED) {
216 try {
217 UNSAFE = sun.misc.Unsafe.getUnsafe();
218 HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
219 HashMap.class.getDeclaredField("hashSeed"));
220 } catch (NoSuchFieldException | SecurityException e) {
221 throw new InternalError("Failed to record hashSeed offset", e);
222 }
223 } else {
224 UNSAFE = null;
225 HASHSEED_OFFSET = 0;
226 }
227 }
228 }
229
230 /*
231 * A randomizing value associated with this instance that is applied to
232 * hash code of keys to make hash collisions harder to find.
233 *
234 * Non-final so it can be set lazily, but be sure not to set more than once.
235 */
236 transient final int hashSeed;
237
238 /*
239 * TreeBin/TreeNode code from CHM doesn't handle the null key. Store the
240 * null key entry here.
241 */
242 transient Entry<K,V> nullKeyEntry = null;
243
244 /*
245 * In order to improve performance under high hash-collision conditions,
246 * HashMap will switch to storing a bin's entries in a balanced tree
247 * (TreeBin) instead of a linked-list once the number of entries in the bin
248 * passes a certain threshold (TreeBin.TREE_THRESHOLD), if at least one of
249 * the keys in the bin implements Comparable. This technique is borrowed
250 * from ConcurrentHashMap.
251 */
252
253 /*
254 * Code based on CHMv8
255 *
256 * Node type for TreeBin
257 */
258 final static class TreeNode<K,V> {
259 TreeNode parent; // red-black tree links
260 TreeNode left;
261 TreeNode right;
262 TreeNode prev; // needed to unlink next upon deletion
263 boolean red;
264 final HashMap.Entry<K,V> entry;
265
266 TreeNode(HashMap.Entry<K,V> entry, Object next, TreeNode parent) {
267 this.entry = entry;
268 this.entry.next = next;
269 this.parent = parent;
270 }
271 }
272
273 /**
274 * Returns a Class for the given object of the form "class C
275 * implements Comparable<C>", if one exists, else null. See the TreeBin
276 * docs, below, for explanation.
277 */
278 static Class<?> comparableClassFor(Object x) {
279 Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
280 if ((c = x.getClass()) == String.class) // bypass checks
281 return c;
282 if ((cmpc = Comparable.class).isAssignableFrom(c)) {
283 while (cmpc.isAssignableFrom(s = c.getSuperclass()))
284 c = s; // find topmost comparable class
285 if ((ts = c.getGenericInterfaces()) != null) {
286 for (int i = 0; i < ts.length; ++i) {
287 if (((t = ts[i]) instanceof ParameterizedType) &&
288 ((p = (ParameterizedType)t).getRawType() == cmpc) &&
289 (as = p.getActualTypeArguments()) != null &&
290 as.length == 1 && as[0] == c) // type arg is c
291 return c;
292 }
293 }
294 }
295 return null;
296 }
297
298 /*
299 * Code based on CHMv8
300 *
301 * A specialized form of red-black tree for use in bins
302 * whose size exceeds a threshold.
303 *
304 * TreeBins use a special form of comparison for search and
305 * related operations (which is the main reason we cannot use
306 * existing collections such as TreeMaps). TreeBins contain
307 * Comparable elements, but may contain others, as well as
308 * elements that are Comparable but not necessarily Comparable<T>
309 * for the same T, so we cannot invoke compareTo among them. To
310 * handle this, the tree is ordered primarily by hash value, then
311 * by Comparable.compareTo order if applicable. On lookup at a
312 * node, if elements are not comparable or compare as 0 then both
313 * left and right children may need to be searched in the case of
314 * tied hash values. (This corresponds to the full list search
315 * that would be necessary if all elements were non-Comparable and
316 * had tied hashes.) The red-black balancing code is updated from
317 * pre-jdk-collections
318 * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
319 * based in turn on Cormen, Leiserson, and Rivest "Introduction to
320 * Algorithms" (CLR).
321 */
322 final class TreeBin {
323 /*
324 * The bin count threshold for using a tree rather than list for a bin. The
325 * value reflects the approximate break-even point for using tree-based
326 * operations.
327 */
328 static final int TREE_THRESHOLD = 16;
329
330 TreeNode<K,V> root; // root of tree
331 TreeNode<K,V> first; // head of next-pointer list
332
333 /*
334 * Split a TreeBin into lo and hi parts and install in given table.
335 *
336 * Existing Entrys are re-used, which maintains the before/after links for
337 * LinkedHashMap.Entry.
338 *
339 * No check for Comparable, though this is the same as CHM.
340 */
341 final void splitTreeBin(Object[] newTable, int i, TreeBin loTree, TreeBin hiTree) {
342 TreeBin oldTree = this;
343 int bit = newTable.length >>> 1;
344 int loCount = 0, hiCount = 0;
345 TreeNode<K,V> e = oldTree.first;
346 TreeNode<K,V> next;
347
348 // This method is called when the table has just increased capacity,
349 // so indexFor() is now taking one additional bit of hash into
350 // account ("bit"). Entries in this TreeBin now belong in one of
351 // two bins, "i" or "i+bit", depending on if the new top bit of the
352 // hash is set. The trees for the two bins are loTree and hiTree.
353 // If either tree ends up containing fewer than TREE_THRESHOLD
354 // entries, it is converted back to a linked list.
355 while (e != null) {
356 // Save entry.next - it will get overwritten in putTreeNode()
357 next = (TreeNode<K,V>)e.entry.next;
358
359 int h = e.entry.hash;
360 K k = (K) e.entry.key;
361 V v = e.entry.value;
362 if ((h & bit) == 0) {
363 ++loCount;
364 // Re-using e.entry
365 loTree.putTreeNode(h, k, v, e.entry);
366 } else {
367 ++hiCount;
368 hiTree.putTreeNode(h, k, v, e.entry);
369 }
370 // Iterate using the saved 'next'
371 e = next;
372 }
373 if (loCount < TREE_THRESHOLD) { // too small, convert back to list
374 HashMap.Entry loEntry = null;
375 TreeNode<K,V> p = loTree.first;
376 while (p != null) {
377 @SuppressWarnings("unchecked")
378 TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;
379 p.entry.next = loEntry;
380 loEntry = p.entry;
381 p = savedNext;
382 }
383 // assert newTable[i] == null;
384 newTable[i] = loEntry;
385 } else {
386 // assert newTable[i] == null;
387 newTable[i] = loTree;
388 }
389 if (hiCount < TREE_THRESHOLD) { // too small, convert back to list
390 HashMap.Entry hiEntry = null;
391 TreeNode<K,V> p = hiTree.first;
392 while (p != null) {
393 @SuppressWarnings("unchecked")
394 TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;
395 p.entry.next = hiEntry;
396 hiEntry = p.entry;
397 p = savedNext;
398 }
399 // assert newTable[i + bit] == null;
400 newTable[i + bit] = hiEntry;
401 } else {
402 // assert newTable[i + bit] == null;
403 newTable[i + bit] = hiTree;
404 }
405 }
406
407 /*
408 * Popuplate the TreeBin with entries from the linked list e
409 *
410 * Assumes 'this' is a new/empty TreeBin
411 *
412 * Note: no check for Comparable
413 * Note: I believe this changes iteration order
414 */
415 @SuppressWarnings("unchecked")
416 void populate(HashMap.Entry e) {
417 // assert root == null;
418 // assert first == null;
419 HashMap.Entry next;
420 while (e != null) {
421 // Save entry.next - it will get overwritten in putTreeNode()
422 next = (HashMap.Entry)e.next;
423 // Re-using Entry e will maintain before/after in LinkedHM
424 putTreeNode(e.hash, (K)e.key, (V)e.value, e);
425 // Iterate using the saved 'next'
426 e = next;
427 }
428 }
429
430 /**
431 * Copied from CHMv8
432 * From CLR
433 */
434 private void rotateLeft(TreeNode p) {
435 if (p != null) {
436 TreeNode r = p.right, pp, rl;
437 if ((rl = p.right = r.left) != null) {
438 rl.parent = p;
439 }
440 if ((pp = r.parent = p.parent) == null) {
441 root = r;
442 } else if (pp.left == p) {
443 pp.left = r;
444 } else {
445 pp.right = r;
446 }
447 r.left = p;
448 p.parent = r;
449 }
450 }
451
452 /**
453 * Copied from CHMv8
454 * From CLR
455 */
456 private void rotateRight(TreeNode p) {
457 if (p != null) {
458 TreeNode l = p.left, pp, lr;
459 if ((lr = p.left = l.right) != null) {
460 lr.parent = p;
461 }
462 if ((pp = l.parent = p.parent) == null) {
463 root = l;
464 } else if (pp.right == p) {
465 pp.right = l;
466 } else {
467 pp.left = l;
468 }
469 l.right = p;
470 p.parent = l;
471 }
472 }
473
474 /**
475 * Returns the TreeNode (or null if not found) for the given
476 * key. A front-end for recursive version.
477 */
478 final TreeNode getTreeNode(int h, K k) {
479 return getTreeNode(h, k, root, comparableClassFor(k));
480 }
481
482 /**
483 * Returns the TreeNode (or null if not found) for the given key
484 * starting at given root.
485 */
486 @SuppressWarnings("unchecked")
487 final TreeNode getTreeNode (int h, K k, TreeNode p, Class<?> cc) {
488 // assert k != null;
489 while (p != null) {
490 int dir, ph; Object pk;
491 if ((ph = p.entry.hash) != h)
492 dir = (h < ph) ? -1 : 1;
493 else if ((pk = p.entry.key) == k || k.equals(pk))
494 return p;
495 else if (cc == null || comparableClassFor(pk) != cc ||
496 (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
497 // assert pk != null;
498 TreeNode r, pl, pr; // check both sides
499 if ((pr = p.right) != null &&
500 (r = getTreeNode(h, k, pr, cc)) != null)
501 return r;
502 else if ((pl = p.left) != null)
503 dir = -1;
504 else // nothing there
505 break;
506 }
507 p = (dir > 0) ? p.right : p.left;
508 }
509 return null;
510 }
511
512 /*
513 * Finds or adds a node.
514 *
515 * 'entry' should be used to recycle an existing Entry (e.g. in the case
516 * of converting a linked-list bin to a TreeBin).
517 * If entry is null, a new Entry will be created for the new TreeNode
518 *
519 * @return the TreeNode containing the mapping, or null if a new
520 * TreeNode was added
521 */
522 @SuppressWarnings("unchecked")
523 TreeNode putTreeNode(int h, K k, V v, HashMap.Entry<K,V> entry) {
524 // assert k != null;
525 //if (entry != null) {
526 // assert h == entry.hash;
527 // assert k == entry.key;
528 // assert v == entry.value;
529 // }
530 Class<?> cc = comparableClassFor(k);
531 TreeNode pp = root, p = null;
532 int dir = 0;
533 while (pp != null) { // find existing node or leaf to insert at
534 int ph; Object pk;
535 p = pp;
536 if ((ph = p.entry.hash) != h)
537 dir = (h < ph) ? -1 : 1;
538 else if ((pk = p.entry.key) == k || k.equals(pk))
539 return p;
540 else if (cc == null || comparableClassFor(pk) != cc ||
541 (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
542 TreeNode r, pr;
543 if ((pr = p.right) != null &&
544 (r = getTreeNode(h, k, pr, cc)) != null)
545 return r;
546 else // continue left
547 dir = -1;
548 }
549 pp = (dir > 0) ? p.right : p.left;
550 }
551
552 // Didn't find the mapping in the tree, so add it
553 TreeNode f = first;
554 TreeNode x;
555 if (entry != null) {
556 x = new TreeNode(entry, f, p);
557 } else {
558 x = new TreeNode(newEntry(h, k, v, null), f, p);
559 }
560 first = x;
561
562 if (p == null) {
563 root = x;
564 } else { // attach and rebalance; adapted from CLR
565 TreeNode xp, xpp;
566 if (f != null) {
567 f.prev = x;
568 }
569 if (dir <= 0) {
570 p.left = x;
571 } else {
572 p.right = x;
573 }
574 x.red = true;
575 while (x != null && (xp = x.parent) != null && xp.red
576 && (xpp = xp.parent) != null) {
577 TreeNode xppl = xpp.left;
578 if (xp == xppl) {
579 TreeNode y = xpp.right;
580 if (y != null && y.red) {
581 y.red = false;
582 xp.red = false;
583 xpp.red = true;
584 x = xpp;
585 } else {
586 if (x == xp.right) {
587 rotateLeft(x = xp);
588 xpp = (xp = x.parent) == null ? null : xp.parent;
589 }
590 if (xp != null) {
591 xp.red = false;
592 if (xpp != null) {
593 xpp.red = true;
594 rotateRight(xpp);
595 }
596 }
597 }
598 } else {
599 TreeNode y = xppl;
600 if (y != null && y.red) {
601 y.red = false;
602 xp.red = false;
603 xpp.red = true;
604 x = xpp;
605 } else {
606 if (x == xp.left) {
607 rotateRight(x = xp);
608 xpp = (xp = x.parent) == null ? null : xp.parent;
609 }
610 if (xp != null) {
611 xp.red = false;
612 if (xpp != null) {
613 xpp.red = true;
614 rotateLeft(xpp);
615 }
616 }
617 }
618 }
619 }
620 TreeNode r = root;
621 if (r != null && r.red) {
622 r.red = false;
623 }
624 }
625 return null;
626 }
627
628 /*
629 * From CHMv8
630 *
631 * Removes the given node, that must be present before this
632 * call. This is messier than typical red-black deletion code
633 * because we cannot swap the contents of an interior node
634 * with a leaf successor that is pinned by "next" pointers
635 * that are accessible independently of lock. So instead we
636 * swap the tree linkages.
637 */
638 final void deleteTreeNode(TreeNode p) {
639 TreeNode next = (TreeNode) p.entry.next; // unlink traversal pointers
640 TreeNode pred = p.prev;
641 if (pred == null) {
642 first = next;
643 } else {
644 pred.entry.next = next;
645 }
646 if (next != null) {
647 next.prev = pred;
648 }
649 TreeNode replacement;
650 TreeNode pl = p.left;
651 TreeNode pr = p.right;
652 if (pl != null && pr != null) {
653 TreeNode s = pr, sl;
654 while ((sl = s.left) != null) // find successor
655 {
656 s = sl;
657 }
658 boolean c = s.red;
659 s.red = p.red;
660 p.red = c; // swap colors
661 TreeNode sr = s.right;
662 TreeNode pp = p.parent;
663 if (s == pr) { // p was s's direct parent
664 p.parent = s;
665 s.right = p;
666 } else {
667 TreeNode sp = s.parent;
668 if ((p.parent = sp) != null) {
669 if (s == sp.left) {
670 sp.left = p;
671 } else {
672 sp.right = p;
673 }
674 }
675 if ((s.right = pr) != null) {
676 pr.parent = s;
677 }
678 }
679 p.left = null;
680 if ((p.right = sr) != null) {
681 sr.parent = p;
682 }
683 if ((s.left = pl) != null) {
684 pl.parent = s;
685 }
686 if ((s.parent = pp) == null) {
687 root = s;
688 } else if (p == pp.left) {
689 pp.left = s;
690 } else {
691 pp.right = s;
692 }
693 replacement = sr;
694 } else {
695 replacement = (pl != null) ? pl : pr;
696 }
697 TreeNode pp = p.parent;
698 if (replacement == null) {
699 if (pp == null) {
700 root = null;
701 return;
702 }
703 replacement = p;
704 } else {
705 replacement.parent = pp;
706 if (pp == null) {
707 root = replacement;
708 } else if (p == pp.left) {
709 pp.left = replacement;
710 } else {
711 pp.right = replacement;
712 }
713 p.left = p.right = p.parent = null;
714 }
715 if (!p.red) { // rebalance, from CLR
716 TreeNode x = replacement;
717 while (x != null) {
718 TreeNode xp, xpl;
719 if (x.red || (xp = x.parent) == null) {
720 x.red = false;
721 break;
722 }
723 if (x == (xpl = xp.left)) {
724 TreeNode sib = xp.right;
725 if (sib != null && sib.red) {
726 sib.red = false;
727 xp.red = true;
728 rotateLeft(xp);
729 sib = (xp = x.parent) == null ? null : xp.right;
730 }
731 if (sib == null) {
732 x = xp;
733 } else {
734 TreeNode sl = sib.left, sr = sib.right;
735 if ((sr == null || !sr.red)
736 && (sl == null || !sl.red)) {
737 sib.red = true;
738 x = xp;
739 } else {
740 if (sr == null || !sr.red) {
741 if (sl != null) {
742 sl.red = false;
743 }
744 sib.red = true;
745 rotateRight(sib);
746 sib = (xp = x.parent) == null ?
747 null : xp.right;
748 }
749 if (sib != null) {
750 sib.red = (xp == null) ? false : xp.red;
751 if ((sr = sib.right) != null) {
752 sr.red = false;
753 }
754 }
755 if (xp != null) {
756 xp.red = false;
757 rotateLeft(xp);
758 }
759 x = root;
760 }
761 }
762 } else { // symmetric
763 TreeNode sib = xpl;
764 if (sib != null && sib.red) {
765 sib.red = false;
766 xp.red = true;
767 rotateRight(xp);
768 sib = (xp = x.parent) == null ? null : xp.left;
769 }
770 if (sib == null) {
771 x = xp;
772 } else {
773 TreeNode sl = sib.left, sr = sib.right;
774 if ((sl == null || !sl.red)
775 && (sr == null || !sr.red)) {
776 sib.red = true;
777 x = xp;
778 } else {
779 if (sl == null || !sl.red) {
780 if (sr != null) {
781 sr.red = false;
782 }
783 sib.red = true;
784 rotateLeft(sib);
785 sib = (xp = x.parent) == null ?
786 null : xp.left;
787 }
788 if (sib != null) {
789 sib.red = (xp == null) ? false : xp.red;
790 if ((sl = sib.left) != null) {
791 sl.red = false;
792 }
793 }
794 if (xp != null) {
795 xp.red = false;
796 rotateRight(xp);
797 }
798 x = root;
799 }
800 }
801 }
802 }
803 }
804 if (p == replacement && (pp = p.parent) != null) {
805 if (p == pp.left) // detach pointers
806 {
807 pp.left = null;
808 } else if (p == pp.right) {
809 pp.right = null;
810 }
811 p.parent = null;
812 }
813 }
814 }
815
816 /**
817 * Constructs an empty <tt>HashMap</tt> with the specified initial
818 * capacity and load factor.
819 *
820 * @param initialCapacity the initial capacity
821 * @param loadFactor the load factor
822 * @throws IllegalArgumentException if the initial capacity is negative
823 * or the load factor is nonpositive
824 */
825 public HashMap(int initialCapacity, float loadFactor) {
826 if (initialCapacity < 0)
827 throw new IllegalArgumentException("Illegal initial capacity: " +
828 initialCapacity);
829 if (initialCapacity > MAXIMUM_CAPACITY)
830 initialCapacity = MAXIMUM_CAPACITY;
831 if (loadFactor <= 0 || Float.isNaN(loadFactor))
832 throw new IllegalArgumentException("Illegal load factor: " +
833 loadFactor);
834 this.loadFactor = loadFactor;
835 threshold = initialCapacity;
836 hashSeed = initHashSeed();
837 init();
838 }
839
840 /**
841 * Constructs an empty <tt>HashMap</tt> with the specified initial
842 * capacity and the default load factor (0.75).
843 *
844 * @param initialCapacity the initial capacity.
845 * @throws IllegalArgumentException if the initial capacity is negative.
846 */
847 public HashMap(int initialCapacity) {
848 this(initialCapacity, DEFAULT_LOAD_FACTOR);
849 }
850
851 /**
852 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
853 * (16) and the default load factor (0.75).
854 */
855 public HashMap() {
856 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
857 }
858
859 /**
860 * Constructs a new <tt>HashMap</tt> with the same mappings as the
861 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
862 * default load factor (0.75) and an initial capacity sufficient to
863 * hold the mappings in the specified <tt>Map</tt>.
864 *
865 * @param m the map whose mappings are to be placed in this map
866 * @throws NullPointerException if the specified map is null
867 */
868 public HashMap(Map<? extends K, ? extends V> m) {
869 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
870 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
871 inflateTable(threshold);
872
873 putAllForCreate(m);
874 // assert size == m.size();
875 }
876
877 private static int roundUpToPowerOf2(int number) {
878 // assert number >= 0 : "number must be non-negative";
879 int rounded = number >= MAXIMUM_CAPACITY
880 ? MAXIMUM_CAPACITY
881 : (rounded = Integer.highestOneBit(number)) != 0
882 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
883 : 1;
884
885 return rounded;
886 }
887
888 /**
889 * Inflates the table.
890 */
891 private void inflateTable(int toSize) {
892 // Find a power of 2 >= toSize
893 int capacity = roundUpToPowerOf2(toSize);
894
895 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
896 table = new Object[capacity];
897 }
898
899 // internal utilities
900
901 /**
902 * Initialization hook for subclasses. This method is called
903 * in all constructors and pseudo-constructors (clone, readObject)
904 * after HashMap has been initialized but before any entries have
905 * been inserted. (In the absence of this method, readObject would
906 * require explicit knowledge of subclasses.)
907 */
908 void init() {
909 }
910
911 /**
912 * Return an initial value for the hashSeed, or 0 if the random seed is not
913 * enabled.
914 */
915 final int initHashSeed() {
916 if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) {
917 int seed = ThreadLocalRandom.current().nextInt();
918 return (seed != 0) ? seed : 1;
919 }
920 return 0;
921 }
922
923 /**
924 * Retrieve object hash code and applies a supplemental hash function to the
925 * result hash, which defends against poor quality hash functions. This is
926 * critical because HashMap uses power-of-two length hash tables, that
927 * otherwise encounter collisions for hashCodes that do not differ
928 * in lower bits.
929 */
930 final int hash(Object k) {
931 int h = hashSeed ^ k.hashCode();
932
933 // This function ensures that hashCodes that differ only by
934 // constant multiples at each bit position have a bounded
935 // number of collisions (approximately 8 at default load factor).
936 h ^= (h >>> 20) ^ (h >>> 12);
937 return h ^ (h >>> 7) ^ (h >>> 4);
938 }
939
940 /**
941 * Returns index for hash code h.
942 */
943 static int indexFor(int h, int length) {
944 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
945 return h & (length-1);
946 }
947
948 /**
949 * Returns the number of key-value mappings in this map.
950 *
951 * @return the number of key-value mappings in this map
952 */
953 public int size() {
954 return size;
955 }
956
957 /**
958 * Returns <tt>true</tt> if this map contains no key-value mappings.
959 *
960 * @return <tt>true</tt> if this map contains no key-value mappings
961 */
962 public boolean isEmpty() {
963 return size == 0;
964 }
965
966 /**
967 * Returns the value to which the specified key is mapped,
968 * or {@code null} if this map contains no mapping for the key.
969 *
970 * <p>More formally, if this map contains a mapping from a key
971 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
972 * key.equals(k))}, then this method returns {@code v}; otherwise
973 * it returns {@code null}. (There can be at most one such mapping.)
974 *
975 * <p>A return value of {@code null} does not <i>necessarily</i>
976 * indicate that the map contains no mapping for the key; it's also
977 * possible that the map explicitly maps the key to {@code null}.
978 * The {@link #containsKey containsKey} operation may be used to
979 * distinguish these two cases.
980 *
981 * @see #put(Object, Object)
982 */
983 @SuppressWarnings("unchecked")
984 public V get(Object key) {
985 Entry<K,V> entry = getEntry(key);
986
987 return null == entry ? null : entry.getValue();
988 }
989
990 @Override
991 public V getOrDefault(Object key, V defaultValue) {
992 Entry<K,V> entry = getEntry(key);
993
994 return (entry == null) ? defaultValue : entry.getValue();
995 }
996
997 /**
998 * Returns <tt>true</tt> if this map contains a mapping for the
999 * specified key.
1000 *
1001 * @param key The key whose presence in this map is to be tested
1002 * @return <tt>true</tt> if this map contains a mapping for the specified
1003 * key.
1004 */
1005 public boolean containsKey(Object key) {
1006 return getEntry(key) != null;
1007 }
1008
1009 /**
1010 * Returns the entry associated with the specified key in the
1011 * HashMap. Returns null if the HashMap contains no mapping
1012 * for the key.
1013 */
1014 @SuppressWarnings("unchecked")
1015 final Entry<K,V> getEntry(Object key) {
1016 if (isEmpty()) {
1017 return null;
1018 }
1019 if (key == null) {
1020 return nullKeyEntry;
1021 }
1022 int hash = hash(key);
1023 int bin = indexFor(hash, table.length);
1024
1025 if (table[bin] instanceof Entry) {
1026 Entry<K,V> e = (Entry<K,V>) table[bin];
1027 for (; e != null; e = (Entry<K,V>)e.next) {
1028 Object k;
1029 if (e.hash == hash &&
1030 ((k = e.key) == key || key.equals(k))) {
1031 return e;
1032 }
1033 }
1034 } else if (table[bin] != null) {
1035 TreeBin e = (TreeBin)table[bin];
1036 TreeNode p = e.getTreeNode(hash, (K)key);
1037 if (p != null) {
1038 // assert p.entry.hash == hash && p.entry.key.equals(key);
1039 return (Entry<K,V>)p.entry;
1040 } else {
1041 return null;
1042 }
1043 }
1044 return null;
1045 }
1046
1047
1048 /**
1049 * Associates the specified value with the specified key in this map.
1050 * If the map previously contained a mapping for the key, the old
1051 * value is replaced.
1052 *
1053 * @param key key with which the specified value is to be associated
1054 * @param value value to be associated with the specified key
1055 * @return the previous value associated with <tt>key</tt>, or
1056 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1057 * (A <tt>null</tt> return can also indicate that the map
1058 * previously associated <tt>null</tt> with <tt>key</tt>.)
1059 */
1060 @SuppressWarnings("unchecked")
1061 public V put(K key, V value) {
1062 if (table == EMPTY_TABLE) {
1063 inflateTable(threshold);
1064 }
1065 if (key == null)
1066 return putForNullKey(value);
1067 int hash = hash(key);
1068 int i = indexFor(hash, table.length);
1069 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1070
1071 if (table[i] instanceof Entry) {
1072 // Bin contains ordinary Entries. Search for key in the linked list
1073 // of entries, counting the number of entries. Only check for
1074 // TreeBin conversion if the list size is >= TREE_THRESHOLD.
1075 // (The conversion still may not happen if the table gets resized.)
1076 int listSize = 0;
1077 Entry<K,V> e = (Entry<K,V>) table[i];
1078 for (; e != null; e = (Entry<K,V>)e.next) {
1079 Object k;
1080 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
1081 V oldValue = e.value;
1082 e.value = value;
1083 e.recordAccess(this);
1084 return oldValue;
1085 }
1086 listSize++;
1087 }
1088 // Didn't find, so fall through and call addEntry() to add the
1089 // Entry and check for TreeBin conversion.
1090 checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1091 } else if (table[i] != null) {
1092 TreeBin e = (TreeBin)table[i];
1093 TreeNode p = e.putTreeNode(hash, key, value, null);
1094 if (p == null) { // putTreeNode() added a new node
1095 modCount++;
1096 size++;
1097 if (size >= threshold) {
1098 resize(2 * table.length);
1099 }
1100 return null;
1101 } else { // putTreeNode() found an existing node
1102 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1103 V oldVal = pEntry.value;
1104 pEntry.value = value;
1105 pEntry.recordAccess(this);
1106 return oldVal;
1107 }
1108 }
1109 modCount++;
1110 addEntry(hash, key, value, i, checkIfNeedTree);
1111 return null;
1112 }
1113
1114 /**
1115 * Offloaded version of put for null keys
1116 */
1117 private V putForNullKey(V value) {
1118 if (nullKeyEntry != null) {
1119 V oldValue = nullKeyEntry.value;
1120 nullKeyEntry.value = value;
1121 nullKeyEntry.recordAccess(this);
1122 return oldValue;
1123 }
1124 modCount++;
1125 size++; // newEntry() skips size++
1126 nullKeyEntry = newEntry(0, null, value, null);
1127 return null;
1128 }
1129
1130 private void putForCreateNullKey(V value) {
1131 // Look for preexisting entry for key. This will never happen for
1132 // clone or deserialize. It will only happen for construction if the
1133 // input Map is a sorted map whose ordering is inconsistent w/ equals.
1134 if (nullKeyEntry != null) {
1135 nullKeyEntry.value = value;
1136 } else {
1137 nullKeyEntry = newEntry(0, null, value, null);
1138 size++;
1139 }
1140 }
1141
1142
1143 /**
1144 * This method is used instead of put by constructors and
1145 * pseudoconstructors (clone, readObject). It does not resize the table,
1146 * check for comodification, etc, though it will convert bins to TreeBins
1147 * as needed. It calls createEntry rather than addEntry.
1148 */
1149 @SuppressWarnings("unchecked")
1150 private void putForCreate(K key, V value) {
1151 if (null == key) {
1152 putForCreateNullKey(value);
1153 return;
1154 }
1155 int hash = hash(key);
1156 int i = indexFor(hash, table.length);
1157 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1158
1159 /**
1160 * Look for preexisting entry for key. This will never happen for
1161 * clone or deserialize. It will only happen for construction if the
1162 * input Map is a sorted map whose ordering is inconsistent w/ equals.
1163 */
1164 if (table[i] instanceof Entry) {
1165 int listSize = 0;
1166 Entry<K,V> e = (Entry<K,V>) table[i];
1167 for (; e != null; e = (Entry<K,V>)e.next) {
1168 Object k;
1169 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
1170 e.value = value;
1171 return;
1172 }
1173 listSize++;
1174 }
1175 // Didn't find, fall through to createEntry().
1176 // Check for conversion to TreeBin done via createEntry().
1177 checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1178 } else if (table[i] != null) {
1179 TreeBin e = (TreeBin)table[i];
1180 TreeNode p = e.putTreeNode(hash, key, value, null);
1181 if (p != null) {
1182 p.entry.setValue(value); // Found an existing node, set value
1183 } else {
1184 size++; // Added a new TreeNode, so update size
1185 }
1186 // don't need modCount++/check for resize - just return
1187 return;
1188 }
1189
1190 createEntry(hash, key, value, i, checkIfNeedTree);
1191 }
1192
1193 private void putAllForCreate(Map<? extends K, ? extends V> m) {
1194 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1195 putForCreate(e.getKey(), e.getValue());
1196 }
1197
1198 /**
1199 * Rehashes the contents of this map into a new array with a
1200 * larger capacity. This method is called automatically when the
1201 * number of keys in this map reaches its threshold.
1202 *
1203 * If current capacity is MAXIMUM_CAPACITY, this method does not
1204 * resize the map, but sets threshold to Integer.MAX_VALUE.
1205 * This has the effect of preventing future calls.
1206 *
1207 * @param newCapacity the new capacity, MUST be a power of two;
1208 * must be greater than current capacity unless current
1209 * capacity is MAXIMUM_CAPACITY (in which case value
1210 * is irrelevant).
1211 */
1212 void resize(int newCapacity) {
1213 Object[] oldTable = table;
1214 int oldCapacity = oldTable.length;
1215 if (oldCapacity == MAXIMUM_CAPACITY) {
1216 threshold = Integer.MAX_VALUE;
1217 return;
1218 }
1219
1220 Object[] newTable = new Object[newCapacity];
1221 transfer(newTable);
1222 table = newTable;
1223 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
1224 }
1225
1226 /**
1227 * Transfers all entries from current table to newTable.
1228 *
1229 * Assumes newTable is larger than table
1230 */
1231 @SuppressWarnings("unchecked")
1232 void transfer(Object[] newTable) {
1233 Object[] src = table;
1234 // assert newTable.length > src.length : "newTable.length(" +
1235 // newTable.length + ") expected to be > src.length("+src.length+")";
1236 int newCapacity = newTable.length;
1237 for (int j = 0; j < src.length; j++) {
1238 if (src[j] instanceof Entry) {
1239 // Assume: since wasn't TreeBin before, won't need TreeBin now
1240 Entry<K,V> e = (Entry<K,V>) src[j];
1241 while (null != e) {
1242 Entry<K,V> next = (Entry<K,V>)e.next;
1243 int i = indexFor(e.hash, newCapacity);
1244 e.next = (Entry<K,V>) newTable[i];
1245 newTable[i] = e;
1246 e = next;
1247 }
1248 } else if (src[j] != null) {
1249 TreeBin e = (TreeBin) src[j];
1250 TreeBin loTree = new TreeBin();
1251 TreeBin hiTree = new TreeBin();
1252 e.splitTreeBin(newTable, j, loTree, hiTree);
1253 }
1254 }
1255 Arrays.fill(table, null);
1256 }
1257
1258 /**
1259 * Copies all of the mappings from the specified map to this map.
1260 * These mappings will replace any mappings that this map had for
1261 * any of the keys currently in the specified map.
1262 *
1263 * @param m mappings to be stored in this map
1264 * @throws NullPointerException if the specified map is null
1265 */
1266 public void putAll(Map<? extends K, ? extends V> m) {
1267 int numKeysToBeAdded = m.size();
1268 if (numKeysToBeAdded == 0)
1269 return;
1270
1271 if (table == EMPTY_TABLE) {
1272 inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
1273 }
1274
1275 /*
1276 * Expand the map if the map if the number of mappings to be added
1277 * is greater than or equal to threshold. This is conservative; the
1278 * obvious condition is (m.size() + size) >= threshold, but this
1279 * condition could result in a map with twice the appropriate capacity,
1280 * if the keys to be added overlap with the keys already in this map.
1281 * By using the conservative calculation, we subject ourself
1282 * to at most one extra resize.
1283 */
1284 if (numKeysToBeAdded > threshold && table.length < MAXIMUM_CAPACITY) {
1285 resize(table.length * 2);
1286 }
1287
1288 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
1289 put(e.getKey(), e.getValue());
1290 }
1291
1292 /**
1293 * Removes the mapping for the specified key from this map if present.
1294 *
1295 * @param key key whose mapping is to be removed from the map
1296 * @return the previous value associated with <tt>key</tt>, or
1297 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
1298 * (A <tt>null</tt> return can also indicate that the map
1299 * previously associated <tt>null</tt> with <tt>key</tt>.)
1300 */
1301 public V remove(Object key) {
1302 Entry<K,V> e = removeEntryForKey(key);
1303 return (e == null ? null : e.value);
1304 }
1305 // optimized implementations of default methods in Map
1306
1307 @Override
1308 public void forEach(BiConsumer<? super K, ? super V> action) {
1309 Objects.requireNonNull(action);
1310 final int expectedModCount = modCount;
1311 if (nullKeyEntry != null) {
1312 forEachNullKey(expectedModCount, action);
1313 }
1314 Object[] tab = this.table;
1315 for(int index = 0; index < tab.length; index++) {
1316 Object item = tab[index];
1317 if (item == null) {
1318 continue;
1319 }
1320 if (item instanceof HashMap.TreeBin) {
1321 eachTreeNode(expectedModCount, ((TreeBin)item).first, action);
1322 continue;
1323 }
1324 @SuppressWarnings("unchecked")
1325 Entry<K,V> entry = (Entry<K,V>)item;
1326 while (entry != null) {
1327 action.accept(entry.key, entry.value);
1328 entry = (Entry<K,V>)entry.next;
1329
1330 if (expectedModCount != modCount) {
1331 throw new ConcurrentModificationException();
1332 }
1333 }
1334 }
1335 }
1336
1337 private void eachTreeNode(int expectedModCount, TreeNode<K,V> node, BiConsumer<? super K, ? super V> action) {
1338 while (node != null) {
1339 @SuppressWarnings("unchecked")
1340 Entry<K,V> entry = (Entry<K,V>)node.entry;
1341 action.accept(entry.key, entry.value);
1342 node = (TreeNode<K,V>)entry.next;
1343
1344 if (expectedModCount != modCount) {
1345 throw new ConcurrentModificationException();
1346 }
1347 }
1348 }
1349
1350 private void forEachNullKey(int expectedModCount, BiConsumer<? super K, ? super V> action) {
1351 action.accept(null, nullKeyEntry.value);
1352
1353 if (expectedModCount != modCount) {
1354 throw new ConcurrentModificationException();
1355 }
1356 }
1357
1358 @Override
1359 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1360 Objects.requireNonNull(function);
1361 final int expectedModCount = modCount;
1362 if (nullKeyEntry != null) {
1363 replaceforNullKey(expectedModCount, function);
1364 }
1365 Object[] tab = this.table;
1366 for(int index = 0; index < tab.length; index++) {
1367 Object item = tab[index];
1368 if (item == null) {
1369 continue;
1370 }
1371 if (item instanceof HashMap.TreeBin) {
1372 replaceEachTreeNode(expectedModCount, ((TreeBin)item).first, function);
1373 continue;
1374 }
1375 @SuppressWarnings("unchecked")
1376 Entry<K,V> entry = (Entry<K,V>)item;
1377 while (entry != null) {
1378 function.apply(entry.key, entry.value);
1379 entry = (Entry<K,V>)entry.next;
1380
1381 if (expectedModCount != modCount) {
1382 throw new ConcurrentModificationException();
1383 }
1384 }
1385 }
1386 }
1387
1388 private void replaceEachTreeNode(int expectedModCount, TreeNode<K,V> node, BiFunction<? super K, ? super V, ? extends V> function) {
1389 while (node != null) {
1390 @SuppressWarnings("unchecked")
1391 Entry<K,V> entry = (Entry<K,V>)node.entry;
1392 entry.value = function.apply(entry.key, entry.value);
1393 node = (TreeNode<K,V>)entry.next;
1394
1395 if (expectedModCount != modCount) {
1396 throw new ConcurrentModificationException();
1397 }
1398 }
1399 }
1400
1401 private void replaceforNullKey(int expectedModCount, BiFunction<? super K, ? super V, ? extends V> function) {
1402 nullKeyEntry.value = function.apply(null, nullKeyEntry.value);
1403
1404 if (expectedModCount != modCount) {
1405 throw new ConcurrentModificationException();
1406 }
1407 }
1408
1409 @Override
1410 public V putIfAbsent(K key, V value) {
1411 if (table == EMPTY_TABLE) {
1412 inflateTable(threshold);
1413 }
1414 if (key == null) {
1415 if (nullKeyEntry == null || nullKeyEntry.value == null) {
1416 putForNullKey(value);
1417 return null;
1418 } else {
1419 return nullKeyEntry.value;
1420 }
1421 }
1422 int hash = hash(key);
1423 int i = indexFor(hash, table.length);
1424 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1425
1426 if (table[i] instanceof Entry) {
1427 int listSize = 0;
1428 Entry<K,V> e = (Entry<K,V>) table[i];
1429 for (; e != null; e = (Entry<K,V>)e.next) {
1430 if (e.hash == hash && Objects.equals(e.key, key)) {
1431 if (e.value != null) {
1432 return e.value;
1433 }
1434 e.value = value;
1435 e.recordAccess(this);
1436 return null;
1437 }
1438 listSize++;
1439 }
1440 // Didn't find, so fall through and call addEntry() to add the
1441 // Entry and check for TreeBin conversion.
1442 checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1443 } else if (table[i] != null) {
1444 TreeBin e = (TreeBin)table[i];
1445 TreeNode p = e.putTreeNode(hash, key, value, null);
1446 if (p == null) { // not found, putTreeNode() added a new node
1447 modCount++;
1448 size++;
1449 if (size >= threshold) {
1450 resize(2 * table.length);
1451 }
1452 return null;
1453 } else { // putTreeNode() found an existing node
1454 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1455 V oldVal = pEntry.value;
1456 if (oldVal == null) { // only replace if maps to null
1457 pEntry.value = value;
1458 pEntry.recordAccess(this);
1459 }
1460 return oldVal;
1461 }
1462 }
1463 modCount++;
1464 addEntry(hash, key, value, i, checkIfNeedTree);
1465 return null;
1466 }
1467
1468 @Override
1469 public boolean remove(Object key, Object value) {
1470 if (isEmpty()) {
1471 return false;
1472 }
1473 if (key == null) {
1474 if (nullKeyEntry != null &&
1475 Objects.equals(nullKeyEntry.value, value)) {
1476 removeNullKey();
1477 return true;
1478 }
1479 return false;
1480 }
1481 int hash = hash(key);
1482 int i = indexFor(hash, table.length);
1483
1484 if (table[i] instanceof Entry) {
1485 @SuppressWarnings("unchecked")
1486 Entry<K,V> prev = (Entry<K,V>) table[i];
1487 Entry<K,V> e = prev;
1488 while (e != null) {
1489 @SuppressWarnings("unchecked")
1490 Entry<K,V> next = (Entry<K,V>) e.next;
1491 if (e.hash == hash && Objects.equals(e.key, key)) {
1492 if (!Objects.equals(e.value, value)) {
1493 return false;
1494 }
1495 modCount++;
1496 size--;
1497 if (prev == e)
1498 table[i] = next;
1499 else
1500 prev.next = next;
1501 e.recordRemoval(this);
1502 return true;
1503 }
1504 prev = e;
1505 e = next;
1506 }
1507 } else if (table[i] != null) {
1508 TreeBin tb = ((TreeBin) table[i]);
1509 TreeNode p = tb.getTreeNode(hash, (K)key);
1510 if (p != null) {
1511 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1512 // assert pEntry.key.equals(key);
1513 if (Objects.equals(pEntry.value, value)) {
1514 modCount++;
1515 size--;
1516 tb.deleteTreeNode(p);
1517 pEntry.recordRemoval(this);
1518 if (tb.root == null || tb.first == null) {
1519 // assert tb.root == null && tb.first == null :
1520 // "TreeBin.first and root should both be null";
1521 // TreeBin is now empty, we should blank this bin
1522 table[i] = null;
1523 }
1524 return true;
1525 }
1526 }
1527 }
1528 return false;
1529 }
1530
1531 @Override
1532 public boolean replace(K key, V oldValue, V newValue) {
1533 if (isEmpty()) {
1534 return false;
1535 }
1536 if (key == null) {
1537 if (nullKeyEntry != null &&
1538 Objects.equals(nullKeyEntry.value, oldValue)) {
1539 putForNullKey(newValue);
1540 return true;
1541 }
1542 return false;
1543 }
1544 int hash = hash(key);
1545 int i = indexFor(hash, table.length);
1546
1547 if (table[i] instanceof Entry) {
1548 @SuppressWarnings("unchecked")
1549 Entry<K,V> e = (Entry<K,V>) table[i];
1550 for (; e != null; e = (Entry<K,V>)e.next) {
1551 if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) {
1552 e.value = newValue;
1553 e.recordAccess(this);
1554 return true;
1555 }
1556 }
1557 return false;
1558 } else if (table[i] != null) {
1559 TreeBin tb = ((TreeBin) table[i]);
1560 TreeNode p = tb.getTreeNode(hash, key);
1561 if (p != null) {
1562 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1563 // assert pEntry.key.equals(key);
1564 if (Objects.equals(pEntry.value, oldValue)) {
1565 pEntry.value = newValue;
1566 pEntry.recordAccess(this);
1567 return true;
1568 }
1569 }
1570 }
1571 return false;
1572 }
1573
1574 @Override
1575 public V replace(K key, V value) {
1576 if (isEmpty()) {
1577 return null;
1578 }
1579 if (key == null) {
1580 if (nullKeyEntry != null) {
1581 return putForNullKey(value);
1582 }
1583 return null;
1584 }
1585 int hash = hash(key);
1586 int i = indexFor(hash, table.length);
1587 if (table[i] instanceof Entry) {
1588 @SuppressWarnings("unchecked")
1589 Entry<K,V> e = (Entry<K,V>)table[i];
1590 for (; e != null; e = (Entry<K,V>)e.next) {
1591 if (e.hash == hash && Objects.equals(e.key, key)) {
1592 V oldValue = e.value;
1593 e.value = value;
1594 e.recordAccess(this);
1595 return oldValue;
1596 }
1597 }
1598
1599 return null;
1600 } else if (table[i] != null) {
1601 TreeBin tb = ((TreeBin) table[i]);
1602 TreeNode p = tb.getTreeNode(hash, key);
1603 if (p != null) {
1604 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1605 // assert pEntry.key.equals(key);
1606 V oldValue = pEntry.value;
1607 pEntry.value = value;
1608 pEntry.recordAccess(this);
1609 return oldValue;
1610 }
1611 }
1612 return null;
1613 }
1614
1615 @Override
1616 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
1617 if (table == EMPTY_TABLE) {
1618 inflateTable(threshold);
1619 }
1620 if (key == null) {
1621 if (nullKeyEntry == null || nullKeyEntry.value == null) {
1622 V newValue = mappingFunction.apply(key);
1623 if (newValue != null) {
1624 putForNullKey(newValue);
1625 }
1626 return newValue;
1627 }
1628 return nullKeyEntry.value;
1629 }
1630 int hash = hash(key);
1631 int i = indexFor(hash, table.length);
1632 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1633
1634 if (table[i] instanceof Entry) {
1635 int listSize = 0;
1636 @SuppressWarnings("unchecked")
1637 Entry<K,V> e = (Entry<K,V>)table[i];
1638 for (; e != null; e = (Entry<K,V>)e.next) {
1639 if (e.hash == hash && Objects.equals(e.key, key)) {
1640 V oldValue = e.value;
1641 if (oldValue == null) {
1642 V newValue = mappingFunction.apply(key);
1643 if (newValue != null) {
1644 e.value = newValue;
1645 e.recordAccess(this);
1646 }
1647 return newValue;
1648 }
1649 return oldValue;
1650 }
1651 listSize++;
1652 }
1653 // Didn't find, fall through to call the mapping function
1654 checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1655 } else if (table[i] != null) {
1656 TreeBin e = (TreeBin)table[i];
1657 V value = mappingFunction.apply(key);
1658 if (value == null) { // Return the existing value, if any
1659 TreeNode p = e.getTreeNode(hash, key);
1660 if (p != null) {
1661 return (V) p.entry.value;
1662 }
1663 return null;
1664 } else { // Put the new value into the Tree, if absent
1665 TreeNode p = e.putTreeNode(hash, key, value, null);
1666 if (p == null) { // not found, new node was added
1667 modCount++;
1668 size++;
1669 if (size >= threshold) {
1670 resize(2 * table.length);
1671 }
1672 return value;
1673 } else { // putTreeNode() found an existing node
1674 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1675 V oldVal = pEntry.value;
1676 if (oldVal == null) { // only replace if maps to null
1677 pEntry.value = value;
1678 pEntry.recordAccess(this);
1679 return value;
1680 }
1681 return oldVal;
1682 }
1683 }
1684 }
1685 V newValue = mappingFunction.apply(key);
1686 if (newValue != null) { // add Entry and check for TreeBin conversion
1687 modCount++;
1688 addEntry(hash, key, newValue, i, checkIfNeedTree);
1689 }
1690
1691 return newValue;
1692 }
1693
1694 @Override
1695 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1696 if (isEmpty()) {
1697 return null;
1698 }
1699 if (key == null) {
1700 V oldValue;
1701 if (nullKeyEntry != null && (oldValue = nullKeyEntry.value) != null) {
1702 V newValue = remappingFunction.apply(key, oldValue);
1703 if (newValue != null ) {
1704 putForNullKey(newValue);
1705 return newValue;
1706 } else {
1707 removeNullKey();
1708 }
1709 }
1710 return null;
1711 }
1712 int hash = hash(key);
1713 int i = indexFor(hash, table.length);
1714 if (table[i] instanceof Entry) {
1715 @SuppressWarnings("unchecked")
1716 Entry<K,V> prev = (Entry<K,V>)table[i];
1717 Entry<K,V> e = prev;
1718 while (e != null) {
1719 Entry<K,V> next = (Entry<K,V>)e.next;
1720 if (e.hash == hash && Objects.equals(e.key, key)) {
1721 V oldValue = e.value;
1722 if (oldValue == null)
1723 break;
1724 V newValue = remappingFunction.apply(key, oldValue);
1725 if (newValue == null) {
1726 modCount++;
1727 size--;
1728 if (prev == e)
1729 table[i] = next;
1730 else
1731 prev.next = next;
1732 e.recordRemoval(this);
1733 } else {
1734 e.value = newValue;
1735 e.recordAccess(this);
1736 }
1737 return newValue;
1738 }
1739 prev = e;
1740 e = next;
1741 }
1742 } else if (table[i] != null) {
1743 TreeBin tb = (TreeBin)table[i];
1744 TreeNode p = tb.getTreeNode(hash, key);
1745 if (p != null) {
1746 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1747 // assert pEntry.key.equals(key);
1748 V oldValue = pEntry.value;
1749 if (oldValue != null) {
1750 V newValue = remappingFunction.apply(key, oldValue);
1751 if (newValue == null) { // remove mapping
1752 modCount++;
1753 size--;
1754 tb.deleteTreeNode(p);
1755 pEntry.recordRemoval(this);
1756 if (tb.root == null || tb.first == null) {
1757 // assert tb.root == null && tb.first == null :
1758 // "TreeBin.first and root should both be null";
1759 // TreeBin is now empty, we should blank this bin
1760 table[i] = null;
1761 }
1762 } else {
1763 pEntry.value = newValue;
1764 pEntry.recordAccess(this);
1765 }
1766 return newValue;
1767 }
1768 }
1769 }
1770 return null;
1771 }
1772
1773 @Override
1774 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1775 if (table == EMPTY_TABLE) {
1776 inflateTable(threshold);
1777 }
1778 if (key == null) {
1779 V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
1780 V newValue = remappingFunction.apply(key, oldValue);
1781 if (newValue != oldValue) {
1782 if (newValue == null) {
1783 removeNullKey();
1784 } else {
1785 putForNullKey(newValue);
1786 }
1787 }
1788 return newValue;
1789 }
1790 int hash = hash(key);
1791 int i = indexFor(hash, table.length);
1792 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1793
1794 if (table[i] instanceof Entry) {
1795 int listSize = 0;
1796 @SuppressWarnings("unchecked")
1797 Entry<K,V> prev = (Entry<K,V>)table[i];
1798 Entry<K,V> e = prev;
1799
1800 while (e != null) {
1801 Entry<K,V> next = (Entry<K,V>)e.next;
1802 if (e.hash == hash && Objects.equals(e.key, key)) {
1803 V oldValue = e.value;
1804 V newValue = remappingFunction.apply(key, oldValue);
1805 if (newValue != oldValue) {
1806 if (newValue == null) {
1807 modCount++;
1808 size--;
1809 if (prev == e)
1810 table[i] = next;
1811 else
1812 prev.next = next;
1813 e.recordRemoval(this);
1814 } else {
1815 e.value = newValue;
1816 e.recordAccess(this);
1817 }
1818 }
1819 return newValue;
1820 }
1821 prev = e;
1822 e = next;
1823 listSize++;
1824 }
1825 checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1826 } else if (table[i] != null) {
1827 TreeBin tb = (TreeBin)table[i];
1828 TreeNode p = tb.getTreeNode(hash, key);
1829 V oldValue = p == null ? null : (V)p.entry.value;
1830 V newValue = remappingFunction.apply(key, oldValue);
1831 if (newValue != oldValue) {
1832 if (newValue == null) {
1833 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1834 modCount++;
1835 size--;
1836 tb.deleteTreeNode(p);
1837 pEntry.recordRemoval(this);
1838 if (tb.root == null || tb.first == null) {
1839 // assert tb.root == null && tb.first == null :
1840 // "TreeBin.first and root should both be null";
1841 // TreeBin is now empty, we should blank this bin
1842 table[i] = null;
1843 }
1844 } else {
1845 if (p != null) { // just update the value
1846 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1847 pEntry.value = newValue;
1848 pEntry.recordAccess(this);
1849 } else { // need to put new node
1850 p = tb.putTreeNode(hash, key, newValue, null);
1851 // assert p == null; // should have added a new node
1852 modCount++;
1853 size++;
1854 if (size >= threshold) {
1855 resize(2 * table.length);
1856 }
1857 }
1858 }
1859 }
1860 return newValue;
1861 }
1862
1863 V newValue = remappingFunction.apply(key, null);
1864 if (newValue != null) {
1865 modCount++;
1866 addEntry(hash, key, newValue, i, checkIfNeedTree);
1867 }
1868
1869 return newValue;
1870 }
1871
1872 @Override
1873 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1874 if (table == EMPTY_TABLE) {
1875 inflateTable(threshold);
1876 }
1877 if (key == null) {
1878 V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
1879 V newValue = oldValue == null ? value : remappingFunction.apply(oldValue, value);
1880 if (newValue != null) {
1881 putForNullKey(newValue);
1882 } else if (nullKeyEntry != null) {
1883 removeNullKey();
1884 }
1885 return newValue;
1886 }
1887 int hash = hash(key);
1888 int i = indexFor(hash, table.length);
1889 boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
1890
1891 if (table[i] instanceof Entry) {
1892 int listSize = 0;
1893 @SuppressWarnings("unchecked")
1894 Entry<K,V> prev = (Entry<K,V>)table[i];
1895 Entry<K,V> e = prev;
1896
1897 while (e != null) {
1898 Entry<K,V> next = (Entry<K,V>)e.next;
1899 if (e.hash == hash && Objects.equals(e.key, key)) {
1900 V oldValue = e.value;
1901 V newValue = (oldValue == null) ? value :
1902 remappingFunction.apply(oldValue, value);
1903 if (newValue == null) {
1904 modCount++;
1905 size--;
1906 if (prev == e)
1907 table[i] = next;
1908 else
1909 prev.next = next;
1910 e.recordRemoval(this);
1911 } else {
1912 e.value = newValue;
1913 e.recordAccess(this);
1914 }
1915 return newValue;
1916 }
1917 prev = e;
1918 e = next;
1919 listSize++;
1920 }
1921 // Didn't find, so fall through and (maybe) call addEntry() to add
1922 // the Entry and check for TreeBin conversion.
1923 checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
1924 } else if (table[i] != null) {
1925 TreeBin tb = (TreeBin)table[i];
1926 TreeNode p = tb.getTreeNode(hash, key);
1927 V oldValue = p == null ? null : (V)p.entry.value;
1928 V newValue = (oldValue == null) ? value :
1929 remappingFunction.apply(oldValue, value);
1930 if (newValue == null) {
1931 if (p != null) {
1932 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1933 modCount++;
1934 size--;
1935 tb.deleteTreeNode(p);
1936 pEntry.recordRemoval(this);
1937
1938 if (tb.root == null || tb.first == null) {
1939 // assert tb.root == null && tb.first == null :
1940 // "TreeBin.first and root should both be null";
1941 // TreeBin is now empty, we should blank this bin
1942 table[i] = null;
1943 }
1944 }
1945 return null;
1946 } else if (newValue != oldValue) {
1947 if (p != null) { // just update the value
1948 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
1949 pEntry.value = newValue;
1950 pEntry.recordAccess(this);
1951 } else { // need to put new node
1952 p = tb.putTreeNode(hash, key, newValue, null);
1953 // assert p == null; // should have added a new node
1954 modCount++;
1955 size++;
1956 if (size >= threshold) {
1957 resize(2 * table.length);
1958 }
1959 }
1960 }
1961 return newValue;
1962 }
1963 if (value != null) {
1964 modCount++;
1965 addEntry(hash, key, value, i, checkIfNeedTree);
1966 }
1967 return value;
1968 }
1969
1970 // end of optimized implementations of default methods in Map
1971
1972 /**
1973 * Removes and returns the entry associated with the specified key
1974 * in the HashMap. Returns null if the HashMap contains no mapping
1975 * for this key.
1976 *
1977 * We don't bother converting TreeBins back to Entry lists if the bin falls
1978 * back below TREE_THRESHOLD, but we do clear bins when removing the last
1979 * TreeNode in a TreeBin.
1980 */
1981 final Entry<K,V> removeEntryForKey(Object key) {
1982 if (isEmpty()) {
1983 return null;
1984 }
1985 if (key == null) {
1986 if (nullKeyEntry != null) {
1987 return removeNullKey();
1988 }
1989 return null;
1990 }
1991 int hash = hash(key);
1992 int i = indexFor(hash, table.length);
1993
1994 if (table[i] instanceof Entry) {
1995 @SuppressWarnings("unchecked")
1996 Entry<K,V> prev = (Entry<K,V>)table[i];
1997 Entry<K,V> e = prev;
1998
1999 while (e != null) {
2000 @SuppressWarnings("unchecked")
2001 Entry<K,V> next = (Entry<K,V>) e.next;
2002 if (e.hash == hash && Objects.equals(e.key, key)) {
2003 modCount++;
2004 size--;
2005 if (prev == e)
2006 table[i] = next;
2007 else
2008 prev.next = next;
2009 e.recordRemoval(this);
2010 return e;
2011 }
2012 prev = e;
2013 e = next;
2014 }
2015 } else if (table[i] != null) {
2016 TreeBin tb = ((TreeBin) table[i]);
2017 TreeNode p = tb.getTreeNode(hash, (K)key);
2018 if (p != null) {
2019 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
2020 // assert pEntry.key.equals(key);
2021 modCount++;
2022 size--;
2023 tb.deleteTreeNode(p);
2024 pEntry.recordRemoval(this);
2025 if (tb.root == null || tb.first == null) {
2026 // assert tb.root == null && tb.first == null :
2027 // "TreeBin.first and root should both be null";
2028 // TreeBin is now empty, we should blank this bin
2029 table[i] = null;
2030 }
2031 return pEntry;
2032 }
2033 }
2034 return null;
2035 }
2036
2037 /**
2038 * Special version of remove for EntrySet using {@code Map.Entry.equals()}
2039 * for matching.
2040 */
2041 final Entry<K,V> removeMapping(Object o) {
2042 if (isEmpty() || !(o instanceof Map.Entry))
2043 return null;
2044
2045 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
2046 Object key = entry.getKey();
2047
2048 if (key == null) {
2049 if (entry.equals(nullKeyEntry)) {
2050 return removeNullKey();
2051 }
2052 return null;
2053 }
2054
2055 int hash = hash(key);
2056 int i = indexFor(hash, table.length);
2057
2058 if (table[i] instanceof Entry) {
2059 @SuppressWarnings("unchecked")
2060 Entry<K,V> prev = (Entry<K,V>)table[i];
2061 Entry<K,V> e = prev;
2062
2063 while (e != null) {
2064 @SuppressWarnings("unchecked")
2065 Entry<K,V> next = (Entry<K,V>)e.next;
2066 if (e.hash == hash && e.equals(entry)) {
2067 modCount++;
2068 size--;
2069 if (prev == e)
2070 table[i] = next;
2071 else
2072 prev.next = next;
2073 e.recordRemoval(this);
2074 return e;
2075 }
2076 prev = e;
2077 e = next;
2078 }
2079 } else if (table[i] != null) {
2080 TreeBin tb = ((TreeBin) table[i]);
2081 TreeNode p = tb.getTreeNode(hash, (K)key);
2082 if (p != null && p.entry.equals(entry)) {
2083 @SuppressWarnings("unchecked")
2084 Entry<K,V> pEntry = (Entry<K,V>)p.entry;
2085 // assert pEntry.key.equals(key);
2086 modCount++;
2087 size--;
2088 tb.deleteTreeNode(p);
2089 pEntry.recordRemoval(this);
2090 if (tb.root == null || tb.first == null) {
2091 // assert tb.root == null && tb.first == null :
2092 // "TreeBin.first and root should both be null";
2093 // TreeBin is now empty, we should blank this bin
2094 table[i] = null;
2095 }
2096 return pEntry;
2097 }
2098 }
2099 return null;
2100 }
2101
2102 /*
2103 * Remove the mapping for the null key, and update internal accounting
2104 * (size, modcount, recordRemoval, etc).
2105 *
2106 * Assumes nullKeyEntry is non-null.
2107 */
2108 private Entry<K,V> removeNullKey() {
2109 // assert nullKeyEntry != null;
2110 Entry<K,V> retVal = nullKeyEntry;
2111 modCount++;
2112 size--;
2113 retVal.recordRemoval(this);
2114 nullKeyEntry = null;
2115 return retVal;
2116 }
2117
2118 /**
2119 * Removes all of the mappings from this map.
2120 * The map will be empty after this call returns.
2121 */
2122 public void clear() {
2123 modCount++;
2124 if (nullKeyEntry != null) {
2125 nullKeyEntry = null;
2126 }
2127 Arrays.fill(table, null);
2128 size = 0;
2129 }
2130
2131 /**
2132 * Returns <tt>true</tt> if this map maps one or more keys to the
2133 * specified value.
2134 *
2135 * @param value value whose presence in this map is to be tested
2136 * @return <tt>true</tt> if this map maps one or more keys to the
2137 * specified value
2138 */
2139 public boolean containsValue(Object value) {
2140 if (value == null) {
2141 return containsNullValue();
2142 }
2143 Object[] tab = table;
2144 for (int i = 0; i < tab.length; i++) {
2145 if (tab[i] instanceof Entry) {
2146 Entry<?,?> e = (Entry<?,?>)tab[i];
2147 for (; e != null; e = (Entry<?,?>)e.next) {
2148 if (value.equals(e.value)) {
2149 return true;
2150 }
2151 }
2152 } else if (tab[i] != null) {
2153 TreeBin e = (TreeBin)tab[i];
2154 TreeNode p = e.first;
2155 for (; p != null; p = (TreeNode) p.entry.next) {
2156 if (value == p.entry.value || value.equals(p.entry.value)) {
2157 return true;
2158 }
2159 }
2160 }
2161 }
2162 // Didn't find value in table - could be in nullKeyEntry
2163 return (nullKeyEntry != null && (value == nullKeyEntry.value ||
2164 value.equals(nullKeyEntry.value)));
2165 }
2166
2167 /**
2168 * Special-case code for containsValue with null argument
2169 */
2170 private boolean containsNullValue() {
2171 Object[] tab = table;
2172 for (int i = 0; i < tab.length; i++) {
2173 if (tab[i] instanceof Entry) {
2174 Entry<K,V> e = (Entry<K,V>)tab[i];
2175 for (; e != null; e = (Entry<K,V>)e.next) {
2176 if (e.value == null) {
2177 return true;
2178 }
2179 }
2180 } else if (tab[i] != null) {
2181 TreeBin e = (TreeBin)tab[i];
2182 TreeNode p = e.first;
2183 for (; p != null; p = (TreeNode) p.entry.next) {
2184 if (p.entry.value == null) {
2185 return true;
2186 }
2187 }
2188 }
2189 }
2190 // Didn't find value in table - could be in nullKeyEntry
2191 return (nullKeyEntry != null && nullKeyEntry.value == null);
2192 }
2193
2194 /**
2195 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
2196 * values themselves are not cloned.
2197 *
2198 * @return a shallow copy of this map
2199 */
2200 @SuppressWarnings("unchecked")
2201 public Object clone() {
2202 HashMap<K,V> result = null;
2203 try {
2204 result = (HashMap<K,V>)super.clone();
2205 } catch (CloneNotSupportedException e) {
2206 // assert false;
2207 }
2208 if (result.table != EMPTY_TABLE) {
2209 result.inflateTable(Math.min(
2210 (int) Math.min(
2211 size * Math.min(1 / loadFactor, 4.0f),
2212 // we have limits...
2213 HashMap.MAXIMUM_CAPACITY),
2214 table.length));
2215 }
2216 result.entrySet = null;
2217 result.modCount = 0;
2218 result.size = 0;
2219 result.nullKeyEntry = null;
2220 result.init();
2221 result.putAllForCreate(this);
2222
2223 return result;
2224 }
2225
2226 static class Entry<K,V> implements Map.Entry<K,V> {
2227 final K key;
2228 V value;
2229 Object next; // an Entry, or a TreeNode
2230 final int hash;
2231
2232 /**
2233 * Creates new entry.
2234 */
2235 Entry(int h, K k, V v, Object n) {
2236 value = v;
2237 next = n;
2238 key = k;
2239 hash = h;
2240 }
2241
2242 public final K getKey() {
2243 return key;
2244 }
2245
2246 public final V getValue() {
2247 return value;
2248 }
2249
2250 public final V setValue(V newValue) {
2251 V oldValue = value;
2252 value = newValue;
2253 return oldValue;
2254 }
2255
2256 public final boolean equals(Object o) {
2257 if (!(o instanceof Map.Entry))
2258 return false;
2259 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2260 Object k1 = getKey();
2261 Object k2 = e.getKey();
2262 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
2263 Object v1 = getValue();
2264 Object v2 = e.getValue();
2265 if (v1 == v2 || (v1 != null && v1.equals(v2)))
2266 return true;
2267 }
2268 return false;
2269 }
2270
2271 public final int hashCode() {
2272 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
2273 }
2274
2275 public final String toString() {
2276 return getKey() + "=" + getValue();
2277 }
2278
2279 /**
2280 * This method is invoked whenever the value in an entry is
2281 * overwritten for a key that's already in the HashMap.
2282 */
2283 void recordAccess(HashMap<K,V> m) {
2284 }
2285
2286 /**
2287 * This method is invoked whenever the entry is
2288 * removed from the table.
2289 */
2290 void recordRemoval(HashMap<K,V> m) {
2291 }
2292 }
2293
2294 void addEntry(int hash, K key, V value, int bucketIndex) {
2295 addEntry(hash, key, value, bucketIndex, true);
2296 }
2297
2298 /**
2299 * Adds a new entry with the specified key, value and hash code to
2300 * the specified bucket. It is the responsibility of this
2301 * method to resize the table if appropriate. The new entry is then
2302 * created by calling createEntry().
2303 *
2304 * Subclass overrides this to alter the behavior of put method.
2305 *
2306 * If checkIfNeedTree is false, it is known that this bucket will not need
2307 * to be converted to a TreeBin, so don't bothering checking.
2308 *
2309 * Assumes key is not null.
2310 */
2311 void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
2312 // assert key != null;
2313 if ((size >= threshold) && (null != table[bucketIndex])) {
2314 resize(2 * table.length);
2315 hash = hash(key);
2316 bucketIndex = indexFor(hash, table.length);
2317 }
2318 createEntry(hash, key, value, bucketIndex, checkIfNeedTree);
2319 }
2320
2321 /**
2322 * Called by addEntry(), and also used when creating entries
2323 * as part of Map construction or "pseudo-construction" (cloning,
2324 * deserialization). This version does not check for resizing of the table.
2325 *
2326 * This method is responsible for converting a bucket to a TreeBin once
2327 * TREE_THRESHOLD is reached. However if checkIfNeedTree is false, it is known
2328 * that this bucket will not need to be converted to a TreeBin, so don't
2329 * bother checking. The new entry is constructed by calling newEntry().
2330 *
2331 * Assumes key is not null.
2332 *
2333 * Note: buckets already converted to a TreeBin don't call this method, but
2334 * instead call TreeBin.putTreeNode() to create new entries.
2335 */
2336 void createEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
2337 // assert key != null;
2338 @SuppressWarnings("unchecked")
2339 Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
2340 table[bucketIndex] = newEntry(hash, key, value, e);
2341 size++;
2342
2343 if (checkIfNeedTree) {
2344 int listSize = 0;
2345 for (e = (Entry<K,V>) table[bucketIndex]; e != null; e = (Entry<K,V>)e.next) {
2346 listSize++;
2347 if (listSize >= TreeBin.TREE_THRESHOLD) { // Convert to TreeBin
2348 if (comparableClassFor(key) != null) {
2349 TreeBin t = new TreeBin();
2350 t.populate((Entry)table[bucketIndex]);
2351 table[bucketIndex] = t;
2352 }
2353 break;
2354 }
2355 }
2356 }
2357 }
2358
2359 /*
2360 * Factory method to create a new Entry object.
2361 */
2362 Entry<K,V> newEntry(int hash, K key, V value, Object next) {
2363 return new HashMap.Entry<>(hash, key, value, next);
2364 }
2365
2366
2367 private abstract class HashIterator<E> implements Iterator<E> {
2368 Object next; // next entry to return, an Entry or a TreeNode
2369 int expectedModCount; // For fast-fail
2370 int index; // current slot
2371 Object current; // current entry, an Entry or a TreeNode
2372
2373 HashIterator() {
2374 expectedModCount = modCount;
2375 if (size > 0) { // advance to first entry
2376 if (nullKeyEntry != null) {
2377 // assert nullKeyEntry.next == null;
2378 // This works with nextEntry(): nullKeyEntry isa Entry, and
2379 // e.next will be null, so we'll hit the findNextBin() call.
2380 next = nullKeyEntry;
2381 } else {
2382 findNextBin();
2383 }
2384 }
2385 }
2386
2387 public final boolean hasNext() {
2388 return next != null;
2389 }
2390
2391 @SuppressWarnings("unchecked")
2392 final Entry<K,V> nextEntry() {
2393 if (modCount != expectedModCount) {
2394 throw new ConcurrentModificationException();
2395 }
2396 Object e = next;
2397 Entry<K,V> retVal;
2398
2399 if (e == null)
2400 throw new NoSuchElementException();
2401
2402 if (e instanceof TreeNode) { // TreeBin
2403 retVal = (Entry<K,V>)((TreeNode)e).entry;
2404 next = retVal.next;
2405 } else {
2406 retVal = (Entry<K,V>)e;
2407 next = ((Entry<K,V>)e).next;
2408 }
2409
2410 if (next == null) { // Move to next bin
2411 findNextBin();
2412 }
2413 current = e;
2414 return retVal;
2415 }
2416
2417 public void remove() {
2418 if (current == null)
2419 throw new IllegalStateException();
2420 if (modCount != expectedModCount)
2421 throw new ConcurrentModificationException();
2422 K k;
2423
2424 if (current instanceof Entry) {
2425 k = ((Entry<K,V>)current).key;
2426 } else {
2427 k = ((Entry<K,V>)((TreeNode)current).entry).key;
2428
2429 }
2430 current = null;
2431 HashMap.this.removeEntryForKey(k);
2432 expectedModCount = modCount;
2433 }
2434
2435 /*
2436 * Set 'next' to the first entry of the next non-empty bin in the table
2437 */
2438 private void findNextBin() {
2439 // assert next == null;
2440 Object[] t = table;
2441
2442 while (index < t.length && (next = t[index++]) == null)
2443 ;
2444 if (next instanceof HashMap.TreeBin) { // Point to the first TreeNode
2445 next = ((TreeBin) next).first;
2446 // assert next != null; // There should be no empty TreeBins
2447 }
2448 }
2449 }
2450
2451 private final class ValueIterator extends HashIterator<V> {
2452 public V next() {
2453 return nextEntry().value;
2454 }
2455 }
2456
2457 private final class KeyIterator extends HashIterator<K> {
2458 public K next() {
2459 return nextEntry().getKey();
2460 }
2461 }
2462
2463 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
2464 public Map.Entry<K,V> next() {
2465 return nextEntry();
2466 }
2467 }
2468
2469 // Subclass overrides these to alter behavior of views' iterator() method
2470 Iterator<K> newKeyIterator() {
2471 return new KeyIterator();
2472 }
2473 Iterator<V> newValueIterator() {
2474 return new ValueIterator();
2475 }
2476 Iterator<Map.Entry<K,V>> newEntryIterator() {
2477 return new EntryIterator();
2478 }
2479
2480
2481 // Views
2482
2483 private transient Set<Map.Entry<K,V>> entrySet = null;
2484
2485 /**
2486 * Returns a {@link Set} view of the keys contained in this map.
2487 * The set is backed by the map, so changes to the map are
2488 * reflected in the set, and vice-versa. If the map is modified
2489 * while an iteration over the set is in progress (except through
2490 * the iterator's own <tt>remove</tt> operation), the results of
2491 * the iteration are undefined. The set supports element removal,
2492 * which removes the corresponding mapping from the map, via the
2493 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
2494 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
2495 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
2496 * operations.
2497 */
2498 public Set<K> keySet() {
2499 Set<K> ks = keySet;
2500 return (ks != null ? ks : (keySet = new KeySet()));
2501 }
2502
2503 private final class KeySet extends AbstractSet<K> {
2504 public Iterator<K> iterator() {
2505 return newKeyIterator();
2506 }
2507 public int size() {
2508 return size;
2509 }
2510 public boolean contains(Object o) {
2511 return containsKey(o);
2512 }
2513 public boolean remove(Object o) {
2514 return HashMap.this.removeEntryForKey(o) != null;
2515 }
2516 public void clear() {
2517 HashMap.this.clear();
2518 }
2519
2520 public Spliterator<K> spliterator() {
2521 if (HashMap.this.getClass() == HashMap.class)
2522 return new KeySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
2523 else
2524 return Spliterators.spliterator
2525 (this, Spliterator.SIZED | Spliterator.DISTINCT);
2526 }
2527 }
2528
2529 /**
2530 * Returns a {@link Collection} view of the values contained in this map.
2531 * The collection is backed by the map, so changes to the map are
2532 * reflected in the collection, and vice-versa. If the map is
2533 * modified while an iteration over the collection is in progress
2534 * (except through the iterator's own <tt>remove</tt> operation),
2535 * the results of the iteration are undefined. The collection
2536 * supports element removal, which removes the corresponding
2537 * mapping from the map, via the <tt>Iterator.remove</tt>,
2538 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
2539 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
2540 * support the <tt>add</tt> or <tt>addAll</tt> operations.
2541 */
2542 public Collection<V> values() {
2543 Collection<V> vs = values;
2544 return (vs != null ? vs : (values = new Values()));
2545 }
2546
2547 private final class Values extends AbstractCollection<V> {
2548 public Iterator<V> iterator() {
2549 return newValueIterator();
2550 }
2551 public int size() {
2552 return size;
2553 }
2554 public boolean contains(Object o) {
2555 return containsValue(o);
2556 }
2557 public void clear() {
2558 HashMap.this.clear();
2559 }
2560
2561 public Spliterator<V> spliterator() {
2562 if (HashMap.this.getClass() == HashMap.class)
2563 return new ValueSpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
2564 else
2565 return Spliterators.spliterator
2566 (this, Spliterator.SIZED);
2567 }
2568 }
2569
2570 /**
2571 * Returns a {@link Set} view of the mappings contained in this map.
2572 * The set is backed by the map, so changes to the map are
2573 * reflected in the set, and vice-versa. If the map is modified
2574 * while an iteration over the set is in progress (except through
2575 * the iterator's own <tt>remove</tt> operation, or through the
2576 * <tt>setValue</tt> operation on a map entry returned by the
2577 * iterator) the results of the iteration are undefined. The set
2578 * supports element removal, which removes the corresponding
2579 * mapping from the map, via the <tt>Iterator.remove</tt>,
2580 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
2581 * <tt>clear</tt> operations. It does not support the
2582 * <tt>add</tt> or <tt>addAll</tt> operations.
2583 *
2584 * @return a set view of the mappings contained in this map
2585 */
2586 public Set<Map.Entry<K,V>> entrySet() {
2587 return entrySet0();
2588 }
2589
2590 private Set<Map.Entry<K,V>> entrySet0() {
2591 Set<Map.Entry<K,V>> es = entrySet;
2592 return es != null ? es : (entrySet = new EntrySet());
2593 }
2594
2595 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
2596 public Iterator<Map.Entry<K,V>> iterator() {
2597 return newEntryIterator();
2598 }
2599 public boolean contains(Object o) {
2600 if (!(o instanceof Map.Entry))
2601 return false;
2602 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
2603 Entry<K,V> candidate = getEntry(e.getKey());
2604 return candidate != null && candidate.equals(e);
2605 }
2606 public boolean remove(Object o) {
2607 return removeMapping(o) != null;
2608 }
2609 public int size() {
2610 return size;
2611 }
2612 public void clear() {
2613 HashMap.this.clear();
2614 }
2615
2616 public Spliterator<Map.Entry<K,V>> spliterator() {
2617 if (HashMap.this.getClass() == HashMap.class)
2618 return new EntrySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
2619 else
2620 return Spliterators.spliterator
2621 (this, Spliterator.SIZED | Spliterator.DISTINCT);
2622 }
2623 }
2624
2625 /**
2626 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
2627 * serialize it).
2628 *
2629 * @serialData The <i>capacity</i> of the HashMap (the length of the
2630 * bucket array) is emitted (int), followed by the
2631 * <i>size</i> (an int, the number of key-value
2632 * mappings), followed by the key (Object) and value (Object)
2633 * for each key-value mapping. The key-value mappings are
2634 * emitted in no particular order.
2635 */
2636 private void writeObject(java.io.ObjectOutputStream s)
2637 throws IOException
2638 {
2639 // Write out the threshold, loadfactor, and any hidden stuff
2640 s.defaultWriteObject();
2641
2642 // Write out number of buckets
2643 if (table==EMPTY_TABLE) {
2644 s.writeInt(roundUpToPowerOf2(threshold));
2645 } else {
2646 s.writeInt(table.length);
2647 }
2648
2649 // Write out size (number of Mappings)
2650 s.writeInt(size);
2651
2652 // Write out keys and values (alternating)
2653 if (size > 0) {
2654 for(Map.Entry<K,V> e : entrySet0()) {
2655 s.writeObject(e.getKey());
2656 s.writeObject(e.getValue());
2657 }
2658 }
2659 }
2660
2661 private static final long serialVersionUID = 362498820763181265L;
2662
2663 /**
2664 * Reconstitute the {@code HashMap} instance from a stream (i.e.,
2665 * deserialize it).
2666 */
2667 private void readObject(java.io.ObjectInputStream s)
2668 throws IOException, ClassNotFoundException
2669 {
2670 // Read in the threshold (ignored), loadfactor, and any hidden stuff
2671 s.defaultReadObject();
2672 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
2673 throw new InvalidObjectException("Illegal load factor: " +
2674 loadFactor);
2675 }
2676
2677 // set other fields that need values
2678 if (Holder.USE_HASHSEED) {
2679 int seed = ThreadLocalRandom.current().nextInt();
2680 Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
2681 (seed != 0) ? seed : 1);
2682 }
2683 table = EMPTY_TABLE;
2684
2685 // Read in number of buckets
2686 s.readInt(); // ignored.
2687
2688 // Read number of mappings
2689 int mappings = s.readInt();
2690 if (mappings < 0)
2691 throw new InvalidObjectException("Illegal mappings count: " +
2692 mappings);
2693
2694 // capacity chosen by number of mappings and desired load (if >= 0.25)
2695 int capacity = (int) Math.min(
2696 mappings * Math.min(1 / loadFactor, 4.0f),
2697 // we have limits...
2698 HashMap.MAXIMUM_CAPACITY);
2699
2700 // allocate the bucket array;
2701 if (mappings > 0) {
2702 inflateTable(capacity);
2703 } else {
2704 threshold = capacity;
2705 }
2706
2707 init(); // Give subclass a chance to do its thing.
2708
2709 // Read the keys and values, and put the mappings in the HashMap
2710 for (int i=0; i<mappings; i++) {
2711 @SuppressWarnings("unchecked")
2712 K key = (K) s.readObject();
2713 @SuppressWarnings("unchecked")
2714 V value = (V) s.readObject();
2715 putForCreate(key, value);
2716 }
2717 }
2718
2719 // These methods are used when serializing HashSets
2720 int capacity() { return table.length; }
2721 float loadFactor() { return loadFactor; }
2722
2723 /**
2724 * Standin until HM overhaul; based loosely on Weak and Identity HM.
2725 */
2726 static class HashMapSpliterator<K,V> {
2727 final HashMap<K,V> map;
2728 Object current; // current node, can be Entry or TreeNode
2729 int index; // current index, modified on advance/split
2730 int fence; // one past last index
2731 int est; // size estimate
2732 int expectedModCount; // for comodification checks
2733 boolean acceptedNull; // Have we accepted the null key?
2734 // Without this, we can't distinguish
2735 // between being at the very beginning (and
2736 // needing to accept null), or being at the
2737 // end of the list in bin 0. In both cases,
2738 // current == null && index == 0.
2739
2740 HashMapSpliterator(HashMap<K,V> m, int origin,
2741 int fence, int est,
2742 int expectedModCount) {
2743 this.map = m;
2744 this.index = origin;
2745 this.fence = fence;
2746 this.est = est;
2747 this.expectedModCount = expectedModCount;
2748 this.acceptedNull = false;
2749 }
2750
2751 final int getFence() { // initialize fence and size on first use
2752 int hi;
2753 if ((hi = fence) < 0) {
2754 HashMap<K,V> m = map;
2755 est = m.size;
2756 expectedModCount = m.modCount;
2757 hi = fence = m.table.length;
2758 }
2759 return hi;
2760 }
2761
2762 public final long estimateSize() {
2763 getFence(); // force init
2764 return (long) est;
2765 }
2766 }
2767
2768 static final class KeySpliterator<K,V>
2769 extends HashMapSpliterator<K,V>
2770 implements Spliterator<K> {
2771 KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
2772 int expectedModCount) {
2773 super(m, origin, fence, est, expectedModCount);
2774 }
2775
2776 public KeySpliterator<K,V> trySplit() {
2777 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
2778 if (lo >= mid || current != null) {
2779 return null;
2780 } else {
2781 KeySpliterator<K,V> retVal = new KeySpliterator<K,V>(map, lo,
2782 index = mid, est >>>= 1, expectedModCount);
2783 // Only 'this' Spliterator chould check for null.
2784 retVal.acceptedNull = true;
2785 return retVal;
2786 }
2787 }
2788
2789 @SuppressWarnings("unchecked")
2790 public void forEachRemaining(Consumer<? super K> action) {
2791 int i, hi, mc;
2792 if (action == null)
2793 throw new NullPointerException();
2794 HashMap<K,V> m = map;
2795 Object[] tab = m.table;
2796 if ((hi = fence) < 0) {
2797 mc = expectedModCount = m.modCount;
2798 hi = fence = tab.length;
2799 }
2800 else
2801 mc = expectedModCount;
2802
2803 if (!acceptedNull) {
2804 acceptedNull = true;
2805 if (m.nullKeyEntry != null) {
2806 action.accept(m.nullKeyEntry.key);
2807 }
2808 }
2809 if (tab.length >= hi && (i = index) >= 0 &&
2810 (i < (index = hi) || current != null)) {
2811 Object p = current;
2812 current = null;
2813 do {
2814 if (p == null) {
2815 p = tab[i++];
2816 if (p instanceof HashMap.TreeBin) {
2817 p = ((HashMap.TreeBin)p).first;
2818 }
2819 } else {
2820 HashMap.Entry<K,V> entry;
2821 if (p instanceof HashMap.Entry) {
2822 entry = (HashMap.Entry<K,V>)p;
2823 } else {
2824 entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
2825 }
2826 action.accept(entry.key);
2827 p = entry.next;
2828 }
2829 } while (p != null || i < hi);
2830 if (m.modCount != mc)
2831 throw new ConcurrentModificationException();
2832 }
2833 }
2834
2835 @SuppressWarnings("unchecked")
2836 public boolean tryAdvance(Consumer<? super K> action) {
2837 int hi;
2838 if (action == null)
2839 throw new NullPointerException();
2840 Object[] tab = map.table;
2841 hi = getFence();
2842
2843 if (!acceptedNull) {
2844 acceptedNull = true;
2845 if (map.nullKeyEntry != null) {
2846 action.accept(map.nullKeyEntry.key);
2847 if (map.modCount != expectedModCount)
2848 throw new ConcurrentModificationException();
2849 return true;
2850 }
2851 }
2852 if (tab.length >= hi && index >= 0) {
2853 while (current != null || index < hi) {
2854 if (current == null) {
2855 current = tab[index++];
2856 if (current instanceof HashMap.TreeBin) {
2857 current = ((HashMap.TreeBin)current).first;
2858 }
2859 } else {
2860 HashMap.Entry<K,V> entry;
2861 if (current instanceof HashMap.Entry) {
2862 entry = (HashMap.Entry<K,V>)current;
2863 } else {
2864 entry = (HashMap.Entry<K,V>)((TreeNode)current).entry;
2865 }
2866 K k = entry.key;
2867 current = entry.next;
2868 action.accept(k);
2869 if (map.modCount != expectedModCount)
2870 throw new ConcurrentModificationException();
2871 return true;
2872 }
2873 }
2874 }
2875 return false;
2876 }
2877
2878 public int characteristics() {
2879 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
2880 Spliterator.DISTINCT;
2881 }
2882 }
2883
2884 static final class ValueSpliterator<K,V>
2885 extends HashMapSpliterator<K,V>
2886 implements Spliterator<V> {
2887 ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
2888 int expectedModCount) {
2889 super(m, origin, fence, est, expectedModCount);
2890 }
2891
2892 public ValueSpliterator<K,V> trySplit() {
2893 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
2894 if (lo >= mid || current != null) {
2895 return null;
2896 } else {
2897 ValueSpliterator<K,V> retVal = new ValueSpliterator<K,V>(map,
2898 lo, index = mid, est >>>= 1, expectedModCount);
2899 // Only 'this' Spliterator chould check for null.
2900 retVal.acceptedNull = true;
2901 return retVal;
2902 }
2903 }
2904
2905 @SuppressWarnings("unchecked")
2906 public void forEachRemaining(Consumer<? super V> action) {
2907 int i, hi, mc;
2908 if (action == null)
2909 throw new NullPointerException();
2910 HashMap<K,V> m = map;
2911 Object[] tab = m.table;
2912 if ((hi = fence) < 0) {
2913 mc = expectedModCount = m.modCount;
2914 hi = fence = tab.length;
2915 }
2916 else
2917 mc = expectedModCount;
2918
2919 if (!acceptedNull) {
2920 acceptedNull = true;
2921 if (m.nullKeyEntry != null) {
2922 action.accept(m.nullKeyEntry.value);
2923 }
2924 }
2925 if (tab.length >= hi && (i = index) >= 0 &&
2926 (i < (index = hi) || current != null)) {
2927 Object p = current;
2928 current = null;
2929 do {
2930 if (p == null) {
2931 p = tab[i++];
2932 if (p instanceof HashMap.TreeBin) {
2933 p = ((HashMap.TreeBin)p).first;
2934 }
2935 } else {
2936 HashMap.Entry<K,V> entry;
2937 if (p instanceof HashMap.Entry) {
2938 entry = (HashMap.Entry<K,V>)p;
2939 } else {
2940 entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
2941 }
2942 action.accept(entry.value);
2943 p = entry.next;
2944 }
2945 } while (p != null || i < hi);
2946 if (m.modCount != mc)
2947 throw new ConcurrentModificationException();
2948 }
2949 }
2950
2951 @SuppressWarnings("unchecked")
2952 public boolean tryAdvance(Consumer<? super V> action) {
2953 int hi;
2954 if (action == null)
2955 throw new NullPointerException();
2956 Object[] tab = map.table;
2957 hi = getFence();
2958
2959 if (!acceptedNull) {
2960 acceptedNull = true;
2961 if (map.nullKeyEntry != null) {
2962 action.accept(map.nullKeyEntry.value);
2963 if (map.modCount != expectedModCount)
2964 throw new ConcurrentModificationException();
2965 return true;
2966 }
2967 }
2968 if (tab.length >= hi && index >= 0) {
2969 while (current != null || index < hi) {
2970 if (current == null) {
2971 current = tab[index++];
2972 if (current instanceof HashMap.TreeBin) {
2973 current = ((HashMap.TreeBin)current).first;
2974 }
2975 } else {
2976 HashMap.Entry<K,V> entry;
2977 if (current instanceof HashMap.Entry) {
2978 entry = (Entry<K,V>)current;
2979 } else {
2980 entry = (Entry<K,V>)((TreeNode)current).entry;
2981 }
2982 V v = entry.value;
2983 current = entry.next;
2984 action.accept(v);
2985 if (map.modCount != expectedModCount)
2986 throw new ConcurrentModificationException();
2987 return true;
2988 }
2989 }
2990 }
2991 return false;
2992 }
2993
2994 public int characteristics() {
2995 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
2996 }
2997 }
2998
2999 static final class EntrySpliterator<K,V>
3000 extends HashMapSpliterator<K,V>
3001 implements Spliterator<Map.Entry<K,V>> {
3002 EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
3003 int expectedModCount) {
3004 super(m, origin, fence, est, expectedModCount);
3005 }
3006
3007 public EntrySpliterator<K,V> trySplit() {
3008 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
3009 if (lo >= mid || current != null) {
3010 return null;
3011 } else {
3012 EntrySpliterator<K,V> retVal = new EntrySpliterator<K,V>(map,
3013 lo, index = mid, est >>>= 1, expectedModCount);
3014 // Only 'this' Spliterator chould check for null.
3015 retVal.acceptedNull = true;
3016 return retVal;
3017 }
3018 }
3019
3020 @SuppressWarnings("unchecked")
3021 public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
3022 int i, hi, mc;
3023 if (action == null)
3024 throw new NullPointerException();
3025 HashMap<K,V> m = map;
3026 Object[] tab = m.table;
3027 if ((hi = fence) < 0) {
3028 mc = expectedModCount = m.modCount;
3029 hi = fence = tab.length;
3030 }
3031 else
3032 mc = expectedModCount;
3033
3034 if (!acceptedNull) {
3035 acceptedNull = true;
3036 if (m.nullKeyEntry != null) {
3037 action.accept(m.nullKeyEntry);
3038 }
3039 }
3040 if (tab.length >= hi && (i = index) >= 0 &&
3041 (i < (index = hi) || current != null)) {
3042 Object p = current;
3043 current = null;
3044 do {
3045 if (p == null) {
3046 p = tab[i++];
3047 if (p instanceof HashMap.TreeBin) {
3048 p = ((HashMap.TreeBin)p).first;
3049 }
3050 } else {
3051 HashMap.Entry<K,V> entry;
3052 if (p instanceof HashMap.Entry) {
3053 entry = (HashMap.Entry<K,V>)p;
3054 } else {
3055 entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
3056 }
3057 action.accept(entry);
3058 p = entry.next;
3059
3060 }
3061 } while (p != null || i < hi);
3062 if (m.modCount != mc)
3063 throw new ConcurrentModificationException();
3064 }
3065 }
3066
3067 @SuppressWarnings("unchecked")
3068 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
3069 int hi;
3070 if (action == null)
3071 throw new NullPointerException();
3072 Object[] tab = map.table;
3073 hi = getFence();
3074
3075 if (!acceptedNull) {
3076 acceptedNull = true;
3077 if (map.nullKeyEntry != null) {
3078 action.accept(map.nullKeyEntry);
3079 if (map.modCount != expectedModCount)
3080 throw new ConcurrentModificationException();
3081 return true;
3082 }
3083 }
3084 if (tab.length >= hi && index >= 0) {
3085 while (current != null || index < hi) {
3086 if (current == null) {
3087 current = tab[index++];
3088 if (current instanceof HashMap.TreeBin) {
3089 current = ((HashMap.TreeBin)current).first;
3090 }
3091 } else {
3092 HashMap.Entry<K,V> e;
3093 if (current instanceof HashMap.Entry) {
3094 e = (Entry<K,V>)current;
3095 } else {
3096 e = (Entry<K,V>)((TreeNode)current).entry;
3097 }
3098 current = e.next;
3099 action.accept(e);
3100 if (map.modCount != expectedModCount)
3101 throw new ConcurrentModificationException();
3102 return true;
3103 }
3104 }
3105 }
3106 return false;
3107 }
3108
3109 public int characteristics() {
3110 return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
3111 Spliterator.DISTINCT;
3112 }
3113 }
3114 }