src/share/classes/java/util/HashMap.java

Print this page
rev 5382 : 7126277: Alternative hashing implementation

@@ -173,10 +173,39 @@
      * rehash).  This field is used to make iterators on Collection-views of
      * the HashMap fail-fast.  (See ConcurrentModificationException).
      */
     transient int modCount;
 
+    private static class Holder {
+         /**
+         * 
+         */
+        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(
+                    HashMap.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);
+
     /**
      * Constructs an empty <tt>HashMap</tt> with the specified initial
      * capacity and load factor.
      *
      * @param  initialCapacity the initial capacity

@@ -198,11 +227,11 @@
         int capacity = 1;
         while (capacity < initialCapacity)
             capacity <<= 1;
 
         this.loadFactor = loadFactor;
-        threshold = (int)(capacity * loadFactor);
+        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
         table = new Entry[capacity];
         init();
     }
 
     /**

@@ -219,14 +248,11 @@
     /**
      * Constructs an empty <tt>HashMap</tt> with the default initial capacity
      * (16) and the default load factor (0.75).
      */
     public HashMap() {
-        this.loadFactor = DEFAULT_LOAD_FACTOR;
-        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
-        table = new Entry[DEFAULT_INITIAL_CAPACITY];
-        init();
+        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
     }
 
     /**
      * Constructs a new <tt>HashMap</tt> with the same mappings as the
      * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with

@@ -253,17 +279,24 @@
      */
     void init() {
     }
 
     /**
-     * Applies a supplemental hash function to a given hashCode, which
-     * defends against poor quality hash functions.  This is critical
-     * because HashMap uses power-of-two length hash tables, that
+     * 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.
+     * in lower bits.
      */
-    static int hash(int h) {
+    final int hash(Object k) {
+        int h = hashSeed;
+        if (k instanceof String) {
+            return h ^ ((String)k).hash32();
+        }
+
+        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);

@@ -311,36 +344,13 @@
      *
      * @see #put(Object, Object)
      */
     @SuppressWarnings("unchecked")
     public V get(Object key) {
-        if (key == null)
-            return (V)getForNullKey();
-        int hash = hash(key.hashCode());
-        for (Entry<?,?> e = table[indexFor(hash, table.length)];
-             e != null;
-             e = e.next) {
-            Object k;
-            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
-                return (V)e.value;
-        }
-        return null;
-    }
+        Entry<K,V> entry = getEntry(key);
 
-    /**
-     * Offloaded version of get() to look up null keys.  Null keys map
-     * to index 0.  This null case is split out into separate methods
-     * for the sake of performance in the two most commonly used
-     * operations (get and put), but incorporated with conditionals in
-     * others.
-     */
-    private Object getForNullKey() {
-        for (Entry<?,?> e = table[0]; e != null; e = e.next) {
-            if (e.key == null)
-                return e.value;
-        }
-        return null;
+        return null == entry ? null : entry.getValue();
     }
 
     /**
      * Returns <tt>true</tt> if this map contains a mapping for the
      * specified key.

@@ -358,11 +368,11 @@
      * HashMap.  Returns null if the HashMap contains no mapping
      * for the key.
      */
     @SuppressWarnings("unchecked")
     final Entry<K,V> getEntry(Object key) {
-        int hash = (key == null) ? 0 : hash(key.hashCode());
+        int hash = (key == null) ? 0 : hash(key);
         for (Entry<?,?> e = table[indexFor(hash, table.length)];
              e != null;
              e = e.next) {
             Object k;
             if (e.hash == hash &&

@@ -386,11 +396,11 @@
      *         previously associated <tt>null</tt> with <tt>key</tt>.)
      */
     public V put(K key, V value) {
         if (key == null)
             return putForNullKey(value);
-        int hash = hash(key.hashCode());
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
         @SuppressWarnings("unchecked")
         Entry<K,V> e = (Entry<K,V>)table[i];
         for(; e != null; e = e.next) {
             Object k;

@@ -431,11 +441,11 @@
      * pseudoconstructors (clone, readObject).  It does not resize the table,
      * check for comodification, etc.  It calls createEntry rather than
      * addEntry.
      */
     private void putForCreate(K key, V value) {
-        int hash = (key == null) ? 0 : hash(key.hashCode());
+        int hash = null == key ? 0 : hash(key);
         int i = indexFor(hash, table.length);
 
         /**
          * Look for preexisting entry for key.  This will never happen for
          * clone or deserialize.  It will only happen for construction if the

@@ -482,33 +492,31 @@
         }
 
         Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
         transfer(newTable);
         table = newTable;
-        threshold = (int)(newCapacity * loadFactor);
+        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
     }
 
     /**
      * Transfers all entries from current table to newTable.
      */
     @SuppressWarnings("unchecked")
     void transfer(Entry<?,?>[] newTable) {
         Entry<?,?>[] src = table;
         int newCapacity = newTable.length;
-        for (int j = 0; j < src.length; j++) {
-            Entry<K,V> e = (Entry<K,V>)src[j];
-            if (e != null) {
-                src[j] = null;
-                do {
+        for (int j = 0; j < src.length; j++ ) {
+            Entry<K,V> e = (Entry<K,V>) src[j];
+            while(null != e) {
                     Entry<K,V> next = e.next;
                     int i = indexFor(e.hash, newCapacity);
-                    e.next = (Entry<K,V>)newTable[i];
+                e.next = (Entry<K,V>) newTable[i];
                     newTable[i] = e;
                     e = next;
-                } while (e != null);
             }
         }
+        Arrays.fill(table, null);
     }
 
     /**
      * Copies all of the mappings from the specified map to this map.
      * These mappings will replace any mappings that this map had for

@@ -564,11 +572,11 @@
      * Removes and returns the entry associated with the specified key
      * in the HashMap.  Returns null if the HashMap contains no mapping
      * for this key.
      */
     final Entry<K,V> removeEntryForKey(Object key) {
-        int hash = (key == null) ? 0 : hash(key.hashCode());
+        int hash = (key == null) ? 0 : hash(key);
         int i = indexFor(hash, table.length);
         @SuppressWarnings("unchecked")
             Entry<K,V> prev = (Entry<K,V>)table[i];
         Entry<K,V> e = prev;
 

@@ -592,11 +600,12 @@
 
         return e;
     }
 
     /**
-     * Special version of remove for EntrySet.
+     * Special version of remove for EntrySet using {@code Map.Entry.equals()}
+     * for matching.
      */
     final Entry<K,V> removeMapping(Object o) {
         if (!(o instanceof Map.Entry))
             return null;
 

@@ -771,15 +780,17 @@
      * method to resize the table if appropriate.
      *
      * Subclass overrides this to alter the behavior of put method.
      */
     void addEntry(int hash, K key, V value, int bucketIndex) {
-        @SuppressWarnings("unchecked")
-            Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
-        table[bucketIndex] = new Entry<>(hash, key, value, e);
-        if (size++ >= threshold)
+        if ((size >= threshold) && (null != table[bucketIndex])) {
             resize(2 * table.length);
+            hash = hash(key);
+            bucketIndex = indexFor(hash, table.length);
+        }
+        
+        createEntry(hash, key, value, bucketIndex);
     }
 
     /**
      * Like addEntry except that this version is used when creating entries
      * as part of Map construction or "pseudo-construction" (cloning,

@@ -839,11 +850,10 @@
             Object k = current.key;
             current = null;
             HashMap.this.removeEntryForKey(k);
             expectedModCount = modCount;
         }
-
     }
 
     private final class ValueIterator extends HashIterator<V> {
         public V next() {
             return nextEntry().value;

@@ -1019,42 +1029,65 @@
 
         // Write out size (number of Mappings)
         s.writeInt(size);
 
         // Write out keys and values (alternating)
-        if (i != null) {
-            while (i.hasNext()) {
-                Map.Entry<K,V> e = i.next();
+        if (size > 0) {
+            for(Map.Entry<K,V> e : entrySet0()) {
                 s.writeObject(e.getKey());
                 s.writeObject(e.getValue());
             }
         }
     }
 
     private static final long serialVersionUID = 362498820763181265L;
 
     /**
-     * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
+     * Reconstitute the {@code HashMap} instance from a stream (i.e.,
      * deserialize it).
      */
     private void readObject(java.io.ObjectInputStream s)
          throws IOException, ClassNotFoundException
     {
-        // Read in the threshold, loadfactor, and any hidden stuff
+        // Read in the threshold (ignored), loadfactor, and any hidden stuff
         s.defaultReadObject();
+        if (loadFactor <= 0 || Float.isNaN(loadFactor))
+            throw new InvalidObjectException("Illegal load factor: " +
+                                               loadFactor);
+                
+        // set hashMask
+        Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET, 
+                sun.misc.Hashing.randomHashSeed(this));
 
         // Read in number of buckets and allocate the bucket array;
-        int numBuckets = s.readInt();
-        table = new Entry[numBuckets];
+        s.readInt(); // ignored
 
+        // Read number of mappings
+        int mappings = s.readInt();
+        if (mappings < 0)
+            throw new InvalidObjectException("Illegal mappings count: " +
+                                               mappings);
+        
+        int initialCapacity = (int) Math.min(
+                // capacity chosen by number of mappings 
+                // and desired load (if >= 0.25)
+                mappings * Math.min(1 / loadFactor, 4.0f),
+                // we have limits...
+                HashMap.MAXIMUM_CAPACITY);
+        int capacity = 1;
+        // find smallest power of two which holds all mappings
+        while (capacity < initialCapacity) {
+            capacity <<= 1;
+        }
+        
+        table = new Entry[capacity];
+        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);        
         init();  // Give subclass a chance to do its thing.
 
-        // Read in size (number of Mappings)
-        int size = s.readInt();
 
         // Read the keys and values, and put the mappings in the HashMap
-        for (int i=0; i<size; i++) {
+        for (int i=0; i<mappings; i++) {
             @SuppressWarnings("unchecked")
                 K key = (K) s.readObject();
             @SuppressWarnings("unchecked")
                 V value = (V) s.readObject();
             putForCreate(key, value);