1 /*
   2  * Copyright (c) 1997, 2013, 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 
  32 /**
  33  * An object that maps keys to values.  A map cannot contain duplicate keys;
  34  * each key can map to at most one value.
  35  *
  36  * <p>This interface takes the place of the <tt>Dictionary</tt> class, which
  37  * was a totally abstract class rather than an interface.
  38  *
  39  * <p>The <tt>Map</tt> interface provides three <i>collection views</i>, which
  40  * allow a map's contents to be viewed as a set of keys, collection of values,
  41  * or set of key-value mappings.  The <i>order</i> of a map is defined as
  42  * the order in which the iterators on the map's collection views return their
  43  * elements.  Some map implementations, like the <tt>TreeMap</tt> class, make
  44  * specific guarantees as to their order; others, like the <tt>HashMap</tt>
  45  * class, do not.
  46  *
  47  * <p>Note: great care must be exercised if mutable objects are used as map
  48  * keys.  The behavior of a map is not specified if the value of an object is
  49  * changed in a manner that affects <tt>equals</tt> comparisons while the
  50  * object is a key in the map.  A special case of this prohibition is that it
  51  * is not permissible for a map to contain itself as a key.  While it is
  52  * permissible for a map to contain itself as a value, extreme caution is
  53  * advised: the <tt>equals</tt> and <tt>hashCode</tt> methods are no longer
  54  * well defined on such a map.
  55  *
  56  * <p>All general-purpose map implementation classes should provide two
  57  * "standard" constructors: a void (no arguments) constructor which creates an
  58  * empty map, and a constructor with a single argument of type <tt>Map</tt>,
  59  * which creates a new map with the same key-value mappings as its argument.
  60  * In effect, the latter constructor allows the user to copy any map,
  61  * producing an equivalent map of the desired class.  There is no way to
  62  * enforce this recommendation (as interfaces cannot contain constructors) but
  63  * all of the general-purpose map implementations in the JDK comply.
  64  *
  65  * <p>The "destructive" methods contained in this interface, that is, the
  66  * methods that modify the map on which they operate, are specified to throw
  67  * <tt>UnsupportedOperationException</tt> if this map does not support the
  68  * operation.  If this is the case, these methods may, but are not required
  69  * to, throw an <tt>UnsupportedOperationException</tt> if the invocation would
  70  * have no effect on the map.  For example, invoking the {@link #putAll(Map)}
  71  * method on an unmodifiable map may, but is not required to, throw the
  72  * exception if the map whose mappings are to be "superimposed" is empty.
  73  *
  74  * <p>Some map implementations have restrictions on the keys and values they
  75  * may contain.  For example, some implementations prohibit null keys and
  76  * values, and some have restrictions on the types of their keys.  Attempting
  77  * to insert an ineligible key or value throws an unchecked exception,
  78  * typically <tt>NullPointerException</tt> or <tt>ClassCastException</tt>.
  79  * Attempting to query the presence of an ineligible key or value may throw an
  80  * exception, or it may simply return false; some implementations will exhibit
  81  * the former behavior and some will exhibit the latter.  More generally,
  82  * attempting an operation on an ineligible key or value whose completion
  83  * would not result in the insertion of an ineligible element into the map may
  84  * throw an exception or it may succeed, at the option of the implementation.
  85  * Such exceptions are marked as "optional" in the specification for this
  86  * interface.
  87  *
  88  * <p>This interface is a member of the
  89  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  90  * Java Collections Framework</a>.
  91  *
  92  * <p>Many methods in Collections Framework interfaces are defined
  93  * in terms of the {@link Object#equals(Object) equals} method.  For
  94  * example, the specification for the {@link #containsKey(Object)
  95  * containsKey(Object key)} method says: "returns <tt>true</tt> if and
  96  * only if this map contains a mapping for a key <tt>k</tt> such that
  97  * <tt>(key==null ? k==null : key.equals(k))</tt>." This specification should
  98  * <i>not</i> be construed to imply that invoking <tt>Map.containsKey</tt>
  99  * with a non-null argument <tt>key</tt> will cause <tt>key.equals(k)</tt> to
 100  * be invoked for any key <tt>k</tt>.  Implementations are free to
 101  * implement optimizations whereby the <tt>equals</tt> invocation is avoided,
 102  * for example, by first comparing the hash codes of the two keys.  (The
 103  * {@link Object#hashCode()} specification guarantees that two objects with
 104  * unequal hash codes cannot be equal.)  More generally, implementations of
 105  * the various Collections Framework interfaces are free to take advantage of
 106  * the specified behavior of underlying {@link Object} methods wherever the
 107  * implementor deems it appropriate.
 108  *
 109  * @param <K> the type of keys maintained by this map
 110  * @param <V> the type of mapped values
 111  *
 112  * @author  Josh Bloch
 113  * @see HashMap
 114  * @see TreeMap
 115  * @see Hashtable
 116  * @see SortedMap
 117  * @see Collection
 118  * @see Set
 119  * @since 1.2
 120  */
 121 public interface Map<K,V> {
 122     // Query Operations
 123 
 124     /**
 125      * Returns the number of key-value mappings in this map.  If the
 126      * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
 127      * <tt>Integer.MAX_VALUE</tt>.
 128      *
 129      * @return the number of key-value mappings in this map
 130      */
 131     int size();
 132 
 133     /**
 134      * Returns <tt>true</tt> if this map contains no key-value mappings.
 135      *
 136      * @return <tt>true</tt> if this map contains no key-value mappings
 137      */
 138     boolean isEmpty();
 139 
 140     /**
 141      * Returns <tt>true</tt> if this map contains a mapping for the specified
 142      * key.  More formally, returns <tt>true</tt> if and only if
 143      * this map contains a mapping for a key <tt>k</tt> such that
 144      * <tt>(key==null ? k==null : key.equals(k))</tt>.  (There can be
 145      * at most one such mapping.)
 146      *
 147      * @param key key whose presence in this map is to be tested
 148      * @return <tt>true</tt> if this map contains a mapping for the specified
 149      *         key
 150      * @throws ClassCastException if the key is of an inappropriate type for
 151      *         this map
 152      * (<a href="Collection.html#optional-restrictions">optional</a>)
 153      * @throws NullPointerException if the specified key is null and this map
 154      *         does not permit null keys
 155      * (<a href="Collection.html#optional-restrictions">optional</a>)
 156      */
 157     boolean containsKey(Object key);
 158 
 159     /**
 160      * Returns <tt>true</tt> if this map maps one or more keys to the
 161      * specified value.  More formally, returns <tt>true</tt> if and only if
 162      * this map contains at least one mapping to a value <tt>v</tt> such that
 163      * <tt>(value==null ? v==null : value.equals(v))</tt>.  This operation
 164      * will probably require time linear in the map size for most
 165      * implementations of the <tt>Map</tt> interface.
 166      *
 167      * @param value value whose presence in this map is to be tested
 168      * @return <tt>true</tt> if this map maps one or more keys to the
 169      *         specified value
 170      * @throws ClassCastException if the value is of an inappropriate type for
 171      *         this map
 172      * (<a href="Collection.html#optional-restrictions">optional</a>)
 173      * @throws NullPointerException if the specified value is null and this
 174      *         map does not permit null values
 175      * (<a href="Collection.html#optional-restrictions">optional</a>)
 176      */
 177     boolean containsValue(Object value);
 178 
 179     /**
 180      * Returns the value to which the specified key is mapped,
 181      * or {@code null} if this map contains no mapping for the key.
 182      *
 183      * <p>More formally, if this map contains a mapping from a key
 184      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 185      * key.equals(k))}, then this method returns {@code v}; otherwise
 186      * it returns {@code null}.  (There can be at most one such mapping.)
 187      *
 188      * <p>If this map permits null values, then a return value of
 189      * {@code null} does not <i>necessarily</i> indicate that the map
 190      * contains no mapping for the key; it's also possible that the map
 191      * explicitly maps the key to {@code null}.  The {@link #containsKey
 192      * containsKey} operation may be used to distinguish these two cases.
 193      *
 194      * @param key the key whose associated value is to be returned
 195      * @return the value to which the specified key is mapped, or
 196      *         {@code null} if this map contains no mapping for the key
 197      * @throws ClassCastException if the key is of an inappropriate type for
 198      *         this map
 199      * (<a href="Collection.html#optional-restrictions">optional</a>)
 200      * @throws NullPointerException if the specified key is null and this map
 201      *         does not permit null keys
 202      * (<a href="Collection.html#optional-restrictions">optional</a>)
 203      */
 204     V get(Object key);
 205 
 206     // Modification Operations
 207 
 208     /**
 209      * Associates the specified value with the specified key in this map
 210      * (optional operation).  If the map previously contained a mapping for
 211      * the key, the old value is replaced by the specified value.  (A map
 212      * <tt>m</tt> is said to contain a mapping for a key <tt>k</tt> if and only
 213      * if {@link #containsKey(Object) m.containsKey(k)} would return
 214      * <tt>true</tt>.)
 215      *
 216      * @param key key with which the specified value is to be associated
 217      * @param value value to be associated with the specified key
 218      * @return the previous value associated with <tt>key</tt>, or
 219      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 220      *         (A <tt>null</tt> return can also indicate that the map
 221      *         previously associated <tt>null</tt> with <tt>key</tt>,
 222      *         if the implementation supports <tt>null</tt> values.)
 223      * @throws UnsupportedOperationException if the <tt>put</tt> operation
 224      *         is not supported by this map
 225      * @throws ClassCastException if the class of the specified key or value
 226      *         prevents it from being stored in this map
 227      * @throws NullPointerException if the specified key or value is null
 228      *         and this map does not permit null keys or values
 229      * @throws IllegalArgumentException if some property of the specified key
 230      *         or value prevents it from being stored in this map
 231      */
 232     V put(K key, V value);
 233 
 234     /**
 235      * Removes the mapping for a key from this map if it is present
 236      * (optional operation).   More formally, if this map contains a mapping
 237      * from key <tt>k</tt> to value <tt>v</tt> such that
 238      * <code>(key==null ?  k==null : key.equals(k))</code>, that mapping
 239      * is removed.  (The map can contain at most one such mapping.)
 240      *
 241      * <p>Returns the value to which this map previously associated the key,
 242      * or <tt>null</tt> if the map contained no mapping for the key.
 243      *
 244      * <p>If this map permits null values, then a return value of
 245      * <tt>null</tt> does not <i>necessarily</i> indicate that the map
 246      * contained no mapping for the key; it's also possible that the map
 247      * explicitly mapped the key to <tt>null</tt>.
 248      *
 249      * <p>The map will not contain a mapping for the specified key once the
 250      * call returns.
 251      *
 252      * @param key key whose mapping is to be removed from the map
 253      * @return the previous value associated with <tt>key</tt>, or
 254      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 255      * @throws UnsupportedOperationException if the <tt>remove</tt> operation
 256      *         is not supported by this map
 257      * @throws ClassCastException if the key is of an inappropriate type for
 258      *         this map
 259      * (<a href="Collection.html#optional-restrictions">optional</a>)
 260      * @throws NullPointerException if the specified key is null and this
 261      *         map does not permit null keys
 262      * (<a href="Collection.html#optional-restrictions">optional</a>)
 263      */
 264     V remove(Object key);
 265 
 266 
 267     // Bulk Operations
 268 
 269     /**
 270      * Copies all of the mappings from the specified map to this map
 271      * (optional operation).  The effect of this call is equivalent to that
 272      * of calling {@link #put(Object,Object) put(k, v)} on this map once
 273      * for each mapping from key <tt>k</tt> to value <tt>v</tt> in the
 274      * specified map.  The behavior of this operation is undefined if the
 275      * specified map is modified while the operation is in progress.
 276      *
 277      * @param m mappings to be stored in this map
 278      * @throws UnsupportedOperationException if the <tt>putAll</tt> operation
 279      *         is not supported by this map
 280      * @throws ClassCastException if the class of a key or value in the
 281      *         specified map prevents it from being stored in this map
 282      * @throws NullPointerException if the specified map is null, or if
 283      *         this map does not permit null keys or values, and the
 284      *         specified map contains null keys or values
 285      * @throws IllegalArgumentException if some property of a key or value in
 286      *         the specified map prevents it from being stored in this map
 287      */
 288     void putAll(Map<? extends K, ? extends V> m);
 289 
 290     /**
 291      * Removes all of the mappings from this map (optional operation).
 292      * The map will be empty after this call returns.
 293      *
 294      * @throws UnsupportedOperationException if the <tt>clear</tt> operation
 295      *         is not supported by this map
 296      */
 297     void clear();
 298 
 299 
 300     // Views
 301 
 302     /**
 303      * Returns a {@link Set} view of the keys contained in this map.
 304      * The set is backed by the map, so changes to the map are
 305      * reflected in the set, and vice-versa.  If the map is modified
 306      * while an iteration over the set is in progress (except through
 307      * the iterator's own <tt>remove</tt> operation), the results of
 308      * the iteration are undefined.  The set supports element removal,
 309      * which removes the corresponding mapping from the map, via the
 310      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 311      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 312      * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
 313      * operations.
 314      *
 315      * @return a set view of the keys contained in this map
 316      */
 317     Set<K> keySet();
 318 
 319     /**
 320      * Returns a {@link Collection} view of the values contained in this map.
 321      * The collection is backed by the map, so changes to the map are
 322      * reflected in the collection, and vice-versa.  If the map is
 323      * modified while an iteration over the collection is in progress
 324      * (except through the iterator's own <tt>remove</tt> operation),
 325      * the results of the iteration are undefined.  The collection
 326      * supports element removal, which removes the corresponding
 327      * mapping from the map, via the <tt>Iterator.remove</tt>,
 328      * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 329      * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
 330      * support the <tt>add</tt> or <tt>addAll</tt> operations.
 331      *
 332      * @return a collection view of the values contained in this map
 333      */
 334     Collection<V> values();
 335 
 336     /**
 337      * Returns a {@link Set} view of the mappings contained in this map.
 338      * The set is backed by the map, so changes to the map are
 339      * reflected in the set, and vice-versa.  If the map is modified
 340      * while an iteration over the set is in progress (except through
 341      * the iterator's own <tt>remove</tt> operation, or through the
 342      * <tt>setValue</tt> operation on a map entry returned by the
 343      * iterator) the results of the iteration are undefined.  The set
 344      * supports element removal, which removes the corresponding
 345      * mapping from the map, via the <tt>Iterator.remove</tt>,
 346      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
 347      * <tt>clear</tt> operations.  It does not support the
 348      * <tt>add</tt> or <tt>addAll</tt> operations.
 349      *
 350      * @return a set view of the mappings contained in this map
 351      */
 352     Set<Map.Entry<K, V>> entrySet();
 353 
 354     /**
 355      * A map entry (key-value pair).  The <tt>Map.entrySet</tt> method returns
 356      * a collection-view of the map, whose elements are of this class.  The
 357      * <i>only</i> way to obtain a reference to a map entry is from the
 358      * iterator of this collection-view.  These <tt>Map.Entry</tt> objects are
 359      * valid <i>only</i> for the duration of the iteration; more formally,
 360      * the behavior of a map entry is undefined if the backing map has been
 361      * modified after the entry was returned by the iterator, except through
 362      * the <tt>setValue</tt> operation on the map entry.
 363      *
 364      * @see Map#entrySet()
 365      * @since 1.2
 366      */
 367     interface Entry<K,V> {
 368         /**
 369          * Returns the key corresponding to this entry.
 370          *
 371          * @return the key corresponding to this entry
 372          * @throws IllegalStateException implementations may, but are not
 373          *         required to, throw this exception if the entry has been
 374          *         removed from the backing map.
 375          */
 376         K getKey();
 377 
 378         /**
 379          * Returns the value corresponding to this entry.  If the mapping
 380          * has been removed from the backing map (by the iterator's
 381          * <tt>remove</tt> operation), the results of this call are undefined.
 382          *
 383          * @return the value corresponding to this entry
 384          * @throws IllegalStateException implementations may, but are not
 385          *         required to, throw this exception if the entry has been
 386          *         removed from the backing map.
 387          */
 388         V getValue();
 389 
 390         /**
 391          * Replaces the value corresponding to this entry with the specified
 392          * value (optional operation).  (Writes through to the map.)  The
 393          * behavior of this call is undefined if the mapping has already been
 394          * removed from the map (by the iterator's <tt>remove</tt> operation).
 395          *
 396          * @param value new value to be stored in this entry
 397          * @return old value corresponding to the entry
 398          * @throws UnsupportedOperationException if the <tt>put</tt> operation
 399          *         is not supported by the backing map
 400          * @throws ClassCastException if the class of the specified value
 401          *         prevents it from being stored in the backing map
 402          * @throws NullPointerException if the backing map does not permit
 403          *         null values, and the specified value is null
 404          * @throws IllegalArgumentException if some property of this value
 405          *         prevents it from being stored in the backing map
 406          * @throws IllegalStateException implementations may, but are not
 407          *         required to, throw this exception if the entry has been
 408          *         removed from the backing map.
 409          */
 410         V setValue(V value);
 411 
 412         /**
 413          * Compares the specified object with this entry for equality.
 414          * Returns <tt>true</tt> if the given object is also a map entry and
 415          * the two entries represent the same mapping.  More formally, two
 416          * entries <tt>e1</tt> and <tt>e2</tt> represent the same mapping
 417          * if<pre>
 418          *     (e1.getKey()==null ?
 419          *      e2.getKey()==null : e1.getKey().equals(e2.getKey()))  &amp;&amp;
 420          *     (e1.getValue()==null ?
 421          *      e2.getValue()==null : e1.getValue().equals(e2.getValue()))
 422          * </pre>
 423          * This ensures that the <tt>equals</tt> method works properly across
 424          * different implementations of the <tt>Map.Entry</tt> interface.
 425          *
 426          * @param o object to be compared for equality with this map entry
 427          * @return <tt>true</tt> if the specified object is equal to this map
 428          *         entry
 429          */
 430         boolean equals(Object o);
 431 
 432         /**
 433          * Returns the hash code value for this map entry.  The hash code
 434          * of a map entry <tt>e</tt> is defined to be: <pre>
 435          *     (e.getKey()==null   ? 0 : e.getKey().hashCode()) ^
 436          *     (e.getValue()==null ? 0 : e.getValue().hashCode())
 437          * </pre>
 438          * This ensures that <tt>e1.equals(e2)</tt> implies that
 439          * <tt>e1.hashCode()==e2.hashCode()</tt> for any two Entries
 440          * <tt>e1</tt> and <tt>e2</tt>, as required by the general
 441          * contract of <tt>Object.hashCode</tt>.
 442          *
 443          * @return the hash code value for this map entry
 444          * @see Object#hashCode()
 445          * @see Object#equals(Object)
 446          * @see #equals(Object)
 447          */
 448         int hashCode();
 449     }
 450 
 451     // Comparison and hashing
 452 
 453     /**
 454      * Compares the specified object with this map for equality.  Returns
 455      * <tt>true</tt> if the given object is also a map and the two maps
 456      * represent the same mappings.  More formally, two maps <tt>m1</tt> and
 457      * <tt>m2</tt> represent the same mappings if
 458      * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the
 459      * <tt>equals</tt> method works properly across different implementations
 460      * of the <tt>Map</tt> interface.
 461      *
 462      * @param o object to be compared for equality with this map
 463      * @return <tt>true</tt> if the specified object is equal to this map
 464      */
 465     boolean equals(Object o);
 466 
 467     /**
 468      * Returns the hash code value for this map.  The hash code of a map is
 469      * defined to be the sum of the hash codes of each entry in the map's
 470      * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>
 471      * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps
 472      * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of
 473      * {@link Object#hashCode}.
 474      *
 475      * @return the hash code value for this map
 476      * @see Map.Entry#hashCode()
 477      * @see Object#equals(Object)
 478      * @see #equals(Object)
 479      */
 480     int hashCode();
 481 
 482     // Defaultable methods
 483 
 484     /**
 485     *  Returns the value to which the specified key is mapped,
 486     *  or {@code defaultValue} if this map contains no mapping
 487     *  for the key.
 488     *
 489     * @param key the key whose associated value is to be returned
 490     * @return the value to which the specified key is mapped, or
 491     * {@code defaultValue} if this map contains no mapping for the key
 492     * @throws ClassCastException if the key is of an inappropriate type for
 493     * this map
 494     * (<a href="Collection.html#optional-restrictions">optional</a>)
 495     * @throws NullPointerException if the specified key is null and this map
 496     * does not permit null keys
 497     * (<a href="Collection.html#optional-restrictions">optional</a>)
 498     */
 499     default V getOrDefault(Object key, V defaultValue) {
 500         V v;
 501         return (((v = get(key)) != null) || containsKey(key))
 502             ? v
 503             : defaultValue;
 504     }
 505 
 506     /**
 507      * Performs the given action on each entry in this map, in the
 508      * order entries are returned by an entry set iterator, until all entries
 509      * have been processed or the action throws an {@code Exception}.
 510      * Exceptions thrown by the action are relayed to the caller.
 511      *
 512      * <p>The default implementation should be overridden by implementations if
 513      * they can provide a more performant implementation than an iterator-based
 514      * one.
 515      *
 516      * <p>The default implementation makes no guarantees about synchronization
 517      * or atomicity properties of this method. Any class which wishes to provide
 518      * specific synchronization, atomicity or concurrency behaviour should
 519      * override this method.
 520      *
 521      * @implSpec The default implementation is equivalent to, for this
 522      * {@code map}:
 523      * <pre> {@code
 524      *     for ((Map.Entry<K, V> entry : map.entrySet())
 525      *         action.accept(entry.getKey(), entry.getValue());
 526      * }</pre>
 527      *
 528      * @param action The action to be performed for each entry
 529      * @throws NullPointerException if the specified action is null
 530      * @throws ConcurrentModificationException if an entry is found to be
 531      * removed during iteration
 532      * @since 1.8
 533      */
 534     default void forEach(BiConsumer<? super K, ? super V> action) {
 535         Objects.requireNonNull(action);
 536         for (Map.Entry<K, V> entry : entrySet()) {
 537             K k;
 538             V v;
 539             try {
 540                k = entry.getKey();
 541                v = entry.getValue();
 542             } catch(IllegalStateException ise) {
 543                 throw new ConcurrentModificationException(ise);
 544             }
 545             action.accept(k, v);
 546         }
 547     }
 548 
 549     /**
 550      * Replaces each entry's value with the result of invoking the given
 551      * function on that entry, in the order entries are returned by an entry
 552      * set iterator, until all entries have been processed or the function
 553      * throws an exception.
 554      *
 555      * <p>The default implementation makes no guarantees about synchronization
 556      * or atomicity properties of this method. Any class which wishes to provide
 557      * specific synchronization, atomicity or concurrency behaviour should
 558      * override this method.
 559      *
 560      * @implSpec
 561      * <p>The default implementation is equivalent to, for this {@code map}:
 562      * <pre> {@code
 563      *     for ((Map.Entry<K, V> entry : map.entrySet())
 564      *         entry.setValue(function.apply(entry.getKey(), entry.getValue()));
 565      * }</pre>
 566      *
 567      * @param function the function to apply to each entry
 568      * @throws UnsupportedOperationException if the <tt>set</tt> operation
 569      * is not supported by this map's entry set iterator.
 570      * @throws ClassCastException if the class of a replacement value
 571      * prevents it from being stored in this map
 572      * @throws NullPointerException if the specified function is null, or the
 573      * specified replacement value is null, and this map does not permit null
 574      * values
 575      * @throws ClassCastException if a replacement value is of an inappropriate
 576      *         type for this map
 577      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 578      * @throws NullPointerException if function or a replacement value is null,
 579      *         and this map does not permit null keys or values
 580      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 581      * @throws IllegalArgumentException if some property of a replacement value
 582      *         prevents it from being stored in this map
 583      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 584      * @throws ConcurrentModificationException if an entry is found to be
 585      * removed during iteration
 586      * @since 1.8
 587      */
 588     default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
 589         Objects.requireNonNull(function);
 590         for (Map.Entry<K, V> entry : entrySet()) {
 591             K k;
 592             V v;
 593             try {
 594                k = entry.getKey();
 595                v = entry.getValue();
 596             } catch(IllegalStateException ise) {
 597                 throw new ConcurrentModificationException(ise);
 598             }
 599             entry.setValue(function.apply(k, v));
 600         }
 601     }
 602 
 603     /**
 604      * If the specified key is not already associated with a value (or is mapped
 605      * to {@code null}) associates it with the given value and returns
 606      * {@code null}, else returns the current value.
 607      *
 608      * <p>The default implementation makes no guarantees about
 609      * synchronization or atomicity properties of this method. Any
 610      * class overriding this method must specify its concurrency
 611      * properties. In particular, all implementations of
 612      * subinterface {@link java.util.concurrent.ConcurrentMap}
 613      * must ensure that this operation is performed atomically.
 614      *
 615      * @implSpec
 616      * The default implementation is equivalent to, for this {@code
 617      * map}:
 618      *
 619      *  <pre> {@code
 620      * if (map.get(key) == null)
 621      *   return map.put(key, value);
 622      * else
 623      *   return map.get(key);}</pre>
 624      *
 625      * @param key key with which the specified value is to be associated
 626      * @param value value to be associated with the specified key
 627      * @return the previous value associated with the specified key, or
 628      *         {@code 1} if there was no mapping for the key.
 629      *         (A <tt>null</tt> return can also indicate that the map
 630      *         previously associated <tt>null</tt> with the key,
 631      *         if the implementation supports null values.)
 632      * @throws UnsupportedOperationException if the <tt>put</tt> operation
 633      *         is not supported by this map
 634      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 635      * @throws ClassCastException if the key or value is of an inappropriate
 636      *         type for this map
 637      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 638      * @throws NullPointerException if the specified key or value is null,
 639      *         and this map does not permit null keys or values
 640      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 641      * @throws IllegalArgumentException if some property of the specified key
 642      *         or value prevents it from being stored in this map
 643      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 644      * @throws ConcurrentModificationException if a modification of the map is
 645      * detected during insertion of the value.
 646      * @since 1.8
 647      */
 648     default V putIfAbsent(K key, V value) {
 649         V v = get(key);
 650         if (v == null) {
 651             if (put(key, value) != null) {
 652                 throw new ConcurrentModificationException();
 653             }
 654         }
 655 
 656         return v;
 657     }
 658 
 659     /**
 660      * Removes the entry for the specified key only if it is currently
 661      * mapped to the specified value.
 662      *
 663      * <p>The default implementation makes no guarantees about
 664      * synchronization or atomicity properties of this method. Any
 665      * class overriding this method must specify its concurrency
 666      * properties. In particular, all implementations of
 667      * subinterface {@link java.util.concurrent.ConcurrentMap}
 668      * must ensure that this operation is performed atomically.
 669      *
 670      * @implSpec
 671      * The default implementation is equivalent to, for this {@code map}:
 672      *
 673      * <pre> {@code
 674      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
 675      *   map.remove(key);
 676      *   return true;
 677      * } else
 678      *   return false;}</pre>
 679      *
 680      * @param key key with which the specified value is associated
 681      * @param value value expected to be associated with the specified key
 682      * @return <tt>true</tt> if the value was removed
 683      * @throws UnsupportedOperationException if the <tt>remove</tt> operation
 684      *         is not supported by this map
 685      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 686      * @throws ClassCastException if the key or value is of an inappropriate
 687      *         type for this map
 688      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 689      * @throws NullPointerException if the specified key or value is null,
 690      *         and this map does not permit null keys or values
 691      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 692      * @since 1.8
 693      */
 694     default boolean remove(Object key, Object value) {
 695         if (!Objects.equals(get(key), value) || !containsKey(key))
 696             return false;
 697         remove(key);
 698         return true;
 699     }
 700 
 701     /**
 702      * Replaces the entry for the specified key only if currently
 703      * mapped to the specified value.
 704      *
 705      * <p>The default implementation makes no guarantees about
 706      * synchronization or atomicity properties of this method. Any
 707      * class overriding this method must specify its concurrency
 708      * properties. In particular, all implementations of
 709      * subinterface {@link java.util.concurrent.ConcurrentMap}
 710      * must ensure that this operation is performed atomically.
 711      *
 712      * @implSpec
 713      * The default implementation is equivalent to, for this {@code map}:
 714      *
 715      * <pre> {@code
 716      * if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
 717      *   map.put(key, newValue);
 718      *   return true;
 719      * } else
 720      *   return false;}</pre>
 721      *
 722      * @param key key with which the specified value is associated
 723      * @param oldValue value expected to be associated with the specified key
 724      * @param newValue value to be associated with the specified key
 725      * @return <tt>true</tt> if the value was replaced
 726      * @throws UnsupportedOperationException if the <tt>put</tt> operation
 727      *         is not supported by this map
 728      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 729      * @throws ClassCastException if the class of a specified key or value
 730      *         prevents it from being stored in this map
 731      * @throws NullPointerException if a specified key or value is null,
 732      *         and this map does not permit null keys or values
 733      * @throws IllegalArgumentException if some property of a specified key
 734      *         or value prevents it from being stored in this map
 735      * @since 1.8
 736      */
 737     default boolean replace(K key, V oldValue, V newValue) {
 738         if (!containsKey(key) || !Objects.equals(get(key), oldValue))
 739             return false;
 740         put(key, newValue);
 741         return true;
 742     }
 743 
 744     /**
 745      * Replaces the entry for the specified key only if it is
 746      * currently mapped to some value.
 747      *
 748      * <p>The default implementation makes no guarantees about
 749      * synchronization or atomicity properties of this method. Any
 750      * class overriding this method must specify its concurrency
 751      * properties. In particular, all implementations of
 752      * subinterface {@link java.util.concurrent.ConcurrentMap}
 753      * must ensure that this operation is performed atomically.
 754      *
 755      * @implSpec
 756      * The default implementation is equivalent to, for this {@code map}:
 757      *
 758      * <pre> {@code
 759      * if (map.containsKey(key)) {
 760      *   return map.put(key, value);
 761      * } else
 762      *   return null;}</pre>
 763      *
 764      * @param key key with which the specified value is associated
 765      * @param value value to be associated with the specified key
 766      * @return the previous value associated with the specified key, or
 767      *         <tt>null</tt> if there was no mapping for the key.
 768      *         (A <tt>null</tt> return can also indicate that the map
 769      *         previously associated <tt>null</tt> with the key,
 770      *         if the implementation supports null values.)
 771      * @throws UnsupportedOperationException if the <tt>put</tt> operation
 772      *         is not supported by this map
 773      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 774      * @throws ClassCastException if the class of the specified key or value
 775      *         prevents it from being stored in this map
 776      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 777      * @throws NullPointerException if the specified key or value is null,
 778      *         and this map does not permit null keys or values
 779      * @throws IllegalArgumentException if some property of the specified key
 780      *         or value prevents it from being stored in this map
 781      * @since 1.8
 782      */
 783     default V replace(K key, V value) {
 784         return containsKey(key) ? put(key, value) : null;
 785     }
 786 
 787     /**
 788      * If the specified key is not already associated with a value (or
 789      * is mapped to {@code null}), attempts to compute its value using
 790      * the given mapping function and enters it into this map unless
 791      * {@code null}.
 792      *
 793      * <p>If the function returns {@code null} no mapping is recorded. If
 794      * the function itself throws an (unchecked) exception, the
 795      * exception is rethrown, and no mapping is recorded.  The most
 796      * common usage is to construct a new object serving as an initial
 797      * mapped value or memoized result, as in:
 798      *
 799      * <pre> {@code
 800      * map.computeIfAbsent(key, k -> new Value(f(k)));}</pre>
 801      *
 802      * <p>The default implementation makes no guarantees about
 803      * synchronization or atomicity properties of this method or the
 804      * application of the mapping function. Any class overriding this
 805      * method must specify its concurrency properties.  In particular,
 806      * all implementations of subinterface {@link
 807      * java.util.concurrent.ConcurrentMap} must document whether the
 808      * function is applied once atomically only if the value is not
 809      * present.  Any class that permits null values must document
 810      * whether and how this method distinguishes absence from null
 811      * mappings.
 812      *
 813      * @implSpec
 814      * The default implementation is equivalent to the following
 815      * steps for this {@code map}, then returning the current value or
 816      * {@code null} if now absent:
 817      *
 818      * <pre> {@code
 819      * if (map.get(key) == null) {
 820      *   V newValue = mappingFunction.apply(key);
 821      *   if (newValue != null)
 822      *      map.putIfAbsent(key, newValue);
 823      * }}</pre>
 824      *
 825      * @param key key with which the specified value is to be associated
 826      * @param mappingFunction the function to compute a value
 827      * @return the current (existing or computed) value associated with
 828      *         the specified key, or null if the computed value is null
 829      * @throws NullPointerException if the specified key is null and
 830      *         this map does not support null keys, or the
 831      *         mappingFunction is null
 832      * @throws UnsupportedOperationException if the <tt>put</tt> operation
 833      *         is not supported by this map
 834      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 835      * @throws ClassCastException if the class of the specified key or value
 836      *         prevents it from being stored in this map
 837      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 838      * @since 1.8
 839      */
 840     default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
 841         V v, newValue;
 842         return ((v = get(key)) == null &&
 843                 (newValue = mappingFunction.apply(key)) != null &&
 844                 (v = putIfAbsent(key, newValue)) == null) ? newValue : v;
 845     }
 846 
 847     /**
 848      * If the value for the specified key is present and non-null, attempts to
 849      * compute a new mapping given the key and its current mapped value.
 850      *
 851      * <p>If the function returns {@code null}, the mapping is removed.  If the
 852      * function itself throws an (unchecked) exception, the exception is
 853      * rethrown, and the current mapping is left unchanged.
 854      *
 855      * <p>The default implementation makes no guarantees about
 856      * synchronization or atomicity properties of this method or the
 857      * application of the remapping function. Any class overriding
 858      * this method must specify its concurrency properties.  In
 859      * particular, all implementations of subinterface {@link
 860      * java.util.concurrent.ConcurrentMap} must document whether the
 861      * function is applied once atomically only if the value is
 862      * present.  Any class that permits null values must document
 863      * whether and how this method distinguishes absence from null
 864      * mappings.
 865      *
 866      * @implSpec
 867      * The default implementation is equivalent to performing the
 868      * following steps for this {@code map}, then returning the
 869      * current value or {@code null} if now absent:
 870      *
 871      * <pre> {@code
 872      * if (map.get(key) != null) {
 873      *   V oldValue = map.get(key);
 874      *   V newValue = remappingFunction.apply(key, oldValue);
 875      *   if (newValue != null)
 876      *     map.replace(key, oldValue, newValue);
 877      *   else
 878      *     map.remove(key, oldValue);
 879      * }}</pre>
 880      *
 881      * In concurrent contexts, the default implementation may retry
 882      * these steps when multiple threads attempt updates.
 883      *
 884      * @param key key with which the specified value is to be associated
 885      * @param remappingFunction the function to compute a value
 886      * @return the new value associated with the specified key, or null if none
 887      * @throws NullPointerException if the specified key is null and
 888      *         this map does not support null keys, or the
 889      *         remappingFunction is null
 890      * @throws UnsupportedOperationException if the <tt>put</tt> operation
 891      *         is not supported by this map
 892      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 893      * @throws ClassCastException if the class of the specified key or value
 894      *         prevents it from being stored in this map
 895      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 896      * @since 1.8
 897      */
 898     default V computeIfPresent(K key,
 899                                BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 900         V oldValue;
 901         while ((oldValue = get(key)) != null) {
 902             V newValue = remappingFunction.apply(key, oldValue);
 903             if (newValue != null) {
 904                 if (replace(key, oldValue, newValue))
 905                     return newValue;
 906             } else if (remove(key, oldValue))
 907                 return null;
 908         }
 909         return oldValue;
 910     }
 911 
 912     /**
 913      * Attempts to compute a mapping for the specified key and its
 914      * current mapped value (or {@code null} if there is no current
 915      * mapping). For example, to either create or append a {@code
 916      * String msg} to a value mapping:
 917      *
 918      * <pre> {@code
 919      * map.compute(key, (k, v) -> (v == null) ? msg : v.concat(msg))}</pre>
 920      * (Method {@link #merge} is often simpler to use for such purposes.)
 921      *
 922      * <p>If the function returns {@code null}, the mapping is removed (or
 923      * remains absent if initially absent).  If the function itself throws an
 924      * (unchecked) exception, the exception is rethrown, and the current mapping
 925      * is left unchanged.
 926      *
 927      * <p>The default implementation makes no guarantees about
 928      * synchronization or atomicity properties of this method or the
 929      * application of the remapping function. Any class overriding
 930      * this method must specify its concurrency properties.  In
 931      * particular, all implementations of subinterface {@link
 932      * java.util.concurrent.ConcurrentMap} must document whether the
 933      * function is applied exactly once atomically. Any class that
 934      * permits null values must document whether and how this method
 935      * distinguishes absence from null mappings.
 936      *
 937      * @implSpec
 938      * The default implementation is equivalent to performing the following
 939      * steps for this {@code map}, then returning the current value or
 940      * {@code null} if absent:
 941      *
 942      * <pre>{@code
 943      * V oldValue = map.get(key);
 944      * V newValue = remappingFunction.apply(key, oldValue);
 945      * if (oldValue != null )
 946      *    if (newValue != null)
 947      *       map.replace(key, oldValue, newValue);
 948      *    else
 949      *       map.remove(key, oldValue);
 950      * else
 951      *    if (newValue != null)
 952      *       map.putIfAbsent(key, newValue);
 953      *    else
 954      *       return null;
 955      * }</pre>
 956      *
 957      * In concurrent contexts, the default implementation may retry
 958      * these steps when multiple threads attempt updates.
 959      *
 960      * @param key key with which the specified value is to be associated
 961      * @param remappingFunction the function to compute a value
 962      * @return the new value associated with the specified key, or null if none
 963      * @throws NullPointerException if the specified key is null and
 964      *         this map does not support null keys, or the
 965      *         remappingFunction is null
 966      * @throws UnsupportedOperationException if the <tt>put</tt> operation
 967      *         is not supported by this map
 968      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 969      * @throws ClassCastException if the class of the specified key or value
 970      *         prevents it from being stored in this map
 971      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 972      * @since 1.8
 973      */
 974     default V compute(K key,
 975                       BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
 976         V oldValue = get(key);
 977         for (;;) {
 978             V newValue = remappingFunction.apply(key, oldValue);
 979             if (oldValue != null) {
 980                 if (newValue != null) {
 981                     if (replace(key, oldValue, newValue))
 982                         return newValue;
 983                 } else if (remove(key, oldValue)) {
 984                     return null;
 985                 }
 986                 oldValue = get(key);
 987             } else {
 988                 if (newValue != null) {
 989                     if ((oldValue = putIfAbsent(key, newValue)) == null)
 990                         return newValue;
 991                 } else {
 992                     return null;
 993                 }
 994             }
 995         }
 996     }
 997 
 998     /**
 999      * If the specified key is not already associated with a
1000      * (non-null) value, associates it with the given value.
1001      * Otherwise, replaces the value with the results of the given
1002      * remapping function, or removes if {@code null}. This method may
1003      * be of use when combining multiple mapped values for a key.  For
1004      * example, to either create or append a {@code String msg} to a
1005      * value mapping:
1006      *
1007      * <pre> {@code
1008      * map.merge(key, msg, String::concat)}</pre>
1009      *
1010      * <p>If the function returns {@code null}, the mapping is removed (or
1011      * remains absent if initially absent).  If the function itself throws an
1012      * (unchecked) exception, the exception is rethrown, and the current mapping
1013      * is left unchanged.
1014      *
1015      * <p>The default implementation makes no guarantees about
1016      * synchronization or atomicity properties of this method or the
1017      * application of the remapping function. Any class overriding
1018      * this method must specify its concurrency properties.  In
1019      * particular, all implementations of subinterface {@link
1020      * java.util.concurrent.ConcurrentMap} must document whether the
1021      * function is applied exactly once atomically. Any class that
1022      * permits null values must document whether and how this method
1023      * distinguishes absence from null mappings.
1024      *
1025      * @implSpec
1026      * The default implementation is equivalent to performing the
1027      * following steps for this {@code map}, then returning the
1028      * current value or {@code null} if absent:
1029      *
1030      * <pre> {@code
1031      * V oldValue = map.get(key);
1032      * V newValue = (oldValue == null) ? value :
1033      *              remappingFunction.apply(oldValue, value);
1034      * if (newValue == null)
1035      *   map.remove(key, oldValue);
1036      * else if (oldValue == null)
1037      *   map.putIfAbsent(key, newValue);
1038      * else
1039      *   map.replace(key, oldValue, newValue);
1040      * }</pre>
1041      *
1042      * In concurrent contexts, the default implementation may retry
1043      * these steps when multiple threads attempt updates.
1044      *
1045      * @param key key with which the specified value is to be associated
1046      * @param value the value to use if absent
1047      * @param remappingFunction the function to recompute a value if present
1048      * @return the new value associated with the specified key, or null if none
1049      * @throws UnsupportedOperationException if the <tt>put</tt> operation
1050      *         is not supported by this map
1051      *         (<a href="Collection.html#optional-restrictions">optional</a>)
1052      * @throws ClassCastException if the class of the specified key or value
1053      *         prevents it from being stored in this map
1054      *         (<a href="Collection.html#optional-restrictions">optional</a>)
1055      * @throws NullPointerException if the specified key is null and
1056      *         this map does not support null keys, or the
1057      *         remappingFunction is null
1058      * @since 1.8
1059      */
1060     default V merge(K key, V value,
1061                     BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
1062         V oldValue = get(key);
1063         for (;;) {
1064             if (oldValue != null) {
1065                 V newValue = remappingFunction.apply(oldValue, value);
1066                 if (newValue != null) {
1067                     if (replace(key, oldValue, newValue))
1068                         return newValue;
1069                 } else if (remove(key, oldValue)) {
1070                     return null;
1071                 }
1072                 oldValue = get(key);
1073             } else {
1074                 if (value == null) {
1075                     return null;
1076                 }
1077 
1078                 if ((oldValue = putIfAbsent(key, value)) == null) {
1079                     return value;
1080                 }
1081             }
1082         }
1083     }
1084 }