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.Consumer;
29 import java.util.function.BiConsumer;
30 import java.util.function.BiFunction;
31 import java.io.Serializable;
32 import java.io.IOException;
33
34 /**
35 * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,
36 * with predictable iteration order. This implementation differs from
37 * <tt>HashMap</tt> in that it maintains a doubly-linked list running through
38 * all of its entries. This linked list defines the iteration ordering,
39 * which is normally the order in which keys were inserted into the map
40 * (<i>insertion-order</i>). Note that insertion order is not affected
41 * if a key is <i>re-inserted</i> into the map. (A key <tt>k</tt> is
42 * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when
43 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to
44 * the invocation.)
45 *
46 * <p>This implementation spares its clients from the unspecified, generally
47 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}),
48 * without incurring the increased cost associated with {@link TreeMap}. It
49 * can be used to produce a copy of a map that has the same order as the
50 * original, regardless of the original map's implementation:
51 * <pre>
52 * void foo(Map m) {
53 * Map copy = new LinkedHashMap(m);
54 * ...
55 * }
56 * </pre>
57 * This technique is particularly useful if a module takes a map on input,
58 * copies it, and later returns results whose order is determined by that of
59 * the copy. (Clients generally appreciate having things returned in the same
60 * order they were presented.)
61 *
62 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is
63 * provided to create a linked hash map whose order of iteration is the order
64 * in which its entries were last accessed, from least-recently accessed to
65 * most-recently (<i>access-order</i>). This kind of map is well-suited to
66 * building LRU caches. Invoking the <tt>put</tt> or <tt>get</tt> method
67 * results in an access to the corresponding entry (assuming it exists after
68 * the invocation completes). The <tt>putAll</tt> method generates one entry
69 * access for each mapping in the specified map, in the order that key-value
70 * mappings are provided by the specified map's entry set iterator. <i>No
71 * other methods generate entry accesses.</i> In particular, operations on
72 * collection-views do <i>not</i> affect the order of iteration of the backing
73 * map.
74 *
75 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
76 * impose a policy for removing stale mappings automatically when new mappings
77 * are added to the map.
78 *
79 * <p>This class provides all of the optional <tt>Map</tt> operations, and
80 * permits null elements. Like <tt>HashMap</tt>, it provides constant-time
81 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and
82 * <tt>remove</tt>), assuming the hash function disperses elements
83 * properly among the buckets. Performance is likely to be just slightly
84 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the
85 * linked list, with one exception: Iteration over the collection-views
86 * of a <tt>LinkedHashMap</tt> requires time proportional to the <i>size</i>
87 * of the map, regardless of its capacity. Iteration over a <tt>HashMap</tt>
88 * is likely to be more expensive, requiring time proportional to its
89 * <i>capacity</i>.
90 *
91 * <p>A linked hash map has two parameters that affect its performance:
92 * <i>initial capacity</i> and <i>load factor</i>. They are defined precisely
93 * as for <tt>HashMap</tt>. Note, however, that the penalty for choosing an
426 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
427 * key.equals(k))}, then this method returns {@code v}; otherwise
428 * it returns {@code null}. (There can be at most one such mapping.)
429 *
430 * <p>A return value of {@code null} does not <i>necessarily</i>
431 * indicate that the map contains no mapping for the key; it's also
432 * possible that the map explicitly maps the key to {@code null}.
433 * The {@link #containsKey containsKey} operation may be used to
434 * distinguish these two cases.
435 */
436 public V get(Object key) {
437 Node<K,V> e;
438 if ((e = getNode(hash(key), key)) == null)
439 return null;
440 if (accessOrder)
441 afterNodeAccess(e);
442 return e.value;
443 }
444
445 /**
446 * Removes all of the mappings from this map.
447 * The map will be empty after this call returns.
448 */
449 public void clear() {
450 super.clear();
451 head = tail = null;
452 }
453
454 /**
455 * Returns <tt>true</tt> if this map should remove its eldest entry.
456 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
457 * inserting a new entry into the map. It provides the implementor
458 * with the opportunity to remove the eldest entry each time a new one
459 * is added. This is useful if the map represents a cache: it allows
460 * the map to reduce memory consumption by deleting stale entries.
461 *
462 * <p>Sample use: this override will allow the map to grow up to 100
463 * entries and then delete the eldest entry each time a new entry is
464 * added, maintaining a steady state of 100 entries.
465 * <pre>
466 * private static final int MAX_ENTRIES = 100;
467 *
|
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.Consumer;
29 import java.util.function.BiConsumer;
30 import java.util.function.BiFunction;
31 import java.io.IOException;
32
33 /**
34 * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,
35 * with predictable iteration order. This implementation differs from
36 * <tt>HashMap</tt> in that it maintains a doubly-linked list running through
37 * all of its entries. This linked list defines the iteration ordering,
38 * which is normally the order in which keys were inserted into the map
39 * (<i>insertion-order</i>). Note that insertion order is not affected
40 * if a key is <i>re-inserted</i> into the map. (A key <tt>k</tt> is
41 * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when
42 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to
43 * the invocation.)
44 *
45 * <p>This implementation spares its clients from the unspecified, generally
46 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}),
47 * without incurring the increased cost associated with {@link TreeMap}. It
48 * can be used to produce a copy of a map that has the same order as the
49 * original, regardless of the original map's implementation:
50 * <pre>
51 * void foo(Map m) {
52 * Map copy = new LinkedHashMap(m);
53 * ...
54 * }
55 * </pre>
56 * This technique is particularly useful if a module takes a map on input,
57 * copies it, and later returns results whose order is determined by that of
58 * the copy. (Clients generally appreciate having things returned in the same
59 * order they were presented.)
60 *
61 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is
62 * provided to create a linked hash map whose order of iteration is the order
63 * in which its entries were last accessed, from least-recently accessed to
64 * most-recently (<i>access-order</i>). This kind of map is well-suited to
65 * building LRU caches. Invoking the {@code put}, {@code putIfAbsent},
66 * {@code get}, {@code computeIfAbsent} or {@code getOrDefault} methods results
67 * in an access to the corresponding entry (assuming it exists after the
68 * invocation completes). Invoking the {@code replace}, {@code merge},
69 * {@code compute} or {@code computeIfPresent} methods results in one or more
70 * accesses of the corresponding entry. The {@code putAll} method generates one
71 * entry access for each mapping in the specified map, in the order that
72 * key-value mappings are provided by the specified map's entry set iterator.
73 * <i>No other methods generate entry accesses.</i> In particular, operations
74 * on collection-views do <i>not</i> affect the order of iteration of the
75 * backing map.
76 *
77 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
78 * impose a policy for removing stale mappings automatically when new mappings
79 * are added to the map.
80 *
81 * <p>This class provides all of the optional <tt>Map</tt> operations, and
82 * permits null elements. Like <tt>HashMap</tt>, it provides constant-time
83 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and
84 * <tt>remove</tt>), assuming the hash function disperses elements
85 * properly among the buckets. Performance is likely to be just slightly
86 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the
87 * linked list, with one exception: Iteration over the collection-views
88 * of a <tt>LinkedHashMap</tt> requires time proportional to the <i>size</i>
89 * of the map, regardless of its capacity. Iteration over a <tt>HashMap</tt>
90 * is likely to be more expensive, requiring time proportional to its
91 * <i>capacity</i>.
92 *
93 * <p>A linked hash map has two parameters that affect its performance:
94 * <i>initial capacity</i> and <i>load factor</i>. They are defined precisely
95 * as for <tt>HashMap</tt>. Note, however, that the penalty for choosing an
428 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
429 * key.equals(k))}, then this method returns {@code v}; otherwise
430 * it returns {@code null}. (There can be at most one such mapping.)
431 *
432 * <p>A return value of {@code null} does not <i>necessarily</i>
433 * indicate that the map contains no mapping for the key; it's also
434 * possible that the map explicitly maps the key to {@code null}.
435 * The {@link #containsKey containsKey} operation may be used to
436 * distinguish these two cases.
437 */
438 public V get(Object key) {
439 Node<K,V> e;
440 if ((e = getNode(hash(key), key)) == null)
441 return null;
442 if (accessOrder)
443 afterNodeAccess(e);
444 return e.value;
445 }
446
447 /**
448 * {@inheritDoc}
449 */
450 public V getOrDefault(Object key, V defaultValue) {
451 Node<K,V> e;
452 if ((e = getNode(hash(key), key)) == null)
453 return defaultValue;
454 if (accessOrder)
455 afterNodeAccess(e);
456 return e.value;
457 }
458
459 /**
460 * {@inheritDoc}
461 */
462 public void clear() {
463 super.clear();
464 head = tail = null;
465 }
466
467 /**
468 * Returns <tt>true</tt> if this map should remove its eldest entry.
469 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
470 * inserting a new entry into the map. It provides the implementor
471 * with the opportunity to remove the eldest entry each time a new one
472 * is added. This is useful if the map represents a cache: it allows
473 * the map to reduce memory consumption by deleting stale entries.
474 *
475 * <p>Sample use: this override will allow the map to grow up to 100
476 * entries and then delete the eldest entry each time a new entry is
477 * added, maintaining a steady state of 100 entries.
478 * <pre>
479 * private static final int MAX_ENTRIES = 100;
480 *
|