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.IOException;
29 import java.io.InvalidObjectException;
30 import java.io.Serializable;
31 import java.lang.reflect.ParameterizedType;
32 import java.lang.reflect.Type;
33 import java.util.function.BiConsumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Consumer;
36 import java.util.function.Function;
37
38 /**
39 * Hash table based implementation of the <tt>Map</tt> interface. This
40 * implementation provides all of the optional map operations, and permits
41 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
42 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
43 * unsynchronized and permits nulls.) This class makes no guarantees as to
44 * the order of the map; in particular, it does not guarantee that the order
45 * will remain constant over time.
46 *
47 * <p>This implementation provides constant-time performance for the basic
48 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
49 * disperses the elements properly among the buckets. Iteration over
50 * collection views requires time proportional to the "capacity" of the
51 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
52 * of key-value mappings). Thus, it's very important not to set the initial
53 * capacity too high (or the load factor too low) if iteration performance is
54 * important.
55 *
56 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
57 * performance: <i>initial capacity</i> and <i>load factor</i>. The
58 * <i>capacity</i> is the number of buckets in the hash table, and the initial
59 * capacity is simply the capacity at the time the hash table is created. The
60 * <i>load factor</i> is a measure of how full the hash table is allowed to
61 * get before its capacity is automatically increased. When the number of
62 * entries in the hash table exceeds the product of the load factor and the
63 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
64 * structures are rebuilt) so that the hash table has approximately twice the
65 * number of buckets.
66 *
67 * <p>As a general rule, the default load factor (.75) offers a good
68 * tradeoff between time and space costs. Higher values decrease the
69 * space overhead but increase the lookup cost (reflected in most of
70 * the operations of the <tt>HashMap</tt> class, including
71 * <tt>get</tt> and <tt>put</tt>). The expected number of entries in
72 * the map and its load factor should be taken into account when
73 * setting its initial capacity, so as to minimize the number of
74 * rehash operations. If the initial capacity is greater than the
75 * maximum number of entries divided by the load factor, no rehash
76 * operations will ever occur.
77 *
78 * <p>If many mappings are to be stored in a <tt>HashMap</tt>
79 * instance, creating it with a sufficiently large capacity will allow
80 * the mappings to be stored more efficiently than letting it perform
81 * automatic rehashing as needed to grow the table. Note that using
82 * many keys with the same {@code hashCode()} is a sure way to slow
83 * down performance of any hash table. To ameliorate impact, when keys
84 * are {@link Comparable}, this class may use comparison order among
85 * keys to help break ties.
86 *
87 * <p><strong>Note that this implementation is not synchronized.</strong>
88 * If multiple threads access a hash map concurrently, and at least one of
89 * the threads modifies the map structurally, it <i>must</i> be
90 * synchronized externally. (A structural modification is any operation
91 * that adds or deletes one or more mappings; merely changing the value
92 * associated with a key that an instance already contains is not a
93 * structural modification.) This is typically accomplished by
94 * synchronizing on some object that naturally encapsulates the map.
95 *
96 * If no such object exists, the map should be "wrapped" using the
97 * {@link Collections#synchronizedMap Collections.synchronizedMap}
98 * method. This is best done at creation time, to prevent accidental
99 * unsynchronized access to the map:<pre>
100 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
101 *
102 * <p>The iterators returned by all of this class's "collection view methods"
103 * are <i>fail-fast</i>: if the map is structurally modified at any time after
104 * the iterator is created, in any way except through the iterator's own
105 * <tt>remove</tt> method, the iterator will throw a
106 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
107 * modification, the iterator fails quickly and cleanly, rather than risking
108 * arbitrary, non-deterministic behavior at an undetermined time in the
109 * future.
110 *
111 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
112 * as it is, generally speaking, impossible to make any hard guarantees in the
113 * presence of unsynchronized concurrent modification. Fail-fast iterators
114 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
115 * Therefore, it would be wrong to write a program that depended on this
116 * exception for its correctness: <i>the fail-fast behavior of iterators
117 * should be used only to detect bugs.</i>
118 *
119 * <p>This class is a member of the
120 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
121 * Java Collections Framework</a>.
122 *
123 * @param <K> the type of keys maintained by this map
124 * @param <V> the type of mapped values
125 *
126 * @author Doug Lea
127 * @author Josh Bloch
128 * @author Arthur van Hoff
129 * @author Neal Gafter
130 * @see Object#hashCode()
131 * @see Collection
132 * @see Map
133 * @see TreeMap
134 * @see Hashtable
418 * The next size value at which to resize (capacity * load factor).
419 *
420 * @serial
421 */
422 // (The javadoc description is true upon serialization.
423 // Additionally, if the table array has not been allocated, this
424 // field holds the initial array capacity, or zero signifying
425 // DEFAULT_INITIAL_CAPACITY.)
426 int threshold;
427
428 /**
429 * The load factor for the hash table.
430 *
431 * @serial
432 */
433 final float loadFactor;
434
435 /* ---------------- Public operations -------------- */
436
437 /**
438 * Constructs an empty <tt>HashMap</tt> with the specified initial
439 * capacity and load factor.
440 *
441 * @param initialCapacity the initial capacity
442 * @param loadFactor the load factor
443 * @throws IllegalArgumentException if the initial capacity is negative
444 * or the load factor is nonpositive
445 */
446 public HashMap(int initialCapacity, float loadFactor) {
447 if (initialCapacity < 0)
448 throw new IllegalArgumentException("Illegal initial capacity: " +
449 initialCapacity);
450 if (initialCapacity > MAXIMUM_CAPACITY)
451 initialCapacity = MAXIMUM_CAPACITY;
452 if (loadFactor <= 0 || Float.isNaN(loadFactor))
453 throw new IllegalArgumentException("Illegal load factor: " +
454 loadFactor);
455 this.loadFactor = loadFactor;
456 this.threshold = tableSizeFor(initialCapacity);
457 }
458
459 /**
460 * Constructs an empty <tt>HashMap</tt> with the specified initial
461 * capacity and the default load factor (0.75).
462 *
463 * @param initialCapacity the initial capacity.
464 * @throws IllegalArgumentException if the initial capacity is negative.
465 */
466 public HashMap(int initialCapacity) {
467 this(initialCapacity, DEFAULT_LOAD_FACTOR);
468 }
469
470 /**
471 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
472 * (16) and the default load factor (0.75).
473 */
474 public HashMap() {
475 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
476 }
477
478 /**
479 * Constructs a new <tt>HashMap</tt> with the same mappings as the
480 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
481 * default load factor (0.75) and an initial capacity sufficient to
482 * hold the mappings in the specified <tt>Map</tt>.
483 *
484 * @param m the map whose mappings are to be placed in this map
485 * @throws NullPointerException if the specified map is null
486 */
487 public HashMap(Map<? extends K, ? extends V> m) {
488 this.loadFactor = DEFAULT_LOAD_FACTOR;
489 putMapEntries(m, false);
490 }
491
492 /**
493 * Implements Map.putAll and Map constructor
494 *
495 * @param m the map
496 * @param evict false when initially constructing this map, else
497 * true (relayed to method afterNodeInsertion).
498 */
499 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
500 int s = m.size();
501 if (s > 0) {
502 if (table == null) { // pre-size
509 else if (s > threshold)
510 resize();
511 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
512 K key = e.getKey();
513 V value = e.getValue();
514 putVal(hash(key), key, value, false, evict);
515 }
516 }
517 }
518
519 /**
520 * Returns the number of key-value mappings in this map.
521 *
522 * @return the number of key-value mappings in this map
523 */
524 public int size() {
525 return size;
526 }
527
528 /**
529 * Returns <tt>true</tt> if this map contains no key-value mappings.
530 *
531 * @return <tt>true</tt> if this map contains no key-value mappings
532 */
533 public boolean isEmpty() {
534 return size == 0;
535 }
536
537 /**
538 * Returns the value to which the specified key is mapped,
539 * or {@code null} if this map contains no mapping for the key.
540 *
541 * <p>More formally, if this map contains a mapping from a key
542 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
543 * key.equals(k))}, then this method returns {@code v}; otherwise
544 * it returns {@code null}. (There can be at most one such mapping.)
545 *
546 * <p>A return value of {@code null} does not <i>necessarily</i>
547 * indicate that the map contains no mapping for the key; it's also
548 * possible that the map explicitly maps the key to {@code null}.
549 * The {@link #containsKey containsKey} operation may be used to
550 * distinguish these two cases.
551 *
567 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
568 if ((tab = table) != null && (n = tab.length) > 0 &&
569 (first = tab[(n - 1) & hash]) != null) {
570 if (first.hash == hash && // always check first node
571 ((k = first.key) == key || (key != null && key.equals(k))))
572 return first;
573 if ((e = first.next) != null) {
574 if (first instanceof TreeNode)
575 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
576 do {
577 if (e.hash == hash &&
578 ((k = e.key) == key || (key != null && key.equals(k))))
579 return e;
580 } while ((e = e.next) != null);
581 }
582 }
583 return null;
584 }
585
586 /**
587 * Returns <tt>true</tt> if this map contains a mapping for the
588 * specified key.
589 *
590 * @param key The key whose presence in this map is to be tested
591 * @return <tt>true</tt> if this map contains a mapping for the specified
592 * key.
593 */
594 public boolean containsKey(Object key) {
595 return getNode(hash(key), key) != null;
596 }
597
598 /**
599 * Associates the specified value with the specified key in this map.
600 * If the map previously contained a mapping for the key, the old
601 * value is replaced.
602 *
603 * @param key key with which the specified value is to be associated
604 * @param value value to be associated with the specified key
605 * @return the previous value associated with <tt>key</tt>, or
606 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
607 * (A <tt>null</tt> return can also indicate that the map
608 * previously associated <tt>null</tt> with <tt>key</tt>.)
609 */
610 public V put(K key, V value) {
611 return putVal(hash(key), key, value, false, true);
612 }
613
614 /**
615 * Implements Map.put and related methods
616 *
617 * @param hash hash for key
618 * @param key the key
619 * @param value the value to put
620 * @param onlyIfAbsent if true, don't change existing value
621 * @param evict if false, the table is in creation mode.
622 * @return previous value, or null if none
623 */
624 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
625 boolean evict) {
626 Node<K,V>[] tab; Node<K,V> p; int n, i;
627 if ((tab = table) == null || (n = tab.length) == 0)
628 n = (tab = resize()).length;
771 hd.treeify(tab);
772 }
773 }
774
775 /**
776 * Copies all of the mappings from the specified map to this map.
777 * These mappings will replace any mappings that this map had for
778 * any of the keys currently in the specified map.
779 *
780 * @param m mappings to be stored in this map
781 * @throws NullPointerException if the specified map is null
782 */
783 public void putAll(Map<? extends K, ? extends V> m) {
784 putMapEntries(m, true);
785 }
786
787 /**
788 * Removes the mapping for the specified key from this map if present.
789 *
790 * @param key key whose mapping is to be removed from the map
791 * @return the previous value associated with <tt>key</tt>, or
792 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
793 * (A <tt>null</tt> return can also indicate that the map
794 * previously associated <tt>null</tt> with <tt>key</tt>.)
795 */
796 public V remove(Object key) {
797 Node<K,V> e;
798 return (e = removeNode(hash(key), key, null, false, true)) == null ?
799 null : e.value;
800 }
801
802 /**
803 * Implements Map.remove and related methods
804 *
805 * @param hash hash for key
806 * @param key the key
807 * @param value the value to match if matchValue, else ignored
808 * @param matchValue if true only remove if value is equal
809 * @param movable if false do not move other nodes while removing
810 * @return the node, or null if none
811 */
812 final Node<K,V> removeNode(int hash, Object key, Object value,
813 boolean matchValue, boolean movable) {
814 Node<K,V>[] tab; Node<K,V> p; int n, index;
848 }
849 }
850 return null;
851 }
852
853 /**
854 * Removes all of the mappings from this map.
855 * The map will be empty after this call returns.
856 */
857 public void clear() {
858 Node<K,V>[] tab;
859 modCount++;
860 if ((tab = table) != null && size > 0) {
861 size = 0;
862 for (int i = 0; i < tab.length; ++i)
863 tab[i] = null;
864 }
865 }
866
867 /**
868 * Returns <tt>true</tt> if this map maps one or more keys to the
869 * specified value.
870 *
871 * @param value value whose presence in this map is to be tested
872 * @return <tt>true</tt> if this map maps one or more keys to the
873 * specified value
874 */
875 public boolean containsValue(Object value) {
876 Node<K,V>[] tab; V v;
877 if ((tab = table) != null && size > 0) {
878 for (Node<K, V> e : tab) {
879 for (; e != null; e = e.next) {
880 if ((v = e.value) == value ||
881 (value != null && value.equals(v)))
882 return true;
883 }
884 }
885 }
886 return false;
887 }
888
889 /**
890 * Returns a {@link Set} view of the keys contained in this map.
891 * The set is backed by the map, so changes to the map are
892 * reflected in the set, and vice-versa. If the map is modified
893 * while an iteration over the set is in progress (except through
894 * the iterator's own <tt>remove</tt> operation), the results of
895 * the iteration are undefined. The set supports element removal,
896 * which removes the corresponding mapping from the map, via the
897 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
898 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
899 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
900 * operations.
901 *
902 * @return a set view of the keys contained in this map
903 */
904 public Set<K> keySet() {
905 Set<K> ks;
906 return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
907 }
908
909 final class KeySet extends AbstractSet<K> {
910 public final int size() { return size; }
911 public final void clear() { HashMap.this.clear(); }
912 public final Iterator<K> iterator() { return new KeyIterator(); }
913 public final boolean contains(Object o) { return containsKey(o); }
914 public final boolean remove(Object key) {
915 return removeNode(hash(key), key, null, false, true) != null;
916 }
917 public final Spliterator<K> spliterator() {
918 return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
919 }
921 Node<K,V>[] tab;
922 if (action == null)
923 throw new NullPointerException();
924 if (size > 0 && (tab = table) != null) {
925 int mc = modCount;
926 for (Node<K, V> e : tab) {
927 for (; e != null; e = e.next)
928 action.accept(e.key);
929 }
930 if (modCount != mc)
931 throw new ConcurrentModificationException();
932 }
933 }
934 }
935
936 /**
937 * Returns a {@link Collection} view of the values contained in this map.
938 * The collection is backed by the map, so changes to the map are
939 * reflected in the collection, and vice-versa. If the map is
940 * modified while an iteration over the collection is in progress
941 * (except through the iterator's own <tt>remove</tt> operation),
942 * the results of the iteration are undefined. The collection
943 * supports element removal, which removes the corresponding
944 * mapping from the map, via the <tt>Iterator.remove</tt>,
945 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
946 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
947 * support the <tt>add</tt> or <tt>addAll</tt> operations.
948 *
949 * @return a view of the values contained in this map
950 */
951 public Collection<V> values() {
952 Collection<V> vs;
953 return (vs = values) == null ? (values = new Values()) : vs;
954 }
955
956 final class Values extends AbstractCollection<V> {
957 public final int size() { return size; }
958 public final void clear() { HashMap.this.clear(); }
959 public final Iterator<V> iterator() { return new ValueIterator(); }
960 public final boolean contains(Object o) { return containsValue(o); }
961 public final Spliterator<V> spliterator() {
962 return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
963 }
964 public final void forEach(Consumer<? super V> action) {
965 Node<K,V>[] tab;
966 if (action == null)
967 throw new NullPointerException();
968 if (size > 0 && (tab = table) != null) {
969 int mc = modCount;
970 for (Node<K, V> e : tab) {
971 for (; e != null; e = e.next)
972 action.accept(e.value);
973 }
974 if (modCount != mc)
975 throw new ConcurrentModificationException();
976 }
977 }
978 }
979
980 /**
981 * Returns a {@link Set} view of the mappings contained in this map.
982 * The set is backed by the map, so changes to the map are
983 * reflected in the set, and vice-versa. If the map is modified
984 * while an iteration over the set is in progress (except through
985 * the iterator's own <tt>remove</tt> operation, or through the
986 * <tt>setValue</tt> operation on a map entry returned by the
987 * iterator) the results of the iteration are undefined. The set
988 * supports element removal, which removes the corresponding
989 * mapping from the map, via the <tt>Iterator.remove</tt>,
990 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
991 * <tt>clear</tt> operations. It does not support the
992 * <tt>add</tt> or <tt>addAll</tt> operations.
993 *
994 * @return a set view of the mappings contained in this map
995 */
996 public Set<Map.Entry<K,V>> entrySet() {
997 Set<Map.Entry<K,V>> es;
998 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
999 }
1000
1001 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1002 public final int size() { return size; }
1003 public final void clear() { HashMap.this.clear(); }
1004 public final Iterator<Map.Entry<K,V>> iterator() {
1005 return new EntryIterator();
1006 }
1007 public final boolean contains(Object o) {
1008 if (!(o instanceof Map.Entry))
1009 return false;
1010 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1011 Object key = e.getKey();
1012 Node<K,V> candidate = getNode(hash(key), key);
1340 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1341 Node<K,V>[] tab;
1342 if (function == null)
1343 throw new NullPointerException();
1344 if (size > 0 && (tab = table) != null) {
1345 int mc = modCount;
1346 for (Node<K, V> e : tab) {
1347 for (; e != null; e = e.next) {
1348 e.value = function.apply(e.key, e.value);
1349 }
1350 }
1351 if (modCount != mc)
1352 throw new ConcurrentModificationException();
1353 }
1354 }
1355
1356 /* ------------------------------------------------------------ */
1357 // Cloning and serialization
1358
1359 /**
1360 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
1361 * values themselves are not cloned.
1362 *
1363 * @return a shallow copy of this map
1364 */
1365 @SuppressWarnings("unchecked")
1366 @Override
1367 public Object clone() {
1368 HashMap<K,V> result;
1369 try {
1370 result = (HashMap<K,V>)super.clone();
1371 } catch (CloneNotSupportedException e) {
1372 // this shouldn't happen, since we are Cloneable
1373 throw new InternalError(e);
1374 }
1375 result.reinitialize();
1376 result.putMapEntries(this, false);
1377 return result;
1378 }
1379
1380 // These methods are also used when serializing HashSets
1381 final float loadFactor() { return loadFactor; }
1382 final int capacity() {
1383 return (table != null) ? table.length :
1384 (threshold > 0) ? threshold :
1385 DEFAULT_INITIAL_CAPACITY;
1386 }
1387
1388 /**
1389 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1390 * serialize it).
1391 *
1392 * @serialData The <i>capacity</i> of the HashMap (the length of the
1393 * bucket array) is emitted (int), followed by the
1394 * <i>size</i> (an int, the number of key-value
1395 * mappings), followed by the key (Object) and value (Object)
1396 * for each key-value mapping. The key-value mappings are
1397 * emitted in no particular order.
1398 */
1399 private void writeObject(java.io.ObjectOutputStream s)
1400 throws IOException {
1401 int buckets = capacity();
1402 // Write out the threshold, loadfactor, and any hidden stuff
1403 s.defaultWriteObject();
1404 s.writeInt(buckets);
1405 s.writeInt(size);
1406 internalWriteEntries(s);
1407 }
1408
1409 /**
|
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.IOException;
29 import java.io.InvalidObjectException;
30 import java.io.Serializable;
31 import java.lang.reflect.ParameterizedType;
32 import java.lang.reflect.Type;
33 import java.util.function.BiConsumer;
34 import java.util.function.BiFunction;
35 import java.util.function.Consumer;
36 import java.util.function.Function;
37
38 /**
39 * Hash table based implementation of the {@code Map} interface. This
40 * implementation provides all of the optional map operations, and permits
41 * {@code null} values and the {@code null} key. (The {@code HashMap}
42 * class is roughly equivalent to {@code Hashtable}, except that it is
43 * unsynchronized and permits nulls.) This class makes no guarantees as to
44 * the order of the map; in particular, it does not guarantee that the order
45 * will remain constant over time.
46 *
47 * <p>This implementation provides constant-time performance for the basic
48 * operations ({@code get} and {@code put}), assuming the hash function
49 * disperses the elements properly among the buckets. Iteration over
50 * collection views requires time proportional to the "capacity" of the
51 * {@code HashMap} instance (the number of buckets) plus its size (the number
52 * of key-value mappings). Thus, it's very important not to set the initial
53 * capacity too high (or the load factor too low) if iteration performance is
54 * important.
55 *
56 * <p>An instance of {@code HashMap} has two parameters that affect its
57 * performance: <i>initial capacity</i> and <i>load factor</i>. The
58 * <i>capacity</i> is the number of buckets in the hash table, and the initial
59 * capacity is simply the capacity at the time the hash table is created. The
60 * <i>load factor</i> is a measure of how full the hash table is allowed to
61 * get before its capacity is automatically increased. When the number of
62 * entries in the hash table exceeds the product of the load factor and the
63 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
64 * structures are rebuilt) so that the hash table has approximately twice the
65 * number of buckets.
66 *
67 * <p>As a general rule, the default load factor (.75) offers a good
68 * tradeoff between time and space costs. Higher values decrease the
69 * space overhead but increase the lookup cost (reflected in most of
70 * the operations of the {@code HashMap} class, including
71 * {@code get} and {@code put}). The expected number of entries in
72 * the map and its load factor should be taken into account when
73 * setting its initial capacity, so as to minimize the number of
74 * rehash operations. If the initial capacity is greater than the
75 * maximum number of entries divided by the load factor, no rehash
76 * operations will ever occur.
77 *
78 * <p>If many mappings are to be stored in a {@code HashMap}
79 * instance, creating it with a sufficiently large capacity will allow
80 * the mappings to be stored more efficiently than letting it perform
81 * automatic rehashing as needed to grow the table. Note that using
82 * many keys with the same {@code hashCode()} is a sure way to slow
83 * down performance of any hash table. To ameliorate impact, when keys
84 * are {@link Comparable}, this class may use comparison order among
85 * keys to help break ties.
86 *
87 * <p><strong>Note that this implementation is not synchronized.</strong>
88 * If multiple threads access a hash map concurrently, and at least one of
89 * the threads modifies the map structurally, it <i>must</i> be
90 * synchronized externally. (A structural modification is any operation
91 * that adds or deletes one or more mappings; merely changing the value
92 * associated with a key that an instance already contains is not a
93 * structural modification.) This is typically accomplished by
94 * synchronizing on some object that naturally encapsulates the map.
95 *
96 * If no such object exists, the map should be "wrapped" using the
97 * {@link Collections#synchronizedMap Collections.synchronizedMap}
98 * method. This is best done at creation time, to prevent accidental
99 * unsynchronized access to the map:<pre>
100 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
101 *
102 * <p>The iterators returned by all of this class's "collection view methods"
103 * are <i>fail-fast</i>: if the map is structurally modified at any time after
104 * the iterator is created, in any way except through the iterator's own
105 * {@code remove} method, the iterator will throw a
106 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
107 * modification, the iterator fails quickly and cleanly, rather than risking
108 * arbitrary, non-deterministic behavior at an undetermined time in the
109 * future.
110 *
111 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
112 * as it is, generally speaking, impossible to make any hard guarantees in the
113 * presence of unsynchronized concurrent modification. Fail-fast iterators
114 * throw {@code ConcurrentModificationException} on a best-effort basis.
115 * Therefore, it would be wrong to write a program that depended on this
116 * exception for its correctness: <i>the fail-fast behavior of iterators
117 * should be used only to detect bugs.</i>
118 *
119 * <p>This class is a member of the
120 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
121 * Java Collections Framework</a>.
122 *
123 * @param <K> the type of keys maintained by this map
124 * @param <V> the type of mapped values
125 *
126 * @author Doug Lea
127 * @author Josh Bloch
128 * @author Arthur van Hoff
129 * @author Neal Gafter
130 * @see Object#hashCode()
131 * @see Collection
132 * @see Map
133 * @see TreeMap
134 * @see Hashtable
418 * The next size value at which to resize (capacity * load factor).
419 *
420 * @serial
421 */
422 // (The javadoc description is true upon serialization.
423 // Additionally, if the table array has not been allocated, this
424 // field holds the initial array capacity, or zero signifying
425 // DEFAULT_INITIAL_CAPACITY.)
426 int threshold;
427
428 /**
429 * The load factor for the hash table.
430 *
431 * @serial
432 */
433 final float loadFactor;
434
435 /* ---------------- Public operations -------------- */
436
437 /**
438 * Constructs an empty {@code HashMap} with the specified initial
439 * capacity and load factor.
440 *
441 * @param initialCapacity the initial capacity
442 * @param loadFactor the load factor
443 * @throws IllegalArgumentException if the initial capacity is negative
444 * or the load factor is nonpositive
445 */
446 public HashMap(int initialCapacity, float loadFactor) {
447 if (initialCapacity < 0)
448 throw new IllegalArgumentException("Illegal initial capacity: " +
449 initialCapacity);
450 if (initialCapacity > MAXIMUM_CAPACITY)
451 initialCapacity = MAXIMUM_CAPACITY;
452 if (loadFactor <= 0 || Float.isNaN(loadFactor))
453 throw new IllegalArgumentException("Illegal load factor: " +
454 loadFactor);
455 this.loadFactor = loadFactor;
456 this.threshold = tableSizeFor(initialCapacity);
457 }
458
459 /**
460 * Constructs an empty {@code HashMap} with the specified initial
461 * capacity and the default load factor (0.75).
462 *
463 * @param initialCapacity the initial capacity.
464 * @throws IllegalArgumentException if the initial capacity is negative.
465 */
466 public HashMap(int initialCapacity) {
467 this(initialCapacity, DEFAULT_LOAD_FACTOR);
468 }
469
470 /**
471 * Constructs an empty {@code HashMap} with the default initial capacity
472 * (16) and the default load factor (0.75).
473 */
474 public HashMap() {
475 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
476 }
477
478 /**
479 * Constructs a new {@code HashMap} with the same mappings as the
480 * specified {@code Map}. The {@code HashMap} is created with
481 * default load factor (0.75) and an initial capacity sufficient to
482 * hold the mappings in the specified {@code Map}.
483 *
484 * @param m the map whose mappings are to be placed in this map
485 * @throws NullPointerException if the specified map is null
486 */
487 public HashMap(Map<? extends K, ? extends V> m) {
488 this.loadFactor = DEFAULT_LOAD_FACTOR;
489 putMapEntries(m, false);
490 }
491
492 /**
493 * Implements Map.putAll and Map constructor
494 *
495 * @param m the map
496 * @param evict false when initially constructing this map, else
497 * true (relayed to method afterNodeInsertion).
498 */
499 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
500 int s = m.size();
501 if (s > 0) {
502 if (table == null) { // pre-size
509 else if (s > threshold)
510 resize();
511 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
512 K key = e.getKey();
513 V value = e.getValue();
514 putVal(hash(key), key, value, false, evict);
515 }
516 }
517 }
518
519 /**
520 * Returns the number of key-value mappings in this map.
521 *
522 * @return the number of key-value mappings in this map
523 */
524 public int size() {
525 return size;
526 }
527
528 /**
529 * Returns {@code true} if this map contains no key-value mappings.
530 *
531 * @return {@code true} if this map contains no key-value mappings
532 */
533 public boolean isEmpty() {
534 return size == 0;
535 }
536
537 /**
538 * Returns the value to which the specified key is mapped,
539 * or {@code null} if this map contains no mapping for the key.
540 *
541 * <p>More formally, if this map contains a mapping from a key
542 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
543 * key.equals(k))}, then this method returns {@code v}; otherwise
544 * it returns {@code null}. (There can be at most one such mapping.)
545 *
546 * <p>A return value of {@code null} does not <i>necessarily</i>
547 * indicate that the map contains no mapping for the key; it's also
548 * possible that the map explicitly maps the key to {@code null}.
549 * The {@link #containsKey containsKey} operation may be used to
550 * distinguish these two cases.
551 *
567 Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
568 if ((tab = table) != null && (n = tab.length) > 0 &&
569 (first = tab[(n - 1) & hash]) != null) {
570 if (first.hash == hash && // always check first node
571 ((k = first.key) == key || (key != null && key.equals(k))))
572 return first;
573 if ((e = first.next) != null) {
574 if (first instanceof TreeNode)
575 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
576 do {
577 if (e.hash == hash &&
578 ((k = e.key) == key || (key != null && key.equals(k))))
579 return e;
580 } while ((e = e.next) != null);
581 }
582 }
583 return null;
584 }
585
586 /**
587 * Returns {@code true} if this map contains a mapping for the
588 * specified key.
589 *
590 * @param key The key whose presence in this map is to be tested
591 * @return {@code true} if this map contains a mapping for the specified
592 * key.
593 */
594 public boolean containsKey(Object key) {
595 return getNode(hash(key), key) != null;
596 }
597
598 /**
599 * Associates the specified value with the specified key in this map.
600 * If the map previously contained a mapping for the key, the old
601 * value is replaced.
602 *
603 * @param key key with which the specified value is to be associated
604 * @param value value to be associated with the specified key
605 * @return the previous value associated with {@code key}, or
606 * {@code null} if there was no mapping for {@code key}.
607 * (A {@code null} return can also indicate that the map
608 * previously associated {@code null} with {@code key}.)
609 */
610 public V put(K key, V value) {
611 return putVal(hash(key), key, value, false, true);
612 }
613
614 /**
615 * Implements Map.put and related methods
616 *
617 * @param hash hash for key
618 * @param key the key
619 * @param value the value to put
620 * @param onlyIfAbsent if true, don't change existing value
621 * @param evict if false, the table is in creation mode.
622 * @return previous value, or null if none
623 */
624 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
625 boolean evict) {
626 Node<K,V>[] tab; Node<K,V> p; int n, i;
627 if ((tab = table) == null || (n = tab.length) == 0)
628 n = (tab = resize()).length;
771 hd.treeify(tab);
772 }
773 }
774
775 /**
776 * Copies all of the mappings from the specified map to this map.
777 * These mappings will replace any mappings that this map had for
778 * any of the keys currently in the specified map.
779 *
780 * @param m mappings to be stored in this map
781 * @throws NullPointerException if the specified map is null
782 */
783 public void putAll(Map<? extends K, ? extends V> m) {
784 putMapEntries(m, true);
785 }
786
787 /**
788 * Removes the mapping for the specified key from this map if present.
789 *
790 * @param key key whose mapping is to be removed from the map
791 * @return the previous value associated with {@code key}, or
792 * {@code null} if there was no mapping for {@code key}.
793 * (A {@code null} return can also indicate that the map
794 * previously associated {@code null} with {@code key}.)
795 */
796 public V remove(Object key) {
797 Node<K,V> e;
798 return (e = removeNode(hash(key), key, null, false, true)) == null ?
799 null : e.value;
800 }
801
802 /**
803 * Implements Map.remove and related methods
804 *
805 * @param hash hash for key
806 * @param key the key
807 * @param value the value to match if matchValue, else ignored
808 * @param matchValue if true only remove if value is equal
809 * @param movable if false do not move other nodes while removing
810 * @return the node, or null if none
811 */
812 final Node<K,V> removeNode(int hash, Object key, Object value,
813 boolean matchValue, boolean movable) {
814 Node<K,V>[] tab; Node<K,V> p; int n, index;
848 }
849 }
850 return null;
851 }
852
853 /**
854 * Removes all of the mappings from this map.
855 * The map will be empty after this call returns.
856 */
857 public void clear() {
858 Node<K,V>[] tab;
859 modCount++;
860 if ((tab = table) != null && size > 0) {
861 size = 0;
862 for (int i = 0; i < tab.length; ++i)
863 tab[i] = null;
864 }
865 }
866
867 /**
868 * Returns {@code true} if this map maps one or more keys to the
869 * specified value.
870 *
871 * @param value value whose presence in this map is to be tested
872 * @return {@code true} if this map maps one or more keys to the
873 * specified value
874 */
875 public boolean containsValue(Object value) {
876 Node<K,V>[] tab; V v;
877 if ((tab = table) != null && size > 0) {
878 for (Node<K, V> e : tab) {
879 for (; e != null; e = e.next) {
880 if ((v = e.value) == value ||
881 (value != null && value.equals(v)))
882 return true;
883 }
884 }
885 }
886 return false;
887 }
888
889 /**
890 * Returns a {@link Set} view of the keys contained in this map.
891 * The set is backed by the map, so changes to the map are
892 * reflected in the set, and vice-versa. If the map is modified
893 * while an iteration over the set is in progress (except through
894 * the iterator's own {@code remove} operation), the results of
895 * the iteration are undefined. The set supports element removal,
896 * which removes the corresponding mapping from the map, via the
897 * {@code Iterator.remove}, {@code Set.remove},
898 * {@code removeAll}, {@code retainAll}, and {@code clear}
899 * operations. It does not support the {@code add} or {@code addAll}
900 * operations.
901 *
902 * @return a set view of the keys contained in this map
903 */
904 public Set<K> keySet() {
905 Set<K> ks;
906 return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
907 }
908
909 final class KeySet extends AbstractSet<K> {
910 public final int size() { return size; }
911 public final void clear() { HashMap.this.clear(); }
912 public final Iterator<K> iterator() { return new KeyIterator(); }
913 public final boolean contains(Object o) { return containsKey(o); }
914 public final boolean remove(Object key) {
915 return removeNode(hash(key), key, null, false, true) != null;
916 }
917 public final Spliterator<K> spliterator() {
918 return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
919 }
921 Node<K,V>[] tab;
922 if (action == null)
923 throw new NullPointerException();
924 if (size > 0 && (tab = table) != null) {
925 int mc = modCount;
926 for (Node<K, V> e : tab) {
927 for (; e != null; e = e.next)
928 action.accept(e.key);
929 }
930 if (modCount != mc)
931 throw new ConcurrentModificationException();
932 }
933 }
934 }
935
936 /**
937 * Returns a {@link Collection} view of the values contained in this map.
938 * The collection is backed by the map, so changes to the map are
939 * reflected in the collection, and vice-versa. If the map is
940 * modified while an iteration over the collection is in progress
941 * (except through the iterator's own {@code remove} operation),
942 * the results of the iteration are undefined. The collection
943 * supports element removal, which removes the corresponding
944 * mapping from the map, via the {@code Iterator.remove},
945 * {@code Collection.remove}, {@code removeAll},
946 * {@code retainAll} and {@code clear} operations. It does not
947 * support the {@code add} or {@code addAll} operations.
948 *
949 * @return a view of the values contained in this map
950 */
951 public Collection<V> values() {
952 Collection<V> vs;
953 return (vs = values) == null ? (values = new Values()) : vs;
954 }
955
956 final class Values extends AbstractCollection<V> {
957 public final int size() { return size; }
958 public final void clear() { HashMap.this.clear(); }
959 public final Iterator<V> iterator() { return new ValueIterator(); }
960 public final boolean contains(Object o) { return containsValue(o); }
961 public final Spliterator<V> spliterator() {
962 return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
963 }
964 public final void forEach(Consumer<? super V> action) {
965 Node<K,V>[] tab;
966 if (action == null)
967 throw new NullPointerException();
968 if (size > 0 && (tab = table) != null) {
969 int mc = modCount;
970 for (Node<K, V> e : tab) {
971 for (; e != null; e = e.next)
972 action.accept(e.value);
973 }
974 if (modCount != mc)
975 throw new ConcurrentModificationException();
976 }
977 }
978 }
979
980 /**
981 * Returns a {@link Set} view of the mappings contained in this map.
982 * The set is backed by the map, so changes to the map are
983 * reflected in the set, and vice-versa. If the map is modified
984 * while an iteration over the set is in progress (except through
985 * the iterator's own {@code remove} operation, or through the
986 * {@code setValue} operation on a map entry returned by the
987 * iterator) the results of the iteration are undefined. The set
988 * supports element removal, which removes the corresponding
989 * mapping from the map, via the {@code Iterator.remove},
990 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
991 * {@code clear} operations. It does not support the
992 * {@code add} or {@code addAll} operations.
993 *
994 * @return a set view of the mappings contained in this map
995 */
996 public Set<Map.Entry<K,V>> entrySet() {
997 Set<Map.Entry<K,V>> es;
998 return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
999 }
1000
1001 final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1002 public final int size() { return size; }
1003 public final void clear() { HashMap.this.clear(); }
1004 public final Iterator<Map.Entry<K,V>> iterator() {
1005 return new EntryIterator();
1006 }
1007 public final boolean contains(Object o) {
1008 if (!(o instanceof Map.Entry))
1009 return false;
1010 Map.Entry<?,?> e = (Map.Entry<?,?>) o;
1011 Object key = e.getKey();
1012 Node<K,V> candidate = getNode(hash(key), key);
1340 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1341 Node<K,V>[] tab;
1342 if (function == null)
1343 throw new NullPointerException();
1344 if (size > 0 && (tab = table) != null) {
1345 int mc = modCount;
1346 for (Node<K, V> e : tab) {
1347 for (; e != null; e = e.next) {
1348 e.value = function.apply(e.key, e.value);
1349 }
1350 }
1351 if (modCount != mc)
1352 throw new ConcurrentModificationException();
1353 }
1354 }
1355
1356 /* ------------------------------------------------------------ */
1357 // Cloning and serialization
1358
1359 /**
1360 * Returns a shallow copy of this {@code HashMap} instance: the keys and
1361 * values themselves are not cloned.
1362 *
1363 * @return a shallow copy of this map
1364 */
1365 @SuppressWarnings("unchecked")
1366 @Override
1367 public Object clone() {
1368 HashMap<K,V> result;
1369 try {
1370 result = (HashMap<K,V>)super.clone();
1371 } catch (CloneNotSupportedException e) {
1372 // this shouldn't happen, since we are Cloneable
1373 throw new InternalError(e);
1374 }
1375 result.reinitialize();
1376 result.putMapEntries(this, false);
1377 return result;
1378 }
1379
1380 // These methods are also used when serializing HashSets
1381 final float loadFactor() { return loadFactor; }
1382 final int capacity() {
1383 return (table != null) ? table.length :
1384 (threshold > 0) ? threshold :
1385 DEFAULT_INITIAL_CAPACITY;
1386 }
1387
1388 /**
1389 * Save the state of the {@code HashMap} instance to a stream (i.e.,
1390 * serialize it).
1391 *
1392 * @serialData The <i>capacity</i> of the HashMap (the length of the
1393 * bucket array) is emitted (int), followed by the
1394 * <i>size</i> (an int, the number of key-value
1395 * mappings), followed by the key (Object) and value (Object)
1396 * for each key-value mapping. The key-value mappings are
1397 * emitted in no particular order.
1398 */
1399 private void writeObject(java.io.ObjectOutputStream s)
1400 throws IOException {
1401 int buckets = capacity();
1402 // Write out the threshold, loadfactor, and any hidden stuff
1403 s.defaultWriteObject();
1404 s.writeInt(buckets);
1405 s.writeInt(size);
1406 internalWriteEntries(s);
1407 }
1408
1409 /**
|