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