< prev index next >

src/java.base/share/classes/java/util/WeakHashMap.java

Print this page

   1 /*
   2  * Copyright (c) 1998, 2024, 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.lang.ref.WeakReference;
  29 import java.lang.ref.ReferenceQueue;

  30 import java.util.function.BiConsumer;
  31 import java.util.function.BiFunction;
  32 import java.util.function.Consumer;
  33 
  34 
  35 /**
  36  * Hash table based implementation of the {@code Map} interface, with
  37  * <em>weak keys</em>.
  38  * An entry in a {@code WeakHashMap} will automatically be removed when
  39  * its key is no longer in ordinary use.  More precisely, the presence of a
  40  * mapping for a given key will not prevent the key from being discarded by the
  41  * garbage collector, that is, made finalizable, finalized, and then reclaimed.
  42  * When a key has been discarded its entry is effectively removed from the map,
  43  * so this class behaves somewhat differently from other {@code Map}
  44  * implementations.
  45  *
  46  * <p> Both null values and the null key are supported. This class has
  47  * performance characteristics similar to those of the {@code HashMap}
  48  * class, and has the same efficiency parameters of <em>initial capacity</em>
  49  * and <em>load factor</em>.

 105  * returned by all of this class's "collection view methods" are
 106  * <i>fail-fast</i>: if the map is structurally modified at any time after the
 107  * iterator is created, in any way except through the iterator's own
 108  * {@code remove} method, the iterator will throw a {@link
 109  * ConcurrentModificationException}.  Thus, in the face of concurrent
 110  * modification, the iterator fails quickly and cleanly, rather than risking
 111  * arbitrary, non-deterministic behavior at an undetermined time in the future.
 112  *
 113  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 114  * as it is, generally speaking, impossible to make any hard guarantees in the
 115  * presence of unsynchronized concurrent modification.  Fail-fast iterators
 116  * throw {@code ConcurrentModificationException} on a best-effort basis.
 117  * Therefore, it would be wrong to write a program that depended on this
 118  * exception for its correctness:  <i>the fail-fast behavior of iterators
 119  * should be used only to detect bugs.</i>
 120  *
 121  * <p>This class is a member of the
 122  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 123  * Java Collections Framework</a>.
 124  *
















 125  * @param <K> the type of keys maintained by this map
 126  * @param <V> the type of mapped values
 127  *
 128  * @author      Doug Lea
 129  * @author      Josh Bloch
 130  * @author      Mark Reinhold
 131  * @since       1.2
 132  * @see         java.util.HashMap
 133  * @see         java.lang.ref.WeakReference
 134  */
 135 public class WeakHashMap<K,V>
 136     extends AbstractMap<K,V>
 137     implements Map<K,V> {
 138 
 139     /**
 140      * The default initial capacity -- MUST be a power of two.
 141      */
 142     private static final int DEFAULT_INITIAL_CAPACITY = 16;
 143 
 144     /**

 271      */
 272     private static final Object NULL_KEY = new Object();
 273 
 274     /**
 275      * Use NULL_KEY for key if it is null.
 276      */
 277     private static Object maskNull(Object key) {
 278         return (key == null) ? NULL_KEY : key;
 279     }
 280 
 281     /**
 282      * Returns internal representation of null key back to caller as null.
 283      */
 284     static Object unmaskNull(Object key) {
 285         return (key == NULL_KEY) ? null : key;
 286     }
 287 
 288     /**
 289      * Checks for equality of non-null reference x and possibly-null y.  By
 290      * default uses Object.equals.


 291      */
 292     private boolean matchesKey(Entry<K,V> e, Object key) {
 293         // check if the given entry refers to the given key without
 294         // keeping a strong reference to the entry's referent
 295         if (e.refersTo(key)) return true;
 296 
 297         // then check for equality if the referent is not cleared
 298         Object k = e.get();
 299         return k != null && key.equals(k);
 300     }
 301 
 302     /**
 303      * Retrieve object hash code and applies a supplemental hash function to the
 304      * result hash, which defends against poor quality hash functions.  This is
 305      * critical because HashMap uses power-of-two length hash tables, that
 306      * otherwise encounter collisions for hashCodes that do not differ
 307      * in lower bits.
 308      */
 309     final int hash(Object k) {
 310         int h = k.hashCode();

 439         int h = hash(k);
 440         Entry<K,V>[] tab = getTable();
 441         int index = indexFor(h, tab.length);
 442         Entry<K,V> e = tab[index];
 443         while (e != null && !(e.hash == h && matchesKey(e, k)))
 444             e = e.next;
 445         return e;
 446     }
 447 
 448     /**
 449      * Associates the specified value with the specified key in this map.
 450      * If the map previously contained a mapping for this key, the old
 451      * value is replaced.
 452      *
 453      * @param key key with which the specified value is to be associated.
 454      * @param value value to be associated with the specified key.
 455      * @return the previous value associated with {@code key}, or
 456      *         {@code null} if there was no mapping for {@code key}.
 457      *         (A {@code null} return can also indicate that the map
 458      *         previously associated {@code null} with {@code key}.)

 459      */
 460     public V put(K key, V value) {
 461         Object k = maskNull(key);

 462         int h = hash(k);
 463         Entry<K,V>[] tab = getTable();
 464         int i = indexFor(h, tab.length);
 465 
 466         for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
 467             if (h == e.hash && matchesKey(e, k)) {
 468                 V oldValue = e.value;
 469                 if (value != oldValue)
 470                     e.value = value;
 471                 return oldValue;
 472             }
 473         }
 474 
 475         modCount++;
 476         Entry<K,V> e = tab[i];
 477         tab[i] = new Entry<>(k, value, queue, h, e);
 478         if (++size > threshold)
 479             resize(tab.length * 2);
 480         return null;
 481     }

 529                 Entry<K,V> next = e.next;
 530                 if (e.refersTo(null)) {
 531                     e.next = null;  // Help GC
 532                     e.value = null; //  "   "
 533                     size--;
 534                 } else {
 535                     int i = indexFor(e.hash, dest.length);
 536                     e.next = dest[i];
 537                     dest[i] = e;
 538                 }
 539                 e = next;
 540             }
 541         }
 542     }
 543 
 544     /**
 545      * Copies all of the mappings from the specified map to this map.
 546      * These mappings will replace any mappings that this map had for any
 547      * of the keys currently in the specified map.
 548      *




 549      * @param m mappings to be stored in this map.
 550      * @throws  NullPointerException if the specified map is null.

 551      */
 552     public void putAll(Map<? extends K, ? extends V> m) {
 553         int numKeysToBeAdded = m.size();
 554         if (numKeysToBeAdded == 0)
 555             return;
 556 
 557         /*
 558          * Expand the map if the map if the number of mappings to be added
 559          * is greater than or equal to threshold.  This is conservative; the
 560          * obvious condition is (m.size() + size) >= threshold, but this
 561          * condition could result in a map with twice the appropriate capacity,
 562          * if the keys to be added overlap with the keys already in this map.
 563          * By using the conservative calculation, we subject ourself
 564          * to at most one extra resize.
 565          */
 566         if (numKeysToBeAdded > threshold) {
 567             int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
 568             if (targetCapacity > MAXIMUM_CAPACITY)
 569                 targetCapacity = MAXIMUM_CAPACITY;
 570             int newCapacity = table.length;

   1 /*
   2  * Copyright (c) 1998, 2025, 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.lang.ref.ReferenceQueue;
  29 import java.lang.ref.WeakReference;
  30 import java.util.function.BiConsumer;
  31 import java.util.function.BiFunction;
  32 import java.util.function.Consumer;
  33 
  34 
  35 /**
  36  * Hash table based implementation of the {@code Map} interface, with
  37  * <em>weak keys</em>.
  38  * An entry in a {@code WeakHashMap} will automatically be removed when
  39  * its key is no longer in ordinary use.  More precisely, the presence of a
  40  * mapping for a given key will not prevent the key from being discarded by the
  41  * garbage collector, that is, made finalizable, finalized, and then reclaimed.
  42  * When a key has been discarded its entry is effectively removed from the map,
  43  * so this class behaves somewhat differently from other {@code Map}
  44  * implementations.
  45  *
  46  * <p> Both null values and the null key are supported. This class has
  47  * performance characteristics similar to those of the {@code HashMap}
  48  * class, and has the same efficiency parameters of <em>initial capacity</em>
  49  * and <em>load factor</em>.

 105  * returned by all of this class's "collection view methods" are
 106  * <i>fail-fast</i>: if the map is structurally modified at any time after the
 107  * iterator is created, in any way except through the iterator's own
 108  * {@code remove} method, the iterator will throw a {@link
 109  * ConcurrentModificationException}.  Thus, in the face of concurrent
 110  * modification, the iterator fails quickly and cleanly, rather than risking
 111  * arbitrary, non-deterministic behavior at an undetermined time in the future.
 112  *
 113  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 114  * as it is, generally speaking, impossible to make any hard guarantees in the
 115  * presence of unsynchronized concurrent modification.  Fail-fast iterators
 116  * throw {@code ConcurrentModificationException} on a best-effort basis.
 117  * Therefore, it would be wrong to write a program that depended on this
 118  * exception for its correctness:  <i>the fail-fast behavior of iterators
 119  * should be used only to detect bugs.</i>
 120  *
 121  * <p>This class is a member of the
 122  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 123  * Java Collections Framework</a>.
 124  *
 125  * @apiNote
 126  * <div class="preview-block">
 127  *      <div class="preview-comment">
 128  *          Objects that are {@linkplain Class#isValue() value objects} do not have identity
 129  *          and can not be used as keys in a {@code WeakHashMap}. {@linkplain java.lang.ref.Reference References}
 130  *          such as {@linkplain WeakReference WeakReference} used by {@code WeakhashMap}
 131  *          to hold the key cannot refer to a value object.
 132  *          Methods such as {@linkplain #get get} or {@linkplain #containsKey containsKey}
 133  *          will always return {@code null} or {@code false} respectively.
 134  *          The methods such as {@linkplain #put put}, {@linkplain #putAll putAll},
 135  *          {@linkplain #compute(Object, BiFunction) compute}, and
 136  *          {@linkplain #computeIfAbsent(Object, Function) computeIfAbsent} or any method putting
 137  *          a value object, as a key, throw {@link IdentityException}.
 138  *      </div>
 139  * </div>
 140  *
 141  * @param <K> the type of keys maintained by this map
 142  * @param <V> the type of mapped values
 143  *
 144  * @author      Doug Lea
 145  * @author      Josh Bloch
 146  * @author      Mark Reinhold
 147  * @since       1.2
 148  * @see         java.util.HashMap
 149  * @see         java.lang.ref.WeakReference
 150  */
 151 public class WeakHashMap<K,V>
 152     extends AbstractMap<K,V>
 153     implements Map<K,V> {
 154 
 155     /**
 156      * The default initial capacity -- MUST be a power of two.
 157      */
 158     private static final int DEFAULT_INITIAL_CAPACITY = 16;
 159 
 160     /**

 287      */
 288     private static final Object NULL_KEY = new Object();
 289 
 290     /**
 291      * Use NULL_KEY for key if it is null.
 292      */
 293     private static Object maskNull(Object key) {
 294         return (key == null) ? NULL_KEY : key;
 295     }
 296 
 297     /**
 298      * Returns internal representation of null key back to caller as null.
 299      */
 300     static Object unmaskNull(Object key) {
 301         return (key == NULL_KEY) ? null : key;
 302     }
 303 
 304     /**
 305      * Checks for equality of non-null reference x and possibly-null y.  By
 306      * default uses Object.equals.
 307      * The key may be a value object, but it will never be equal to the referent
 308      * so does not need a separate Objects.hasIdentity check.
 309      */
 310     private boolean matchesKey(Entry<K,V> e, Object key) {
 311         // check if the given entry refers to the given key without
 312         // keeping a strong reference to the entry's referent
 313         if (e.refersTo(key)) return true;
 314 
 315         // then check for equality if the referent is not cleared
 316         Object k = e.get();
 317         return k != null && key.equals(k);
 318     }
 319 
 320     /**
 321      * Retrieve object hash code and applies a supplemental hash function to the
 322      * result hash, which defends against poor quality hash functions.  This is
 323      * critical because HashMap uses power-of-two length hash tables, that
 324      * otherwise encounter collisions for hashCodes that do not differ
 325      * in lower bits.
 326      */
 327     final int hash(Object k) {
 328         int h = k.hashCode();

 457         int h = hash(k);
 458         Entry<K,V>[] tab = getTable();
 459         int index = indexFor(h, tab.length);
 460         Entry<K,V> e = tab[index];
 461         while (e != null && !(e.hash == h && matchesKey(e, k)))
 462             e = e.next;
 463         return e;
 464     }
 465 
 466     /**
 467      * Associates the specified value with the specified key in this map.
 468      * If the map previously contained a mapping for this key, the old
 469      * value is replaced.
 470      *
 471      * @param key key with which the specified value is to be associated.
 472      * @param value value to be associated with the specified key.
 473      * @return the previous value associated with {@code key}, or
 474      *         {@code null} if there was no mapping for {@code key}.
 475      *         (A {@code null} return can also indicate that the map
 476      *         previously associated {@code null} with {@code key}.)
 477      * @throws IdentityException if {@code key} is a value object
 478      */
 479     public V put(K key, V value) {
 480         Object k = maskNull(key);
 481         Objects.requireIdentity(k);
 482         int h = hash(k);
 483         Entry<K,V>[] tab = getTable();
 484         int i = indexFor(h, tab.length);
 485 
 486         for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
 487             if (h == e.hash && matchesKey(e, k)) {
 488                 V oldValue = e.value;
 489                 if (value != oldValue)
 490                     e.value = value;
 491                 return oldValue;
 492             }
 493         }
 494 
 495         modCount++;
 496         Entry<K,V> e = tab[i];
 497         tab[i] = new Entry<>(k, value, queue, h, e);
 498         if (++size > threshold)
 499             resize(tab.length * 2);
 500         return null;
 501     }

 549                 Entry<K,V> next = e.next;
 550                 if (e.refersTo(null)) {
 551                     e.next = null;  // Help GC
 552                     e.value = null; //  "   "
 553                     size--;
 554                 } else {
 555                     int i = indexFor(e.hash, dest.length);
 556                     e.next = dest[i];
 557                     dest[i] = e;
 558                 }
 559                 e = next;
 560             }
 561         }
 562     }
 563 
 564     /**
 565      * Copies all of the mappings from the specified map to this map.
 566      * These mappings will replace any mappings that this map had for any
 567      * of the keys currently in the specified map.
 568      *
 569      * @apiNote If the specified map contains keys that are {@linkplain Objects#isValueObject value objects}
 570      * an {@linkplain IdentityException } is thrown when the first value object key is encountered.
 571      * Zero or more mappings may have already been copied to this map.
 572      *
 573      * @param m mappings to be stored in this map.
 574      * @throws  NullPointerException if the specified map is null.
 575      * @throws  IdentityException if any of the {@code keys} is a value object
 576      */
 577     public void putAll(Map<? extends K, ? extends V> m) {
 578         int numKeysToBeAdded = m.size();
 579         if (numKeysToBeAdded == 0)
 580             return;
 581 
 582         /*
 583          * Expand the map if the map if the number of mappings to be added
 584          * is greater than or equal to threshold.  This is conservative; the
 585          * obvious condition is (m.size() + size) >= threshold, but this
 586          * condition could result in a map with twice the appropriate capacity,
 587          * if the keys to be added overlap with the keys already in this map.
 588          * By using the conservative calculation, we subject ourself
 589          * to at most one extra resize.
 590          */
 591         if (numKeysToBeAdded > threshold) {
 592             int targetCapacity = (int)Math.ceil(numKeysToBeAdded / (double)loadFactor);
 593             if (targetCapacity > MAXIMUM_CAPACITY)
 594                 targetCapacity = MAXIMUM_CAPACITY;
 595             int newCapacity = table.length;
< prev index next >