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

Print this page
rev 5431 : 7126277: Alternative hashing implementation


 167      * The load factor for the hash table.
 168      */
 169     private final float loadFactor;
 170 
 171     /**
 172      * Reference queue for cleared WeakEntries
 173      */
 174     private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
 175 
 176     /**
 177      * The number of times this WeakHashMap has been structurally modified.
 178      * Structural modifications are those that change the number of
 179      * mappings in the map or otherwise modify its internal structure
 180      * (e.g., rehash).  This field is used to make iterators on
 181      * Collection-views of the map fail-fast.
 182      *
 183      * @see ConcurrentModificationException
 184      */
 185     int modCount;
 186 






 187     @SuppressWarnings("unchecked")
 188     private Entry<K,V>[] newTable(int n) {
 189         return (Entry<K,V>[]) new Entry<?,?>[n];
 190     }
 191 
 192     /**
 193      * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
 194      * capacity and the given load factor.
 195      *
 196      * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
 197      * @param  loadFactor      The load factor of the <tt>WeakHashMap</tt>
 198      * @throws IllegalArgumentException if the initial capacity is negative,
 199      *         or if the load factor is nonpositive.
 200      */
 201     public WeakHashMap(int initialCapacity, float loadFactor) {
 202         if (initialCapacity < 0)
 203             throw new IllegalArgumentException("Illegal Initial Capacity: "+
 204                                                initialCapacity);
 205         if (initialCapacity > MAXIMUM_CAPACITY)
 206             initialCapacity = MAXIMUM_CAPACITY;


 215         this.loadFactor = loadFactor;
 216         threshold = (int)(capacity * loadFactor);
 217     }
 218 
 219     /**
 220      * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
 221      * capacity and the default load factor (0.75).
 222      *
 223      * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
 224      * @throws IllegalArgumentException if the initial capacity is negative
 225      */
 226     public WeakHashMap(int initialCapacity) {
 227         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 228     }
 229 
 230     /**
 231      * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
 232      * capacity (16) and load factor (0.75).
 233      */
 234     public WeakHashMap() {
 235         this.loadFactor = DEFAULT_LOAD_FACTOR;
 236         threshold = DEFAULT_INITIAL_CAPACITY;
 237         table = newTable(DEFAULT_INITIAL_CAPACITY);
 238     }
 239 
 240     /**
 241      * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
 242      * specified map.  The <tt>WeakHashMap</tt> is created with the default
 243      * load factor (0.75) and an initial capacity sufficient to hold the
 244      * mappings in the specified map.
 245      *
 246      * @param   m the map whose mappings are to be placed in this map
 247      * @throws  NullPointerException if the specified map is null
 248      * @since   1.3
 249      */
 250     public WeakHashMap(Map<? extends K, ? extends V> m) {
 251         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),

 252              DEFAULT_LOAD_FACTOR);
 253         putAll(m);
 254     }
 255 
 256     // internal utilities
 257 
 258     /**
 259      * Value representing null keys inside tables.
 260      */
 261     private static final Object NULL_KEY = new Object();
 262 
 263     /**
 264      * Use NULL_KEY for key if it is null.
 265      */
 266     private static Object maskNull(Object key) {
 267         return (key == null) ? NULL_KEY : key;
 268     }
 269 
 270     /**
 271      * Returns internal representation of null key back to caller as null.
 272      */
 273     static Object unmaskNull(Object key) {
 274         return (key == NULL_KEY) ? null : key;
 275     }
 276 
 277     /**
 278      * Checks for equality of non-null reference x and possibly-null y.  By
 279      * default uses Object.equals.
 280      */
 281     private static boolean eq(Object x, Object y) {
 282         return x == y || x.equals(y);
 283     }
 284 
 285     /**






















 286      * Returns index for hash code h.
 287      */
 288     private static int indexFor(int h, int length) {
 289         return h & (length-1);
 290     }
 291 
 292     /**
 293      * Expunges stale entries from the table.
 294      */
 295     private void expungeStaleEntries() {
 296         for (Object x; (x = queue.poll()) != null; ) {
 297             synchronized (queue) {
 298                 @SuppressWarnings("unchecked")
 299                     Entry<K,V> e = (Entry<K,V>) x;
 300                 int i = indexFor(e.hash, table.length);
 301 
 302                 Entry<K,V> prev = table[i];
 303                 Entry<K,V> p = prev;
 304                 while (p != null) {
 305                     Entry<K,V> next = p.next;


 354 
 355     /**
 356      * Returns the value to which the specified key is mapped,
 357      * or {@code null} if this map contains no mapping for the key.
 358      *
 359      * <p>More formally, if this map contains a mapping from a key
 360      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 361      * key.equals(k))}, then this method returns {@code v}; otherwise
 362      * it returns {@code null}.  (There can be at most one such mapping.)
 363      *
 364      * <p>A return value of {@code null} does not <i>necessarily</i>
 365      * indicate that the map contains no mapping for the key; it's also
 366      * possible that the map explicitly maps the key to {@code null}.
 367      * The {@link #containsKey containsKey} operation may be used to
 368      * distinguish these two cases.
 369      *
 370      * @see #put(Object, Object)
 371      */
 372     public V get(Object key) {
 373         Object k = maskNull(key);
 374         int h = HashMap.hash(k.hashCode());
 375         Entry<K,V>[] tab = getTable();
 376         int index = indexFor(h, tab.length);
 377         Entry<K,V> e = tab[index];
 378         while (e != null) {
 379             if (e.hash == h && eq(k, e.get()))
 380                 return e.value;
 381             e = e.next;
 382         }
 383         return null;
 384     }
 385 
 386     /**
 387      * Returns <tt>true</tt> if this map contains a mapping for the
 388      * specified key.
 389      *
 390      * @param  key   The key whose presence in this map is to be tested
 391      * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
 392      *         <tt>false</tt> otherwise
 393      */
 394     public boolean containsKey(Object key) {
 395         return getEntry(key) != null;
 396     }
 397 
 398     /**
 399      * Returns the entry associated with the specified key in this map.
 400      * Returns null if the map contains no mapping for this key.
 401      */
 402     Entry<K,V> getEntry(Object key) {
 403         Object k = maskNull(key);
 404         int h = HashMap.hash(k.hashCode());
 405         Entry<K,V>[] tab = getTable();
 406         int index = indexFor(h, tab.length);
 407         Entry<K,V> e = tab[index];
 408         while (e != null && !(e.hash == h && eq(k, e.get())))
 409             e = e.next;
 410         return e;
 411     }
 412 
 413     /**
 414      * Associates the specified value with the specified key in this map.
 415      * If the map previously contained a mapping for this key, the old
 416      * value is replaced.
 417      *
 418      * @param key key with which the specified value is to be associated.
 419      * @param value value to be associated with the specified key.
 420      * @return the previous value associated with <tt>key</tt>, or
 421      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 422      *         (A <tt>null</tt> return can also indicate that the map
 423      *         previously associated <tt>null</tt> with <tt>key</tt>.)
 424      */
 425     public V put(K key, V value) {
 426         Object k = maskNull(key);
 427         int h = HashMap.hash(k.hashCode());
 428         Entry<K,V>[] tab = getTable();
 429         int i = indexFor(h, tab.length);
 430 
 431         for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
 432             if (h == e.hash && eq(k, e.get())) {
 433                 V oldValue = e.value;
 434                 if (value != oldValue)
 435                     e.value = value;
 436                 return oldValue;
 437             }
 438         }
 439 
 440         modCount++;
 441         Entry<K,V> e = tab[i];
 442         tab[i] = new Entry<>(k, value, queue, h, e);
 443         if (++size >= threshold)
 444             resize(tab.length * 2);
 445         return null;
 446     }
 447 


 549      * More formally, if this map contains a mapping from key <tt>k</tt> to
 550      * value <tt>v</tt> such that <code>(key==null ?  k==null :
 551      * key.equals(k))</code>, that mapping is removed.  (The map can contain
 552      * at most one such mapping.)
 553      *
 554      * <p>Returns the value to which this map previously associated the key,
 555      * or <tt>null</tt> if the map contained no mapping for the key.  A
 556      * return value of <tt>null</tt> does not <i>necessarily</i> indicate
 557      * that the map contained no mapping for the key; it's also possible
 558      * that the map explicitly mapped the key to <tt>null</tt>.
 559      *
 560      * <p>The map will not contain a mapping for the specified key once the
 561      * call returns.
 562      *
 563      * @param key key whose mapping is to be removed from the map
 564      * @return the previous value associated with <tt>key</tt>, or
 565      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 566      */
 567     public V remove(Object key) {
 568         Object k = maskNull(key);
 569         int h = HashMap.hash(k.hashCode());
 570         Entry<K,V>[] tab = getTable();
 571         int i = indexFor(h, tab.length);
 572         Entry<K,V> prev = tab[i];
 573         Entry<K,V> e = prev;
 574 
 575         while (e != null) {
 576             Entry<K,V> next = e.next;
 577             if (h == e.hash && eq(k, e.get())) {
 578                 modCount++;
 579                 size--;
 580                 if (prev == e)
 581                     tab[i] = next;
 582                 else
 583                     prev.next = next;
 584                 return e.value;
 585             }
 586             prev = e;
 587             e = next;
 588         }
 589 
 590         return null;
 591     }
 592 
 593     /** Special version of remove needed by Entry set */
 594     boolean removeMapping(Object o) {
 595         if (!(o instanceof Map.Entry))
 596             return false;
 597         Entry<K,V>[] tab = getTable();
 598         Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
 599         Object k = maskNull(entry.getKey());
 600         int h = HashMap.hash(k.hashCode());
 601         int i = indexFor(h, tab.length);
 602         Entry<K,V> prev = tab[i];
 603         Entry<K,V> e = prev;
 604 
 605         while (e != null) {
 606             Entry<K,V> next = e.next;
 607             if (h == e.hash && e.equals(entry)) {
 608                 modCount++;
 609                 size--;
 610                 if (prev == e)
 611                     tab[i] = next;
 612                 else
 613                     prev.next = next;
 614                 return true;
 615             }
 616             prev = e;
 617             e = next;
 618         }
 619 
 620         return false;




 167      * The load factor for the hash table.
 168      */
 169     private final float loadFactor;
 170 
 171     /**
 172      * Reference queue for cleared WeakEntries
 173      */
 174     private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
 175 
 176     /**
 177      * The number of times this WeakHashMap has been structurally modified.
 178      * Structural modifications are those that change the number of
 179      * mappings in the map or otherwise modify its internal structure
 180      * (e.g., rehash).  This field is used to make iterators on
 181      * Collection-views of the map fail-fast.
 182      *
 183      * @see ConcurrentModificationException
 184      */
 185     int modCount;
 186             
 187     /**
 188      * A randomizing value associated with this instance that is applied to  
 189      * hash code of keys to make hash collisions harder to find.
 190      */
 191     transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
 192 
 193     @SuppressWarnings("unchecked")
 194     private Entry<K,V>[] newTable(int n) {
 195         return (Entry<K,V>[]) new Entry<?,?>[n];
 196     }
 197 
 198     /**
 199      * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
 200      * capacity and the given load factor.
 201      *
 202      * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
 203      * @param  loadFactor      The load factor of the <tt>WeakHashMap</tt>
 204      * @throws IllegalArgumentException if the initial capacity is negative,
 205      *         or if the load factor is nonpositive.
 206      */
 207     public WeakHashMap(int initialCapacity, float loadFactor) {
 208         if (initialCapacity < 0)
 209             throw new IllegalArgumentException("Illegal Initial Capacity: "+
 210                                                initialCapacity);
 211         if (initialCapacity > MAXIMUM_CAPACITY)
 212             initialCapacity = MAXIMUM_CAPACITY;


 221         this.loadFactor = loadFactor;
 222         threshold = (int)(capacity * loadFactor);
 223     }
 224 
 225     /**
 226      * Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
 227      * capacity and the default load factor (0.75).
 228      *
 229      * @param  initialCapacity The initial capacity of the <tt>WeakHashMap</tt>
 230      * @throws IllegalArgumentException if the initial capacity is negative
 231      */
 232     public WeakHashMap(int initialCapacity) {
 233         this(initialCapacity, DEFAULT_LOAD_FACTOR);
 234     }
 235 
 236     /**
 237      * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
 238      * capacity (16) and load factor (0.75).
 239      */
 240     public WeakHashMap() {
 241         this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);


 242     }
 243 
 244     /**
 245      * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
 246      * specified map.  The <tt>WeakHashMap</tt> is created with the default
 247      * load factor (0.75) and an initial capacity sufficient to hold the
 248      * mappings in the specified map.
 249      *
 250      * @param   m the map whose mappings are to be placed in this map
 251      * @throws  NullPointerException if the specified map is null
 252      * @since   1.3
 253      */
 254     public WeakHashMap(Map<? extends K, ? extends V> m) {
 255         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 
 256                 DEFAULT_INITIAL_CAPACITY),
 257              DEFAULT_LOAD_FACTOR);
 258         putAll(m);
 259     }
 260 
 261     // internal utilities
 262 
 263     /**
 264      * Value representing null keys inside tables.
 265      */
 266     private static final Object NULL_KEY = new Object();
 267 
 268     /**
 269      * Use NULL_KEY for key if it is null.
 270      */
 271     private static Object maskNull(Object key) {
 272         return (key == null) ? NULL_KEY : key;
 273     }
 274 
 275     /**
 276      * Returns internal representation of null key back to caller as null.
 277      */
 278     static Object unmaskNull(Object key) {
 279         return (key == NULL_KEY) ? null : key;
 280     }
 281 
 282     /**
 283      * Checks for equality of non-null reference x and possibly-null y.  By
 284      * default uses Object.equals.
 285      */
 286     private static boolean eq(Object x, Object y) {
 287         return x == y || x.equals(y);
 288     }
 289 
 290     /**
 291      * Retrieve object hash code and applies a supplemental hash function to the 
 292      * result hash, which defends against poor quality hash functions.  This is 
 293      * critical because HashMap uses power-of-two length hash tables, that
 294      * otherwise encounter collisions for hashCodes that do not differ
 295      * in lower bits.
 296      */
 297     int hash(Object k) {
 298         int h = hashSeed;
 299         if (k instanceof String) {
 300             return ((String) k).hash32();
 301         } else {
 302             h ^= k.hashCode();
 303         }
 304         
 305         // This function ensures that hashCodes that differ only by
 306         // constant multiples at each bit position have a bounded
 307         // number of collisions (approximately 8 at default load factor).
 308         h ^= (h >>> 20) ^ (h >>> 12);
 309         return h ^ (h >>> 7) ^ (h >>> 4);
 310     }
 311     
 312     /**
 313      * Returns index for hash code h.
 314      */
 315     private static int indexFor(int h, int length) {
 316         return h & (length-1);
 317     }
 318 
 319     /**
 320      * Expunges stale entries from the table.
 321      */
 322     private void expungeStaleEntries() {
 323         for (Object x; (x = queue.poll()) != null; ) {
 324             synchronized (queue) {
 325                 @SuppressWarnings("unchecked")
 326                     Entry<K,V> e = (Entry<K,V>) x;
 327                 int i = indexFor(e.hash, table.length);
 328 
 329                 Entry<K,V> prev = table[i];
 330                 Entry<K,V> p = prev;
 331                 while (p != null) {
 332                     Entry<K,V> next = p.next;


 381 
 382     /**
 383      * Returns the value to which the specified key is mapped,
 384      * or {@code null} if this map contains no mapping for the key.
 385      *
 386      * <p>More formally, if this map contains a mapping from a key
 387      * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 388      * key.equals(k))}, then this method returns {@code v}; otherwise
 389      * it returns {@code null}.  (There can be at most one such mapping.)
 390      *
 391      * <p>A return value of {@code null} does not <i>necessarily</i>
 392      * indicate that the map contains no mapping for the key; it's also
 393      * possible that the map explicitly maps the key to {@code null}.
 394      * The {@link #containsKey containsKey} operation may be used to
 395      * distinguish these two cases.
 396      *
 397      * @see #put(Object, Object)
 398      */
 399     public V get(Object key) {
 400         Object k = maskNull(key);
 401         int h = hash(k);
 402         Entry<K,V>[] tab = getTable();
 403         int index = indexFor(h, tab.length);
 404         Entry<K,V> e = tab[index];
 405         while (e != null) {
 406             if (e.hash == h && eq(k, e.get()))
 407                 return e.value;
 408             e = e.next;
 409         }
 410         return null;
 411     }
 412 
 413     /**
 414      * Returns <tt>true</tt> if this map contains a mapping for the
 415      * specified key.
 416      *
 417      * @param  key   The key whose presence in this map is to be tested
 418      * @return <tt>true</tt> if there is a mapping for <tt>key</tt>;
 419      *         <tt>false</tt> otherwise
 420      */
 421     public boolean containsKey(Object key) {
 422         return getEntry(key) != null;
 423     }
 424 
 425     /**
 426      * Returns the entry associated with the specified key in this map.
 427      * Returns null if the map contains no mapping for this key.
 428      */
 429     Entry<K,V> getEntry(Object key) {
 430         Object k = maskNull(key);
 431         int h = hash(k);
 432         Entry<K,V>[] tab = getTable();
 433         int index = indexFor(h, tab.length);
 434         Entry<K,V> e = tab[index];
 435         while (e != null && !(e.hash == h && eq(k, e.get())))
 436             e = e.next;
 437         return e;
 438     }
 439 
 440     /**
 441      * Associates the specified value with the specified key in this map.
 442      * If the map previously contained a mapping for this key, the old
 443      * value is replaced.
 444      *
 445      * @param key key with which the specified value is to be associated.
 446      * @param value value to be associated with the specified key.
 447      * @return the previous value associated with <tt>key</tt>, or
 448      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 449      *         (A <tt>null</tt> return can also indicate that the map
 450      *         previously associated <tt>null</tt> with <tt>key</tt>.)
 451      */
 452     public V put(K key, V value) {
 453         Object k = maskNull(key);
 454         int h = hash(k);
 455         Entry<K,V>[] tab = getTable();
 456         int i = indexFor(h, tab.length);
 457 
 458         for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
 459             if (h == e.hash && eq(k, e.get())) {
 460                 V oldValue = e.value;
 461                 if (value != oldValue)
 462                     e.value = value;
 463                 return oldValue;
 464             }
 465         }
 466 
 467         modCount++;
 468         Entry<K,V> e = tab[i];
 469         tab[i] = new Entry<>(k, value, queue, h, e);
 470         if (++size >= threshold)
 471             resize(tab.length * 2);
 472         return null;
 473     }
 474 


 576      * More formally, if this map contains a mapping from key <tt>k</tt> to
 577      * value <tt>v</tt> such that <code>(key==null ?  k==null :
 578      * key.equals(k))</code>, that mapping is removed.  (The map can contain
 579      * at most one such mapping.)
 580      *
 581      * <p>Returns the value to which this map previously associated the key,
 582      * or <tt>null</tt> if the map contained no mapping for the key.  A
 583      * return value of <tt>null</tt> does not <i>necessarily</i> indicate
 584      * that the map contained no mapping for the key; it's also possible
 585      * that the map explicitly mapped the key to <tt>null</tt>.
 586      *
 587      * <p>The map will not contain a mapping for the specified key once the
 588      * call returns.
 589      *
 590      * @param key key whose mapping is to be removed from the map
 591      * @return the previous value associated with <tt>key</tt>, or
 592      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 593      */
 594     public V remove(Object key) {
 595         Object k = maskNull(key);
 596         int h = hash(k);
 597         Entry<K,V>[] tab = getTable();
 598         int i = indexFor(h, tab.length);
 599         Entry<K,V> prev = tab[i];
 600         Entry<K,V> e = prev;
 601 
 602         while (e != null) {
 603             Entry<K,V> next = e.next;
 604             if (h == e.hash && eq(k, e.get())) {
 605                 modCount++;
 606                 size--;
 607                 if (prev == e)
 608                     tab[i] = next;
 609                 else
 610                     prev.next = next;
 611                 return e.value;
 612             }
 613             prev = e;
 614             e = next;
 615         }
 616 
 617         return null;
 618     }
 619 
 620     /** Special version of remove needed by Entry set */
 621     boolean removeMapping(Object o) {
 622         if (!(o instanceof Map.Entry))
 623             return false;
 624         Entry<K,V>[] tab = getTable();
 625         Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
 626         Object k = maskNull(entry.getKey());
 627         int h = hash(k);
 628         int i = indexFor(h, tab.length);
 629         Entry<K,V> prev = tab[i];
 630         Entry<K,V> e = prev;
 631 
 632         while (e != null) {
 633             Entry<K,V> next = e.next;
 634             if (h == e.hash && e.equals(entry)) {
 635                 modCount++;
 636                 size--;
 637                 if (prev == e)
 638                     tab[i] = next;
 639                 else
 640                     prev.next = next;
 641                 return true;
 642             }
 643             prev = e;
 644             e = next;
 645         }
 646 
 647         return false;