WeakHashMap.java revision c3a9db83a352d92d5a6e0098f22bde07e34a1d3b
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. Oracle designates this 9 * particular file as subject to the "Classpath" exception as provided 10 * by Oracle in the LICENSE file that accompanied this code. 11 * 12 * This code is distributed in the hope that it will be useful, but WITHOUT 13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 * version 2 for more details (a copy is included in the LICENSE file that 16 * accompanied this code). 17 * 18 * You should have received a copy of the GNU General Public License version 19 * 2 along with this work; if not, write to the Free Software Foundation, 20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 21 * 22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 23 * or visit www.oracle.com if you need additional information or have any 24 * questions. 25 */ 26 27package java.util; 28import java.lang.ref.WeakReference; 29import java.lang.ref.ReferenceQueue; 30import java.util.function.BiConsumer; 31import java.util.function.Consumer; 32 33 34/** 35 * Hash table based implementation of the <tt>Map</tt> interface, with 36 * <em>weak keys</em>. 37 * An entry in a <tt>WeakHashMap</tt> will automatically be removed when 38 * its key is no longer in ordinary use. More precisely, the presence of a 39 * mapping for a given key will not prevent the key from being discarded by the 40 * garbage collector, that is, made finalizable, finalized, and then reclaimed. 41 * When a key has been discarded its entry is effectively removed from the map, 42 * so this class behaves somewhat differently from other <tt>Map</tt> 43 * implementations. 44 * 45 * <p> Both null values and the null key are supported. This class has 46 * performance characteristics similar to those of the <tt>HashMap</tt> 47 * class, and has the same efficiency parameters of <em>initial capacity</em> 48 * and <em>load factor</em>. 49 * 50 * <p> Like most collection classes, this class is not synchronized. 51 * A synchronized <tt>WeakHashMap</tt> may be constructed using the 52 * {@link Collections#synchronizedMap Collections.synchronizedMap} 53 * method. 54 * 55 * <p> This class is intended primarily for use with key objects whose 56 * <tt>equals</tt> methods test for object identity using the 57 * <tt>==</tt> operator. Once such a key is discarded it can never be 58 * recreated, so it is impossible to do a lookup of that key in a 59 * <tt>WeakHashMap</tt> at some later time and be surprised that its entry 60 * has been removed. This class will work perfectly well with key objects 61 * whose <tt>equals</tt> methods are not based upon object identity, such 62 * as <tt>String</tt> instances. With such recreatable key objects, 63 * however, the automatic removal of <tt>WeakHashMap</tt> entries whose 64 * keys have been discarded may prove to be confusing. 65 * 66 * <p> The behavior of the <tt>WeakHashMap</tt> class depends in part upon 67 * the actions of the garbage collector, so several familiar (though not 68 * required) <tt>Map</tt> invariants do not hold for this class. Because 69 * the garbage collector may discard keys at any time, a 70 * <tt>WeakHashMap</tt> may behave as though an unknown thread is silently 71 * removing entries. In particular, even if you synchronize on a 72 * <tt>WeakHashMap</tt> instance and invoke none of its mutator methods, it 73 * is possible for the <tt>size</tt> method to return smaller values over 74 * time, for the <tt>isEmpty</tt> method to return <tt>false</tt> and 75 * then <tt>true</tt>, for the <tt>containsKey</tt> method to return 76 * <tt>true</tt> and later <tt>false</tt> for a given key, for the 77 * <tt>get</tt> method to return a value for a given key but later return 78 * <tt>null</tt>, for the <tt>put</tt> method to return 79 * <tt>null</tt> and the <tt>remove</tt> method to return 80 * <tt>false</tt> for a key that previously appeared to be in the map, and 81 * for successive examinations of the key set, the value collection, and 82 * the entry set to yield successively smaller numbers of elements. 83 * 84 * <p> Each key object in a <tt>WeakHashMap</tt> is stored indirectly as 85 * the referent of a weak reference. Therefore a key will automatically be 86 * removed only after the weak references to it, both inside and outside of the 87 * map, have been cleared by the garbage collector. 88 * 89 * <p> <strong>Implementation note:</strong> The value objects in a 90 * <tt>WeakHashMap</tt> are held by ordinary strong references. Thus care 91 * should be taken to ensure that value objects do not strongly refer to their 92 * own keys, either directly or indirectly, since that will prevent the keys 93 * from being discarded. Note that a value object may refer indirectly to its 94 * key via the <tt>WeakHashMap</tt> itself; that is, a value object may 95 * strongly refer to some other key object whose associated value object, in 96 * turn, strongly refers to the key of the first value object. If the values 97 * in the map do not rely on the map holding strong references to them, one way 98 * to deal with this is to wrap values themselves within 99 * <tt>WeakReferences</tt> before 100 * inserting, as in: <tt>m.put(key, new WeakReference(value))</tt>, 101 * and then unwrapping upon each <tt>get</tt>. 102 * 103 * <p>The iterators returned by the <tt>iterator</tt> method of the collections 104 * returned by all of this class's "collection view methods" are 105 * <i>fail-fast</i>: if the map is structurally modified at any time after the 106 * iterator is created, in any way except through the iterator's own 107 * <tt>remove</tt> method, the iterator will throw a {@link 108 * ConcurrentModificationException}. Thus, in the face of concurrent 109 * modification, the iterator fails quickly and cleanly, rather than risking 110 * arbitrary, non-deterministic behavior at an undetermined time in the future. 111 * 112 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 113 * as it is, generally speaking, impossible to make any hard guarantees in the 114 * presence of unsynchronized concurrent modification. Fail-fast iterators 115 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 116 * Therefore, it would be wrong to write a program that depended on this 117 * exception for its correctness: <i>the fail-fast behavior of iterators 118 * should be used only to detect bugs.</i> 119 * 120 * <p>This class is a member of the 121 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 122 * Java Collections Framework</a>. 123 * 124 * @param <K> the type of keys maintained by this map 125 * @param <V> the type of mapped values 126 * 127 * @author Doug Lea 128 * @author Josh Bloch 129 * @author Mark Reinhold 130 * @since 1.2 131 * @see java.util.HashMap 132 * @see java.lang.ref.WeakReference 133 */ 134public class WeakHashMap<K,V> 135 extends AbstractMap<K,V> 136 implements Map<K,V> { 137 138 /** 139 * The default initial capacity -- MUST be a power of two. 140 */ 141 private static final int DEFAULT_INITIAL_CAPACITY = 16; 142 143 /** 144 * The maximum capacity, used if a higher value is implicitly specified 145 * by either of the constructors with arguments. 146 * MUST be a power of two <= 1<<30. 147 */ 148 private static final int MAXIMUM_CAPACITY = 1 << 30; 149 150 /** 151 * The load factor used when none specified in constructor. 152 */ 153 private static final float DEFAULT_LOAD_FACTOR = 0.75f; 154 155 /** 156 * The table, resized as necessary. Length MUST Always be a power of two. 157 */ 158 Entry<K,V>[] table; 159 160 /** 161 * The number of key-value mappings contained in this weak hash map. 162 */ 163 private int size; 164 165 /** 166 * The next size value at which to resize (capacity * load factor). 167 */ 168 private int threshold; 169 170 /** 171 * The load factor for the hash table. 172 */ 173 private final float loadFactor; 174 175 /** 176 * Reference queue for cleared WeakEntries 177 */ 178 private final ReferenceQueue<Object> queue = new ReferenceQueue<>(); 179 180 /** 181 * The number of times this WeakHashMap has been structurally modified. 182 * Structural modifications are those that change the number of 183 * mappings in the map or otherwise modify its internal structure 184 * (e.g., rehash). This field is used to make iterators on 185 * Collection-views of the map fail-fast. 186 * 187 * @see ConcurrentModificationException 188 */ 189 int modCount; 190 191 /** 192 * The default threshold of map capacity above which alternative hashing is 193 * used for String keys. Alternative hashing reduces the incidence of 194 * collisions due to weak hash code calculation for String keys. 195 * <p/> 196 * This value may be overridden by defining the system property 197 * {@code jdk.map.althashing.threshold}. A property value of {@code 1} 198 * forces alternative hashing to be used at all times whereas 199 * {@code -1} value ensures that alternative hashing is never used. 200 */ 201 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; 202 203 /** 204 * holds values which can't be initialized until after VM is booted. 205 */ 206 private static class Holder { 207 208 /** 209 * Table capacity above which to switch to use alternative hashing. 210 */ 211 static final int ALTERNATIVE_HASHING_THRESHOLD; 212 213 static { 214 String altThreshold = java.security.AccessController.doPrivileged( 215 new sun.security.action.GetPropertyAction( 216 "jdk.map.althashing.threshold")); 217 218 int threshold; 219 try { 220 threshold = (null != altThreshold) 221 ? Integer.parseInt(altThreshold) 222 : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; 223 224 // disable alternative hashing if -1 225 if (threshold == -1) { 226 threshold = Integer.MAX_VALUE; 227 } 228 229 if (threshold < 0) { 230 throw new IllegalArgumentException("value must be positive integer."); 231 } 232 } catch(IllegalArgumentException failed) { 233 throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed); 234 } 235 ALTERNATIVE_HASHING_THRESHOLD = threshold; 236 } 237 } 238 239 /** 240 * If {@code true} then perform alternate hashing to reduce the incidence of 241 * collisions due to weak hash code calculation. 242 */ 243 transient boolean useAltHashing; 244 245 /** 246 * A randomizing value associated with this instance that is applied to 247 * hash code of keys to make hash collisions harder to find. 248 * 249 * This hash seed is only used if {@code useAltHashing} is true. 250 */ 251 transient int hashSeed; 252 253 @SuppressWarnings("unchecked") 254 private Entry<K,V>[] newTable(int n) { 255 return (Entry<K,V>[]) new Entry[n]; 256 } 257 258 /** 259 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 260 * capacity and the given load factor. 261 * 262 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 263 * @param loadFactor The load factor of the <tt>WeakHashMap</tt> 264 * @throws IllegalArgumentException if the initial capacity is negative, 265 * or if the load factor is nonpositive. 266 */ 267 public WeakHashMap(int initialCapacity, float loadFactor) { 268 if (initialCapacity < 0) 269 throw new IllegalArgumentException("Illegal Initial Capacity: "+ 270 initialCapacity); 271 if (initialCapacity > MAXIMUM_CAPACITY) 272 initialCapacity = MAXIMUM_CAPACITY; 273 274 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 275 throw new IllegalArgumentException("Illegal Load factor: "+ 276 loadFactor); 277 int capacity = 1; 278 while (capacity < initialCapacity) 279 capacity <<= 1; 280 table = newTable(capacity); 281 this.loadFactor = loadFactor; 282 threshold = (int)(capacity * loadFactor); 283 useAltHashing = sun.misc.VM.isBooted() && 284 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 285 if (useAltHashing) { 286 hashSeed = sun.misc.Hashing.randomHashSeed(this); 287 } else { 288 hashSeed = 0; 289 } 290 } 291 292 /** 293 * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial 294 * capacity and the default load factor (0.75). 295 * 296 * @param initialCapacity The initial capacity of the <tt>WeakHashMap</tt> 297 * @throws IllegalArgumentException if the initial capacity is negative 298 */ 299 public WeakHashMap(int initialCapacity) { 300 this(initialCapacity, DEFAULT_LOAD_FACTOR); 301 } 302 303 /** 304 * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial 305 * capacity (16) and load factor (0.75). 306 */ 307 public WeakHashMap() { 308 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); 309 } 310 311 /** 312 * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the 313 * specified map. The <tt>WeakHashMap</tt> is created with the default 314 * load factor (0.75) and an initial capacity sufficient to hold the 315 * mappings in the specified map. 316 * 317 * @param m the map whose mappings are to be placed in this map 318 * @throws NullPointerException if the specified map is null 319 * @since 1.3 320 */ 321 public WeakHashMap(Map<? extends K, ? extends V> m) { 322 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 323 DEFAULT_INITIAL_CAPACITY), 324 DEFAULT_LOAD_FACTOR); 325 putAll(m); 326 } 327 328 // internal utilities 329 330 /** 331 * Value representing null keys inside tables. 332 */ 333 private static final Object NULL_KEY = new Object(); 334 335 /** 336 * Use NULL_KEY for key if it is null. 337 */ 338 private static Object maskNull(Object key) { 339 return (key == null) ? NULL_KEY : key; 340 } 341 342 /** 343 * Returns internal representation of null key back to caller as null. 344 */ 345 static Object unmaskNull(Object key) { 346 return (key == NULL_KEY) ? null : key; 347 } 348 349 /** 350 * Checks for equality of non-null reference x and possibly-null y. By 351 * default uses Object.equals. 352 */ 353 private static boolean eq(Object x, Object y) { 354 return x == y || x.equals(y); 355 } 356 357 /** 358 * Retrieve object hash code and applies a supplemental hash function to the 359 * result hash, which defends against poor quality hash functions. This is 360 * critical because HashMap uses power-of-two length hash tables, that 361 * otherwise encounter collisions for hashCodes that do not differ 362 * in lower bits. 363 */ 364 int hash(Object k) { 365 366 int h; 367 if (useAltHashing) { 368 h = hashSeed; 369 if (k instanceof String) { 370 return sun.misc.Hashing.stringHash32((String) k); 371 } else { 372 h ^= k.hashCode(); 373 } 374 } else { 375 h = k.hashCode(); 376 } 377 378 // This function ensures that hashCodes that differ only by 379 // constant multiples at each bit position have a bounded 380 // number of collisions (approximately 8 at default load factor). 381 h ^= (h >>> 20) ^ (h >>> 12); 382 return h ^ (h >>> 7) ^ (h >>> 4); 383 } 384 385 /** 386 * Returns index for hash code h. 387 */ 388 private static int indexFor(int h, int length) { 389 return h & (length-1); 390 } 391 392 /** 393 * Expunges stale entries from the table. 394 */ 395 private void expungeStaleEntries() { 396 for (Object x; (x = queue.poll()) != null; ) { 397 synchronized (queue) { 398 @SuppressWarnings("unchecked") 399 Entry<K,V> e = (Entry<K,V>) x; 400 int i = indexFor(e.hash, table.length); 401 402 Entry<K,V> prev = table[i]; 403 Entry<K,V> p = prev; 404 while (p != null) { 405 Entry<K,V> next = p.next; 406 if (p == e) { 407 if (prev == e) 408 table[i] = next; 409 else 410 prev.next = next; 411 // Must not null out e.next; 412 // stale entries may be in use by a HashIterator 413 e.value = null; // Help GC 414 size--; 415 break; 416 } 417 prev = p; 418 p = next; 419 } 420 } 421 } 422 } 423 424 /** 425 * Returns the table after first expunging stale entries. 426 */ 427 private Entry<K,V>[] getTable() { 428 expungeStaleEntries(); 429 return table; 430 } 431 432 /** 433 * Returns the number of key-value mappings in this map. 434 * This result is a snapshot, and may not reflect unprocessed 435 * entries that will be removed before next attempted access 436 * because they are no longer referenced. 437 */ 438 public int size() { 439 if (size == 0) 440 return 0; 441 expungeStaleEntries(); 442 return size; 443 } 444 445 /** 446 * Returns <tt>true</tt> if this map contains no key-value mappings. 447 * This result is a snapshot, and may not reflect unprocessed 448 * entries that will be removed before next attempted access 449 * because they are no longer referenced. 450 */ 451 public boolean isEmpty() { 452 return size() == 0; 453 } 454 455 /** 456 * Returns the value to which the specified key is mapped, 457 * or {@code null} if this map contains no mapping for the key. 458 * 459 * <p>More formally, if this map contains a mapping from a key 460 * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 461 * key.equals(k))}, then this method returns {@code v}; otherwise 462 * it returns {@code null}. (There can be at most one such mapping.) 463 * 464 * <p>A return value of {@code null} does not <i>necessarily</i> 465 * indicate that the map contains no mapping for the key; it's also 466 * possible that the map explicitly maps the key to {@code null}. 467 * The {@link #containsKey containsKey} operation may be used to 468 * distinguish these two cases. 469 * 470 * @see #put(Object, Object) 471 */ 472 public V get(Object key) { 473 Object k = maskNull(key); 474 int h = hash(k); 475 Entry<K,V>[] tab = getTable(); 476 int index = indexFor(h, tab.length); 477 Entry<K,V> e = tab[index]; 478 while (e != null) { 479 if (e.hash == h && eq(k, e.get())) 480 return e.value; 481 e = e.next; 482 } 483 return null; 484 } 485 486 /** 487 * Returns <tt>true</tt> if this map contains a mapping for the 488 * specified key. 489 * 490 * @param key The key whose presence in this map is to be tested 491 * @return <tt>true</tt> if there is a mapping for <tt>key</tt>; 492 * <tt>false</tt> otherwise 493 */ 494 public boolean containsKey(Object key) { 495 return getEntry(key) != null; 496 } 497 498 /** 499 * Returns the entry associated with the specified key in this map. 500 * Returns null if the map contains no mapping for this key. 501 */ 502 Entry<K,V> getEntry(Object key) { 503 Object k = maskNull(key); 504 int h = hash(k); 505 Entry<K,V>[] tab = getTable(); 506 int index = indexFor(h, tab.length); 507 Entry<K,V> e = tab[index]; 508 while (e != null && !(e.hash == h && eq(k, e.get()))) 509 e = e.next; 510 return e; 511 } 512 513 /** 514 * Associates the specified value with the specified key in this map. 515 * If the map previously contained a mapping for this key, the old 516 * value is replaced. 517 * 518 * @param key key with which the specified value is to be associated. 519 * @param value value to be associated with the specified key. 520 * @return the previous value associated with <tt>key</tt>, or 521 * <tt>null</tt> if there was no mapping for <tt>key</tt>. 522 * (A <tt>null</tt> return can also indicate that the map 523 * previously associated <tt>null</tt> with <tt>key</tt>.) 524 */ 525 public V put(K key, V value) { 526 Object k = maskNull(key); 527 int h = hash(k); 528 Entry<K,V>[] tab = getTable(); 529 int i = indexFor(h, tab.length); 530 531 for (Entry<K,V> e = tab[i]; e != null; e = e.next) { 532 if (h == e.hash && eq(k, e.get())) { 533 V oldValue = e.value; 534 if (value != oldValue) 535 e.value = value; 536 return oldValue; 537 } 538 } 539 540 modCount++; 541 Entry<K,V> e = tab[i]; 542 tab[i] = new Entry<>(k, value, queue, h, e); 543 if (++size >= threshold) 544 resize(tab.length * 2); 545 return null; 546 } 547 548 /** 549 * Rehashes the contents of this map into a new array with a 550 * larger capacity. This method is called automatically when the 551 * number of keys in this map reaches its threshold. 552 * 553 * If current capacity is MAXIMUM_CAPACITY, this method does not 554 * resize the map, but sets threshold to Integer.MAX_VALUE. 555 * This has the effect of preventing future calls. 556 * 557 * @param newCapacity the new capacity, MUST be a power of two; 558 * must be greater than current capacity unless current 559 * capacity is MAXIMUM_CAPACITY (in which case value 560 * is irrelevant). 561 */ 562 void resize(int newCapacity) { 563 Entry<K,V>[] oldTable = getTable(); 564 int oldCapacity = oldTable.length; 565 if (oldCapacity == MAXIMUM_CAPACITY) { 566 threshold = Integer.MAX_VALUE; 567 return; 568 } 569 570 Entry<K,V>[] newTable = newTable(newCapacity); 571 boolean oldAltHashing = useAltHashing; 572 useAltHashing |= sun.misc.VM.isBooted() && 573 (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 574 boolean rehash = oldAltHashing ^ useAltHashing; 575 if (rehash) { 576 hashSeed = sun.misc.Hashing.randomHashSeed(this); 577 } 578 transfer(oldTable, newTable, rehash); 579 table = newTable; 580 581 /* 582 * If ignoring null elements and processing ref queue caused massive 583 * shrinkage, then restore old table. This should be rare, but avoids 584 * unbounded expansion of garbage-filled tables. 585 */ 586 if (size >= threshold / 2) { 587 threshold = (int)(newCapacity * loadFactor); 588 } else { 589 expungeStaleEntries(); 590 transfer(newTable, oldTable, false); 591 table = oldTable; 592 } 593 } 594 595 /** Transfers all entries from src to dest tables */ 596 private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) { 597 for (int j = 0; j < src.length; ++j) { 598 Entry<K,V> e = src[j]; 599 src[j] = null; 600 while (e != null) { 601 Entry<K,V> next = e.next; 602 Object key = e.get(); 603 if (key == null) { 604 e.next = null; // Help GC 605 e.value = null; // " " 606 size--; 607 } else { 608 if (rehash) { 609 e.hash = hash(key); 610 } 611 int i = indexFor(e.hash, dest.length); 612 e.next = dest[i]; 613 dest[i] = e; 614 } 615 e = next; 616 } 617 } 618 } 619 620 /** 621 * Copies all of the mappings from the specified map to this map. 622 * These mappings will replace any mappings that this map had for any 623 * of the keys currently in the specified map. 624 * 625 * @param m mappings to be stored in this map. 626 * @throws NullPointerException if the specified map is null. 627 */ 628 public void putAll(Map<? extends K, ? extends V> m) { 629 int numKeysToBeAdded = m.size(); 630 if (numKeysToBeAdded == 0) 631 return; 632 633 /* 634 * Expand the map if the map if the number of mappings to be added 635 * is greater than or equal to threshold. This is conservative; the 636 * obvious condition is (m.size() + size) >= threshold, but this 637 * condition could result in a map with twice the appropriate capacity, 638 * if the keys to be added overlap with the keys already in this map. 639 * By using the conservative calculation, we subject ourself 640 * to at most one extra resize. 641 */ 642 if (numKeysToBeAdded > threshold) { 643 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1); 644 if (targetCapacity > MAXIMUM_CAPACITY) 645 targetCapacity = MAXIMUM_CAPACITY; 646 int newCapacity = table.length; 647 while (newCapacity < targetCapacity) 648 newCapacity <<= 1; 649 if (newCapacity > table.length) 650 resize(newCapacity); 651 } 652 653 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) 654 put(e.getKey(), e.getValue()); 655 } 656 657 /** 658 * Removes the mapping for a key from this weak hash map if it is present. 659 * More formally, if this map contains a mapping from key <tt>k</tt> to 660 * value <tt>v</tt> such that <code>(key==null ? k==null : 661 * key.equals(k))</code>, that mapping is removed. (The map can contain 662 * at most one such mapping.) 663 * 664 * <p>Returns the value to which this map previously associated the key, 665 * or <tt>null</tt> if the map contained no mapping for the key. A 666 * return value of <tt>null</tt> does not <i>necessarily</i> indicate 667 * that the map contained no mapping for the key; it's also possible 668 * that the map explicitly mapped the key to <tt>null</tt>. 669 * 670 * <p>The map will not contain a mapping for the specified key once the 671 * call returns. 672 * 673 * @param key key whose mapping is to be removed from the map 674 * @return the previous value associated with <tt>key</tt>, or 675 * <tt>null</tt> if there was no mapping for <tt>key</tt> 676 */ 677 public V remove(Object key) { 678 Object k = maskNull(key); 679 int h = hash(k); 680 Entry<K,V>[] tab = getTable(); 681 int i = indexFor(h, tab.length); 682 Entry<K,V> prev = tab[i]; 683 Entry<K,V> e = prev; 684 685 while (e != null) { 686 Entry<K,V> next = e.next; 687 if (h == e.hash && eq(k, e.get())) { 688 modCount++; 689 size--; 690 if (prev == e) 691 tab[i] = next; 692 else 693 prev.next = next; 694 return e.value; 695 } 696 prev = e; 697 e = next; 698 } 699 700 return null; 701 } 702 703 /** Special version of remove needed by Entry set */ 704 boolean removeMapping(Object o) { 705 if (!(o instanceof Map.Entry)) 706 return false; 707 Entry<K,V>[] tab = getTable(); 708 Map.Entry<?,?> entry = (Map.Entry<?,?>)o; 709 Object k = maskNull(entry.getKey()); 710 int h = hash(k); 711 int i = indexFor(h, tab.length); 712 Entry<K,V> prev = tab[i]; 713 Entry<K,V> e = prev; 714 715 while (e != null) { 716 Entry<K,V> next = e.next; 717 if (h == e.hash && e.equals(entry)) { 718 modCount++; 719 size--; 720 if (prev == e) 721 tab[i] = next; 722 else 723 prev.next = next; 724 return true; 725 } 726 prev = e; 727 e = next; 728 } 729 730 return false; 731 } 732 733 /** 734 * Removes all of the mappings from this map. 735 * The map will be empty after this call returns. 736 */ 737 public void clear() { 738 // clear out ref queue. We don't need to expunge entries 739 // since table is getting cleared. 740 while (queue.poll() != null) 741 ; 742 743 modCount++; 744 Arrays.fill(table, null); 745 size = 0; 746 747 // Allocation of array may have caused GC, which may have caused 748 // additional entries to go stale. Removing these entries from the 749 // reference queue will make them eligible for reclamation. 750 while (queue.poll() != null) 751 ; 752 } 753 754 /** 755 * Returns <tt>true</tt> if this map maps one or more keys to the 756 * specified value. 757 * 758 * @param value value whose presence in this map is to be tested 759 * @return <tt>true</tt> if this map maps one or more keys to the 760 * specified value 761 */ 762 public boolean containsValue(Object value) { 763 if (value==null) 764 return containsNullValue(); 765 766 Entry<K,V>[] tab = getTable(); 767 for (int i = tab.length; i-- > 0;) 768 for (Entry<K,V> e = tab[i]; e != null; e = e.next) 769 if (value.equals(e.value)) 770 return true; 771 return false; 772 } 773 774 /** 775 * Special-case code for containsValue with null argument 776 */ 777 private boolean containsNullValue() { 778 Entry<K,V>[] tab = getTable(); 779 for (int i = tab.length; i-- > 0;) 780 for (Entry<K,V> e = tab[i]; e != null; e = e.next) 781 if (e.value==null) 782 return true; 783 return false; 784 } 785 786 /** 787 * The entries in this hash table extend WeakReference, using its main ref 788 * field as the key. 789 */ 790 private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> { 791 V value; 792 int hash; 793 Entry<K,V> next; 794 795 /** 796 * Creates new entry. 797 */ 798 Entry(Object key, V value, 799 ReferenceQueue<Object> queue, 800 int hash, Entry<K,V> next) { 801 super(key, queue); 802 this.value = value; 803 this.hash = hash; 804 this.next = next; 805 } 806 807 @SuppressWarnings("unchecked") 808 public K getKey() { 809 return (K) WeakHashMap.unmaskNull(get()); 810 } 811 812 public V getValue() { 813 return value; 814 } 815 816 public V setValue(V newValue) { 817 V oldValue = value; 818 value = newValue; 819 return oldValue; 820 } 821 822 public boolean equals(Object o) { 823 if (!(o instanceof Map.Entry)) 824 return false; 825 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 826 K k1 = getKey(); 827 Object k2 = e.getKey(); 828 if (k1 == k2 || (k1 != null && k1.equals(k2))) { 829 V v1 = getValue(); 830 Object v2 = e.getValue(); 831 if (v1 == v2 || (v1 != null && v1.equals(v2))) 832 return true; 833 } 834 return false; 835 } 836 837 public int hashCode() { 838 K k = getKey(); 839 V v = getValue(); 840 return ((k==null ? 0 : k.hashCode()) ^ 841 (v==null ? 0 : v.hashCode())); 842 } 843 844 public String toString() { 845 return getKey() + "=" + getValue(); 846 } 847 } 848 849 private abstract class HashIterator<T> implements Iterator<T> { 850 private int index; 851 private Entry<K,V> entry = null; 852 private Entry<K,V> lastReturned = null; 853 private int expectedModCount = modCount; 854 855 /** 856 * Strong reference needed to avoid disappearance of key 857 * between hasNext and next 858 */ 859 private Object nextKey = null; 860 861 /** 862 * Strong reference needed to avoid disappearance of key 863 * between nextEntry() and any use of the entry 864 */ 865 private Object currentKey = null; 866 867 HashIterator() { 868 index = isEmpty() ? 0 : table.length; 869 } 870 871 public boolean hasNext() { 872 Entry<K,V>[] t = table; 873 874 while (nextKey == null) { 875 Entry<K,V> e = entry; 876 int i = index; 877 while (e == null && i > 0) 878 e = t[--i]; 879 entry = e; 880 index = i; 881 if (e == null) { 882 currentKey = null; 883 return false; 884 } 885 nextKey = e.get(); // hold on to key in strong ref 886 if (nextKey == null) 887 entry = entry.next; 888 } 889 return true; 890 } 891 892 /** The common parts of next() across different types of iterators */ 893 protected Entry<K,V> nextEntry() { 894 if (modCount != expectedModCount) 895 throw new ConcurrentModificationException(); 896 if (nextKey == null && !hasNext()) 897 throw new NoSuchElementException(); 898 899 lastReturned = entry; 900 entry = entry.next; 901 currentKey = nextKey; 902 nextKey = null; 903 return lastReturned; 904 } 905 906 public void remove() { 907 if (lastReturned == null) 908 throw new IllegalStateException(); 909 if (modCount != expectedModCount) 910 throw new ConcurrentModificationException(); 911 912 WeakHashMap.this.remove(currentKey); 913 expectedModCount = modCount; 914 lastReturned = null; 915 currentKey = null; 916 } 917 918 } 919 920 private class ValueIterator extends HashIterator<V> { 921 public V next() { 922 return nextEntry().value; 923 } 924 } 925 926 private class KeyIterator extends HashIterator<K> { 927 public K next() { 928 return nextEntry().getKey(); 929 } 930 } 931 932 private class EntryIterator extends HashIterator<Map.Entry<K,V>> { 933 public Map.Entry<K,V> next() { 934 return nextEntry(); 935 } 936 } 937 938 // Views 939 940 private transient Set<Map.Entry<K,V>> entrySet = null; 941 942 /** 943 * Returns a {@link Set} view of the keys contained in this map. 944 * The set is backed by the map, so changes to the map are 945 * reflected in the set, and vice-versa. If the map is modified 946 * while an iteration over the set is in progress (except through 947 * the iterator's own <tt>remove</tt> operation), the results of 948 * the iteration are undefined. The set supports element removal, 949 * which removes the corresponding mapping from the map, via the 950 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, 951 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> 952 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt> 953 * operations. 954 */ 955 public Set<K> keySet() { 956 Set<K> ks = keySet; 957 return (ks != null ? ks : (keySet = new KeySet())); 958 } 959 960 private class KeySet extends AbstractSet<K> { 961 public Iterator<K> iterator() { 962 return new KeyIterator(); 963 } 964 965 public int size() { 966 return WeakHashMap.this.size(); 967 } 968 969 public boolean contains(Object o) { 970 return containsKey(o); 971 } 972 973 public boolean remove(Object o) { 974 if (containsKey(o)) { 975 WeakHashMap.this.remove(o); 976 return true; 977 } 978 else 979 return false; 980 } 981 982 public void clear() { 983 WeakHashMap.this.clear(); 984 } 985 } 986 987 /** 988 * Returns a {@link Collection} view of the values contained in this map. 989 * The collection is backed by the map, so changes to the map are 990 * reflected in the collection, and vice-versa. If the map is 991 * modified while an iteration over the collection is in progress 992 * (except through the iterator's own <tt>remove</tt> operation), 993 * the results of the iteration are undefined. The collection 994 * supports element removal, which removes the corresponding 995 * mapping from the map, via the <tt>Iterator.remove</tt>, 996 * <tt>Collection.remove</tt>, <tt>removeAll</tt>, 997 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not 998 * support the <tt>add</tt> or <tt>addAll</tt> operations. 999 */ 1000 public Collection<V> values() { 1001 Collection<V> vs = values; 1002 return (vs != null) ? vs : (values = new Values()); 1003 } 1004 1005 private class Values extends AbstractCollection<V> { 1006 public Iterator<V> iterator() { 1007 return new ValueIterator(); 1008 } 1009 1010 public int size() { 1011 return WeakHashMap.this.size(); 1012 } 1013 1014 public boolean contains(Object o) { 1015 return containsValue(o); 1016 } 1017 1018 public void clear() { 1019 WeakHashMap.this.clear(); 1020 } 1021 } 1022 1023 /** 1024 * Returns a {@link Set} view of the mappings contained in this map. 1025 * The set is backed by the map, so changes to the map are 1026 * reflected in the set, and vice-versa. If the map is modified 1027 * while an iteration over the set is in progress (except through 1028 * the iterator's own <tt>remove</tt> operation, or through the 1029 * <tt>setValue</tt> operation on a map entry returned by the 1030 * iterator) the results of the iteration are undefined. The set 1031 * supports element removal, which removes the corresponding 1032 * mapping from the map, via the <tt>Iterator.remove</tt>, 1033 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and 1034 * <tt>clear</tt> operations. It does not support the 1035 * <tt>add</tt> or <tt>addAll</tt> operations. 1036 */ 1037 public Set<Map.Entry<K,V>> entrySet() { 1038 Set<Map.Entry<K,V>> es = entrySet; 1039 return es != null ? es : (entrySet = new EntrySet()); 1040 } 1041 1042 private class EntrySet extends AbstractSet<Map.Entry<K,V>> { 1043 public Iterator<Map.Entry<K,V>> iterator() { 1044 return new EntryIterator(); 1045 } 1046 1047 public boolean contains(Object o) { 1048 if (!(o instanceof Map.Entry)) 1049 return false; 1050 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 1051 Entry<K,V> candidate = getEntry(e.getKey()); 1052 return candidate != null && candidate.equals(e); 1053 } 1054 1055 public boolean remove(Object o) { 1056 return removeMapping(o); 1057 } 1058 1059 public int size() { 1060 return WeakHashMap.this.size(); 1061 } 1062 1063 public void clear() { 1064 WeakHashMap.this.clear(); 1065 } 1066 1067 private List<Map.Entry<K,V>> deepCopy() { 1068 List<Map.Entry<K,V>> list = new ArrayList<>(size()); 1069 for (Map.Entry<K,V> e : this) 1070 list.add(new AbstractMap.SimpleEntry<>(e)); 1071 return list; 1072 } 1073 1074 public Object[] toArray() { 1075 return deepCopy().toArray(); 1076 } 1077 1078 public <T> T[] toArray(T[] a) { 1079 return deepCopy().toArray(a); 1080 } 1081 } 1082 1083 @SuppressWarnings("unchecked") 1084 @Override 1085 public void forEach(BiConsumer<? super K, ? super V> action) { 1086 Objects.requireNonNull(action); 1087 int expectedModCount = modCount; 1088 1089 Entry<K, V>[] tab = getTable(); 1090 for (Entry<K, V> entry : tab) { 1091 while (entry != null) { 1092 Object key = entry.get(); 1093 if (key != null) { 1094 action.accept((K)WeakHashMap.unmaskNull(key), entry.value); 1095 } 1096 entry = entry.next; 1097 1098 if (expectedModCount != modCount) { 1099 throw new ConcurrentModificationException(); 1100 } 1101 } 1102 } 1103 } 1104} 1105