1 /*

     2  * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package java.util;

    27 

    28 import java.util.function.BiConsumer;

    29 import java.util.function.BiFunction;

    30 import java.util.function.Function;

    31 import java.io.Serializable;

    32 

    33 /**

    34  * An object that maps keys to values.  A map cannot contain duplicate keys;

    35  * each key can map to at most one value.

    36  *

    37  * <p>This interface takes the place of the {@code Dictionary} class, which

    38  * was a totally abstract class rather than an interface.

    39  *

    40  * <p>The {@code Map} interface provides three <i>collection views</i>, which

    41  * allow a map's contents to be viewed as a set of keys, collection of values,

    42  * or set of key-value mappings.  The <i>order</i> of a map is defined as

    43  * the order in which the iterators on the map's collection views return their

    44  * elements.  Some map implementations, like the {@code TreeMap} class, make

    45  * specific guarantees as to their order; others, like the {@code HashMap}

    46  * class, do not.

    47  *

    48  * <p>Note: great care must be exercised if mutable objects are used as map

    49  * keys.  The behavior of a map is not specified if the value of an object is

    50  * changed in a manner that affects {@code equals} comparisons while the

    51  * object is a key in the map.  A special case of this prohibition is that it

    52  * is not permissible for a map to contain itself as a key.  While it is

    53  * permissible for a map to contain itself as a value, extreme caution is

    54  * advised: the {@code equals} and {@code hashCode} methods are no longer

    55  * well defined on such a map.

    56  *

    57  * <p>All general-purpose map implementation classes should provide two

    58  * "standard" constructors: a void (no arguments) constructor which creates an

    59  * empty map, and a constructor with a single argument of type {@code Map},

    60  * which creates a new map with the same key-value mappings as its argument.

    61  * In effect, the latter constructor allows the user to copy any map,

    62  * producing an equivalent map of the desired class.  There is no way to

    63  * enforce this recommendation (as interfaces cannot contain constructors) but

    64  * all of the general-purpose map implementations in the JDK comply.

    65  *

    66  * <p>The "destructive" methods contained in this interface, that is, the

    67  * methods that modify the map on which they operate, are specified to throw

    68  * {@code UnsupportedOperationException} if this map does not support the

    69  * operation.  If this is the case, these methods may, but are not required

    70  * to, throw an {@code UnsupportedOperationException} if the invocation would

    71  * have no effect on the map.  For example, invoking the {@link #putAll(Map)}

    72  * method on an unmodifiable map may, but is not required to, throw the

    73  * exception if the map whose mappings are to be "superimposed" is empty.

    74  *

    75  * <p>Some map implementations have restrictions on the keys and values they

    76  * may contain.  For example, some implementations prohibit null keys and

    77  * values, and some have restrictions on the types of their keys.  Attempting

    78  * to insert an ineligible key or value throws an unchecked exception,

    79  * typically {@code NullPointerException} or {@code ClassCastException}.

    80  * Attempting to query the presence of an ineligible key or value may throw an

    81  * exception, or it may simply return false; some implementations will exhibit

    82  * the former behavior and some will exhibit the latter.  More generally,

    83  * attempting an operation on an ineligible key or value whose completion

    84  * would not result in the insertion of an ineligible element into the map may

    85  * throw an exception or it may succeed, at the option of the implementation.

    86  * Such exceptions are marked as "optional" in the specification for this

    87  * interface.

    88  *

    89  * <p>Many methods in Collections Framework interfaces are defined

    90  * in terms of the {@link Object#equals(Object) equals} method.  For

    91  * example, the specification for the {@link #containsKey(Object)

    92  * containsKey(Object key)} method says: "returns {@code true} if and

    93  * only if this map contains a mapping for a key {@code k} such that

    94  * {@code (key==null ? k==null : key.equals(k))}." This specification should

    95  * <i>not</i> be construed to imply that invoking {@code Map.containsKey}

    96  * with a non-null argument {@code key} will cause {@code key.equals(k)} to

    97  * be invoked for any key {@code k}.  Implementations are free to

    98  * implement optimizations whereby the {@code equals} invocation is avoided,

    99  * for example, by first comparing the hash codes of the two keys.  (The

   100  * {@link Object#hashCode()} specification guarantees that two objects with

   101  * unequal hash codes cannot be equal.)  More generally, implementations of

   102  * the various Collections Framework interfaces are free to take advantage of

   103  * the specified behavior of underlying {@link Object} methods wherever the

   104  * implementor deems it appropriate.

   105  *

   106  * <p>Some map operations which perform recursive traversal of the map may fail

   107  * with an exception for self-referential instances where the map directly or

   108  * indirectly contains itself. This includes the {@code clone()},

   109  * {@code equals()}, {@code hashCode()} and {@code toString()} methods.

   110  * Implementations may optionally handle the self-referential scenario, however

   111  * most current implementations do not do so.

   112  *

   113  * <h2><a id="immutable">Immutable Map Static Factory Methods</a></h2>

   114  * <p>The {@link Map#of() Map.of()} and

   115  * {@link Map#ofEntries(Map.Entry...) Map.ofEntries()}

   116  * static factory methods provide a convenient way to create immutable maps.

   117  * The {@code Map}

   118  * instances created by these methods have the following characteristics:

   119  *

   120  * <ul>

   121  * <li>They are <em>structurally immutable</em>. Keys and values cannot be added,

   122  * removed, or updated. Calling any mutator method will always cause

   123  * {@code UnsupportedOperationException} to be thrown.

   124  * However, if the contained keys or values are themselves mutable, this may cause the

   125  * Map to behave inconsistently or its contents to appear to change.

   126  * <li>They disallow {@code null} keys and values. Attempts to create them with

   127  * {@code null} keys or values result in {@code NullPointerException}.

   128  * <li>They are serializable if all keys and values are serializable.

   129  * <li>They reject duplicate keys at creation time. Duplicate keys

   130  * passed to a static factory method result in {@code IllegalArgumentException}.

   131  * <li>The iteration order of mappings is unspecified and is subject to change.

   132  * <li>They are <a href="../lang/doc-files/ValueBased.html">value-based</a>.

   133  * Callers should make no assumptions about the identity of the returned instances.

   134  * Factories are free to create new instances or reuse existing ones. Therefore,

   135  * identity-sensitive operations on these instances (reference equality ({@code ==}),

   136  * identity hash code, and synchronization) are unreliable and should be avoided.

   137  * <li>They are serialized as specified on the

   138  * <a href="{@docRoot}/serialized-form.html#java.util.CollSer">Serialized Form</a>

   139  * page.

   140  * </ul>

   141  *

   142  * <p>This interface is a member of the

   143  * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">

   144  * Java Collections Framework</a>.

   145  *

   146  * @param <K> the type of keys maintained by this map

   147  * @param <V> the type of mapped values

   148  *

   149  * @author  Josh Bloch

   150  * @see HashMap

   151  * @see TreeMap

   152  * @see Hashtable

   153  * @see SortedMap

   154  * @see Collection

   155  * @see Set

   156  * @since 1.2

   157  */

   158 public interface Map<K, V> {

   159     // Query Operations

   160 

   161     /**

   162      * Returns the number of key-value mappings in this map.  If the

   163      * map contains more than {@code Integer.MAX_VALUE} elements, returns

   164      * {@code Integer.MAX_VALUE}.

   165      *

   166      * @return the number of key-value mappings in this map

   167      */

   168     int size();

   169 

   170     /**

   171      * Returns {@code true} if this map contains no key-value mappings.

   172      *

   173      * @return {@code true} if this map contains no key-value mappings

   174      */

   175     boolean isEmpty();

   176 

   177     /**

   178      * Returns {@code true} if this map contains a mapping for the specified

   179      * key.  More formally, returns {@code true} if and only if

   180      * this map contains a mapping for a key {@code k} such that

   181      * {@code Objects.equals(key, k)}.  (There can be

   182      * at most one such mapping.)

   183      *

   184      * @param key key whose presence in this map is to be tested

   185      * @return {@code true} if this map contains a mapping for the specified

   186      *         key

   187      * @throws ClassCastException if the key is of an inappropriate type for

   188      *         this map

   189      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   190      * @throws NullPointerException if the specified key is null and this map

   191      *         does not permit null keys

   192      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   193      */

   194     boolean containsKey(Object key);

   195 

   196     /**

   197      * Returns {@code true} if this map maps one or more keys to the

   198      * specified value.  More formally, returns {@code true} if and only if

   199      * this map contains at least one mapping to a value {@code v} such that

   200      * {@code Objects.equals(value, v)}.  This operation

   201      * will probably require time linear in the map size for most

   202      * implementations of the {@code Map} interface.

   203      *

   204      * @param value value whose presence in this map is to be tested

   205      * @return {@code true} if this map maps one or more keys to the

   206      *         specified value

   207      * @throws ClassCastException if the value is of an inappropriate type for

   208      *         this map

   209      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   210      * @throws NullPointerException if the specified value is null and this

   211      *         map does not permit null values

   212      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   213      */

   214     boolean containsValue(Object value);

   215 

   216     /**

   217      * Returns the value to which the specified key is mapped,

   218      * or {@code null} if this map contains no mapping for the key.

   219      *

   220      * <p>More formally, if this map contains a mapping from a key

   221      * {@code k} to a value {@code v} such that

   222      * {@code Objects.equals(key, k)},

   223      * then this method returns {@code v}; otherwise

   224      * it returns {@code null}.  (There can be at most one such mapping.)

   225      *

   226      * <p>If this map permits null values, then a return value of

   227      * {@code null} does not <i>necessarily</i> indicate that the map

   228      * contains no mapping for the key; it's also possible that the map

   229      * explicitly maps the key to {@code null}.  The {@link #containsKey

   230      * containsKey} operation may be used to distinguish these two cases.

   231      *

   232      * @param key the key whose associated value is to be returned

   233      * @return the value to which the specified key is mapped, or

   234      *         {@code null} if this map contains no mapping for the key

   235      * @throws ClassCastException if the key is of an inappropriate type for

   236      *         this map

   237      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   238      * @throws NullPointerException if the specified key is null and this map

   239      *         does not permit null keys

   240      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   241      */

   242     V get(Object key);

   243 

   244     // Modification Operations

   245 

   246     /**

   247      * Associates the specified value with the specified key in this map

   248      * (optional operation).  If the map previously contained a mapping for

   249      * the key, the old value is replaced by the specified value.  (A map

   250      * {@code m} is said to contain a mapping for a key {@code k} if and only

   251      * if {@link #containsKey(Object) m.containsKey(k)} would return

   252      * {@code true}.)

   253      *

   254      * @param key key with which the specified value is to be associated

   255      * @param value value to be associated with the specified key

   256      * @return the previous value associated with {@code key}, or

   257      *         {@code null} if there was no mapping for {@code key}.

   258      *         (A {@code null} return can also indicate that the map

   259      *         previously associated {@code null} with {@code key},

   260      *         if the implementation supports {@code null} values.)

   261      * @throws UnsupportedOperationException if the {@code put} operation

   262      *         is not supported by this map

   263      * @throws ClassCastException if the class of the specified key or value

   264      *         prevents it from being stored in this map

   265      * @throws NullPointerException if the specified key or value is null

   266      *         and this map does not permit null keys or values

   267      * @throws IllegalArgumentException if some property of the specified key

   268      *         or value prevents it from being stored in this map

   269      */

   270     V put(K key, V value);

   271 

   272     /**

   273      * Removes the mapping for a key from this map if it is present

   274      * (optional operation).   More formally, if this map contains a mapping

   275      * from key {@code k} to value {@code v} such that

   276      * {@code Objects.equals(key, k)}, that mapping

   277      * is removed.  (The map can contain at most one such mapping.)

   278      *

   279      * <p>Returns the value to which this map previously associated the key,

   280      * or {@code null} if the map contained no mapping for the key.

   281      *

   282      * <p>If this map permits null values, then a return value of

   283      * {@code null} does not <i>necessarily</i> indicate that the map

   284      * contained no mapping for the key; it's also possible that the map

   285      * explicitly mapped the key to {@code null}.

   286      *

   287      * <p>The map will not contain a mapping for the specified key once the

   288      * call returns.

   289      *

   290      * @param key key whose mapping is to be removed from the map

   291      * @return the previous value associated with {@code key}, or

   292      *         {@code null} if there was no mapping for {@code key}.

   293      * @throws UnsupportedOperationException if the {@code remove} operation

   294      *         is not supported by this map

   295      * @throws ClassCastException if the key is of an inappropriate type for

   296      *         this map

   297      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   298      * @throws NullPointerException if the specified key is null and this

   299      *         map does not permit null keys

   300      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   301      */

   302     V remove(Object key);

   303 

   304 

   305     // Bulk Operations

   306 

   307     /**

   308      * Copies all of the mappings from the specified map to this map

   309      * (optional operation).  The effect of this call is equivalent to that

   310      * of calling {@link #put(Object,Object) put(k, v)} on this map once

   311      * for each mapping from key {@code k} to value {@code v} in the

   312      * specified map.  The behavior of this operation is undefined if the

   313      * specified map is modified while the operation is in progress.

   314      *

   315      * @param m mappings to be stored in this map

   316      * @throws UnsupportedOperationException if the {@code putAll} operation

   317      *         is not supported by this map

   318      * @throws ClassCastException if the class of a key or value in the

   319      *         specified map prevents it from being stored in this map

   320      * @throws NullPointerException if the specified map is null, or if

   321      *         this map does not permit null keys or values, and the

   322      *         specified map contains null keys or values

   323      * @throws IllegalArgumentException if some property of a key or value in

   324      *         the specified map prevents it from being stored in this map

   325      */

   326     void putAll(Map<? extends K, ? extends V> m);

   327 

   328     /**

   329      * Removes all of the mappings from this map (optional operation).

   330      * The map will be empty after this call returns.

   331      *

   332      * @throws UnsupportedOperationException if the {@code clear} operation

   333      *         is not supported by this map

   334      */

   335     void clear();

   336 

   337 

   338     // Views

   339 

   340     /**

   341      * Returns a {@link Set} view of the keys contained in this map.

   342      * The set is backed by the map, so changes to the map are

   343      * reflected in the set, and vice-versa.  If the map is modified

   344      * while an iteration over the set is in progress (except through

   345      * the iterator's own {@code remove} operation), the results of

   346      * the iteration are undefined.  The set supports element removal,

   347      * which removes the corresponding mapping from the map, via the

   348      * {@code Iterator.remove}, {@code Set.remove},

   349      * {@code removeAll}, {@code retainAll}, and {@code clear}

   350      * operations.  It does not support the {@code add} or {@code addAll}

   351      * operations.

   352      *

   353      * @return a set view of the keys contained in this map

   354      */

   355     Set<K> keySet();

   356 

   357     /**

   358      * Returns a {@link Collection} view of the values contained in this map.

   359      * The collection is backed by the map, so changes to the map are

   360      * reflected in the collection, and vice-versa.  If the map is

   361      * modified while an iteration over the collection is in progress

   362      * (except through the iterator's own {@code remove} operation),

   363      * the results of the iteration are undefined.  The collection

   364      * supports element removal, which removes the corresponding

   365      * mapping from the map, via the {@code Iterator.remove},

   366      * {@code Collection.remove}, {@code removeAll},

   367      * {@code retainAll} and {@code clear} operations.  It does not

   368      * support the {@code add} or {@code addAll} operations.

   369      *

   370      * @return a collection view of the values contained in this map

   371      */

   372     Collection<V> values();

   373 

   374     /**

   375      * Returns a {@link Set} view of the mappings contained in this map.

   376      * The set is backed by the map, so changes to the map are

   377      * reflected in the set, and vice-versa.  If the map is modified

   378      * while an iteration over the set is in progress (except through

   379      * the iterator's own {@code remove} operation, or through the

   380      * {@code setValue} operation on a map entry returned by the

   381      * iterator) the results of the iteration are undefined.  The set

   382      * supports element removal, which removes the corresponding

   383      * mapping from the map, via the {@code Iterator.remove},

   384      * {@code Set.remove}, {@code removeAll}, {@code retainAll} and

   385      * {@code clear} operations.  It does not support the

   386      * {@code add} or {@code addAll} operations.

   387      *

   388      * @return a set view of the mappings contained in this map

   389      */

   390     Set<Map.Entry<K, V>> entrySet();

   391 

   392     /**

   393      * A map entry (key-value pair).  The {@code Map.entrySet} method returns

   394      * a collection-view of the map, whose elements are of this class.  The

   395      * <i>only</i> way to obtain a reference to a map entry is from the

   396      * iterator of this collection-view.  These {@code Map.Entry} objects are

   397      * valid <i>only</i> for the duration of the iteration; more formally,

   398      * the behavior of a map entry is undefined if the backing map has been

   399      * modified after the entry was returned by the iterator, except through

   400      * the {@code setValue} operation on the map entry.

   401      *

   402      * @see Map#entrySet()

   403      * @since 1.2

   404      */

   405     interface Entry<K, V> {

   406         /**

   407          * Returns the key corresponding to this entry.

   408          *

   409          * @return the key corresponding to this entry

   410          * @throws IllegalStateException implementations may, but are not

   411          *         required to, throw this exception if the entry has been

   412          *         removed from the backing map.

   413          */

   414         K getKey();

   415 

   416         /**

   417          * Returns the value corresponding to this entry.  If the mapping

   418          * has been removed from the backing map (by the iterator's

   419          * {@code remove} operation), the results of this call are undefined.

   420          *

   421          * @return the value corresponding to this entry

   422          * @throws IllegalStateException implementations may, but are not

   423          *         required to, throw this exception if the entry has been

   424          *         removed from the backing map.

   425          */

   426         V getValue();

   427 

   428         /**

   429          * Replaces the value corresponding to this entry with the specified

   430          * value (optional operation).  (Writes through to the map.)  The

   431          * behavior of this call is undefined if the mapping has already been

   432          * removed from the map (by the iterator's {@code remove} operation).

   433          *

   434          * @param value new value to be stored in this entry

   435          * @return old value corresponding to the entry

   436          * @throws UnsupportedOperationException if the {@code put} operation

   437          *         is not supported by the backing map

   438          * @throws ClassCastException if the class of the specified value

   439          *         prevents it from being stored in the backing map

   440          * @throws NullPointerException if the backing map does not permit

   441          *         null values, and the specified value is null

   442          * @throws IllegalArgumentException if some property of this value

   443          *         prevents it from being stored in the backing map

   444          * @throws IllegalStateException implementations may, but are not

   445          *         required to, throw this exception if the entry has been

   446          *         removed from the backing map.

   447          */

   448         V setValue(V value);

   449 

   450         /**

   451          * Compares the specified object with this entry for equality.

   452          * Returns {@code true} if the given object is also a map entry and

   453          * the two entries represent the same mapping.  More formally, two

   454          * entries {@code e1} and {@code e2} represent the same mapping

   455          * if<pre>

   456          *     (e1.getKey()==null ?

   457          *      e2.getKey()==null : e1.getKey().equals(e2.getKey()))  &&

   458          *     (e1.getValue()==null ?

   459          *      e2.getValue()==null : e1.getValue().equals(e2.getValue()))

   460          * </pre>

   461          * This ensures that the {@code equals} method works properly across

   462          * different implementations of the {@code Map.Entry} interface.

   463          *

   464          * @param o object to be compared for equality with this map entry

   465          * @return {@code true} if the specified object is equal to this map

   466          *         entry

   467          */

   468         boolean equals(Object o);

   469 

   470         /**

   471          * Returns the hash code value for this map entry.  The hash code

   472          * of a map entry {@code e} is defined to be: <pre>

   473          *     (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^

   474          *     (e.getValue()==null ? 0 : e.getValue().hashCode())

   475          * </pre>

   476          * This ensures that {@code e1.equals(e2)} implies that

   477          * {@code e1.hashCode()==e2.hashCode()} for any two Entries

   478          * {@code e1} and {@code e2}, as required by the general

   479          * contract of {@code Object.hashCode}.

   480          *

   481          * @return the hash code value for this map entry

   482          * @see Object#hashCode()

   483          * @see Object#equals(Object)

   484          * @see #equals(Object)

   485          */

   486         int hashCode();

   487 

   488         /**

   489          * Returns a comparator that compares {@link Map.Entry} in natural order on key.

   490          *

   491          * <p>The returned comparator is serializable and throws {@link

   492          * NullPointerException} when comparing an entry with a null key.

   493          *

   494          * @param  <K> the {@link Comparable} type of then map keys

   495          * @param  <V> the type of the map values

   496          * @return a comparator that compares {@link Map.Entry} in natural order on key.

   497          * @see Comparable

   498          * @since 1.8

   499          */

   500         public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {

   501             return (Comparator<Map.Entry<K, V>> & Serializable)

   502                 (c1, c2) -> c1.getKey().compareTo(c2.getKey());

   503         }

   504 

   505         /**

   506          * Returns a comparator that compares {@link Map.Entry} in natural order on value.

   507          *

   508          * <p>The returned comparator is serializable and throws {@link

   509          * NullPointerException} when comparing an entry with null values.

   510          *

   511          * @param <K> the type of the map keys

   512          * @param <V> the {@link Comparable} type of the map values

   513          * @return a comparator that compares {@link Map.Entry} in natural order on value.

   514          * @see Comparable

   515          * @since 1.8

   516          */

   517         public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {

   518             return (Comparator<Map.Entry<K, V>> & Serializable)

   519                 (c1, c2) -> c1.getValue().compareTo(c2.getValue());

   520         }

   521 

   522         /**

   523          * Returns a comparator that compares {@link Map.Entry} by key using the given

   524          * {@link Comparator}.

   525          *

   526          * <p>The returned comparator is serializable if the specified comparator

   527          * is also serializable.

   528          *

   529          * @param  <K> the type of the map keys

   530          * @param  <V> the type of the map values

   531          * @param  cmp the key {@link Comparator}

   532          * @return a comparator that compares {@link Map.Entry} by the key.

   533          * @since 1.8

   534          */

   535         public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {

   536             Objects.requireNonNull(cmp);

   537             return (Comparator<Map.Entry<K, V>> & Serializable)

   538                 (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());

   539         }

   540 

   541         /**

   542          * Returns a comparator that compares {@link Map.Entry} by value using the given

   543          * {@link Comparator}.

   544          *

   545          * <p>The returned comparator is serializable if the specified comparator

   546          * is also serializable.

   547          *

   548          * @param  <K> the type of the map keys

   549          * @param  <V> the type of the map values

   550          * @param  cmp the value {@link Comparator}

   551          * @return a comparator that compares {@link Map.Entry} by the value.

   552          * @since 1.8

   553          */

   554         public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {

   555             Objects.requireNonNull(cmp);

   556             return (Comparator<Map.Entry<K, V>> & Serializable)

   557                 (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());

   558         }

   559     }

   560 

   561     // Comparison and hashing

   562 

   563     /**

   564      * Compares the specified object with this map for equality.  Returns

   565      * {@code true} if the given object is also a map and the two maps

   566      * represent the same mappings.  More formally, two maps {@code m1} and

   567      * {@code m2} represent the same mappings if

   568      * {@code m1.entrySet().equals(m2.entrySet())}.  This ensures that the

   569      * {@code equals} method works properly across different implementations

   570      * of the {@code Map} interface.

   571      *

   572      * @param o object to be compared for equality with this map

   573      * @return {@code true} if the specified object is equal to this map

   574      */

   575     boolean equals(Object o);

   576 

   577     /**

   578      * Returns the hash code value for this map.  The hash code of a map is

   579      * defined to be the sum of the hash codes of each entry in the map's

   580      * {@code entrySet()} view.  This ensures that {@code m1.equals(m2)}

   581      * implies that {@code m1.hashCode()==m2.hashCode()} for any two maps

   582      * {@code m1} and {@code m2}, as required by the general contract of

   583      * {@link Object#hashCode}.

   584      *

   585      * @return the hash code value for this map

   586      * @see Map.Entry#hashCode()

   587      * @see Object#equals(Object)

   588      * @see #equals(Object)

   589      */

   590     int hashCode();

   591 

   592     // Defaultable methods

   593 

   594     /**

   595      * Returns the value to which the specified key is mapped, or

   596      * {@code defaultValue} if this map contains no mapping for the key.

   597      *

   598      * @implSpec

   599      * The default implementation makes no guarantees about synchronization

   600      * or atomicity properties of this method. Any implementation providing

   601      * atomicity guarantees must override this method and document its

   602      * concurrency properties.

   603      *

   604      * @param key the key whose associated value is to be returned

   605      * @param defaultValue the default mapping of the key

   606      * @return the value to which the specified key is mapped, or

   607      * {@code defaultValue} if this map contains no mapping for the key

   608      * @throws ClassCastException if the key is of an inappropriate type for

   609      * this map

   610      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   611      * @throws NullPointerException if the specified key is null and this map

   612      * does not permit null keys

   613      * (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   614      * @since 1.8

   615      */

   616     default V getOrDefault(Object key, V defaultValue) {

   617         V v;

   618         return (((v = get(key)) != null) || containsKey(key))

   619             ? v

   620             : defaultValue;

   621     }

   622 

   623     /**

   624      * Performs the given action for each entry in this map until all entries

   625      * have been processed or the action throws an exception.   Unless

   626      * otherwise specified by the implementing class, actions are performed in

   627      * the order of entry set iteration (if an iteration order is specified.)

   628      * Exceptions thrown by the action are relayed to the caller.

   629      *

   630      * @implSpec

   631      * The default implementation is equivalent to, for this {@code map}:

   632      * <pre> {@code

   633      * for (Map.Entry<K, V> entry : map.entrySet())

   634      *     action.accept(entry.getKey(), entry.getValue());

   635      * }</pre>

   636      *

   637      * The default implementation makes no guarantees about synchronization

   638      * or atomicity properties of this method. Any implementation providing

   639      * atomicity guarantees must override this method and document its

   640      * concurrency properties.

   641      *

   642      * @param action The action to be performed for each entry

   643      * @throws NullPointerException if the specified action is null

   644      * @throws ConcurrentModificationException if an entry is found to be

   645      * removed during iteration

   646      * @since 1.8

   647      */

   648     default void forEach(BiConsumer<? super K, ? super V> action) {

   649         Objects.requireNonNull(action);

   650         for (Map.Entry<K, V> entry : entrySet()) {

   651             K k;

   652             V v;

   653             try {

   654                 k = entry.getKey();

   655                 v = entry.getValue();

   656             } catch (IllegalStateException ise) {

   657                 // this usually means the entry is no longer in the map.

   658                 throw new ConcurrentModificationException(ise);

   659             }

   660             action.accept(k, v);

   661         }

   662     }

   663 

   664     /**

   665      * Replaces each entry's value with the result of invoking the given

   666      * function on that entry until all entries have been processed or the

   667      * function throws an exception.  Exceptions thrown by the function are

   668      * relayed to the caller.

   669      *

   670      * @implSpec

   671      * <p>The default implementation is equivalent to, for this {@code map}:

   672      * <pre> {@code

   673      * for (Map.Entry<K, V> entry : map.entrySet())

   674      *     entry.setValue(function.apply(entry.getKey(), entry.getValue()));

   675      * }</pre>

   676      *

   677      * <p>The default implementation makes no guarantees about synchronization

   678      * or atomicity properties of this method. Any implementation providing

   679      * atomicity guarantees must override this method and document its

   680      * concurrency properties.

   681      *

   682      * @param function the function to apply to each entry

   683      * @throws UnsupportedOperationException if the {@code set} operation

   684      * is not supported by this map's entry set iterator.

   685      * @throws ClassCastException if the class of a replacement value

   686      * prevents it from being stored in this map

   687      * @throws NullPointerException if the specified function is null, or the

   688      * specified replacement value is null, and this map does not permit null

   689      * values

   690      * @throws ClassCastException if a replacement value is of an inappropriate

   691      *         type for this map

   692      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   693      * @throws NullPointerException if function or a replacement value is null,

   694      *         and this map does not permit null keys or values

   695      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   696      * @throws IllegalArgumentException if some property of a replacement value

   697      *         prevents it from being stored in this map

   698      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   699      * @throws ConcurrentModificationException if an entry is found to be

   700      * removed during iteration

   701      * @since 1.8

   702      */

   703     default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {

   704         Objects.requireNonNull(function);

   705         for (Map.Entry<K, V> entry : entrySet()) {

   706             K k;

   707             V v;

   708             try {

   709                 k = entry.getKey();

   710                 v = entry.getValue();

   711             } catch (IllegalStateException ise) {

   712                 // this usually means the entry is no longer in the map.

   713                 throw new ConcurrentModificationException(ise);

   714             }

   715 

   716             // ise thrown from function is not a cme.

   717             v = function.apply(k, v);

   718 

   719             try {

   720                 entry.setValue(v);

   721             } catch (IllegalStateException ise) {

   722                 // this usually means the entry is no longer in the map.

   723                 throw new ConcurrentModificationException(ise);

   724             }

   725         }

   726     }

   727 

   728     /**

   729      * If the specified key is not already associated with a value (or is mapped

   730      * to {@code null}) associates it with the given value and returns

   731      * {@code null}, else returns the current value.

   732      *

   733      * @implSpec

   734      * The default implementation is equivalent to, for this {@code

   735      * map}:

   736      *

   737      * <pre> {@code

   738      * V v = map.get(key);

   739      * if (v == null)

   740      *     v = map.put(key, value);

   741      *

   742      * return v;

   743      * }</pre>

   744      *

   745      * <p>The default implementation makes no guarantees about synchronization

   746      * or atomicity properties of this method. Any implementation providing

   747      * atomicity guarantees must override this method and document its

   748      * concurrency properties.

   749      *

   750      * @param key key with which the specified value is to be associated

   751      * @param value value to be associated with the specified key

   752      * @return the previous value associated with the specified key, or

   753      *         {@code null} if there was no mapping for the key.

   754      *         (A {@code null} return can also indicate that the map

   755      *         previously associated {@code null} with the key,

   756      *         if the implementation supports null values.)

   757      * @throws UnsupportedOperationException if the {@code put} operation

   758      *         is not supported by this map

   759      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   760      * @throws ClassCastException if the key or value is of an inappropriate

   761      *         type for this map

   762      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   763      * @throws NullPointerException if the specified key or value is null,

   764      *         and this map does not permit null keys or values

   765      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   766      * @throws IllegalArgumentException if some property of the specified key

   767      *         or value prevents it from being stored in this map

   768      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   769      * @since 1.8

   770      */

   771     default V putIfAbsent(K key, V value) {

   772         V v = get(key);

   773         if (v == null) {

   774             v = put(key, value);

   775         }

   776 

   777         return v;

   778     }

   779 

   780     /**

   781      * Removes the entry for the specified key only if it is currently

   782      * mapped to the specified value.

   783      *

   784      * @implSpec

   785      * The default implementation is equivalent to, for this {@code map}:

   786      *

   787      * <pre> {@code

   788      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {

   789      *     map.remove(key);

   790      *     return true;

   791      * } else

   792      *     return false;

   793      * }</pre>

   794      *

   795      * <p>The default implementation makes no guarantees about synchronization

   796      * or atomicity properties of this method. Any implementation providing

   797      * atomicity guarantees must override this method and document its

   798      * concurrency properties.

   799      *

   800      * @param key key with which the specified value is associated

   801      * @param value value expected to be associated with the specified key

   802      * @return {@code true} if the value was removed

   803      * @throws UnsupportedOperationException if the {@code remove} operation

   804      *         is not supported by this map

   805      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   806      * @throws ClassCastException if the key or value is of an inappropriate

   807      *         type for this map

   808      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   809      * @throws NullPointerException if the specified key or value is null,

   810      *         and this map does not permit null keys or values

   811      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   812      * @since 1.8

   813      */

   814     default boolean remove(Object key, Object value) {

   815         Object curValue = get(key);

   816         if (!Objects.equals(curValue, value) ||

   817             (curValue == null && !containsKey(key))) {

   818             return false;

   819         }

   820         remove(key);

   821         return true;

   822     }

   823 

   824     /**

   825      * Replaces the entry for the specified key only if currently

   826      * mapped to the specified value.

   827      *

   828      * @implSpec

   829      * The default implementation is equivalent to, for this {@code map}:

   830      *

   831      * <pre> {@code

   832      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {

   833      *     map.put(key, newValue);

   834      *     return true;

   835      * } else

   836      *     return false;

   837      * }</pre>

   838      *

   839      * The default implementation does not throw NullPointerException

   840      * for maps that do not support null values if oldValue is null unless

   841      * newValue is also null.

   842      *

   843      * <p>The default implementation makes no guarantees about synchronization

   844      * or atomicity properties of this method. Any implementation providing

   845      * atomicity guarantees must override this method and document its

   846      * concurrency properties.

   847      *

   848      * @param key key with which the specified value is associated

   849      * @param oldValue value expected to be associated with the specified key

   850      * @param newValue value to be associated with the specified key

   851      * @return {@code true} if the value was replaced

   852      * @throws UnsupportedOperationException if the {@code put} operation

   853      *         is not supported by this map

   854      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   855      * @throws ClassCastException if the class of a specified key or value

   856      *         prevents it from being stored in this map

   857      * @throws NullPointerException if a specified key or newValue is null,

   858      *         and this map does not permit null keys or values

   859      * @throws NullPointerException if oldValue is null and this map does not

   860      *         permit null values

   861      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   862      * @throws IllegalArgumentException if some property of a specified key

   863      *         or value prevents it from being stored in this map

   864      * @since 1.8

   865      */

   866     default boolean replace(K key, V oldValue, V newValue) {

   867         Object curValue = get(key);

   868         if (!Objects.equals(curValue, oldValue) ||

   869             (curValue == null && !containsKey(key))) {

   870             return false;

   871         }

   872         put(key, newValue);

   873         return true;

   874     }

   875 

   876     /**

   877      * Replaces the entry for the specified key only if it is

   878      * currently mapped to some value.

   879      *

   880      * @implSpec

   881      * The default implementation is equivalent to, for this {@code map}:

   882      *

   883      * <pre> {@code

   884      * if (map.containsKey(key)) {

   885      *     return map.put(key, value);

   886      * } else

   887      *     return null;

   888      * }</pre>

   889      *

   890      * <p>The default implementation makes no guarantees about synchronization

   891      * or atomicity properties of this method. Any implementation providing

   892      * atomicity guarantees must override this method and document its

   893      * concurrency properties.

   894      *

   895      * @param key key with which the specified value is associated

   896      * @param value value to be associated with the specified key

   897      * @return the previous value associated with the specified key, or

   898      *         {@code null} if there was no mapping for the key.

   899      *         (A {@code null} return can also indicate that the map

   900      *         previously associated {@code null} with the key,

   901      *         if the implementation supports null values.)

   902      * @throws UnsupportedOperationException if the {@code put} operation

   903      *         is not supported by this map

   904      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   905      * @throws ClassCastException if the class of the specified key or value

   906      *         prevents it from being stored in this map

   907      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   908      * @throws NullPointerException if the specified key or value is null,

   909      *         and this map does not permit null keys or values

   910      * @throws IllegalArgumentException if some property of the specified key

   911      *         or value prevents it from being stored in this map

   912      * @since 1.8

   913      */

   914     default V replace(K key, V value) {

   915         V curValue;

   916         if (((curValue = get(key)) != null) || containsKey(key)) {

   917             curValue = put(key, value);

   918         }

   919         return curValue;

   920     }

   921 

   922     /**

   923      * If the specified key is not already associated with a value (or is mapped

   924      * to {@code null}), attempts to compute its value using the given mapping

   925      * function and enters it into this map unless {@code null}.

   926      *

   927      * <p>If the mapping function returns {@code null}, no mapping is recorded.

   928      * If the mapping function itself throws an (unchecked) exception, the

   929      * exception is rethrown, and no mapping is recorded.  The most

   930      * common usage is to construct a new object serving as an initial

   931      * mapped value or memoized result, as in:

   932      *

   933      * <pre> {@code

   934      * map.computeIfAbsent(key, k -> new Value(f(k)));

   935      * }</pre>

   936      *

   937      * <p>Or to implement a multi-value map, {@code Map<K,Collection<V>>},

   938      * supporting multiple values per key:

   939      *

   940      * <pre> {@code

   941      * map.computeIfAbsent(key, k -> new HashSet<V>()).add(v);

   942      * }</pre>

   943      *

   944      * <p>The mapping function should not modify this map during computation.

   945      *

   946      * @implSpec

   947      * The default implementation is equivalent to the following steps for this

   948      * {@code map}, then returning the current value or {@code null} if now

   949      * absent:

   950      *

   951      * <pre> {@code

   952      * if (map.get(key) == null) {

   953      *     V newValue = mappingFunction.apply(key);

   954      *     if (newValue != null)

   955      *         map.put(key, newValue);

   956      * }

   957      * }</pre>

   958      *

   959      * <p>The default implementation makes no guarantees about detecting if the

   960      * mapping function modifies this map during computation and, if

   961      * appropriate, reporting an error. Non-concurrent implementations should

   962      * override this method and, on a best-effort basis, throw a

   963      * {@code ConcurrentModificationException} if it is detected that the

   964      * mapping function modifies this map during computation. Concurrent

   965      * implementations should override this method and, on a best-effort basis,

   966      * throw an {@code IllegalStateException} if it is detected that the

   967      * mapping function modifies this map during computation and as a result

   968      * computation would never complete.

   969      *

   970      * <p>The default implementation makes no guarantees about synchronization

   971      * or atomicity properties of this method. Any implementation providing

   972      * atomicity guarantees must override this method and document its

   973      * concurrency properties. In particular, all implementations of

   974      * subinterface {@link java.util.concurrent.ConcurrentMap} must document

   975      * whether the mapping function is applied once atomically only if the value

   976      * is not present.

   977      *

   978      * @param key key with which the specified value is to be associated

   979      * @param mappingFunction the mapping function to compute a value

   980      * @return the current (existing or computed) value associated with

   981      *         the specified key, or null if the computed value is null

   982      * @throws NullPointerException if the specified key is null and

   983      *         this map does not support null keys, or the mappingFunction

   984      *         is null

   985      * @throws UnsupportedOperationException if the {@code put} operation

   986      *         is not supported by this map

   987      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   988      * @throws ClassCastException if the class of the specified key or value

   989      *         prevents it from being stored in this map

   990      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   991      * @throws IllegalArgumentException if some property of the specified key

   992      *         or value prevents it from being stored in this map

   993      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

   994      * @since 1.8

   995      */

   996     default V computeIfAbsent(K key,

   997             Function<? super K, ? extends V> mappingFunction) {

   998         Objects.requireNonNull(mappingFunction);

   999         V v;

  1000         if ((v = get(key)) == null) {

  1001             V newValue;

  1002             if ((newValue = mappingFunction.apply(key)) != null) {

  1003                 put(key, newValue);

  1004                 return newValue;

  1005             }

  1006         }

  1007 

  1008         return v;

  1009     }

  1010 

  1011     /**

  1012      * If the value for the specified key is present and non-null, attempts to

  1013      * compute a new mapping given the key and its current mapped value.

  1014      *

  1015      * <p>If the remapping function returns {@code null}, the mapping is removed.

  1016      * If the remapping function itself throws an (unchecked) exception, the

  1017      * exception is rethrown, and the current mapping is left unchanged.

  1018      *

  1019      * <p>The remapping function should not modify this map during computation.

  1020      *

  1021      * @implSpec

  1022      * The default implementation is equivalent to performing the following

  1023      * steps for this {@code map}, then returning the current value or

  1024      * {@code null} if now absent:

  1025      *

  1026      * <pre> {@code

  1027      * if (map.get(key) != null) {

  1028      *     V oldValue = map.get(key);

  1029      *     V newValue = remappingFunction.apply(key, oldValue);

  1030      *     if (newValue != null)

  1031      *         map.put(key, newValue);

  1032      *     else

  1033      *         map.remove(key);

  1034      * }

  1035      * }</pre>

  1036      *

  1037      * <p>The default implementation makes no guarantees about detecting if the

  1038      * remapping function modifies this map during computation and, if

  1039      * appropriate, reporting an error. Non-concurrent implementations should

  1040      * override this method and, on a best-effort basis, throw a

  1041      * {@code ConcurrentModificationException} if it is detected that the

  1042      * remapping function modifies this map during computation. Concurrent

  1043      * implementations should override this method and, on a best-effort basis,

  1044      * throw an {@code IllegalStateException} if it is detected that the

  1045      * remapping function modifies this map during computation and as a result

  1046      * computation would never complete.

  1047      *

  1048      * <p>The default implementation makes no guarantees about synchronization

  1049      * or atomicity properties of this method. Any implementation providing

  1050      * atomicity guarantees must override this method and document its

  1051      * concurrency properties. In particular, all implementations of

  1052      * subinterface {@link java.util.concurrent.ConcurrentMap} must document

  1053      * whether the remapping function is applied once atomically only if the

  1054      * value is not present.

  1055      *

  1056      * @param key key with which the specified value is to be associated

  1057      * @param remappingFunction the remapping function to compute a value

  1058      * @return the new value associated with the specified key, or null if none

  1059      * @throws NullPointerException if the specified key is null and

  1060      *         this map does not support null keys, or the

  1061      *         remappingFunction is null

  1062      * @throws UnsupportedOperationException if the {@code put} operation

  1063      *         is not supported by this map

  1064      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

  1065      * @throws ClassCastException if the class of the specified key or value

  1066      *         prevents it from being stored in this map

  1067      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

  1068      * @throws IllegalArgumentException if some property of the specified key

  1069      *         or value prevents it from being stored in this map

  1070      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)

  1071      * @since 1.8

  1072      */

  1073     default V computeIfPresent(K key,

  1074             BiFunction<? super K, ? super V, ? extends V> remappingFunction) {

  1075         Objects.requireNonNull(remappingFunction);

  1076         V oldValue;

  1077         if ((oldValue = get(key)) != null) {

  1078             V newValue = remappingFunction.apply(key, oldValue);

  1079             if (newValue != null) {

  1080                 put(key, newValue);

  1081                 return newValue;

  1082             } else {

  1083                 remove(key);

  1084                 return null;

  1085             }

  1086         } else {

  1087             return null;

  1088         }

  1089     }

  1090 

  1091     /**

  1092      * Attempts to compute a mapping for the specified key and its current

  1093      * mapped value (or {@code null} if there is no current mapping). For

  1094      * example, to either create or append a {@code String} msg to a value

  1095      * mapping:

  1096      *

  1097      * <pre> {@code

  1098      * map.compute(key, (k, v) -> (v == null) ? msg : v.concat(msg))}</pre>

  1099      * (Method {@link #merge merge()} is often simpler to use for such purposes.)

  1100      *

  1101      * <p>If the remapping function returns {@code null}, the mapping is removed

  1102      * (or remains absent if initially absent).  If the remapping function

  1103      * itself throws an (unchecked) exception, the exception is rethrown, and

  1104      * the current mapping is left unchanged.

  1105      *

  1106      * <p>The remapping function should not modify this map during computation.

  1107      *

  1108      * @implSpec

  1109      * The default implementation is equivalent to performing the following

  1110      * steps for this {@code map}, then returning the current value or

  1111      * {@code null} if absent:

  1112      *

  1113      * <pre> {@code

  1114      * V oldValue = map.get(key);

  1115      * V newValue = remappingFunction.apply(key, oldValue);

  1116      * if (oldValue != null) {

  1117      *    if (newValue != null)

  1118      *       map.put(key, newValue);

  1119      *    else

  1120      *       map.remove(key);

  1121      * } else {

  1122      *    if (newValue != null)

  1123      *       map.put(key, newValue);

  1124      *    else

  1125      *       return null;

  1126      * }

  1127      * }</pre>

  1128      *

  1129      * <p>The default implementation makes no guarantees about detecting if the

  1130      * remapping function modifies this map during computation and, if

  1131      * appropriate, reporting an error. Non-concurrent implementations should

  1132      * override this method and, on a best-effort basis, throw a

  1133      * {@code ConcurrentModificationException} if it is detected that the

  1134      * remapping function modifies this map during computation. Concurrent