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 get},
66 * {@code getOrDefault} or {@code replace} methods results in an access to the
67 * corresponding entry (assuming it exists after the invocation completes). The
68 * {@code putAll} method generates one entry access for each mapping in the
69 * specified map, in the order that key-value mappings are provided by the
70 * specified map's entry set iterator. <i>No other methods generate entry
71 * accesses.</i> In particular, operations on collection-views do <i>not</i>
72 * affect the order of iteration of the backing map.
73 *
74 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
75 * impose a policy for removing stale mappings automatically when new mappings
76 * are added to the map.
77 *
78 * <p>This class provides all of the optional <tt>Map</tt> operations, and
79 * permits null elements. Like <tt>HashMap</tt>, it provides constant-time
80 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and
81 * <tt>remove</tt>), assuming the hash function disperses elements
82 * properly among the buckets. Performance is likely to be just slightly
83 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the
84 * linked list, with one exception: Iteration over the collection-views
85 * of a <tt>LinkedHashMap</tt> requires time proportional to the <i>size</i>
86 * of the map, regardless of its capacity. Iteration over a <tt>HashMap</tt>
87 * is likely to be more expensive, requiring time proportional to its
88 * <i>capacity</i>.
89 *
90 * <p>A linked hash map has two parameters that affect its performance:
91 * <i>initial capacity</i> and <i>load factor</i>. They are defined precisely
92 * as for <tt>HashMap</tt>. Note, however, that the penalty for choosing an
425 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
426 * key.equals(k))}, then this method returns {@code v}; otherwise
427 * it returns {@code null}. (There can be at most one such mapping.)
428 *
429 * <p>A return value of {@code null} does not <i>necessarily</i>
430 * indicate that the map contains no mapping for the key; it's also
431 * possible that the map explicitly maps the key to {@code null}.
432 * The {@link #containsKey containsKey} operation may be used to
433 * distinguish these two cases.
434 */
435 public V get(Object key) {
436 Node<K,V> e;
437 if ((e = getNode(hash(key), key)) == null)
438 return null;
439 if (accessOrder)
440 afterNodeAccess(e);
441 return e.value;
442 }
443
444 /**
445 * {@inheritDoc}
446 */
447 public V getOrDefault(Object key, V defaultValue) {
448 Node<K,V> e;
449 if ((e = getNode(hash(key), key)) == null)
450 return defaultValue;
451 if (accessOrder)
452 afterNodeAccess(e);
453 return e.value;
454 }
455
456 /**
457 * {@inheritDoc}
458 */
459 public void clear() {
460 super.clear();
461 head = tail = null;
462 }
463
464 /**
465 * Returns <tt>true</tt> if this map should remove its eldest entry.
466 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
467 * inserting a new entry into the map. It provides the implementor
468 * with the opportunity to remove the eldest entry each time a new one
469 * is added. This is useful if the map represents a cache: it allows
470 * the map to reduce memory consumption by deleting stale entries.
471 *
472 * <p>Sample use: this override will allow the map to grow up to 100
473 * entries and then delete the eldest entry each time a new entry is
474 * added, maintaining a steady state of 100 entries.
475 * <pre>
476 * private static final int MAX_ENTRIES = 100;
477 *
|