jdk/src/java.base/share/classes/java/util/LinkedHashMap.java
author mchung
Fri, 22 May 2015 16:43:39 -0700
changeset 30789 9eca83469588
parent 25859 3317bb8137f4
child 32108 aa5490a167ee
permissions -rw-r--r--
8074431: Remove native2ascii tool Reviewed-by: erikj, alanb, okutsu, mfang, naoto
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     1
/*
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
     2
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
90ce3da70b43 Initial load
duke
parents:
diff changeset
     4
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
90ce3da70b43 Initial load
duke
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     7
 * published by the Free Software Foundation.  Oracle designates this
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     8
 * particular file as subject to the "Classpath" exception as provided
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     9
 * by Oracle in the LICENSE file that accompanied this code.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    10
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    11
 * This code is distributed in the hope that it will be useful, but WITHOUT
90ce3da70b43 Initial load
duke
parents:
diff changeset
    12
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
90ce3da70b43 Initial load
duke
parents:
diff changeset
    13
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
90ce3da70b43 Initial load
duke
parents:
diff changeset
    14
 * version 2 for more details (a copy is included in the LICENSE file that
90ce3da70b43 Initial load
duke
parents:
diff changeset
    15
 * accompanied this code).
90ce3da70b43 Initial load
duke
parents:
diff changeset
    16
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    17
 * You should have received a copy of the GNU General Public License version
90ce3da70b43 Initial load
duke
parents:
diff changeset
    18
 * 2 along with this work; if not, write to the Free Software Foundation,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    19
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    20
 *
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    22
 * or visit www.oracle.com if you need additional information or have any
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    23
 * questions.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    24
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    25
90ce3da70b43 Initial load
duke
parents:
diff changeset
    26
package java.util;
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
    27
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
    28
import java.util.function.Consumer;
18280
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
    29
import java.util.function.BiConsumer;
6c3c0ff49eb5 8016446: Improve forEach/replaceAll for Map, HashMap, Hashtable, IdentityHashMap, WeakHashMap, TreeMap, ConcurrentMap
mduigou
parents: 18156
diff changeset
    30
import java.util.function.BiFunction;
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
    31
import java.io.IOException;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    32
90ce3da70b43 Initial load
duke
parents:
diff changeset
    33
/**
90ce3da70b43 Initial load
duke
parents:
diff changeset
    34
 * <p>Hash table and linked list implementation of the <tt>Map</tt> interface,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    35
 * with predictable iteration order.  This implementation differs from
90ce3da70b43 Initial load
duke
parents:
diff changeset
    36
 * <tt>HashMap</tt> in that it maintains a doubly-linked list running through
90ce3da70b43 Initial load
duke
parents:
diff changeset
    37
 * all of its entries.  This linked list defines the iteration ordering,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    38
 * which is normally the order in which keys were inserted into the map
90ce3da70b43 Initial load
duke
parents:
diff changeset
    39
 * (<i>insertion-order</i>).  Note that insertion order is not affected
90ce3da70b43 Initial load
duke
parents:
diff changeset
    40
 * if a key is <i>re-inserted</i> into the map.  (A key <tt>k</tt> is
90ce3da70b43 Initial load
duke
parents:
diff changeset
    41
 * reinserted into a map <tt>m</tt> if <tt>m.put(k, v)</tt> is invoked when
90ce3da70b43 Initial load
duke
parents:
diff changeset
    42
 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to
90ce3da70b43 Initial load
duke
parents:
diff changeset
    43
 * the invocation.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
    44
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    45
 * <p>This implementation spares its clients from the unspecified, generally
90ce3da70b43 Initial load
duke
parents:
diff changeset
    46
 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}),
90ce3da70b43 Initial load
duke
parents:
diff changeset
    47
 * without incurring the increased cost associated with {@link TreeMap}.  It
90ce3da70b43 Initial load
duke
parents:
diff changeset
    48
 * can be used to produce a copy of a map that has the same order as the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    49
 * original, regardless of the original map's implementation:
90ce3da70b43 Initial load
duke
parents:
diff changeset
    50
 * <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    51
 *     void foo(Map m) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    52
 *         Map copy = new LinkedHashMap(m);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    53
 *         ...
90ce3da70b43 Initial load
duke
parents:
diff changeset
    54
 *     }
90ce3da70b43 Initial load
duke
parents:
diff changeset
    55
 * </pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    56
 * This technique is particularly useful if a module takes a map on input,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    57
 * copies it, and later returns results whose order is determined by that of
90ce3da70b43 Initial load
duke
parents:
diff changeset
    58
 * the copy.  (Clients generally appreciate having things returned in the same
90ce3da70b43 Initial load
duke
parents:
diff changeset
    59
 * order they were presented.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
    60
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    61
 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
    62
 * provided to create a linked hash map whose order of iteration is the order
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
    63
 * in which its entries were last accessed, from least-recently accessed to
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
    64
 * most-recently (<i>access-order</i>).  This kind of map is well-suited to
22058
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    65
 * building LRU caches.  Invoking the {@code put}, {@code putIfAbsent},
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    66
 * {@code get}, {@code getOrDefault}, {@code compute}, {@code computeIfAbsent},
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    67
 * {@code computeIfPresent}, or {@code merge} methods results
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    68
 * in an access to the corresponding entry (assuming it exists after the
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    69
 * invocation completes). The {@code replace} methods only result in an access
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    70
 * of the entry if the value is replaced.  The {@code putAll} method generates one
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    71
 * entry access for each mapping in the specified map, in the order that
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    72
 * key-value mappings are provided by the specified map's entry set iterator.
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    73
 * <i>No other methods generate entry accesses.</i>  In particular, operations
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    74
 * on collection-views do <i>not</i> affect the order of iteration of the
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
    75
 * backing map.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    76
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    77
 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
90ce3da70b43 Initial load
duke
parents:
diff changeset
    78
 * impose a policy for removing stale mappings automatically when new mappings
90ce3da70b43 Initial load
duke
parents:
diff changeset
    79
 * are added to the map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    80
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    81
 * <p>This class provides all of the optional <tt>Map</tt> operations, and
90ce3da70b43 Initial load
duke
parents:
diff changeset
    82
 * permits null elements.  Like <tt>HashMap</tt>, it provides constant-time
90ce3da70b43 Initial load
duke
parents:
diff changeset
    83
 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and
90ce3da70b43 Initial load
duke
parents:
diff changeset
    84
 * <tt>remove</tt>), assuming the hash function disperses elements
90ce3da70b43 Initial load
duke
parents:
diff changeset
    85
 * properly among the buckets.  Performance is likely to be just slightly
90ce3da70b43 Initial load
duke
parents:
diff changeset
    86
 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    87
 * linked list, with one exception: Iteration over the collection-views
90ce3da70b43 Initial load
duke
parents:
diff changeset
    88
 * of a <tt>LinkedHashMap</tt> requires time proportional to the <i>size</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    89
 * of the map, regardless of its capacity.  Iteration over a <tt>HashMap</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    90
 * is likely to be more expensive, requiring time proportional to its
90ce3da70b43 Initial load
duke
parents:
diff changeset
    91
 * <i>capacity</i>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    92
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    93
 * <p>A linked hash map has two parameters that affect its performance:
90ce3da70b43 Initial load
duke
parents:
diff changeset
    94
 * <i>initial capacity</i> and <i>load factor</i>.  They are defined precisely
90ce3da70b43 Initial load
duke
parents:
diff changeset
    95
 * as for <tt>HashMap</tt>.  Note, however, that the penalty for choosing an
90ce3da70b43 Initial load
duke
parents:
diff changeset
    96
 * excessively high value for initial capacity is less severe for this class
90ce3da70b43 Initial load
duke
parents:
diff changeset
    97
 * than for <tt>HashMap</tt>, as iteration times for this class are unaffected
90ce3da70b43 Initial load
duke
parents:
diff changeset
    98
 * by capacity.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    99
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   100
 * <p><strong>Note that this implementation is not synchronized.</strong>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   101
 * If multiple threads access a linked hash map concurrently, and at least
90ce3da70b43 Initial load
duke
parents:
diff changeset
   102
 * one of the threads modifies the map structurally, it <em>must</em> be
90ce3da70b43 Initial load
duke
parents:
diff changeset
   103
 * synchronized externally.  This is typically accomplished by
90ce3da70b43 Initial load
duke
parents:
diff changeset
   104
 * synchronizing on some object that naturally encapsulates the map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   105
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   106
 * If no such object exists, the map should be "wrapped" using the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   107
 * {@link Collections#synchronizedMap Collections.synchronizedMap}
90ce3da70b43 Initial load
duke
parents:
diff changeset
   108
 * method.  This is best done at creation time, to prevent accidental
90ce3da70b43 Initial load
duke
parents:
diff changeset
   109
 * unsynchronized access to the map:<pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   110
 *   Map m = Collections.synchronizedMap(new LinkedHashMap(...));</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   111
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   112
 * A structural modification is any operation that adds or deletes one or more
90ce3da70b43 Initial load
duke
parents:
diff changeset
   113
 * mappings or, in the case of access-ordered linked hash maps, affects
90ce3da70b43 Initial load
duke
parents:
diff changeset
   114
 * iteration order.  In insertion-ordered linked hash maps, merely changing
90ce3da70b43 Initial load
duke
parents:
diff changeset
   115
 * the value associated with a key that is already contained in the map is not
90ce3da70b43 Initial load
duke
parents:
diff changeset
   116
 * a structural modification.  <strong>In access-ordered linked hash maps,
22058
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   117
 * merely querying the map with <tt>get</tt> is a structural modification.
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   118
 * </strong>)
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   119
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   120
 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
90ce3da70b43 Initial load
duke
parents:
diff changeset
   121
 * returned by all of this class's collection view methods are
90ce3da70b43 Initial load
duke
parents:
diff changeset
   122
 * <em>fail-fast</em>: if the map is structurally modified at any time after
90ce3da70b43 Initial load
duke
parents:
diff changeset
   123
 * the iterator is created, in any way except through the iterator's own
90ce3da70b43 Initial load
duke
parents:
diff changeset
   124
 * <tt>remove</tt> method, the iterator will throw a {@link
90ce3da70b43 Initial load
duke
parents:
diff changeset
   125
 * ConcurrentModificationException}.  Thus, in the face of concurrent
90ce3da70b43 Initial load
duke
parents:
diff changeset
   126
 * modification, the iterator fails quickly and cleanly, rather than risking
90ce3da70b43 Initial load
duke
parents:
diff changeset
   127
 * arbitrary, non-deterministic behavior at an undetermined time in the future.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   128
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   129
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
90ce3da70b43 Initial load
duke
parents:
diff changeset
   130
 * as it is, generally speaking, impossible to make any hard guarantees in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   131
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
   132
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   133
 * Therefore, it would be wrong to write a program that depended on this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   134
 * exception for its correctness:   <i>the fail-fast behavior of iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
   135
 * should be used only to detect bugs.</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   136
 *
19435
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   137
 * <p>The spliterators returned by the spliterator method of the collections
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   138
 * returned by all of this class's collection view methods are
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   139
 * <em><a href="Spliterator.html#binding">late-binding</a></em>,
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   140
 * <em>fail-fast</em>, and additionally report {@link Spliterator#ORDERED}.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   141
 *
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   142
 * <p>This class is a member of the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   143
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
90ce3da70b43 Initial load
duke
parents:
diff changeset
   144
 * Java Collections Framework</a>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   145
 *
19435
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   146
 * @implNote
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   147
 * The spliterators returned by the spliterator method of the collections
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   148
 * returned by all of this class's collection view methods are created from
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   149
 * the iterators of the corresponding collections.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 18280
diff changeset
   150
 *
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   151
 * @param <K> the type of keys maintained by this map
90ce3da70b43 Initial load
duke
parents:
diff changeset
   152
 * @param <V> the type of mapped values
90ce3da70b43 Initial load
duke
parents:
diff changeset
   153
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   154
 * @author  Josh Bloch
90ce3da70b43 Initial load
duke
parents:
diff changeset
   155
 * @see     Object#hashCode()
90ce3da70b43 Initial load
duke
parents:
diff changeset
   156
 * @see     Collection
90ce3da70b43 Initial load
duke
parents:
diff changeset
   157
 * @see     Map
90ce3da70b43 Initial load
duke
parents:
diff changeset
   158
 * @see     HashMap
90ce3da70b43 Initial load
duke
parents:
diff changeset
   159
 * @see     TreeMap
90ce3da70b43 Initial load
duke
parents:
diff changeset
   160
 * @see     Hashtable
90ce3da70b43 Initial load
duke
parents:
diff changeset
   161
 * @since   1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   162
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   163
public class LinkedHashMap<K,V>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   164
    extends HashMap<K,V>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   165
    implements Map<K,V>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   166
{
90ce3da70b43 Initial load
duke
parents:
diff changeset
   167
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   168
    /*
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   169
     * Implementation note.  A previous version of this class was
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   170
     * internally structured a little differently. Because superclass
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   171
     * HashMap now uses trees for some of its nodes, class
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   172
     * LinkedHashMap.Entry is now treated as intermediary node class
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   173
     * that can also be converted to tree form. The name of this
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   174
     * class, LinkedHashMap.Entry, is confusing in several ways in its
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   175
     * current context, but cannot be changed.  Otherwise, even though
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   176
     * it is not exported outside this package, some existing source
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   177
     * code is known to have relied on a symbol resolution corner case
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   178
     * rule in calls to removeEldestEntry that suppressed compilation
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   179
     * errors due to ambiguous usages. So, we keep the name to
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   180
     * preserve unmodified compilability.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   181
     *
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   182
     * The changes in node classes also require using two fields
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   183
     * (head, tail) rather than a pointer to a header node to maintain
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   184
     * the doubly-linked before/after list. This class also
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   185
     * previously used a different style of callback methods upon
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   186
     * access, insertion, and removal.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   187
     */
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   188
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   189
    /**
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   190
     * HashMap.Node subclass for normal LinkedHashMap entries.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   191
     */
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   192
    static class Entry<K,V> extends HashMap.Node<K,V> {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   193
        Entry<K,V> before, after;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   194
        Entry(int hash, K key, V value, Node<K,V> next) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   195
            super(hash, key, value, next);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   196
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   197
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   198
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   199
    private static final long serialVersionUID = 3801124242820219131L;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   200
90ce3da70b43 Initial load
duke
parents:
diff changeset
   201
    /**
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   202
     * The head (eldest) of the doubly linked list.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   203
     */
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   204
    transient LinkedHashMap.Entry<K,V> head;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   205
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   206
    /**
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   207
     * The tail (youngest) of the doubly linked list.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   208
     */
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   209
    transient LinkedHashMap.Entry<K,V> tail;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   210
90ce3da70b43 Initial load
duke
parents:
diff changeset
   211
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   212
     * The iteration ordering method for this linked hash map: <tt>true</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   213
     * for access-order, <tt>false</tt> for insertion-order.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   214
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   215
     * @serial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   216
     */
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   217
    final boolean accessOrder;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   218
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   219
    // internal utilities
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   220
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   221
    // link at the end of list
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   222
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   223
        LinkedHashMap.Entry<K,V> last = tail;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   224
        tail = p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   225
        if (last == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   226
            head = p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   227
        else {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   228
            p.before = last;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   229
            last.after = p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   230
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   231
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   232
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   233
    // apply src's links to dst
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   234
    private void transferLinks(LinkedHashMap.Entry<K,V> src,
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   235
                               LinkedHashMap.Entry<K,V> dst) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   236
        LinkedHashMap.Entry<K,V> b = dst.before = src.before;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   237
        LinkedHashMap.Entry<K,V> a = dst.after = src.after;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   238
        if (b == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   239
            head = dst;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   240
        else
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   241
            b.after = dst;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   242
        if (a == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   243
            tail = dst;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   244
        else
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   245
            a.before = dst;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   246
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   247
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   248
    // overrides of HashMap hook methods
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   249
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   250
    void reinitialize() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   251
        super.reinitialize();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   252
        head = tail = null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   253
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   254
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   255
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   256
        LinkedHashMap.Entry<K,V> p =
22078
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 22058
diff changeset
   257
            new LinkedHashMap.Entry<>(hash, key, value, e);
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   258
        linkNodeLast(p);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   259
        return p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   260
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   261
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   262
    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   263
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   264
        LinkedHashMap.Entry<K,V> t =
22078
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 22058
diff changeset
   265
            new LinkedHashMap.Entry<>(q.hash, q.key, q.value, next);
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   266
        transferLinks(q, t);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   267
        return t;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   268
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   269
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   270
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
22078
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 22058
diff changeset
   271
        TreeNode<K,V> p = new TreeNode<>(hash, key, value, next);
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   272
        linkNodeLast(p);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   273
        return p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   274
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   275
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   276
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   277
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
22078
bdec5d53e98c 8030851: Update code in java.util to use newer language features
psandoz
parents: 22058
diff changeset
   278
        TreeNode<K,V> t = new TreeNode<>(q.hash, q.key, q.value, next);
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   279
        transferLinks(q, t);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   280
        return t;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   281
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   282
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   283
    void afterNodeRemoval(Node<K,V> e) { // unlink
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   284
        LinkedHashMap.Entry<K,V> p =
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   285
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   286
        p.before = p.after = null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   287
        if (b == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   288
            head = a;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   289
        else
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   290
            b.after = a;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   291
        if (a == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   292
            tail = b;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   293
        else
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   294
            a.before = b;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   295
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   296
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   297
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   298
        LinkedHashMap.Entry<K,V> first;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   299
        if (evict && (first = head) != null && removeEldestEntry(first)) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   300
            K key = first.key;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   301
            removeNode(hash(key), key, null, false, true);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   302
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   303
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   304
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   305
    void afterNodeAccess(Node<K,V> e) { // move node to last
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   306
        LinkedHashMap.Entry<K,V> last;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   307
        if (accessOrder && (last = tail) != e) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   308
            LinkedHashMap.Entry<K,V> p =
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   309
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   310
            p.after = null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   311
            if (b == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   312
                head = a;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   313
            else
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   314
                b.after = a;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   315
            if (a != null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   316
                a.before = b;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   317
            else
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   318
                last = b;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   319
            if (last == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   320
                head = p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   321
            else {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   322
                p.before = last;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   323
                last.after = p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   324
            }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   325
            tail = p;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   326
            ++modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   327
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   328
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   329
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   330
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   331
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   332
            s.writeObject(e.key);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   333
            s.writeObject(e.value);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   334
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   335
    }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   336
90ce3da70b43 Initial load
duke
parents:
diff changeset
   337
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   338
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
90ce3da70b43 Initial load
duke
parents:
diff changeset
   339
     * with the specified initial capacity and load factor.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   340
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   341
     * @param  initialCapacity the initial capacity
90ce3da70b43 Initial load
duke
parents:
diff changeset
   342
     * @param  loadFactor      the load factor
90ce3da70b43 Initial load
duke
parents:
diff changeset
   343
     * @throws IllegalArgumentException if the initial capacity is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   344
     *         or the load factor is nonpositive
90ce3da70b43 Initial load
duke
parents:
diff changeset
   345
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   346
    public LinkedHashMap(int initialCapacity, float loadFactor) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   347
        super(initialCapacity, loadFactor);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   348
        accessOrder = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   349
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   350
90ce3da70b43 Initial load
duke
parents:
diff changeset
   351
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   352
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
90ce3da70b43 Initial load
duke
parents:
diff changeset
   353
     * with the specified initial capacity and a default load factor (0.75).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   354
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   355
     * @param  initialCapacity the initial capacity
90ce3da70b43 Initial load
duke
parents:
diff changeset
   356
     * @throws IllegalArgumentException if the initial capacity is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   357
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   358
    public LinkedHashMap(int initialCapacity) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   359
        super(initialCapacity);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   360
        accessOrder = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   361
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   362
90ce3da70b43 Initial load
duke
parents:
diff changeset
   363
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   364
     * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
90ce3da70b43 Initial load
duke
parents:
diff changeset
   365
     * with the default initial capacity (16) and load factor (0.75).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   366
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   367
    public LinkedHashMap() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   368
        super();
90ce3da70b43 Initial load
duke
parents:
diff changeset
   369
        accessOrder = false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   370
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   371
90ce3da70b43 Initial load
duke
parents:
diff changeset
   372
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   373
     * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
90ce3da70b43 Initial load
duke
parents:
diff changeset
   374
     * the same mappings as the specified map.  The <tt>LinkedHashMap</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   375
     * instance is created with a default load factor (0.75) and an initial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   376
     * capacity sufficient to hold the mappings in the specified map.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   377
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   378
     * @param  m the map whose mappings are to be placed in this map
90ce3da70b43 Initial load
duke
parents:
diff changeset
   379
     * @throws NullPointerException if the specified map is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   380
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   381
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   382
        super();
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   383
        accessOrder = false;
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   384
        putMapEntries(m, false);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   385
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   386
90ce3da70b43 Initial load
duke
parents:
diff changeset
   387
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   388
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   389
     * specified initial capacity, load factor and ordering mode.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   390
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   391
     * @param  initialCapacity the initial capacity
90ce3da70b43 Initial load
duke
parents:
diff changeset
   392
     * @param  loadFactor      the load factor
90ce3da70b43 Initial load
duke
parents:
diff changeset
   393
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
90ce3da70b43 Initial load
duke
parents:
diff changeset
   394
     *         access-order, <tt>false</tt> for insertion-order
90ce3da70b43 Initial load
duke
parents:
diff changeset
   395
     * @throws IllegalArgumentException if the initial capacity is negative
90ce3da70b43 Initial load
duke
parents:
diff changeset
   396
     *         or the load factor is nonpositive
90ce3da70b43 Initial load
duke
parents:
diff changeset
   397
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   398
    public LinkedHashMap(int initialCapacity,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   399
                         float loadFactor,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   400
                         boolean accessOrder) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   401
        super(initialCapacity, loadFactor);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   402
        this.accessOrder = accessOrder;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   403
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   404
90ce3da70b43 Initial load
duke
parents:
diff changeset
   405
90ce3da70b43 Initial load
duke
parents:
diff changeset
   406
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   407
     * Returns <tt>true</tt> if this map maps one or more keys to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   408
     * specified value.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   409
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   410
     * @param value value whose presence in this map is to be tested
90ce3da70b43 Initial load
duke
parents:
diff changeset
   411
     * @return <tt>true</tt> if this map maps one or more keys to the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   412
     *         specified value
90ce3da70b43 Initial load
duke
parents:
diff changeset
   413
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   414
    public boolean containsValue(Object value) {
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   415
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   416
            V v = e.value;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   417
            if (v == value || (value != null && value.equals(v)))
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   418
                return true;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   419
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   420
        return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   421
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   422
90ce3da70b43 Initial load
duke
parents:
diff changeset
   423
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   424
     * Returns the value to which the specified key is mapped,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   425
     * or {@code null} if this map contains no mapping for the key.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   426
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   427
     * <p>More formally, if this map contains a mapping from a key
90ce3da70b43 Initial load
duke
parents:
diff changeset
   428
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
90ce3da70b43 Initial load
duke
parents:
diff changeset
   429
     * key.equals(k))}, then this method returns {@code v}; otherwise
90ce3da70b43 Initial load
duke
parents:
diff changeset
   430
     * it returns {@code null}.  (There can be at most one such mapping.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
   431
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   432
     * <p>A return value of {@code null} does not <i>necessarily</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   433
     * indicate that the map contains no mapping for the key; it's also
90ce3da70b43 Initial load
duke
parents:
diff changeset
   434
     * possible that the map explicitly maps the key to {@code null}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   435
     * The {@link #containsKey containsKey} operation may be used to
90ce3da70b43 Initial load
duke
parents:
diff changeset
   436
     * distinguish these two cases.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   437
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   438
    public V get(Object key) {
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   439
        Node<K,V> e;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   440
        if ((e = getNode(hash(key), key)) == null)
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   441
            return null;
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   442
        if (accessOrder)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   443
            afterNodeAccess(e);
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   444
        return e.value;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   445
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   446
90ce3da70b43 Initial load
duke
parents:
diff changeset
   447
    /**
22058
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   448
     * {@inheritDoc}
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   449
     */
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   450
    public V getOrDefault(Object key, V defaultValue) {
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   451
       Node<K,V> e;
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   452
       if ((e = getNode(hash(key), key)) == null)
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   453
           return defaultValue;
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   454
       if (accessOrder)
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   455
           afterNodeAccess(e);
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   456
       return e.value;
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   457
   }
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   458
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   459
    /**
db159b144c98 8029795: LinkedHashMap.getOrDefault() doesn't update access order.
mduigou
parents: 19806
diff changeset
   460
     * {@inheritDoc}
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   461
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   462
    public void clear() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   463
        super.clear();
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   464
        head = tail = null;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   465
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   466
90ce3da70b43 Initial load
duke
parents:
diff changeset
   467
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   468
     * Returns <tt>true</tt> if this map should remove its eldest entry.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   469
     * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
90ce3da70b43 Initial load
duke
parents:
diff changeset
   470
     * inserting a new entry into the map.  It provides the implementor
90ce3da70b43 Initial load
duke
parents:
diff changeset
   471
     * with the opportunity to remove the eldest entry each time a new one
90ce3da70b43 Initial load
duke
parents:
diff changeset
   472
     * is added.  This is useful if the map represents a cache: it allows
90ce3da70b43 Initial load
duke
parents:
diff changeset
   473
     * the map to reduce memory consumption by deleting stale entries.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   474
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   475
     * <p>Sample use: this override will allow the map to grow up to 100
90ce3da70b43 Initial load
duke
parents:
diff changeset
   476
     * entries and then delete the eldest entry each time a new entry is
90ce3da70b43 Initial load
duke
parents:
diff changeset
   477
     * added, maintaining a steady state of 100 entries.
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   478
     * <pre>
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   479
     *     private static final int MAX_ENTRIES = 100;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   480
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   481
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   482
     *        return size() &gt; MAX_ENTRIES;
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   483
     *     }
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   484
     * </pre>
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   485
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   486
     * <p>This method typically does not modify the map in any way,
90ce3da70b43 Initial load
duke
parents:
diff changeset
   487
     * instead allowing the map to modify itself as directed by its
90ce3da70b43 Initial load
duke
parents:
diff changeset
   488
     * return value.  It <i>is</i> permitted for this method to modify
90ce3da70b43 Initial load
duke
parents:
diff changeset
   489
     * the map directly, but if it does so, it <i>must</i> return
90ce3da70b43 Initial load
duke
parents:
diff changeset
   490
     * <tt>false</tt> (indicating that the map should not attempt any
90ce3da70b43 Initial load
duke
parents:
diff changeset
   491
     * further modification).  The effects of returning <tt>true</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   492
     * after modifying the map from within this method are unspecified.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   493
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   494
     * <p>This implementation merely returns <tt>false</tt> (so that this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   495
     * map acts like a normal map - the eldest element is never removed).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   496
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   497
     * @param    eldest The least recently inserted entry in the map, or if
90ce3da70b43 Initial load
duke
parents:
diff changeset
   498
     *           this is an access-ordered map, the least recently accessed
90ce3da70b43 Initial load
duke
parents:
diff changeset
   499
     *           entry.  This is the entry that will be removed it this
90ce3da70b43 Initial load
duke
parents:
diff changeset
   500
     *           method returns <tt>true</tt>.  If the map was empty prior
90ce3da70b43 Initial load
duke
parents:
diff changeset
   501
     *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
90ce3da70b43 Initial load
duke
parents:
diff changeset
   502
     *           in this invocation, this will be the entry that was just
90ce3da70b43 Initial load
duke
parents:
diff changeset
   503
     *           inserted; in other words, if the map contains a single
90ce3da70b43 Initial load
duke
parents:
diff changeset
   504
     *           entry, the eldest entry is also the newest.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   505
     * @return   <tt>true</tt> if the eldest entry should be removed
90ce3da70b43 Initial load
duke
parents:
diff changeset
   506
     *           from the map; <tt>false</tt> if it should be retained.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   507
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   508
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   509
        return false;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   510
    }
19806
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   511
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   512
    /**
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   513
     * Returns a {@link Set} view of the keys contained in this map.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   514
     * The set is backed by the map, so changes to the map are
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   515
     * reflected in the set, and vice-versa.  If the map is modified
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   516
     * while an iteration over the set is in progress (except through
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   517
     * the iterator's own <tt>remove</tt> operation), the results of
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   518
     * the iteration are undefined.  The set supports element removal,
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   519
     * which removes the corresponding mapping from the map, via the
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   520
     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   521
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   522
     * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   523
     * operations.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   524
     * Its {@link Spliterator} typically provides faster sequential
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   525
     * performance but much poorer parallel performance than that of
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   526
     * {@code HashMap}.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   527
     *
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   528
     * @return a set view of the keys contained in this map
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   529
     */
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   530
    public Set<K> keySet() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   531
        Set<K> ks;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   532
        return (ks = keySet) == null ? (keySet = new LinkedKeySet()) : ks;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   533
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   534
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   535
    final class LinkedKeySet extends AbstractSet<K> {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   536
        public final int size()                 { return size; }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   537
        public final void clear()               { LinkedHashMap.this.clear(); }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   538
        public final Iterator<K> iterator() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   539
            return new LinkedKeyIterator();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   540
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   541
        public final boolean contains(Object o) { return containsKey(o); }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   542
        public final boolean remove(Object key) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   543
            return removeNode(hash(key), key, null, false, true) != null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   544
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   545
        public final Spliterator<K> spliterator()  {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   546
            return Spliterators.spliterator(this, Spliterator.SIZED |
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   547
                                            Spliterator.ORDERED |
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   548
                                            Spliterator.DISTINCT);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   549
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   550
        public final void forEach(Consumer<? super K> action) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   551
            if (action == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   552
                throw new NullPointerException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   553
            int mc = modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   554
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   555
                action.accept(e.key);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   556
            if (modCount != mc)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   557
                throw new ConcurrentModificationException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   558
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   559
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   560
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   561
    /**
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   562
     * Returns a {@link Collection} view of the values contained in this map.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   563
     * The collection is backed by the map, so changes to the map are
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   564
     * reflected in the collection, and vice-versa.  If the map is
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   565
     * modified while an iteration over the collection is in progress
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   566
     * (except through the iterator's own <tt>remove</tt> operation),
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   567
     * the results of the iteration are undefined.  The collection
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   568
     * supports element removal, which removes the corresponding
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   569
     * mapping from the map, via the <tt>Iterator.remove</tt>,
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   570
     * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   571
     * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   572
     * support the <tt>add</tt> or <tt>addAll</tt> operations.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   573
     * Its {@link Spliterator} typically provides faster sequential
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   574
     * performance but much poorer parallel performance than that of
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   575
     * {@code HashMap}.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   576
     *
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   577
     * @return a view of the values contained in this map
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   578
     */
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   579
    public Collection<V> values() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   580
        Collection<V> vs;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   581
        return (vs = values) == null ? (values = new LinkedValues()) : vs;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   582
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   583
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   584
    final class LinkedValues extends AbstractCollection<V> {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   585
        public final int size()                 { return size; }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   586
        public final void clear()               { LinkedHashMap.this.clear(); }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   587
        public final Iterator<V> iterator() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   588
            return new LinkedValueIterator();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   589
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   590
        public final boolean contains(Object o) { return containsValue(o); }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   591
        public final Spliterator<V> spliterator() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   592
            return Spliterators.spliterator(this, Spliterator.SIZED |
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   593
                                            Spliterator.ORDERED);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   594
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   595
        public final void forEach(Consumer<? super V> action) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   596
            if (action == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   597
                throw new NullPointerException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   598
            int mc = modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   599
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   600
                action.accept(e.value);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   601
            if (modCount != mc)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   602
                throw new ConcurrentModificationException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   603
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   604
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   605
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   606
    /**
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   607
     * Returns a {@link Set} view of the mappings contained in this map.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   608
     * The set is backed by the map, so changes to the map are
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   609
     * reflected in the set, and vice-versa.  If the map is modified
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   610
     * while an iteration over the set is in progress (except through
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   611
     * the iterator's own <tt>remove</tt> operation, or through the
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   612
     * <tt>setValue</tt> operation on a map entry returned by the
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   613
     * iterator) the results of the iteration are undefined.  The set
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   614
     * supports element removal, which removes the corresponding
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   615
     * mapping from the map, via the <tt>Iterator.remove</tt>,
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   616
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   617
     * <tt>clear</tt> operations.  It does not support the
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   618
     * <tt>add</tt> or <tt>addAll</tt> operations.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   619
     * Its {@link Spliterator} typically provides faster sequential
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   620
     * performance but much poorer parallel performance than that of
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   621
     * {@code HashMap}.
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   622
     *
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   623
     * @return a set view of the mappings contained in this map
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   624
     */
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   625
    public Set<Map.Entry<K,V>> entrySet() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   626
        Set<Map.Entry<K,V>> es;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   627
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   628
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   629
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   630
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   631
        public final int size()                 { return size; }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   632
        public final void clear()               { LinkedHashMap.this.clear(); }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   633
        public final Iterator<Map.Entry<K,V>> iterator() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   634
            return new LinkedEntryIterator();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   635
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   636
        public final boolean contains(Object o) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   637
            if (!(o instanceof Map.Entry))
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   638
                return false;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   639
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   640
            Object key = e.getKey();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   641
            Node<K,V> candidate = getNode(hash(key), key);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   642
            return candidate != null && candidate.equals(e);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   643
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   644
        public final boolean remove(Object o) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   645
            if (o instanceof Map.Entry) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   646
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   647
                Object key = e.getKey();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   648
                Object value = e.getValue();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   649
                return removeNode(hash(key), key, value, true, true) != null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   650
            }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   651
            return false;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   652
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   653
        public final Spliterator<Map.Entry<K,V>> spliterator() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   654
            return Spliterators.spliterator(this, Spliterator.SIZED |
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   655
                                            Spliterator.ORDERED |
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   656
                                            Spliterator.DISTINCT);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   657
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   658
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   659
            if (action == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   660
                throw new NullPointerException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   661
            int mc = modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   662
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   663
                action.accept(e);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   664
            if (modCount != mc)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   665
                throw new ConcurrentModificationException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   666
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   667
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   668
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   669
    // Map overrides
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   670
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   671
    public void forEach(BiConsumer<? super K, ? super V> action) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   672
        if (action == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   673
            throw new NullPointerException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   674
        int mc = modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   675
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   676
            action.accept(e.key, e.value);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   677
        if (modCount != mc)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   678
            throw new ConcurrentModificationException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   679
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   680
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   681
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   682
        if (function == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   683
            throw new NullPointerException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   684
        int mc = modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   685
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   686
            e.value = function.apply(e.key, e.value);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   687
        if (modCount != mc)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   688
            throw new ConcurrentModificationException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   689
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   690
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   691
    // Iterators
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   692
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   693
    abstract class LinkedHashIterator {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   694
        LinkedHashMap.Entry<K,V> next;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   695
        LinkedHashMap.Entry<K,V> current;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   696
        int expectedModCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   697
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   698
        LinkedHashIterator() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   699
            next = head;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   700
            expectedModCount = modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   701
            current = null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   702
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   703
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   704
        public final boolean hasNext() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   705
            return next != null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   706
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   707
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   708
        final LinkedHashMap.Entry<K,V> nextNode() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   709
            LinkedHashMap.Entry<K,V> e = next;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   710
            if (modCount != expectedModCount)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   711
                throw new ConcurrentModificationException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   712
            if (e == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   713
                throw new NoSuchElementException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   714
            current = e;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   715
            next = e.after;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   716
            return e;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   717
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   718
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   719
        public final void remove() {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   720
            Node<K,V> p = current;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   721
            if (p == null)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   722
                throw new IllegalStateException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   723
            if (modCount != expectedModCount)
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   724
                throw new ConcurrentModificationException();
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   725
            current = null;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   726
            K key = p.key;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   727
            removeNode(hash(key), key, null, false, false);
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   728
            expectedModCount = modCount;
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   729
        }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   730
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   731
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   732
    final class LinkedKeyIterator extends LinkedHashIterator
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   733
        implements Iterator<K> {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   734
        public final K next() { return nextNode().getKey(); }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   735
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   736
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   737
    final class LinkedValueIterator extends LinkedHashIterator
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   738
        implements Iterator<V> {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   739
        public final V next() { return nextNode().value; }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   740
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   741
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   742
    final class LinkedEntryIterator extends LinkedHashIterator
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   743
        implements Iterator<Map.Entry<K,V>> {
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   744
        public final Map.Entry<K,V> next() { return nextNode(); }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   745
    }
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   746
dda89341ee2d 8023463: Improvements to HashMap/LinkedHashMap use of bins/buckets and trees (red/black)
psandoz
parents: 19435
diff changeset
   747
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   748
}