src/share/classes/java/util/Hashtable.java

Print this page
rev 5382 : 7126277: Alternative hashing implementation

@@ -161,10 +161,56 @@
     private transient int modCount = 0;
 
     /** use serialVersionUID from JDK 1.0.2 for interoperability */
     private static final long serialVersionUID = 1421746759512286392L;
 
+    private static class Holder {
+            // Unsafe mechanics
+        /**
+         * 
+         */
+        static final sun.misc.Unsafe UNSAFE;
+        
+        /**
+         * Offset of "final" hashSeed field we must set in
+         * readObject() method.
+         */
+        static final long HASHSEED_OFFSET;
+                
+        static {           
+            try {
+                UNSAFE = sun.misc.Unsafe.getUnsafe();
+                HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+                    Hashtable.class.getDeclaredField("hashSeed"));                        
+            } catch (NoSuchFieldException | SecurityException e) {
+                throw new InternalError("Failed to record hashSeed offset", e);
+            }
+        }
+    }
+    
+    /**
+     * A randomizing value associated with this instance that is applied to  
+     * hash code of keys to make hash collisions harder to find.
+     */
+    transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+
+    private int hash(Object k) {
+        int h = hashSeed;
+
+        if (k instanceof String) {
+            return h ^ ((String)k).hash32();
+        } 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);
+            return h ^ (h >>> 7) ^ (h >>> 4);
+        }
+    }
+
     /**
      * Constructs a new, empty hashtable with the specified initial
      * capacity and the specified load factor.
      *
      * @param      initialCapacity   the initial capacity of the hashtable.

@@ -181,11 +227,11 @@
 
         if (initialCapacity==0)
             initialCapacity = 1;
         this.loadFactor = loadFactor;
         table = new Entry<?,?>[initialCapacity];
-        threshold = (int)(initialCapacity * loadFactor);
+        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
     }
 
     /**
      * Constructs a new, empty hashtable with the specified initial capacity
      * and default load factor (0.75).

@@ -325,11 +371,11 @@
      * @throws  NullPointerException  if the key is <code>null</code>
      * @see     #contains(Object)
      */
     public synchronized boolean containsKey(Object key) {
         Entry<?,?> tab[] = table;
-        int hash = key.hashCode();
+        int hash = hash(key);
         int index = (hash & 0x7FFFFFFF) % tab.length;
         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
                 return true;
             }

@@ -353,11 +399,11 @@
      * @see     #put(Object, Object)
      */
     @SuppressWarnings("unchecked")
     public synchronized V get(Object key) {
         Entry<?,?> tab[] = table;
-        int hash = key.hashCode();
+        int hash = hash(key);
         int index = (hash & 0x7FFFFFFF) % tab.length;
         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
                 return (V)e.value;
             }

@@ -394,11 +440,11 @@
             newCapacity = MAX_ARRAY_SIZE;
         }
         Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
 
         modCount++;
-        threshold = (int)(newCapacity * loadFactor);
+        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
         table = newMap;
 
         for (int i = oldCapacity ; i-- > 0 ;) {
             for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                 Entry<K,V> e = old;

@@ -434,11 +480,11 @@
             throw new NullPointerException();
         }
 
         // Makes sure the key is not already in the hashtable.
         Entry<?,?> tab[] = table;
-        int hash = key.hashCode();
+        int hash = hash(key);
         int index = (hash & 0x7FFFFFFF) % tab.length;
         @SuppressWarnings("unchecked")
         Entry<K,V> entry = (Entry<K,V>)tab[index];
         for(; entry != null ; entry = entry.next) {
             if ((entry.hash == hash) && entry.key.equals(key)) {

@@ -452,10 +498,11 @@
         if (count >= threshold) {
             // Rehash the table if the threshold is exceeded
             rehash();
 
             tab = table;
+            hash = hash(key);
             index = (hash & 0x7FFFFFFF) % tab.length;
         }
 
         // Creates the new entry.
         @SuppressWarnings("unchecked")

@@ -474,11 +521,11 @@
      *          or <code>null</code> if the key did not have a mapping
      * @throws  NullPointerException  if the key is <code>null</code>
      */
     public synchronized V remove(Object key) {
         Entry<?,?> tab[] = table;
-        int hash = key.hashCode();
+        int hash = hash(key);
         int index = (hash & 0x7FFFFFFF) % tab.length;
         @SuppressWarnings("unchecked")
         Entry<K,V> e = (Entry<K,V>)tab[index];
         for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {

@@ -683,11 +730,11 @@
             if (!(o instanceof Map.Entry))
                 return false;
             Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
             Object key = entry.getKey();
             Entry<?,?>[] tab = table;
-            int hash = key.hashCode();
+            int hash = hash(key);
             int index = (hash & 0x7FFFFFFF) % tab.length;
 
             for (Entry<?,?> e = tab[index]; e != null; e = e.next)
                 if (e.hash==hash && e.equals(entry))
                     return true;

@@ -698,11 +745,11 @@
             if (!(o instanceof Map.Entry))
                 return false;
             Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
             Object key = entry.getKey();
             Entry<?,?>[] tab = table;
-            int hash = key.hashCode();
+            int hash = hash(key);
             int index = (hash & 0x7FFFFFFF) % tab.length;
 
             @SuppressWarnings("unchecked")
             Entry<K,V> e = (Entry<K,V>)tab[index];
             for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {

@@ -833,13 +880,17 @@
         if (count == 0 || loadFactor < 0)
             return h;  // Returns zero
 
         loadFactor = -loadFactor;  // Mark hashCode computation in progress
         Entry<?,?>[] tab = table;
-        for (int i = 0; i < tab.length; i++)
-            for (Entry<?,?> e = tab[i]; e != null; e = e.next)
-                h += e.key.hashCode() ^ e.value.hashCode();
+        for (Entry<?,?> entry : tab) {
+            while (entry != null) {
+                h += entry.hashCode();
+                entry = entry.next;
+            }
+        }
+
         loadFactor = -loadFactor;  // Mark hashCode computation complete
 
         return h;
     }
 

@@ -892,10 +943,14 @@
          throws IOException, ClassNotFoundException
     {
         // Read in the length, threshold, and loadfactor
         s.defaultReadObject();
 
+        // set hashMask
+        Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET, 
+                sun.misc.Hashing.randomHashSeed(this));
+
         // Read the original length of the array and number of elements
         int origlength = s.readInt();
         int elements = s.readInt();
 
         // Compute new size with a bit of room 5% to grow but

@@ -905,11 +960,12 @@
         int length = (int)(elements * loadFactor) + (elements / 20) + 3;
         if (length > elements && (length & 1) == 0)
             length--;
         if (origlength > 0 && length > origlength)
             length = origlength;
-        Entry<?,?>[] table = new Entry<?,?>[length];
+        table = new Entry<?,?>[length];
+        threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
         count = 0;
 
         // Read the number of elements and then all the key/value objects
         for (; elements > 0; elements--) {
             @SuppressWarnings("unchecked")

@@ -917,11 +973,10 @@
             @SuppressWarnings("unchecked")
                 V value = (V)s.readObject();
             // synch could be eliminated for performance
             reconstitutionPut(table, key, value);
         }
-        this.table = table;
     }
 
     /**
      * The put method used by readObject. This is provided because put
      * is overridable and should not be called in readObject since the

@@ -939,11 +994,11 @@
         if (value == null) {
             throw new java.io.StreamCorruptedException();
         }
         // Makes sure the key is not already in the hashtable.
         // This should not happen in deserialized version.
-        int hash = key.hashCode();
+        int hash = hash(key);
         int index = (hash & 0x7FFFFFFF) % tab.length;
         for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
                 throw new java.io.StreamCorruptedException();
             }

@@ -954,14 +1009,14 @@
         tab[index] = new Entry<>(hash, key, value, e);
         count++;
     }
 
     /**
-     * Hashtable collision list.
+     * Hashtable bucket collision list entry
      */
     private static class Entry<K,V> implements Map.Entry<K,V> {
-        int hash;
+        final int hash;
         K key;
         V value;
         Entry<K,V> next;
 
         protected Entry(int hash, K key, V value, Entry<K,V> next) {