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()))  &amp;&amp;
 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
1135      * implementations should override this method and, on a best-effort basis,
1136      * throw an {@code IllegalStateException} if it is detected that the
1137      * remapping function modifies this map during computation and as a result
1138      * computation would never complete.
1139      *
1140      * <p>The default implementation makes no guarantees about synchronization
1141      * or atomicity properties of this method. Any implementation providing
1142      * atomicity guarantees must override this method and document its
1143      * concurrency properties. In particular, all implementations of
1144      * subinterface {@link java.util.concurrent.ConcurrentMap} must document
1145      * whether the remapping function is applied once atomically only if the
1146      * value is not present.
1147      *
1148      * @param key key with which the specified value is to be associated
1149      * @param remappingFunction the remapping function to compute a value
1150      * @return the new value associated with the specified key, or null if none
1151      * @throws NullPointerException if the specified key is null and
1152      *         this map does not support null keys, or the
1153      *         remappingFunction is null
1154      * @throws UnsupportedOperationException if the {@code put} operation
1155      *         is not supported by this map
1156      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
1157      * @throws ClassCastException if the class of the specified key or value
1158      *         prevents it from being stored in this map
1159      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
1160      * @throws IllegalArgumentException if some property of the specified key
1161      *         or value prevents it from being stored in this map
1162      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
1163      * @since 1.8
1164      */
1165     default V compute(K key,
1166             BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
1167         Objects.requireNonNull(remappingFunction);
1168         V oldValue = get(key);
1169 
1170         V newValue = remappingFunction.apply(key, oldValue);
1171         if (newValue == null) {
1172             // delete mapping
1173             if (oldValue != null || containsKey(key)) {
1174                 // something to remove
1175                 remove(key);
1176                 return null;
1177             } else {
1178                 // nothing to do. Leave things as they were.
1179                 return null;
1180             }
1181         } else {
1182             // add or replace old mapping
1183             put(key, newValue);
1184             return newValue;
1185         }
1186     }
1187 
1188     /**
1189      * If the specified key is not already associated with a value or is
1190      * associated with null, associates it with the given non-null value.
1191      * Otherwise, replaces the associated value with the results of the given
1192      * remapping function, or removes if the result is {@code null}. This
1193      * method may be of use when combining multiple mapped values for a key.
1194      * For example, to either create or append a {@code String msg} to a
1195      * value mapping:
1196      *
1197      * <pre> {@code
1198      * map.merge(key, msg, String::concat)
1199      * }</pre>
1200      *
1201      * <p>If the remapping function returns {@code null}, the mapping is removed.
1202      * If the remapping function itself throws an (unchecked) exception, the
1203      * exception is rethrown, and the current mapping is left unchanged.
1204      *
1205      * <p>The remapping function should not modify this map during computation.
1206      *
1207      * @implSpec
1208      * The default implementation is equivalent to performing the following
1209      * steps for this {@code map}, then returning the current value or
1210      * {@code null} if absent:
1211      *
1212      * <pre> {@code
1213      * V oldValue = map.get(key);
1214      * V newValue = (oldValue == null) ? value :
1215      *              remappingFunction.apply(oldValue, value);
1216      * if (newValue == null)
1217      *     map.remove(key);
1218      * else
1219      *     map.put(key, newValue);
1220      * }</pre>
1221      *
1222      * <p>The default implementation makes no guarantees about detecting if the
1223      * remapping function modifies this map during computation and, if
1224      * appropriate, reporting an error. Non-concurrent implementations should
1225      * override this method and, on a best-effort basis, throw a
1226      * {@code ConcurrentModificationException} if it is detected that the
1227      * remapping function modifies this map during computation. Concurrent
1228      * implementations should override this method and, on a best-effort basis,
1229      * throw an {@code IllegalStateException} if it is detected that the
1230      * remapping function modifies this map during computation and as a result
1231      * computation would never complete.
1232      *
1233      * <p>The default implementation makes no guarantees about synchronization
1234      * or atomicity properties of this method. Any implementation providing
1235      * atomicity guarantees must override this method and document its
1236      * concurrency properties. In particular, all implementations of
1237      * subinterface {@link java.util.concurrent.ConcurrentMap} must document
1238      * whether the remapping function is applied once atomically only if the
1239      * value is not present.
1240      *
1241      * @param key key with which the resulting value is to be associated
1242      * @param value the non-null value to be merged with the existing value
1243      *        associated with the key or, if no existing value or a null value
1244      *        is associated with the key, to be associated with the key
1245      * @param remappingFunction the remapping function to recompute a value if
1246      *        present
1247      * @return the new value associated with the specified key, or null if no
1248      *         value is associated with the key
1249      * @throws UnsupportedOperationException if the {@code put} operation
1250      *         is not supported by this map
1251      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
1252      * @throws ClassCastException if the class of the specified key or value
1253      *         prevents it from being stored in this map
1254      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
1255      * @throws IllegalArgumentException if some property of the specified key
1256      *         or value prevents it from being stored in this map
1257      *         (<a href="{@docRoot}/java/util/Collection.html#optional-restrictions">optional</a>)
1258      * @throws NullPointerException if the specified key is null and this map
1259      *         does not support null keys or the value or remappingFunction is
1260      *         null
1261      * @since 1.8
1262      */
1263     default V merge(K key, V value,
1264             BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1265         Objects.requireNonNull(remappingFunction);
1266         Objects.requireNonNull(value);
1267         V oldValue = get(key);
1268         V newValue = (oldValue == null) ? value :
1269                    remappingFunction.apply(oldValue, value);
1270         if (newValue == null) {
1271             remove(key);
1272         } else {
1273             put(key, newValue);
1274         }
1275         return newValue;
1276     }
1277 
1278     /**
1279      * Returns an immutable map containing zero mappings.
1280      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1281      *
1282      * @param <K> the {@code Map}'s key type
1283      * @param <V> the {@code Map}'s value type
1284      * @return an empty {@code Map}
1285      *
1286      * @since 9
1287      */
1288     static <K, V> Map<K, V> of() {
1289         return ImmutableCollections.Map0.instance();
1290     }
1291 
1292     /**
1293      * Returns an immutable map containing a single mapping.
1294      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1295      *
1296      * @param <K> the {@code Map}'s key type
1297      * @param <V> the {@code Map}'s value type
1298      * @param k1 the mapping's key
1299      * @param v1 the mapping's value
1300      * @return a {@code Map} containing the specified mapping
1301      * @throws NullPointerException if the key or the value is {@code null}
1302      *
1303      * @since 9
1304      */
1305     static <K, V> Map<K, V> of(K k1, V v1) {
1306         return new ImmutableCollections.Map1<>(k1, v1);
1307     }
1308 
1309     /**
1310      * Returns an immutable map containing two mappings.
1311      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1312      *
1313      * @param <K> the {@code Map}'s key type
1314      * @param <V> the {@code Map}'s value type
1315      * @param k1 the first mapping's key
1316      * @param v1 the first mapping's value
1317      * @param k2 the second mapping's key
1318      * @param v2 the second mapping's value
1319      * @return a {@code Map} containing the specified mappings
1320      * @throws IllegalArgumentException if the keys are duplicates
1321      * @throws NullPointerException if any key or value is {@code null}
1322      *
1323      * @since 9
1324      */
1325     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2) {
1326         return new ImmutableCollections.MapN<>(k1, v1, k2, v2);
1327     }
1328 
1329     /**
1330      * Returns an immutable map containing three mappings.
1331      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1332      *
1333      * @param <K> the {@code Map}'s key type
1334      * @param <V> the {@code Map}'s value type
1335      * @param k1 the first mapping's key
1336      * @param v1 the first mapping's value
1337      * @param k2 the second mapping's key
1338      * @param v2 the second mapping's value
1339      * @param k3 the third mapping's key
1340      * @param v3 the third mapping's value
1341      * @return a {@code Map} containing the specified mappings
1342      * @throws IllegalArgumentException if there are any duplicate keys
1343      * @throws NullPointerException if any key or value is {@code null}
1344      *
1345      * @since 9
1346      */
1347     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
1348         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3);
1349     }
1350 
1351     /**
1352      * Returns an immutable map containing four mappings.
1353      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1354      *
1355      * @param <K> the {@code Map}'s key type
1356      * @param <V> the {@code Map}'s value type
1357      * @param k1 the first mapping's key
1358      * @param v1 the first mapping's value
1359      * @param k2 the second mapping's key
1360      * @param v2 the second mapping's value
1361      * @param k3 the third mapping's key
1362      * @param v3 the third mapping's value
1363      * @param k4 the fourth mapping's key
1364      * @param v4 the fourth mapping's value
1365      * @return a {@code Map} containing the specified mappings
1366      * @throws IllegalArgumentException if there are any duplicate keys
1367      * @throws NullPointerException if any key or value is {@code null}
1368      *
1369      * @since 9
1370      */
1371     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
1372         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4);
1373     }
1374 
1375     /**
1376      * Returns an immutable map containing five mappings.
1377      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1378      *
1379      * @param <K> the {@code Map}'s key type
1380      * @param <V> the {@code Map}'s value type
1381      * @param k1 the first mapping's key
1382      * @param v1 the first mapping's value
1383      * @param k2 the second mapping's key
1384      * @param v2 the second mapping's value
1385      * @param k3 the third mapping's key
1386      * @param v3 the third mapping's value
1387      * @param k4 the fourth mapping's key
1388      * @param v4 the fourth mapping's value
1389      * @param k5 the fifth mapping's key
1390      * @param v5 the fifth mapping's value
1391      * @return a {@code Map} containing the specified mappings
1392      * @throws IllegalArgumentException if there are any duplicate keys
1393      * @throws NullPointerException if any key or value is {@code null}
1394      *
1395      * @since 9
1396      */
1397     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) {
1398         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
1399     }
1400 
1401     /**
1402      * Returns an immutable map containing six mappings.
1403      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1404      *
1405      * @param <K> the {@code Map}'s key type
1406      * @param <V> the {@code Map}'s value type
1407      * @param k1 the first mapping's key
1408      * @param v1 the first mapping's value
1409      * @param k2 the second mapping's key
1410      * @param v2 the second mapping's value
1411      * @param k3 the third mapping's key
1412      * @param v3 the third mapping's value
1413      * @param k4 the fourth mapping's key
1414      * @param v4 the fourth mapping's value
1415      * @param k5 the fifth mapping's key
1416      * @param v5 the fifth mapping's value
1417      * @param k6 the sixth mapping's key
1418      * @param v6 the sixth mapping's value
1419      * @return a {@code Map} containing the specified mappings
1420      * @throws IllegalArgumentException if there are any duplicate keys
1421      * @throws NullPointerException if any key or value is {@code null}
1422      *
1423      * @since 9
1424      */
1425     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,
1426                                K k6, V v6) {
1427         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1428                                                k6, v6);
1429     }
1430 
1431     /**
1432      * Returns an immutable map containing seven mappings.
1433      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1434      *
1435      * @param <K> the {@code Map}'s key type
1436      * @param <V> the {@code Map}'s value type
1437      * @param k1 the first mapping's key
1438      * @param v1 the first mapping's value
1439      * @param k2 the second mapping's key
1440      * @param v2 the second mapping's value
1441      * @param k3 the third mapping's key
1442      * @param v3 the third mapping's value
1443      * @param k4 the fourth mapping's key
1444      * @param v4 the fourth mapping's value
1445      * @param k5 the fifth mapping's key
1446      * @param v5 the fifth mapping's value
1447      * @param k6 the sixth mapping's key
1448      * @param v6 the sixth mapping's value
1449      * @param k7 the seventh mapping's key
1450      * @param v7 the seventh mapping's value
1451      * @return a {@code Map} containing the specified mappings
1452      * @throws IllegalArgumentException if there are any duplicate keys
1453      * @throws NullPointerException if any key or value is {@code null}
1454      *
1455      * @since 9
1456      */
1457     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,
1458                                K k6, V v6, K k7, V v7) {
1459         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1460                                                k6, v6, k7, v7);
1461     }
1462 
1463     /**
1464      * Returns an immutable map containing eight mappings.
1465      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1466      *
1467      * @param <K> the {@code Map}'s key type
1468      * @param <V> the {@code Map}'s value type
1469      * @param k1 the first mapping's key
1470      * @param v1 the first mapping's value
1471      * @param k2 the second mapping's key
1472      * @param v2 the second mapping's value
1473      * @param k3 the third mapping's key
1474      * @param v3 the third mapping's value
1475      * @param k4 the fourth mapping's key
1476      * @param v4 the fourth mapping's value
1477      * @param k5 the fifth mapping's key
1478      * @param v5 the fifth mapping's value
1479      * @param k6 the sixth mapping's key
1480      * @param v6 the sixth mapping's value
1481      * @param k7 the seventh mapping's key
1482      * @param v7 the seventh mapping's value
1483      * @param k8 the eighth mapping's key
1484      * @param v8 the eighth mapping's value
1485      * @return a {@code Map} containing the specified mappings
1486      * @throws IllegalArgumentException if there are any duplicate keys
1487      * @throws NullPointerException if any key or value is {@code null}
1488      *
1489      * @since 9
1490      */
1491     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,
1492                                K k6, V v6, K k7, V v7, K k8, V v8) {
1493         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1494                                                k6, v6, k7, v7, k8, v8);
1495     }
1496 
1497     /**
1498      * Returns an immutable map containing nine mappings.
1499      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1500      *
1501      * @param <K> the {@code Map}'s key type
1502      * @param <V> the {@code Map}'s value type
1503      * @param k1 the first mapping's key
1504      * @param v1 the first mapping's value
1505      * @param k2 the second mapping's key
1506      * @param v2 the second mapping's value
1507      * @param k3 the third mapping's key
1508      * @param v3 the third mapping's value
1509      * @param k4 the fourth mapping's key
1510      * @param v4 the fourth mapping's value
1511      * @param k5 the fifth mapping's key
1512      * @param v5 the fifth mapping's value
1513      * @param k6 the sixth mapping's key
1514      * @param v6 the sixth mapping's value
1515      * @param k7 the seventh mapping's key
1516      * @param v7 the seventh mapping's value
1517      * @param k8 the eighth mapping's key
1518      * @param v8 the eighth mapping's value
1519      * @param k9 the ninth mapping's key
1520      * @param v9 the ninth mapping's value
1521      * @return a {@code Map} containing the specified mappings
1522      * @throws IllegalArgumentException if there are any duplicate keys
1523      * @throws NullPointerException if any key or value is {@code null}
1524      *
1525      * @since 9
1526      */
1527     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,
1528                                K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9) {
1529         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1530                                                k6, v6, k7, v7, k8, v8, k9, v9);
1531     }
1532 
1533     /**
1534      * Returns an immutable map containing ten mappings.
1535      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1536      *
1537      * @param <K> the {@code Map}'s key type
1538      * @param <V> the {@code Map}'s value type
1539      * @param k1 the first mapping's key
1540      * @param v1 the first mapping's value
1541      * @param k2 the second mapping's key
1542      * @param v2 the second mapping's value
1543      * @param k3 the third mapping's key
1544      * @param v3 the third mapping's value
1545      * @param k4 the fourth mapping's key
1546      * @param v4 the fourth mapping's value
1547      * @param k5 the fifth mapping's key
1548      * @param v5 the fifth mapping's value
1549      * @param k6 the sixth mapping's key
1550      * @param v6 the sixth mapping's value
1551      * @param k7 the seventh mapping's key
1552      * @param v7 the seventh mapping's value
1553      * @param k8 the eighth mapping's key
1554      * @param v8 the eighth mapping's value
1555      * @param k9 the ninth mapping's key
1556      * @param v9 the ninth mapping's value
1557      * @param k10 the tenth mapping's key
1558      * @param v10 the tenth mapping's value
1559      * @return a {@code Map} containing the specified mappings
1560      * @throws IllegalArgumentException if there are any duplicate keys
1561      * @throws NullPointerException if any key or value is {@code null}
1562      *
1563      * @since 9
1564      */
1565     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,
1566                                K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9, K k10, V v10) {
1567         return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
1568                                                k6, v6, k7, v7, k8, v8, k9, v9, k10, v10);
1569     }
1570 
1571     /**
1572      * Returns an immutable map containing keys and values extracted from the given entries.
1573      * The entries themselves are not stored in the map.
1574      * See <a href="#immutable">Immutable Map Static Factory Methods</a> for details.
1575      *
1576      * @apiNote
1577      * It is convenient to create the map entries using the {@link Map#entry Map.entry()} method.
1578      * For example,
1579      *
1580      * <pre>{@code
1581      *     import static java.util.Map.entry;
1582      *
1583      *     Map<Integer,String> map = Map.ofEntries(
1584      *         entry(1, "a"),
1585      *         entry(2, "b"),
1586      *         entry(3, "c"),
1587      *         ...
1588      *         entry(26, "z"));
1589      * }</pre>
1590      *
1591      * @param <K> the {@code Map}'s key type
1592      * @param <V> the {@code Map}'s value type
1593      * @param entries {@code Map.Entry}s containing the keys and values from which the map is populated
1594      * @return a {@code Map} containing the specified mappings
1595      * @throws IllegalArgumentException if there are any duplicate keys
1596      * @throws NullPointerException if any entry, key, or value is {@code null}, or if
1597      *         the {@code entries} array is {@code null}
1598      *
1599      * @see Map#entry Map.entry()
1600      * @since 9
1601      */
1602     @SafeVarargs
1603     @SuppressWarnings("varargs")
1604     static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
1605         if (entries.length == 0) { // implicit null check of entries
1606             return ImmutableCollections.Map0.instance();
1607         } else if (entries.length == 1) {
1608             return new ImmutableCollections.Map1<>(entries[0].getKey(),
1609                                                    entries[0].getValue());
1610         } else {
1611             Object[] kva = new Object[entries.length << 1];
1612             int a = 0;
1613             for (Entry<? extends K, ? extends V> entry : entries) {
1614                 kva[a++] = entry.getKey();
1615                 kva[a++] = entry.getValue();
1616             }
1617             return new ImmutableCollections.MapN<>(kva);
1618         }
1619     }
1620 
1621     /**
1622      * Returns an immutable {@link Entry} containing the given key and value.
1623      * These entries are suitable for populating {@code Map} instances using the
1624      * {@link Map#ofEntries Map.ofEntries()} method.
1625      * The {@code Entry} instances created by this method have the following characteristics:
1626      *
1627      * <ul>
1628      * <li>They disallow {@code null} keys and values. Attempts to create them using a {@code null}
1629      * key or value result in {@code NullPointerException}.
1630      * <li>They are immutable. Calls to {@link Entry#setValue Entry.setValue()}
1631      * on a returned {@code Entry} result in {@code UnsupportedOperationException}.
1632      * <li>They are not serializable.
1633      * <li>They are <a href="../lang/doc-files/ValueBased.html">value-based</a>.
1634      * Callers should make no assumptions about the identity of the returned instances.
1635      * This method is free to create new instances or reuse existing ones. Therefore,
1636      * identity-sensitive operations on these instances (reference equality ({@code ==}),
1637      * identity hash code, and synchronization) are unreliable and should be avoided.
1638      * </ul>
1639      *
1640      * @apiNote
1641      * For a serializable {@code Entry}, see {@link AbstractMap.SimpleEntry} or
1642      * {@link AbstractMap.SimpleImmutableEntry}.
1643      *
1644      * @param <K> the key's type
1645      * @param <V> the value's type
1646      * @param k the key
1647      * @param v the value
1648      * @return an {@code Entry} containing the specified key and value
1649      * @throws NullPointerException if the key or value is {@code null}
1650      *
1651      * @see Map#ofEntries Map.ofEntries()
1652      * @since 9
1653      */
1654     static <K, V> Entry<K, V> entry(K k, V v) {
1655         // KeyValueHolder checks for nulls
1656         return new KeyValueHolder<>(k, v);
1657     }
1658 }