1 /*
   2  * Copyright (c) 1997, 2018, 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="unmodifiable">Unmodifiable Maps</a></h2>
 114  * <p>The {@link Map#of() Map.of},
 115  * {@link Map#ofEntries(Map.Entry...) Map.ofEntries}, and
 116  * {@link Map#copyOf Map.copyOf}
 117  * static factory methods provide a convenient way to create unmodifiable maps.
 118  * The {@code Map}
 119  * instances created by these methods have the following characteristics:
 120  *
 121  * <ul>
 122  * <li>They are <a href="Collection.html#unmodifiable"><i>unmodifiable</i></a>. Keys and values
 123  * cannot be added, removed, or updated. Calling any mutator method on the Map
 124  * will always cause {@code UnsupportedOperationException} to be thrown.
 125  * However, if the contained keys or values are themselves mutable, this may cause the
 126  * Map to behave inconsistently or its contents to appear to change.
 127  * <li>They disallow {@code null} keys and values. Attempts to create them with
 128  * {@code null} keys or values result in {@code NullPointerException}.
 129  * <li>They are serializable if all keys and values are serializable.
 130  * <li>They reject duplicate keys at creation time. Duplicate keys
 131  * passed to a static factory method result in {@code IllegalArgumentException}.
 132  * <li>The iteration order of mappings is unspecified and is subject to change.
 133  * <li>They are <a href="../lang/doc-files/ValueBased.html">value-based</a>.
 134  * Callers should make no assumptions about the identity of the returned instances.
 135  * Factories are free to create new instances or reuse existing ones. Therefore,
 136  * identity-sensitive operations on these instances (reference equality ({@code ==}),
 137  * identity hash code, and synchronization) are unreliable and should be avoided.
 138  * <li>They are serialized as specified on the
 139  * <a href="{@docRoot}/serialized-form.html#java.util.CollSer">Serialized Form</a>
 140  * page.
 141  * </ul>
 142  *
 143  * <p>This interface is a member of the
 144  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 145  * Java Collections Framework</a>.
 146  *
 147  * @param <K> the type of keys maintained by this map
 148  * @param <V> the type of mapped values
 149  *
 150  * @author  Josh Bloch
 151  * @see HashMap
 152  * @see TreeMap
 153  * @see Hashtable
 154  * @see SortedMap
 155  * @see Collection
 156  * @see Set
 157  * @since 1.2
 158  */
 159 public interface Map<K, V> {
 160     // Query Operations
 161 
 162     /**
 163      * Returns the number of key-value mappings in this map.  If the
 164      * map contains more than {@code Integer.MAX_VALUE} elements, returns
 165      * {@code Integer.MAX_VALUE}.
 166      *
 167      * @return the number of key-value mappings in this map
 168      */
 169     int size();
 170 
 171     /**
 172      * Returns {@code true} if this map contains no key-value mappings.
 173      *
 174      * @return {@code true} if this map contains no key-value mappings
 175      */
 176     boolean isEmpty();
 177 
 178     /**
 179      * Returns {@code true} if this map contains a mapping for the specified
 180      * key.  More formally, returns {@code true} if and only if
 181      * this map contains a mapping for a key {@code k} such that
 182      * {@code Objects.equals(key, k)}.  (There can be
 183      * at most one such mapping.)
 184      *
 185      * @param key key whose presence in this map is to be tested
 186      * @return {@code true} if this map contains a mapping for the specified
 187      *         key
 188      * @throws ClassCastException if the key is of an inappropriate type for
 189      *         this map
 190      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 191      * @throws NullPointerException if the specified key is null and this map
 192      *         does not permit null keys
 193      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 194      */
 195     boolean containsKey(Object key);
 196 
 197     /**
 198      * Returns {@code true} if this map maps one or more keys to the
 199      * specified value.  More formally, returns {@code true} if and only if
 200      * this map contains at least one mapping to a value {@code v} such that
 201      * {@code Objects.equals(value, v)}.  This operation
 202      * will probably require time linear in the map size for most
 203      * implementations of the {@code Map} interface.
 204      *
 205      * @param value value whose presence in this map is to be tested
 206      * @return {@code true} if this map maps one or more keys to the
 207      *         specified value
 208      * @throws ClassCastException if the value is of an inappropriate type for
 209      *         this map
 210      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 211      * @throws NullPointerException if the specified value is null and this
 212      *         map does not permit null values
 213      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 214      */
 215     boolean containsValue(Object value);
 216 
 217     /**
 218      * Returns the value to which the specified key is mapped,
 219      * or {@code null} if this map contains no mapping for the key.
 220      *
 221      * <p>More formally, if this map contains a mapping from a key
 222      * {@code k} to a value {@code v} such that
 223      * {@code Objects.equals(key, k)},
 224      * then this method returns {@code v}; otherwise
 225      * it returns {@code null}.  (There can be at most one such mapping.)
 226      *
 227      * <p>If this map permits null values, then a return value of
 228      * {@code null} does not <i>necessarily</i> indicate that the map
 229      * contains no mapping for the key; it's also possible that the map
 230      * explicitly maps the key to {@code null}.  The {@link #containsKey
 231      * containsKey} operation may be used to distinguish these two cases.
 232      *
 233      * @param key the key whose associated value is to be returned
 234      * @return the value to which the specified key is mapped, or
 235      *         {@code null} if this map contains no mapping for the key
 236      * @throws ClassCastException if the key is of an inappropriate type for
 237      *         this map
 238      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 239      * @throws NullPointerException if the specified key is null and this map
 240      *         does not permit null keys
 241      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 242      */
 243     V get(Object key);
 244 
 245     // Modification Operations
 246 
 247     /**
 248      * Associates the specified value with the specified key in this map
 249      * (optional operation).  If the map previously contained a mapping for
 250      * the key, the old value is replaced by the specified value.  (A map
 251      * {@code m} is said to contain a mapping for a key {@code k} if and only
 252      * if {@link #containsKey(Object) m.containsKey(k)} would return
 253      * {@code true}.)
 254      *
 255      * @param key key with which the specified value is to be associated
 256      * @param value value to be associated with the specified key
 257      * @return the previous value associated with {@code key}, or
 258      *         {@code null} if there was no mapping for {@code key}.
 259      *         (A {@code null} return can also indicate that the map
 260      *         previously associated {@code null} with {@code key},
 261      *         if the implementation supports {@code null} values.)
 262      * @throws UnsupportedOperationException if the {@code put} operation
 263      *         is not supported by this map
 264      * @throws ClassCastException if the class of the specified key or value
 265      *         prevents it from being stored in this map
 266      * @throws NullPointerException if the specified key or value is null
 267      *         and this map does not permit null keys or values
 268      * @throws IllegalArgumentException if some property of the specified key
 269      *         or value prevents it from being stored in this map
 270      */
 271     V put(K key, V value);
 272 
 273     /**
 274      * Removes the mapping for a key from this map if it is present
 275      * (optional operation).   More formally, if this map contains a mapping
 276      * from key {@code k} to value {@code v} such that
 277      * {@code Objects.equals(key, k)}, that mapping
 278      * is removed.  (The map can contain at most one such mapping.)
 279      *
 280      * <p>Returns the value to which this map previously associated the key,
 281      * or {@code null} if the map contained no mapping for the key.
 282      *
 283      * <p>If this map permits null values, then a return value of
 284      * {@code null} does not <i>necessarily</i> indicate that the map
 285      * contained no mapping for the key; it's also possible that the map
 286      * explicitly mapped the key to {@code null}.
 287      *
 288      * <p>The map will not contain a mapping for the specified key once the
 289      * call returns.
 290      *
 291      * @param key key whose mapping is to be removed from the map
 292      * @return the previous value associated with {@code key}, or
 293      *         {@code null} if there was no mapping for {@code key}.
 294      * @throws UnsupportedOperationException if the {@code remove} operation
 295      *         is not supported by this map
 296      * @throws ClassCastException if the key is of an inappropriate type for
 297      *         this map
 298      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 299      * @throws NullPointerException if the specified key is null and this
 300      *         map does not permit null keys
 301      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 302      */
 303     V remove(Object key);
 304 
 305 
 306     // Bulk Operations
 307 
 308     /**
 309      * Copies all of the mappings from the specified map to this map
 310      * (optional operation).  The effect of this call is equivalent to that
 311      * of calling {@link #put(Object,Object) put(k, v)} on this map once
 312      * for each mapping from key {@code k} to value {@code v} in the
 313      * specified map.  The behavior of this operation is undefined if the
 314      * specified map is modified while the operation is in progress.
 315      *
 316      * @param m mappings to be stored in this map
 317      * @throws UnsupportedOperationException if the {@code putAll} operation
 318      *         is not supported by this map
 319      * @throws ClassCastException if the class of a key or value in the
 320      *         specified map prevents it from being stored in this map
 321      * @throws NullPointerException if the specified map is null, or if
 322      *         this map does not permit null keys or values, and the
 323      *         specified map contains null keys or values
 324      * @throws IllegalArgumentException if some property of a key or value in
 325      *         the specified map prevents it from being stored in this map
 326      */
 327     void putAll(Map<? extends K, ? extends V> m);
 328 
 329     /**
 330      * Removes all of the mappings from this map (optional operation).
 331      * The map will be empty after this call returns.
 332      *
 333      * @throws UnsupportedOperationException if the {@code clear} operation
 334      *         is not supported by this map
 335      */
 336     void clear();
 337 
 338 
 339     // Views
 340 
 341     /**
 342      * Returns a {@link Set} view of the keys contained in this map.
 343      * The set is backed by the map, so changes to the map are
 344      * reflected in the set, and vice-versa.  If the map is modified
 345      * while an iteration over the set is in progress (except through
 346      * the iterator's own {@code remove} operation), the results of
 347      * the iteration are undefined.  The set supports element removal,
 348      * which removes the corresponding mapping from the map, via the
 349      * {@code Iterator.remove}, {@code Set.remove},
 350      * {@code removeAll}, {@code retainAll}, and {@code clear}
 351      * operations.  It does not support the {@code add} or {@code addAll}
 352      * operations.
 353      *
 354      * @return a set view of the keys contained in this map
 355      */
 356     Set<K> keySet();
 357 
 358     /**
 359      * Returns a {@link Collection} view of the values contained in this map.
 360      * The collection is backed by the map, so changes to the map are
 361      * reflected in the collection, and vice-versa.  If the map is
 362      * modified while an iteration over the collection is in progress
 363      * (except through the iterator's own {@code remove} operation),
 364      * the results of the iteration are undefined.  The collection
 365      * supports element removal, which removes the corresponding
 366      * mapping from the map, via the {@code Iterator.remove},
 367      * {@code Collection.remove}, {@code removeAll},
 368      * {@code retainAll} and {@code clear} operations.  It does not
 369      * support the {@code add} or {@code addAll} operations.
 370      *
 371      * @return a collection view of the values contained in this map
 372      */
 373     Collection<V> values();
 374 
 375     /**
 376      * Returns a {@link Set} view of the mappings contained in this map.
 377      * The set is backed by the map, so changes to the map are
 378      * reflected in the set, and vice-versa.  If the map is modified
 379      * while an iteration over the set is in progress (except through
 380      * the iterator's own {@code remove} operation, or through the
 381      * {@code setValue} operation on a map entry returned by the
 382      * iterator) the results of the iteration are undefined.  The set
 383      * supports element removal, which removes the corresponding
 384      * mapping from the map, via the {@code Iterator.remove},
 385      * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
 386      * {@code clear} operations.  It does not support the
 387      * {@code add} or {@code addAll} operations.
 388      *
 389      * @return a set view of the mappings contained in this map
 390      */
 391     Set<Map.Entry<K, V>> entrySet();
 392 
 393     /**
 394      * A map entry (key-value pair).  The {@code Map.entrySet} method returns
 395      * a collection-view of the map, whose elements are of this class.  The
 396      * <i>only</i> way to obtain a reference to a map entry is from the
 397      * iterator of this collection-view.  These {@code Map.Entry} objects are
 398      * valid <i>only</i> for the duration of the iteration; more formally,
 399      * the behavior of a map entry is undefined if the backing map has been
 400      * modified after the entry was returned by the iterator, except through
 401      * the {@code setValue} operation on the map entry.
 402      *
 403      * @see Map#entrySet()
 404      * @since 1.2
 405      */
 406     interface Entry<K, V> {
 407         /**
 408          * Returns the key corresponding to this entry.
 409          *
 410          * @return the key corresponding to this entry
 411          * @throws IllegalStateException implementations may, but are not
 412          *         required to, throw this exception if the entry has been
 413          *         removed from the backing map.
 414          */
 415         K getKey();
 416 
 417         /**
 418          * Returns the value corresponding to this entry.  If the mapping
 419          * has been removed from the backing map (by the iterator's
 420          * {@code remove} operation), the results of this call are undefined.
 421          *
 422          * @return the value corresponding to this entry
 423          * @throws IllegalStateException implementations may, but are not
 424          *         required to, throw this exception if the entry has been
 425          *         removed from the backing map.
 426          */
 427         V getValue();
 428 
 429         /**
 430          * Replaces the value corresponding to this entry with the specified
 431          * value (optional operation).  (Writes through to the map.)  The
 432          * behavior of this call is undefined if the mapping has already been
 433          * removed from the map (by the iterator's {@code remove} operation).
 434          *
 435          * @param value new value to be stored in this entry
 436          * @return old value corresponding to the entry
 437          * @throws UnsupportedOperationException if the {@code put} operation
 438          *         is not supported by the backing map
 439          * @throws ClassCastException if the class of the specified value
 440          *         prevents it from being stored in the backing map
 441          * @throws NullPointerException if the backing map does not permit
 442          *         null values, and the specified value is null
 443          * @throws IllegalArgumentException if some property of this value
 444          *         prevents it from being stored in the backing map
 445          * @throws IllegalStateException implementations may, but are not
 446          *         required to, throw this exception if the entry has been
 447          *         removed from the backing map.
 448          */
 449         V setValue(V value);
 450 
 451         /**
 452          * Compares the specified object with this entry for equality.
 453          * Returns {@code true} if the given object is also a map entry and
 454          * the two entries represent the same mapping.  More formally, two
 455          * entries {@code e1} and {@code e2} represent the same mapping
 456          * if<pre>
 457          *     (e1.getKey()==null ?
 458          *      e2.getKey()==null : e1.getKey().equals(e2.getKey()))  &amp;&amp;
 459          *     (e1.getValue()==null ?
 460          *      e2.getValue()==null : e1.getValue().equals(e2.getValue()))
 461          * </pre>
 462          * This ensures that the {@code equals} method works properly across
 463          * different implementations of the {@code Map.Entry} interface.
 464          *
 465          * @param o object to be compared for equality with this map entry
 466          * @return {@code true} if the specified object is equal to this map
 467          *         entry
 468          */
 469         boolean equals(Object o);
 470 
 471         /**
 472          * Returns the hash code value for this map entry.  The hash code
 473          * of a map entry {@code e} is defined to be: <pre>
 474          *     (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
 475          *     (e.getValue()==null ? 0 : e.getValue().hashCode())
 476          * </pre>
 477          * This ensures that {@code e1.equals(e2)} implies that
 478          * {@code e1.hashCode()==e2.hashCode()} for any two Entries
 479          * {@code e1} and {@code e2}, as required by the general
 480          * contract of {@code Object.hashCode}.
 481          *
 482          * @return the hash code value for this map entry
 483          * @see Object#hashCode()
 484          * @see Object#equals(Object)
 485          * @see #equals(Object)
 486          */
 487         int hashCode();
 488 
 489         /**
 490          * Returns a comparator that compares {@link Map.Entry} in natural order on key.
 491          *
 492          * <p>The returned comparator is serializable and throws {@link
 493          * NullPointerException} when comparing an entry with a null key.
 494          *
 495          * @param  <K> the {@link Comparable} type of then map keys
 496          * @param  <V> the type of the map values
 497          * @return a comparator that compares {@link Map.Entry} in natural order on key.
 498          * @see Comparable
 499          * @since 1.8
 500          */
 501         public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
 502             return (Comparator<Map.Entry<K, V>> & Serializable)
 503                 (c1, c2) -> c1.getKey().compareTo(c2.getKey());
 504         }
 505 
 506         /**
 507          * Returns a comparator that compares {@link Map.Entry} in natural order on value.
 508          *
 509          * <p>The returned comparator is serializable and throws {@link
 510          * NullPointerException} when comparing an entry with null values.
 511          *
 512          * @param <K> the type of the map keys
 513          * @param <V> the {@link Comparable} type of the map values
 514          * @return a comparator that compares {@link Map.Entry} in natural order on value.
 515          * @see Comparable
 516          * @since 1.8
 517          */
 518         public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
 519             return (Comparator<Map.Entry<K, V>> & Serializable)
 520                 (c1, c2) -> c1.getValue().compareTo(c2.getValue());
 521         }
 522 
 523         /**
 524          * Returns a comparator that compares {@link Map.Entry} by key using the given
 525          * {@link Comparator}.
 526          *
 527          * <p>The returned comparator is serializable if the specified comparator
 528          * is also serializable.
 529          *
 530          * @param  <K> the type of the map keys
 531          * @param  <V> the type of the map values
 532          * @param  cmp the key {@link Comparator}
 533          * @return a comparator that compares {@link Map.Entry} by the key.
 534          * @since 1.8
 535          */
 536         public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
 537             Objects.requireNonNull(cmp);
 538             return (Comparator<Map.Entry<K, V>> & Serializable)
 539                 (c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
 540         }
 541 
 542         /**
 543          * Returns a comparator that compares {@link Map.Entry} by value using the given
 544          * {@link Comparator}.
 545          *
 546          * <p>The returned comparator is serializable if the specified comparator
 547          * is also serializable.
 548          *
 549          * @param  <K> the type of the map keys
 550          * @param  <V> the type of the map values
 551          * @param  cmp the value {@link Comparator}
 552          * @return a comparator that compares {@link Map.Entry} by the value.
 553          * @since 1.8
 554          */
 555         public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
 556             Objects.requireNonNull(cmp);
 557             return (Comparator<Map.Entry<K, V>> & Serializable)
 558                 (c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
 559         }
 560     }
 561 
 562     // Comparison and hashing
 563 
 564     /**
 565      * Compares the specified object with this map for equality.  Returns
 566      * {@code true} if the given object is also a map and the two maps
 567      * represent the same mappings.  More formally, two maps {@code m1} and
 568      * {@code m2} represent the same mappings if
 569      * {@code m1.entrySet().equals(m2.entrySet())}.  This ensures that the
 570      * {@code equals} method works properly across different implementations
 571      * of the {@code Map} interface.
 572      *
 573      * @param o object to be compared for equality with this map
 574      * @return {@code true} if the specified object is equal to this map
 575      */
 576     boolean equals(Object o);
 577 
 578     /**
 579      * Returns the hash code value for this map.  The hash code of a map is
 580      * defined to be the sum of the hash codes of each entry in the map's
 581      * {@code entrySet()} view.  This ensures that {@code m1.equals(m2)}
 582      * implies that {@code m1.hashCode()==m2.hashCode()} for any two maps
 583      * {@code m1} and {@code m2}, as required by the general contract of
 584      * {@link Object#hashCode}.
 585      *
 586      * @return the hash code value for this map
 587      * @see Map.Entry#hashCode()
 588      * @see Object#equals(Object)
 589      * @see #equals(Object)
 590      */
 591     int hashCode();
 592 
 593     // Defaultable methods
 594 
 595     /**
 596      * Returns the value to which the specified key is mapped, or
 597      * {@code defaultValue} if this map contains no mapping for the key.
 598      *
 599      * @implSpec
 600      * The default implementation makes no guarantees about synchronization
 601      * or atomicity properties of this method. Any implementation providing
 602      * atomicity guarantees must override this method and document its
 603      * concurrency properties.
 604      *
 605      * @param key the key whose associated value is to be returned
 606      * @param defaultValue the default mapping of the key
 607      * @return the value to which the specified key is mapped, or
 608      * {@code defaultValue} if this map contains no mapping for the key
 609      * @throws ClassCastException if the key is of an inappropriate type for
 610      * this map
 611      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 612      * @throws NullPointerException if the specified key is null and this map
 613      * does not permit null keys
 614      * (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 615      * @since 1.8
 616      */
 617     default V getOrDefault(Object key, V defaultValue) {
 618         V v;
 619         return (((v = get(key)) != null) || containsKey(key))
 620             ? v
 621             : defaultValue;
 622     }
 623 
 624     /**
 625      * Performs the given action for each entry in this map until all entries
 626      * have been processed or the action throws an exception.   Unless
 627      * otherwise specified by the implementing class, actions are performed in
 628      * the order of entry set iteration (if an iteration order is specified.)
 629      * Exceptions thrown by the action are relayed to the caller.
 630      *
 631      * @implSpec
 632      * The default implementation is equivalent to, for this {@code map}:
 633      * <pre> {@code
 634      * for (Map.Entry<K, V> entry : map.entrySet())
 635      *     action.accept(entry.getKey(), entry.getValue());
 636      * }</pre>
 637      *
 638      * The default implementation makes no guarantees about synchronization
 639      * or atomicity properties of this method. Any implementation providing
 640      * atomicity guarantees must override this method and document its
 641      * concurrency properties.
 642      *
 643      * @param action The action to be performed for each entry
 644      * @throws NullPointerException if the specified action is null
 645      * @throws ConcurrentModificationException if an entry is found to be
 646      * removed during iteration
 647      * @since 1.8
 648      */
 649     default void forEach(BiConsumer<? super K, ? super V> action) {
 650         Objects.requireNonNull(action);
 651         for (Map.Entry<K, V> entry : entrySet()) {
 652             K k;
 653             V v;
 654             try {
 655                 k = entry.getKey();
 656                 v = entry.getValue();
 657             } catch (IllegalStateException ise) {
 658                 // this usually means the entry is no longer in the map.
 659                 throw new ConcurrentModificationException(ise);
 660             }
 661             action.accept(k, v);
 662         }
 663     }
 664 
 665     /**
 666      * Replaces each entry's value with the result of invoking the given
 667      * function on that entry until all entries have been processed or the
 668      * function throws an exception.  Exceptions thrown by the function are
 669      * relayed to the caller.
 670      *
 671      * @implSpec
 672      * <p>The default implementation is equivalent to, for this {@code map}:
 673      * <pre> {@code
 674      * for (Map.Entry<K, V> entry : map.entrySet())
 675      *     entry.setValue(function.apply(entry.getKey(), entry.getValue()));
 676      * }</pre>
 677      *
 678      * <p>The default implementation makes no guarantees about synchronization
 679      * or atomicity properties of this method. Any implementation providing
 680      * atomicity guarantees must override this method and document its
 681      * concurrency properties.
 682      *
 683      * @param function the function to apply to each entry
 684      * @throws UnsupportedOperationException if the {@code set} operation
 685      * is not supported by this map's entry set iterator.
 686      * @throws ClassCastException if the class of a replacement value
 687      * prevents it from being stored in this map
 688      * @throws NullPointerException if the specified function is null, or the
 689      * specified replacement value is null, and this map does not permit null
 690      * values
 691      * @throws ClassCastException if a replacement value is of an inappropriate
 692      *         type for this map
 693      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 694      * @throws NullPointerException if function or a replacement value is null,
 695      *         and this map does not permit null keys or values
 696      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 697      * @throws IllegalArgumentException if some property of a replacement value
 698      *         prevents it from being stored in this map
 699      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 700      * @throws ConcurrentModificationException if an entry is found to be
 701      * removed during iteration
 702      * @since 1.8
 703      */
 704     default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
 705         Objects.requireNonNull(function);
 706         for (Map.Entry<K, V> entry : entrySet()) {
 707             K k;
 708             V v;
 709             try {
 710                 k = entry.getKey();
 711                 v = entry.getValue();
 712             } catch (IllegalStateException ise) {
 713                 // this usually means the entry is no longer in the map.
 714                 throw new ConcurrentModificationException(ise);
 715             }
 716 
 717             // ise thrown from function is not a cme.
 718             v = function.apply(k, v);
 719 
 720             try {
 721                 entry.setValue(v);
 722             } catch (IllegalStateException ise) {
 723                 // this usually means the entry is no longer in the map.
 724                 throw new ConcurrentModificationException(ise);
 725             }
 726         }
 727     }
 728 
 729     /**
 730      * If the specified key is not already associated with a value (or is mapped
 731      * to {@code null}) associates it with the given value and returns
 732      * {@code null}, else returns the current value.
 733      *
 734      * @implSpec
 735      * The default implementation is equivalent to, for this {@code
 736      * map}:
 737      *
 738      * <pre> {@code
 739      * V v = map.get(key);
 740      * if (v == null)
 741      *     v = map.put(key, value);
 742      *
 743      * return v;
 744      * }</pre>
 745      *
 746      * <p>The default implementation makes no guarantees about synchronization
 747      * or atomicity properties of this method. Any implementation providing
 748      * atomicity guarantees must override this method and document its
 749      * concurrency properties.
 750      *
 751      * @param key key with which the specified value is to be associated
 752      * @param value value to be associated with the specified key
 753      * @return the previous value associated with the specified key, or
 754      *         {@code null} if there was no mapping for the key.
 755      *         (A {@code null} return can also indicate that the map
 756      *         previously associated {@code null} with the key,
 757      *         if the implementation supports null values.)
 758      * @throws UnsupportedOperationException if the {@code put} operation
 759      *         is not supported by this map
 760      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 761      * @throws ClassCastException if the key or value is of an inappropriate
 762      *         type for this map
 763      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 764      * @throws NullPointerException if the specified key or value is null,
 765      *         and this map does not permit null keys or values
 766      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 767      * @throws IllegalArgumentException if some property of the specified key
 768      *         or value prevents it from being stored in this map
 769      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 770      * @since 1.8
 771      */
 772     default V putIfAbsent(K key, V value) {
 773         V v = get(key);
 774         if (v == null) {
 775             v = put(key, value);
 776         }
 777 
 778         return v;
 779     }
 780 
 781     /**
 782      * Removes the entry for the specified key only if it is currently
 783      * mapped to the specified value.
 784      *
 785      * @implSpec
 786      * The default implementation is equivalent to, for this {@code map}:
 787      *
 788      * <pre> {@code
 789      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
 790      *     map.remove(key);
 791      *     return true;
 792      * } else
 793      *     return false;
 794      * }</pre>
 795      *
 796      * <p>The default implementation makes no guarantees about synchronization
 797      * or atomicity properties of this method. Any implementation providing
 798      * atomicity guarantees must override this method and document its
 799      * concurrency properties.
 800      *
 801      * @param key key with which the specified value is associated
 802      * @param value value expected to be associated with the specified key
 803      * @return {@code true} if the value was removed
 804      * @throws UnsupportedOperationException if the {@code remove} operation
 805      *         is not supported by this map
 806      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 807      * @throws ClassCastException if the key or value is of an inappropriate
 808      *         type for this map
 809      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 810      * @throws NullPointerException if the specified key or value is null,
 811      *         and this map does not permit null keys or values
 812      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 813      * @since 1.8
 814      */
 815     default boolean remove(Object key, Object value) {
 816         Object curValue = get(key);
 817         if (!Objects.equals(curValue, value) ||
 818             (curValue == null && !containsKey(key))) {
 819             return false;
 820         }
 821         remove(key);
 822         return true;
 823     }
 824 
 825     /**
 826      * Replaces the entry for the specified key only if currently
 827      * mapped to the specified value.
 828      *
 829      * @implSpec
 830      * The default implementation is equivalent to, for this {@code map}:
 831      *
 832      * <pre> {@code
 833      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
 834      *     map.put(key, newValue);
 835      *     return true;
 836      * } else
 837      *     return false;
 838      * }</pre>
 839      *
 840      * The default implementation does not throw NullPointerException
 841      * for maps that do not support null values if oldValue is null unless
 842      * newValue is also null.
 843      *
 844      * <p>The default implementation makes no guarantees about synchronization
 845      * or atomicity properties of this method. Any implementation providing
 846      * atomicity guarantees must override this method and document its
 847      * concurrency properties.
 848      *
 849      * @param key key with which the specified value is associated
 850      * @param oldValue value expected to be associated with the specified key
 851      * @param newValue value to be associated with the specified key
 852      * @return {@code true} if the value was replaced
 853      * @throws UnsupportedOperationException if the {@code put} operation
 854      *         is not supported by this map
 855      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 856      * @throws ClassCastException if the class of a specified key or value
 857      *         prevents it from being stored in this map
 858      * @throws NullPointerException if a specified key or newValue is null,
 859      *         and this map does not permit null keys or values
 860      * @throws NullPointerException if oldValue is null and this map does not
 861      *         permit null values
 862      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 863      * @throws IllegalArgumentException if some property of a specified key
 864      *         or value prevents it from being stored in this map
 865      * @since 1.8
 866      */
 867     default boolean replace(K key, V oldValue, V newValue) {
 868         Object curValue = get(key);
 869         if (!Objects.equals(curValue, oldValue) ||
 870             (curValue == null && !containsKey(key))) {
 871             return false;
 872         }
 873         put(key, newValue);
 874         return true;
 875     }
 876 
 877     /**
 878      * Replaces the entry for the specified key only if it is
 879      * currently mapped to some value.
 880      *
 881      * @implSpec
 882      * The default implementation is equivalent to, for this {@code map}:
 883      *
 884      * <pre> {@code
 885      * if (map.containsKey(key)) {
 886      *     return map.put(key, value);
 887      * } else
 888      *     return null;
 889      * }</pre>
 890      *
 891      * <p>The default implementation makes no guarantees about synchronization
 892      * or atomicity properties of this method. Any implementation providing
 893      * atomicity guarantees must override this method and document its
 894      * concurrency properties.
 895      *
 896      * @param key key with which the specified value is associated
 897      * @param value value to be associated with the specified key
 898      * @return the previous value associated with the specified key, or
 899      *         {@code null} if there was no mapping for the key.
 900      *         (A {@code null} return can also indicate that the map
 901      *         previously associated {@code null} with the key,
 902      *         if the implementation supports null values.)
 903      * @throws UnsupportedOperationException if the {@code put} operation
 904      *         is not supported by this map
 905      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 906      * @throws ClassCastException if the class of the specified key or value
 907      *         prevents it from being stored in this map
 908      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 909      * @throws NullPointerException if the specified key or value is null,
 910      *         and this map does not permit null keys or values
 911      * @throws IllegalArgumentException if some property of the specified key
 912      *         or value prevents it from being stored in this map
 913      * @since 1.8
 914      */
 915     default V replace(K key, V value) {
 916         V curValue;
 917         if (((curValue = get(key)) != null) || containsKey(key)) {
 918             curValue = put(key, value);
 919         }
 920         return curValue;
 921     }
 922 
 923     /**
 924      * If the specified key is not already associated with a value (or is mapped
 925      * to {@code null}), attempts to compute its value using the given mapping
 926      * function and enters it into this map unless {@code null}.
 927      *
 928      * <p>If the mapping function returns {@code null}, no mapping is recorded.
 929      * If the mapping function itself throws an (unchecked) exception, the
 930      * exception is rethrown, and no mapping is recorded.  The most
 931      * common usage is to construct a new object serving as an initial
 932      * mapped value or memoized result, as in:
 933      *
 934      * <pre> {@code
 935      * map.computeIfAbsent(key, k -> new Value(f(k)));
 936      * }</pre>
 937      *
 938      * <p>Or to implement a multi-value map, {@code Map<K,Collection<V>>},
 939      * supporting multiple values per key:
 940      *
 941      * <pre> {@code
 942      * map.computeIfAbsent(key, k -> new HashSet<V>()).add(v);
 943      * }</pre>
 944      *
 945      * <p>The mapping function should not modify this map during computation.
 946      *
 947      * @implSpec
 948      * The default implementation is equivalent to the following steps for this
 949      * {@code map}, then returning the current value or {@code null} if now
 950      * absent:
 951      *
 952      * <pre> {@code
 953      * if (map.get(key) == null) {
 954      *     V newValue = mappingFunction.apply(key);
 955      *     if (newValue != null)
 956      *         map.put(key, newValue);
 957      * }
 958      * }</pre>
 959      *
 960      * <p>The default implementation makes no guarantees about detecting if the
 961      * mapping function modifies this map during computation and, if
 962      * appropriate, reporting an error. Non-concurrent implementations should
 963      * override this method and, on a best-effort basis, throw a
 964      * {@code ConcurrentModificationException} if it is detected that the
 965      * mapping function modifies this map during computation. Concurrent
 966      * implementations should override this method and, on a best-effort basis,
 967      * throw an {@code IllegalStateException} if it is detected that the
 968      * mapping function modifies this map during computation and as a result
 969      * computation would never complete.
 970      *
 971      * <p>The default implementation makes no guarantees about synchronization
 972      * or atomicity properties of this method. Any implementation providing
 973      * atomicity guarantees must override this method and document its
 974      * concurrency properties. In particular, all implementations of
 975      * subinterface {@link java.util.concurrent.ConcurrentMap} must document
 976      * whether the mapping function is applied once atomically only if the value
 977      * is not present.
 978      *
 979      * @param key key with which the specified value is to be associated
 980      * @param mappingFunction the mapping function to compute a value
 981      * @return the current (existing or computed) value associated with
 982      *         the specified key, or null if the computed value is null
 983      * @throws NullPointerException if the specified key is null and
 984      *         this map does not support null keys, or the mappingFunction
 985      *         is null
 986      * @throws UnsupportedOperationException if the {@code put} operation
 987      *         is not supported by this map
 988      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 989      * @throws ClassCastException if the class of the specified key or value
 990      *         prevents it from being stored in this map
 991      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 992      * @throws IllegalArgumentException if some property of the specified key
 993      *         or value prevents it from being stored in this map
 994      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
 995      * @since 1.8
 996      */
 997     default V computeIfAbsent(K key,
 998             Function<? super K, ? extends V> mappingFunction) {
 999         Objects.requireNonNull(mappingFunction);
1000         V v;
1001         if ((v = get(key)) == null) {
1002             V newValue;
1003             if ((newValue = mappingFunction.apply(key)) != null) {
1004                 put(key, newValue);
1005                 return newValue;
1006             }
1007         }
1008 
1009         return v;
1010     }
1011 
1012     /**
1013      * If the value for the specified key is present and non-null, attempts to
1014      * compute a new mapping given the key and its current mapped value.
1015      *
1016      * <p>If the remapping function returns {@code null}, the mapping is removed.
1017      * If the remapping function itself throws an (unchecked) exception, the
1018      * exception is rethrown, and the current mapping is left unchanged.
1019      *
1020      * <p>The remapping function should not modify this map during computation.
1021      *
1022      * @implSpec
1023      * The default implementation is equivalent to performing the following
1024      * steps for this {@code map}, then returning the current value or
1025      * {@code null} if now absent:
1026      *
1027      * <pre> {@code
1028      * if (map.get(key) != null) {
1029      *     V oldValue = map.get(key);
1030      *     V newValue = remappingFunction.apply(key, oldValue);
1031      *     if (newValue != null)
1032      *         map.put(key, newValue);
1033      *     else
1034      *         map.remove(key);
1035      * }
1036      * }</pre>
1037      *
1038      * <p>The default implementation makes no guarantees about detecting if the
1039      * remapping function modifies this map during computation and, if
1040      * appropriate, reporting an error. Non-concurrent implementations should
1041      * override this method and, on a best-effort basis, throw a
1042      * {@code ConcurrentModificationException} if it is detected that the
1043      * remapping function modifies this map during computation. Concurrent
1044      * implementations should override this method and, on a best-effort basis,
1045      * throw an {@code IllegalStateException} if it is detected that the
1046      * remapping function modifies this map during computation and as a result
1047      * computation would never complete.
1048      *
1049      * <p>The default implementation makes no guarantees about synchronization
1050      * or atomicity properties of this method. Any implementation providing
1051      * atomicity guarantees must override this method and document its
1052      * concurrency properties. In particular, all implementations of
1053      * subinterface {@link java.util.concurrent.ConcurrentMap} must document
1054      * whether the remapping function is applied once atomically only if the
1055      * value is not present.
1056      *
1057      * @param key key with which the specified value is to be associated
1058      * @param remappingFunction the remapping function to compute a value
1059      * @return the new value associated with the specified key, or null if none
1060      * @throws NullPointerException if the specified key is null and
1061      *         this map does not support null keys, or the
1062      *         remappingFunction is null
1063      * @throws UnsupportedOperationException if the {@code put} operation
1064      *         is not supported by this map
1065      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1066      * @throws ClassCastException if the class of the specified key or value
1067      *         prevents it from being stored in this map
1068      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1069      * @throws IllegalArgumentException if some property of the specified key
1070      *         or value prevents it from being stored in this map
1071      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1072      * @since 1.8
1073      */
1074     default V computeIfPresent(K key,
1075             BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1076         Objects.requireNonNull(remappingFunction);
1077         V oldValue;
1078         if ((oldValue = get(key)) != null) {
1079             V newValue = remappingFunction.apply(key, oldValue);
1080             if (newValue != null) {
1081                 put(key, newValue);
1082                 return newValue;
1083             } else {
1084                 remove(key);
1085                 return null;
1086             }
1087         } else {
1088             return null;
1089         }
1090     }
1091 
1092     /**
1093      * Attempts to compute a mapping for the specified key and its current
1094      * mapped value (or {@code null} if there is no current mapping). For
1095      * example, to either create or append a {@code String} msg to a value
1096      * mapping:
1097      *
1098      * <pre> {@code
1099      * map.compute(key, (k, v) -> (v == null) ? msg : v.concat(msg))}</pre>
1100      * (Method {@link #merge merge()} is often simpler to use for such purposes.)
1101      *
1102      * <p>If the remapping function returns {@code null}, the mapping is removed
1103      * (or remains absent if initially absent).  If the remapping function
1104      * itself throws an (unchecked) exception, the exception is rethrown, and
1105      * the current mapping is left unchanged.
1106      *
1107      * <p>The remapping function should not modify this map during computation.
1108      *
1109      * @implSpec
1110      * The default implementation is equivalent to performing the following
1111      * steps for this {@code map}, then returning the current value or
1112      * {@code null} if absent:
1113      *
1114      * <pre> {@code
1115      * V oldValue = map.get(key);
1116      * V newValue = remappingFunction.apply(key, oldValue);
1117      * if (oldValue != null) {
1118      *    if (newValue != null)
1119      *       map.put(key, newValue);
1120      *    else
1121      *       map.remove(key);
1122      * } else {
1123      *    if (newValue != null)
1124      *       map.put(key, newValue);
1125      *    else
1126      *       return null;
1127      * }
1128      * }</pre>
1129      *
1130      * <p>The default implementation makes no guarantees about detecting if the
1131      * remapping function modifies this map during computation and, if
1132      * appropriate, reporting an error. Non-concurrent implementations should
1133      * override this method and, on a best-effort basis, throw a
1134      * {@code ConcurrentModificationException} if it is detected that the
1135      * remapping function modifies this map during computation. Concurrent
1136      * implementations should override this method and, on a best-effort basis,
1137      * throw an {@code IllegalStateException} if it is detected that the
1138      * remapping function modifies this map during computation and as a result
1139      * computation would never complete.
1140      *
1141      * <p>The default implementation makes no guarantees about synchronization
1142      * or atomicity properties of this method. Any implementation providing
1143      * atomicity guarantees must override this method and document its
1144      * concurrency properties. In particular, all implementations of
1145      * subinterface {@link java.util.concurrent.ConcurrentMap} must document
1146      * whether the remapping function is applied once atomically only if the
1147      * value is not present.
1148      *
1149      * @param key key with which the specified value is to be associated
1150      * @param remappingFunction the remapping function to compute a value
1151      * @return the new value associated with the specified key, or null if none
1152      * @throws NullPointerException if the specified key is null and
1153      *         this map does not support null keys, or the
1154      *         remappingFunction is null
1155      * @throws UnsupportedOperationException if the {@code put} operation
1156      *         is not supported by this map
1157      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1158      * @throws ClassCastException if the class of the specified key or value
1159      *         prevents it from being stored in this map
1160      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1161      * @throws IllegalArgumentException if some property of the specified key
1162      *         or value prevents it from being stored in this map
1163      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1164      * @since 1.8
1165      */
1166     default V compute(K key,
1167             BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1168         Objects.requireNonNull(remappingFunction);
1169         V oldValue = get(key);
1170 
1171         V newValue = remappingFunction.apply(key, oldValue);
1172         if (newValue == null) {
1173             // delete mapping
1174             if (oldValue != null || containsKey(key)) {
1175                 // something to remove
1176                 remove(key);
1177                 return null;
1178             } else {
1179                 // nothing to do. Leave things as they were.
1180                 return null;
1181             }
1182         } else {
1183             // add or replace old mapping
1184             put(key, newValue);
1185             return newValue;
1186         }
1187     }
1188 
1189     /**
1190      * If the specified key is not already associated with a value or is
1191      * associated with null, associates it with the given non-null value.
1192      * Otherwise, replaces the associated value with the results of the given
1193      * remapping function, or removes if the result is {@code null}. This
1194      * method may be of use when combining multiple mapped values for a key.
1195      * For example, to either create or append a {@code String msg} to a
1196      * value mapping:
1197      *
1198      * <pre> {@code
1199      * map.merge(key, msg, String::concat)
1200      * }</pre>
1201      *
1202      * <p>If the remapping function returns {@code null}, the mapping is removed.
1203      * If the remapping function itself throws an (unchecked) exception, the
1204      * exception is rethrown, and the current mapping is left unchanged.
1205      *
1206      * <p>The remapping function should not modify this map during computation.
1207      *
1208      * @implSpec
1209      * The default implementation is equivalent to performing the following
1210      * steps for this {@code map}, then returning the current value or
1211      * {@code null} if absent:
1212      *
1213      * <pre> {@code
1214      * V oldValue = map.get(key);
1215      * V newValue = (oldValue == null) ? value :
1216      *              remappingFunction.apply(oldValue, value);
1217      * if (newValue == null)
1218      *     map.remove(key);
1219      * else
1220      *     map.put(key, newValue);
1221      * }</pre>
1222      *
1223      * <p>The default implementation makes no guarantees about detecting if the
1224      * remapping function modifies this map during computation and, if
1225      * appropriate, reporting an error. Non-concurrent implementations should
1226      * override this method and, on a best-effort basis, throw a
1227      * {@code ConcurrentModificationException} if it is detected that the
1228      * remapping function modifies this map during computation. Concurrent
1229      * implementations should override this method and, on a best-effort basis,
1230      * throw an {@code IllegalStateException} if it is detected that the
1231      * remapping function modifies this map during computation and as a result
1232      * computation would never complete.
1233      *
1234      * <p>The default implementation makes no guarantees about synchronization
1235      * or atomicity properties of this method. Any implementation providing
1236      * atomicity guarantees must override this method and document its
1237      * concurrency properties. In particular, all implementations of
1238      * subinterface {@link java.util.concurrent.ConcurrentMap} must document
1239      * whether the remapping function is applied once atomically only if the
1240      * value is not present.
1241      *
1242      * @param key key with which the resulting value is to be associated
1243      * @param value the non-null value to be merged with the existing value
1244      *        associated with the key or, if no existing value or a null value
1245      *        is associated with the key, to be associated with the key
1246      * @param remappingFunction the remapping function to recompute a value if
1247      *        present
1248      * @return the new value associated with the specified key, or null if no
1249      *         value is associated with the key
1250      * @throws UnsupportedOperationException if the {@code put} operation
1251      *         is not supported by this map
1252      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1253      * @throws ClassCastException if the class of the specified key or value
1254      *         prevents it from being stored in this map
1255      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1256      * @throws IllegalArgumentException if some property of the specified key
1257      *         or value prevents it from being stored in this map
1258      *         (<a href="{@docRoot}/java.base/java/util/Collection.html#optional-restrictions">optional</a>)
1259      * @throws NullPointerException if the specified key is null and this map
1260      *         does not support null keys or the value or remappingFunction is
1261      *         null
1262      * @since 1.8
1263      */
1264     default V merge(K key, V value,
1265             BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1266         Objects.requireNonNull(remappingFunction);
1267         Objects.requireNonNull(value);
1268         V oldValue = get(key);
1269         V newValue = (oldValue == null) ? value :
1270                    remappingFunction.apply(oldValue, value);
1271         if (newValue == null) {
1272             remove(key);
1273         } else {
1274             put(key, newValue);
1275         }
1276         return newValue;
1277     }
1278 
1279     /**
1280      * Returns an unmodifiable map containing zero mappings.
1281      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1282      *
1283      * @param <K> the {@code Map}'s key type
1284      * @param <V> the {@code Map}'s value type
1285      * @return an empty {@code Map}
1286      *
1287      * @since 9
1288      */
1289     static <K, V> Map<K, V> of() {
1290         return ImmutableCollections.emptyMap();
1291     }
1292 
1293     /**
1294      * Returns an unmodifiable map containing a single mapping.
1295      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1296      *
1297      * @param <K> the {@code Map}'s key type
1298      * @param <V> the {@code Map}'s value type
1299      * @param k1 the mapping's key
1300      * @param v1 the mapping's value
1301      * @return a {@code Map} containing the specified mapping
1302      * @throws NullPointerException if the key or the value is {@code null}
1303      *
1304      * @since 9
1305      */
1306     static <K, V> Map<K, V> of(K k1, V v1) {
1307         return new ImmutableCollections.Map1<>(k1, v1);
1308     }
1309 
1310     /**
1311      * Returns an unmodifiable map containing two mappings.
1312      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1313      *
1314      * @param <K> the {@code Map}'s key type
1315      * @param <V> the {@code Map}'s value type
1316      * @param k1 the first mapping's key
1317      * @param v1 the first mapping's value
1318      * @param k2 the second mapping's key
1319      * @param v2 the second mapping's value
1320      * @return a {@code Map} containing the specified mappings
1321      * @throws IllegalArgumentException if the keys are duplicates
1322      * @throws NullPointerException if any key or value is {@code null}
1323      *
1324      * @since 9
1325      */
1326     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2) {
1327         return new ImmutableCollections.MapN<>(k1, v1, k2, v2);
1328     }
1329 
1330     /**
1331      * Returns an unmodifiable map containing three mappings.
1332      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1333      *
1334      * @param <K> the {@code Map}'s key type
1335      * @param <V> the {@code Map}'s value type
1336      * @param k1 the first mapping's key
1337      * @param v1 the first mapping's value
1338      * @param k2 the second mapping's key
1339      * @param v2 the second mapping's value
1340      * @param k3 the third mapping's key
1341      * @param v3 the third mapping's value
1342      * @return a {@code Map} containing the specified mappings
1343      * @throws IllegalArgumentException if there are any duplicate keys
1344      * @throws NullPointerException if any key or value is {@code null}
1345      *
1346      * @since 9
1347      */
1348     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
1349         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3);
1350     }
1351 
1352     /**
1353      * Returns an unmodifiable map containing four mappings.
1354      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1355      *
1356      * @param <K> the {@code Map}'s key type
1357      * @param <V> the {@code Map}'s value type
1358      * @param k1 the first mapping's key
1359      * @param v1 the first mapping's value
1360      * @param k2 the second mapping's key
1361      * @param v2 the second mapping's value
1362      * @param k3 the third mapping's key
1363      * @param v3 the third mapping's value
1364      * @param k4 the fourth mapping's key
1365      * @param v4 the fourth mapping's value
1366      * @return a {@code Map} containing the specified mappings
1367      * @throws IllegalArgumentException if there are any duplicate keys
1368      * @throws NullPointerException if any key or value is {@code null}
1369      *
1370      * @since 9
1371      */
1372     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
1373         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4);
1374     }
1375 
1376     /**
1377      * Returns an unmodifiable map containing five mappings.
1378      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1379      *
1380      * @param <K> the {@code Map}'s key type
1381      * @param <V> the {@code Map}'s value type
1382      * @param k1 the first mapping's key
1383      * @param v1 the first mapping's value
1384      * @param k2 the second mapping's key
1385      * @param v2 the second mapping's value
1386      * @param k3 the third mapping's key
1387      * @param v3 the third mapping's value
1388      * @param k4 the fourth mapping's key
1389      * @param v4 the fourth mapping's value
1390      * @param k5 the fifth mapping's key
1391      * @param v5 the fifth mapping's value
1392      * @return a {@code Map} containing the specified mappings
1393      * @throws IllegalArgumentException if there are any duplicate keys
1394      * @throws NullPointerException if any key or value is {@code null}
1395      *
1396      * @since 9
1397      */
1398     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
1399         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
1400     }
1401 
1402     /**
1403      * Returns an unmodifiable map containing six mappings.
1404      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1405      *
1406      * @param <K> the {@code Map}'s key type
1407      * @param <V> the {@code Map}'s value type
1408      * @param k1 the first mapping's key
1409      * @param v1 the first mapping's value
1410      * @param k2 the second mapping's key
1411      * @param v2 the second mapping's value
1412      * @param k3 the third mapping's key
1413      * @param v3 the third mapping's value
1414      * @param k4 the fourth mapping's key
1415      * @param v4 the fourth mapping's value
1416      * @param k5 the fifth mapping's key
1417      * @param v5 the fifth mapping's value
1418      * @param k6 the sixth mapping's key
1419      * @param v6 the sixth mapping's value
1420      * @return a {@code Map} containing the specified mappings
1421      * @throws IllegalArgumentException if there are any duplicate keys
1422      * @throws NullPointerException if any key or value is {@code null}
1423      *
1424      * @since 9
1425      */
1426     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
1427                                K k6, V v6) {
1428         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1429                                                k6, v6);
1430     }
1431 
1432     /**
1433      * Returns an unmodifiable map containing seven mappings.
1434      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1435      *
1436      * @param <K> the {@code Map}'s key type
1437      * @param <V> the {@code Map}'s value type
1438      * @param k1 the first mapping's key
1439      * @param v1 the first mapping's value
1440      * @param k2 the second mapping's key
1441      * @param v2 the second mapping's value
1442      * @param k3 the third mapping's key
1443      * @param v3 the third mapping's value
1444      * @param k4 the fourth mapping's key
1445      * @param v4 the fourth mapping's value
1446      * @param k5 the fifth mapping's key
1447      * @param v5 the fifth mapping's value
1448      * @param k6 the sixth mapping's key
1449      * @param v6 the sixth mapping's value
1450      * @param k7 the seventh mapping's key
1451      * @param v7 the seventh mapping's value
1452      * @return a {@code Map} containing the specified mappings
1453      * @throws IllegalArgumentException if there are any duplicate keys
1454      * @throws NullPointerException if any key or value is {@code null}
1455      *
1456      * @since 9
1457      */
1458     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
1459                                K k6, V v6, K k7, V v7) {
1460         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1461                                                k6, v6, k7, v7);
1462     }
1463 
1464     /**
1465      * Returns an unmodifiable map containing eight mappings.
1466      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1467      *
1468      * @param <K> the {@code Map}'s key type
1469      * @param <V> the {@code Map}'s value type
1470      * @param k1 the first mapping's key
1471      * @param v1 the first mapping's value
1472      * @param k2 the second mapping's key
1473      * @param v2 the second mapping's value
1474      * @param k3 the third mapping's key
1475      * @param v3 the third mapping's value
1476      * @param k4 the fourth mapping's key
1477      * @param v4 the fourth mapping's value
1478      * @param k5 the fifth mapping's key
1479      * @param v5 the fifth mapping's value
1480      * @param k6 the sixth mapping's key
1481      * @param v6 the sixth mapping's value
1482      * @param k7 the seventh mapping's key
1483      * @param v7 the seventh mapping's value
1484      * @param k8 the eighth mapping's key
1485      * @param v8 the eighth mapping's value
1486      * @return a {@code Map} containing the specified mappings
1487      * @throws IllegalArgumentException if there are any duplicate keys
1488      * @throws NullPointerException if any key or value is {@code null}
1489      *
1490      * @since 9
1491      */
1492     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
1493                                K k6, V v6, K k7, V v7, K k8, V v8) {
1494         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1495                                                k6, v6, k7, v7, k8, v8);
1496     }
1497 
1498     /**
1499      * Returns an unmodifiable map containing nine mappings.
1500      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1501      *
1502      * @param <K> the {@code Map}'s key type
1503      * @param <V> the {@code Map}'s value type
1504      * @param k1 the first mapping's key
1505      * @param v1 the first mapping's value
1506      * @param k2 the second mapping's key
1507      * @param v2 the second mapping's value
1508      * @param k3 the third mapping's key
1509      * @param v3 the third mapping's value
1510      * @param k4 the fourth mapping's key
1511      * @param v4 the fourth mapping's value
1512      * @param k5 the fifth mapping's key
1513      * @param v5 the fifth mapping's value
1514      * @param k6 the sixth mapping's key
1515      * @param v6 the sixth mapping's value
1516      * @param k7 the seventh mapping's key
1517      * @param v7 the seventh mapping's value
1518      * @param k8 the eighth mapping's key
1519      * @param v8 the eighth mapping's value
1520      * @param k9 the ninth mapping's key
1521      * @param v9 the ninth mapping's value
1522      * @return a {@code Map} containing the specified mappings
1523      * @throws IllegalArgumentException if there are any duplicate keys
1524      * @throws NullPointerException if any key or value is {@code null}
1525      *
1526      * @since 9
1527      */
1528     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
1529                                K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9) {
1530         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1531                                                k6, v6, k7, v7, k8, v8, k9, v9);
1532     }
1533 
1534     /**
1535      * Returns an unmodifiable map containing ten mappings.
1536      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1537      *
1538      * @param <K> the {@code Map}'s key type
1539      * @param <V> the {@code Map}'s value type
1540      * @param k1 the first mapping's key
1541      * @param v1 the first mapping's value
1542      * @param k2 the second mapping's key
1543      * @param v2 the second mapping's value
1544      * @param k3 the third mapping's key
1545      * @param v3 the third mapping's value
1546      * @param k4 the fourth mapping's key
1547      * @param v4 the fourth mapping's value
1548      * @param k5 the fifth mapping's key
1549      * @param v5 the fifth mapping's value
1550      * @param k6 the sixth mapping's key
1551      * @param v6 the sixth mapping's value
1552      * @param k7 the seventh mapping's key
1553      * @param v7 the seventh mapping's value
1554      * @param k8 the eighth mapping's key
1555      * @param v8 the eighth mapping's value
1556      * @param k9 the ninth mapping's key
1557      * @param v9 the ninth mapping's value
1558      * @param k10 the tenth mapping's key
1559      * @param v10 the tenth mapping's value
1560      * @return a {@code Map} containing the specified mappings
1561      * @throws IllegalArgumentException if there are any duplicate keys
1562      * @throws NullPointerException if any key or value is {@code null}
1563      *
1564      * @since 9
1565      */
1566     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
1567                                K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9, K k10, V v10) {
1568         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1569                                                k6, v6, k7, v7, k8, v8, k9, v9, k10, v10);
1570     }
1571 
1572     /**
1573      * Returns an unmodifiable map containing keys and values extracted from the given entries.
1574      * The entries themselves are not stored in the map.
1575      * See <a href="#unmodifiable">Unmodifiable Maps</a> for details.
1576      *
1577      * @apiNote
1578      * It is convenient to create the map entries using the {@link Map#entry Map.entry()} method.
1579      * For example,
1580      *
1581      * <pre>{@code
1582      *     import static java.util.Map.entry;
1583      *
1584      *     Map<Integer,String> map = Map.ofEntries(
1585      *         entry(1, "a"),
1586      *         entry(2, "b"),
1587      *         entry(3, "c"),
1588      *         ...
1589      *         entry(26, "z"));
1590      * }</pre>
1591      *
1592      * @param <K> the {@code Map}'s key type
1593      * @param <V> the {@code Map}'s value type
1594      * @param entries {@code Map.Entry}s containing the keys and values from which the map is populated
1595      * @return a {@code Map} containing the specified mappings
1596      * @throws IllegalArgumentException if there are any duplicate keys
1597      * @throws NullPointerException if any entry, key, or value is {@code null}, or if
1598      *         the {@code entries} array is {@code null}
1599      *
1600      * @see Map#entry Map.entry()
1601      * @since 9
1602      */
1603     @SafeVarargs
1604     @SuppressWarnings("varargs")
1605     static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
1606         if (entries.length == 0) { // implicit null check of entries array
1607             return ImmutableCollections.emptyMap();
1608         } else if (entries.length == 1) {
1609             // implicit null check of the array slot
1610             return new ImmutableCollections.Map1<>(entries[0].getKey(),
1611                     entries[0].getValue());
1612         } else {
1613             Object[] kva = new Object[entries.length << 1];
1614             int a = 0;
1615             for (Entry<? extends K, ? extends V> entry : entries) {
1616                 // implicit null checks of each array slot
1617                 kva[a++] = entry.getKey();
1618                 kva[a++] = entry.getValue();
1619             }
1620             return new ImmutableCollections.MapN<>(kva);
1621         }
1622     }
1623 
1624     /**
1625      * Returns an unmodifiable {@link Entry} containing the given key and value.
1626      * These entries are suitable for populating {@code Map} instances using the
1627      * {@link Map#ofEntries Map.ofEntries()} method.
1628      * The {@code Entry} instances created by this method have the following characteristics:
1629      *
1630      * <ul>
1631      * <li>They disallow {@code null} keys and values. Attempts to create them using a {@code null}
1632      * key or value result in {@code NullPointerException}.
1633      * <li>They are unmodifiable. Calls to {@link Entry#setValue Entry.setValue()}
1634      * on a returned {@code Entry} result in {@code UnsupportedOperationException}.
1635      * <li>They are not serializable.
1636      * <li>They are <a href="../lang/doc-files/ValueBased.html">value-based</a>.
1637      * Callers should make no assumptions about the identity of the returned instances.
1638      * This method is free to create new instances or reuse existing ones. Therefore,
1639      * identity-sensitive operations on these instances (reference equality ({@code ==}),
1640      * identity hash code, and synchronization) are unreliable and should be avoided.
1641      * </ul>
1642      *
1643      * @apiNote
1644      * For a serializable {@code Entry}, see {@link AbstractMap.SimpleEntry} or
1645      * {@link AbstractMap.SimpleImmutableEntry}.
1646      *
1647      * @param <K> the key's type
1648      * @param <V> the value's type
1649      * @param k the key
1650      * @param v the value
1651      * @return an {@code Entry} containing the specified key and value
1652      * @throws NullPointerException if the key or value is {@code null}
1653      *
1654      * @see Map#ofEntries Map.ofEntries()
1655      * @since 9
1656      */
1657     static <K, V> Entry<K, V> entry(K k, V v) {
1658         // KeyValueHolder checks for nulls
1659         return new KeyValueHolder<>(k, v);
1660     }
1661 
1662     /**
1663      * Returns an <a href="#unmodifiable">unmodifiable Map</a> containing the entries
1664      * of the given Map. The given Map must not be null, and it must not contain any
1665      * null keys or values. If the given Map is subsequently modified, the returned
1666      * Map will not reflect such modifications.
1667      *
1668      * @implNote
1669      * If the given Map is an <a href="#unmodifiable">unmodifiable Map</a>,
1670      * calling copyOf will generally not create a copy.
1671      *
1672      * @param <K> the {@code Map}'s key type
1673      * @param <V> the {@code Map}'s value type
1674      * @param map a {@code Map} from which entries are drawn, must be non-null
1675      * @return a {@code Map} containing the entries of the given {@code Map}
1676      * @throws NullPointerException if map is null, or if it contains any null keys or values
1677      * @since 10
1678      */
1679     @SuppressWarnings({"rawtypes","unchecked"})
1680     static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map) {
1681         if (map instanceof ImmutableCollections.AbstractImmutableMap) {
1682             return (Map<K,V>)map;
1683         } else {
1684             return (Map<K,V>)Map.ofEntries(map.entrySet().toArray(new Entry[0]));
1685         }
1686     }
1687 }