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