src/share/classes/java/util/concurrent/ConcurrentHashMap.java

Print this page
rev 5382 : 7126277: Alternative hashing implementation

@@ -173,10 +173,16 @@
     static final int RETRIES_BEFORE_LOCK = 2;
 
     /* ---------------- Fields -------------- */
 
     /**
+     * A randomizing value associated with this instance that is applied to  
+     * hash code of keys to make hash collisions harder to find.
+     */
+   private transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+    
+    /**
      * Mask value for indexing into segments. The upper bits of a
      * key's hash code are used to choose the segment.
      */
     final int segmentMask;
 

@@ -260,11 +266,19 @@
      * defends against poor quality hash functions.  This is critical
      * because ConcurrentHashMap uses power-of-two length hash tables,
      * that otherwise encounter collisions for hashCodes that do not
      * differ in lower or upper bits.
      */
-    private static int hash(int h) {
+    private int hash(Object k) {        
+       int h = hashSeed;
+
+        if (k instanceof String) {
+            return h ^ ((String) k).hash32();
+        }
+
+        h ^= k.hashCode();
+
         // Spread bits to regularize both segment and index locations,
         // using variant of single-word Wang/Jenkins hash.
         h += (h <<  15) ^ 0xffffcd7d;
         h ^= (h >>> 10);
         h += (h <<   3);

@@ -915,11 +929,11 @@
      */
     @SuppressWarnings("unchecked")
     public V get(Object key) {
         Segment<K,V> s; // manually integrate access methods to reduce overhead
         HashEntry<K,V>[] tab;
-        int h = hash(key.hashCode());
+        int h = hash(key);
         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
         if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
             (tab = s.table) != null) {
             for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                      (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);

@@ -943,11 +957,11 @@
      */
     @SuppressWarnings("unchecked")
     public boolean containsKey(Object key) {
         Segment<K,V> s; // same as get() except no need for volatile value read
         HashEntry<K,V>[] tab;
-        int h = hash(key.hashCode());
+        int h = hash(key);
         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
         if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
             (tab = s.table) != null) {
             for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                      (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);

@@ -1052,11 +1066,11 @@
     @SuppressWarnings("unchecked")
     public V put(K key, V value) {
         Segment<K,V> s;
         if (value == null)
             throw new NullPointerException();
-        int hash = hash(key.hashCode());
+        int hash = hash(key);
         int j = (hash >>> segmentShift) & segmentMask;
         if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
              (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
             s = ensureSegment(j);
         return s.put(key, hash, value, false);

@@ -1072,11 +1086,11 @@
     @SuppressWarnings("unchecked")
     public V putIfAbsent(K key, V value) {
         Segment<K,V> s;
         if (value == null)
             throw new NullPointerException();
-        int hash = hash(key.hashCode());
+        int hash = hash(key);
         int j = (hash >>> segmentShift) & segmentMask;
         if ((s = (Segment<K,V>)UNSAFE.getObject
              (segments, (j << SSHIFT) + SBASE)) == null)
             s = ensureSegment(j);
         return s.put(key, hash, value, true);

@@ -1102,22 +1116,22 @@
      * @return the previous value associated with <tt>key</tt>, or
      *         <tt>null</tt> if there was no mapping for <tt>key</tt>
      * @throws NullPointerException if the specified key is null
      */
     public V remove(Object key) {
-        int hash = hash(key.hashCode());
+        int hash = hash(key);
         Segment<K,V> s = segmentForHash(hash);
         return s == null ? null : s.remove(key, hash, null);
     }
 
     /**
      * {@inheritDoc}
      *
      * @throws NullPointerException if the specified key is null
      */
     public boolean remove(Object key, Object value) {
-        int hash = hash(key.hashCode());
+        int hash = hash(key);
         Segment<K,V> s;
         return value != null && (s = segmentForHash(hash)) != null &&
             s.remove(key, hash, value) != null;
     }
 

@@ -1125,11 +1139,11 @@
      * {@inheritDoc}
      *
      * @throws NullPointerException if any of the arguments are null
      */
     public boolean replace(K key, V oldValue, V newValue) {
-        int hash = hash(key.hashCode());
+        int hash = hash(key);
         if (oldValue == null || newValue == null)
             throw new NullPointerException();
         Segment<K,V> s = segmentForHash(hash);
         return s != null && s.replace(key, hash, oldValue, newValue);
     }

@@ -1140,11 +1154,11 @@
      * @return the previous value associated with the specified key,
      *         or <tt>null</tt> if there was no mapping for the key
      * @throws NullPointerException if the specified key or value is null
      */
     public V replace(K key, V value) {
-        int hash = hash(key.hashCode());
+        int hash = hash(key);
         if (value == null)
             throw new NullPointerException();
         Segment<K,V> s = segmentForHash(hash);
         return s == null ? null : s.replace(key, hash, value);
     }

@@ -1471,10 +1485,14 @@
     @SuppressWarnings("unchecked")
     private void readObject(java.io.ObjectInputStream s)
             throws java.io.IOException, ClassNotFoundException {
         s.defaultReadObject();
 
+        // set hashMask
+        UNSAFE.putIntVolatile(this, HASHSEED_OFFSET, 
+                 sun.misc.Hashing.randomHashSeed(this));
+
         // Re-initialize segments to be minimally sized, and let grow.
         int cap = MIN_SEGMENT_TABLE_CAPACITY;
         final Segment<K,V>[] segments = this.segments;
         for (int k = 0; k < segments.length; ++k) {
             Segment<K,V> seg = segments[k];

@@ -1498,10 +1516,11 @@
     private static final sun.misc.Unsafe UNSAFE;
     private static final long SBASE;
     private static final int SSHIFT;
     private static final long TBASE;
     private static final int TSHIFT;
+    private static final long HASHSEED_OFFSET;
 
     static {
         int ss, ts;
         try {
             UNSAFE = sun.misc.Unsafe.getUnsafe();

@@ -1509,10 +1528,12 @@
             Class<?> sc = Segment[].class;
             TBASE = UNSAFE.arrayBaseOffset(tc);
             SBASE = UNSAFE.arrayBaseOffset(sc);
             ts = UNSAFE.arrayIndexScale(tc);
             ss = UNSAFE.arrayIndexScale(sc);
+            HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+                ConcurrentHashMap.class.getDeclaredField("hashSeed"));                        
         } catch (Exception e) {
             throw new Error(e);
         }
         if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
             throw new Error("data type scale not a power of two");