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