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

rev 5380 : 7126277: Alternative hashing implementation

@@ -182,10 +182,16 @@
      *
      * @see ConcurrentModificationException
      */
     int modCount;
 
+    /**
+     * A random mask value that is used for hashcode values associated with this
+     * instance to make hash collisions harder to find.
+     */
+    transient final int hashMask = sun.misc.Hashing.makeHashMask(this);
+
     @SuppressWarnings("unchecked")
     private Entry<K,V>[] newTable(int n) {
         return (Entry<K,V>[]) new Entry<?,?>[n];
     }
 

@@ -230,13 +236,11 @@
     /**
      * Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
      * capacity (16) and load factor (0.75).
      */
     public WeakHashMap() {
-        this.loadFactor = DEFAULT_LOAD_FACTOR;
-        threshold = DEFAULT_INITIAL_CAPACITY;
-        table = newTable(DEFAULT_INITIAL_CAPACITY);
+        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
     }
 
     /**
      * Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
      * specified map.  The <tt>WeakHashMap</tt> is created with the default

@@ -246,11 +250,12 @@
      * @param   m the map whose mappings are to be placed in this map
      * @throws  NullPointerException if the specified map is null
      * @since   1.3
      */
     public WeakHashMap(Map<? extends K, ? extends V> m) {
-        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
+        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, 
+                DEFAULT_INITIAL_CAPACITY),
              DEFAULT_LOAD_FACTOR);
         putAll(m);
     }
 
     // internal utilities

@@ -281,10 +286,42 @@
     private static boolean eq(Object x, Object y) {
         return x == y || x.equals(y);
     }
 
     /**
+     * Retrieve object hash code and applies a supplemental hash function to the 
+     * result hash, which defends against poor quality hash functions.  This is 
+     * critical because HashMap uses power-of-two length hash tables, that
+     * otherwise encounter collisions for hashCodes that do not differ
+     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
+     */
+    int hash(Object k) {
+        if (null == k) {
+            return 0;
+        }
+
+        int h = hashMask;
+        if (0 == hashMask) {
+            if (k instanceof Hashable32) {
+                h ^= ((Hashable32) k).hash32();
+            } else {
+                h ^= k.hashCode();
+            }
+        } else  {
+            h = k.hashCode();
+        }
+        
+        // This function ensures that hashCodes that differ only by
+        // constant multiples at each bit position have a bounded
+        // number of collisions (approximately 8 at default load factor).
+        h ^= (h >>> 20) ^ (h >>> 12);
+        h ^= (h >>> 7) ^ (h >>> 4);
+        
+        return h;
+    }
+    
+    /**
      * Returns index for hash code h.
      */
     private static int indexFor(int h, int length) {
         return h & (length-1);
     }

@@ -369,11 +406,11 @@
      *
      * @see #put(Object, Object)
      */
     public V get(Object key) {
         Object k = maskNull(key);
-        int h = HashMap.hash(k.hashCode());
+        int h = hash(k);
         Entry<K,V>[] tab = getTable();
         int index = indexFor(h, tab.length);
         Entry<K,V> e = tab[index];
         while (e != null) {
             if (e.hash == h && eq(k, e.get()))

@@ -399,11 +436,11 @@
      * Returns the entry associated with the specified key in this map.
      * Returns null if the map contains no mapping for this key.
      */
     Entry<K,V> getEntry(Object key) {
         Object k = maskNull(key);
-        int h = HashMap.hash(k.hashCode());
+        int h = hash(k);
         Entry<K,V>[] tab = getTable();
         int index = indexFor(h, tab.length);
         Entry<K,V> e = tab[index];
         while (e != null && !(e.hash == h && eq(k, e.get())))
             e = e.next;

@@ -422,11 +459,11 @@
      *         (A <tt>null</tt> return can also indicate that the map
      *         previously associated <tt>null</tt> with <tt>key</tt>.)
      */
     public V put(K key, V value) {
         Object k = maskNull(key);
-        int h = HashMap.hash(k.hashCode());
+        int h = hash(k);
         Entry<K,V>[] tab = getTable();
         int i = indexFor(h, tab.length);
 
         for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
             if (h == e.hash && eq(k, e.get())) {

@@ -564,11 +601,11 @@
      * @return the previous value associated with <tt>key</tt>, or
      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
      */
     public V remove(Object key) {
         Object k = maskNull(key);
-        int h = HashMap.hash(k.hashCode());
+        int h = hash(k);
         Entry<K,V>[] tab = getTable();
         int i = indexFor(h, tab.length);
         Entry<K,V> prev = tab[i];
         Entry<K,V> e = prev;
 

@@ -595,11 +632,11 @@
         if (!(o instanceof Map.Entry))
             return false;
         Entry<K,V>[] tab = getTable();
         Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
         Object k = maskNull(entry.getKey());
-        int h = HashMap.hash(k.hashCode());
+        int h = hash(k);
         int i = indexFor(h, tab.length);
         Entry<K,V> prev = tab[i];
         Entry<K,V> e = prev;
 
         while (e != null) {

@@ -677,11 +714,11 @@
      * The entries in this hash table extend WeakReference, using its main ref
      * field as the key.
      */
     private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
         V value;
-        final int hash;
+        int hash;
         Entry<K,V> next;
 
         /**
          * Creates new entry.
          */