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