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