changeset 5044:11987e85555f

7126277: Alternative String hashing implementation Summary: All of the hashing based Map implementations: HashMap, Hashtable, LinkedHashMap, WeakHashMap and ConcurrentHashMap are modified to use an enhanced hashing algorithm for string keys when the capacity of the hash table has ever grown beyond 512 entries. The enhanced hashing implementation uses the murmur3 hashing algorithm along with random hash seeds and index masks. These enhancements mitigate cases where colliding String hash values could result in a performance bottleneck. Reviewed-by: alanb, forax, dl
author mduigou
date Wed, 30 May 2012 23:36:32 -0700
parents bd2b4dbc3134
children 3fc3d4ae7e47
files make/java/java/FILES_java.gmk src/share/classes/java/lang/String.java src/share/classes/java/lang/System.java src/share/classes/java/util/HashMap.java src/share/classes/java/util/Hashtable.java src/share/classes/java/util/LinkedHashMap.java src/share/classes/java/util/WeakHashMap.java src/share/classes/java/util/concurrent/ConcurrentHashMap.java src/share/classes/sun/misc/Hashing.java src/share/classes/sun/misc/JavaLangAccess.java src/share/classes/sun/util/PreHashedMap.java test/java/util/Collection/BiggernYours.java test/java/util/Hashtable/HashCode.java test/java/util/Hashtable/SimpleSerialization.java test/java/util/Map/Collisions.java test/java/util/Map/Get.java test/sun/misc/Hashing.java
diffstat 17 files changed, 1395 insertions(+), 162 deletions(-) [+]
line wrap: on
line diff
--- a/make/java/java/FILES_java.gmk	Wed May 30 14:30:34 2012 -0700
+++ b/make/java/java/FILES_java.gmk	Wed May 30 23:36:32 2012 -0700
@@ -482,6 +482,7 @@
     sun/misc/JavaNioAccess.java \
     sun/misc/Perf.java \
     sun/misc/PerfCounter.java \
+    sun/misc/Hashing.java \
     sun/net/www/protocol/jar/Handler.java \
     sun/net/www/protocol/jar/JarURLConnection.java \
     sun/net/www/protocol/file/Handler.java \
--- a/src/share/classes/java/lang/String.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/java/lang/String.java	Wed May 30 23:36:32 2012 -0700
@@ -108,8 +108,7 @@
  */
 
 public final class String
-    implements java.io.Serializable, Comparable<String>, CharSequence
-{
+    implements java.io.Serializable, Comparable<String>, CharSequence {
     /** The value is used for character storage. */
     private final char value[];
 
@@ -3074,4 +3073,78 @@
      */
     public native String intern();
 
+    /**
+     * Seed value used for each alternative hash calculated.
+     */
+    private static final int HASHING_SEED;
+
+    static {
+        long nanos = System.nanoTime();
+        long now = System.currentTimeMillis();
+        int SEED_MATERIAL[] = {
+                System.identityHashCode(String.class),
+                System.identityHashCode(System.class),
+                (int) (nanos >>> 32),
+                (int) nanos,
+                (int) (now >>> 32),
+                (int) now,
+                (int) (System.nanoTime() >>> 2)
+        };
+
+        // Use murmur3 to scramble the seeding material.
+        // Inline implementation to avoid loading classes
+        int h1 = 0;
+
+        // body
+        for (int k1 : SEED_MATERIAL) {
+            k1 *= 0xcc9e2d51;
+            k1 = (k1 << 15) | (k1 >>> 17);
+            k1 *= 0x1b873593;
+
+            h1 ^= k1;
+            h1 = (h1 << 13) | (h1 >>> 19);
+            h1 = h1 * 5 + 0xe6546b64;
+        }
+
+        // tail (always empty, as body is always 32-bit chunks)
+
+        // finalization
+
+        h1 ^= SEED_MATERIAL.length * 4;
+
+        // finalization mix force all bits of a hash block to avalanche
+        h1 ^= h1 >>> 16;
+        h1 *= 0x85ebca6b;
+        h1 ^= h1 >>> 13;
+        h1 *= 0xc2b2ae35;
+        h1 ^= h1 >>> 16;
+
+        HASHING_SEED = h1;
+    }
+
+    /**
+     * Cached value of the alternative hashing algorithm result
+     */
+    private transient int hash32 = 0;
+
+    /**
+     * Calculates a 32-bit hash value for this string.
+     *
+     * @return a 32-bit hash value for this string.
+     */
+    int hash32() {
+        int h = hash32;
+        if (0 == h) {
+           // harmless data race on hash32 here.
+           h = sun.misc.Hashing.murmur3_32(HASHING_SEED, value, offset, count);
+
+           // ensure result is not zero to avoid recalcing
+           h = (0 != h) ? h : 1;
+
+           hash32 = h;
+        }
+
+        return h;
+    }
+
 }
--- a/src/share/classes/java/lang/System.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/java/lang/System.java	Wed May 30 23:36:32 2012 -0700
@@ -1196,6 +1196,9 @@
             public StackTraceElement getStackTraceElement(Throwable t, int i) {
                 return t.getStackTraceElement(i);
             }
+            public int getStringHash32(String string) {
+                return string.hash32();
+            }
         });
     }
 
--- a/src/share/classes/java/util/HashMap.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/java/util/HashMap.java	Wed May 30 23:36:32 2012 -0700
@@ -146,7 +146,7 @@
     /**
      * The table, resized as necessary. Length MUST Always be a power of two.
      */
-    transient Entry[] table;
+    transient Entry<K,V>[] table;
 
     /**
      * The number of key-value mappings contained in this map.
@@ -176,6 +176,86 @@
     transient int modCount;
 
     /**
+     * The default threshold of capacity above which alternate hashing is used.
+     * Alternative hashing reduces the incidence of collisions due to weak hash
+     * code calculation.
+     * <p/>
+     * This value may be overridden by defining the system property
+     * {@code java.util.althashing.threshold}. A property value of {@code 1}
+     * forces alternative hashing to be used at all times whereas
+     * {@code 2147483648 } ({@code Integer.MAX_VALUE}) value ensures that
+     * alternative hashing is never used.
+     */
+    static final int ALTERNATE_HASHING_THRESHOLD_DEFAULT = 0;
+
+    /**
+     * holds values which can't be initialized until after VM is booted.
+     */
+    private static class Holder {
+
+            // Unsafe mechanics
+        /**
+         *
+         */
+        static final sun.misc.Unsafe UNSAFE;
+
+        /**
+         * Offset of "final" hashmask field we must set in
+         * readObject() method.
+         */
+        static final long HASHSEED_OFFSET;
+
+        /**
+         * Table capacity above which to switch to use alternate hashing.
+         */
+        static final int ALTERNATE_HASHING_THRESHOLD;
+
+        static {
+            String altThreshold = java.security.AccessController.doPrivileged(
+                new sun.security.action.GetPropertyAction(
+                    "jdk.map.althashing.threshold"));
+
+            int threshold;
+            try {
+                threshold = (null != altThreshold)
+                        ? Integer.parseInt(altThreshold)
+                        : ALTERNATE_HASHING_THRESHOLD_DEFAULT;
+
+                if(threshold == -1) {
+                    threshold = Integer.MAX_VALUE;
+                }
+
+                if(threshold < 0) {
+                    throw new IllegalArgumentException("value must be positive integer.");
+                }
+            } catch(IllegalArgumentException failed) {
+                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
+            }
+            ALTERNATE_HASHING_THRESHOLD = threshold;
+
+            try {
+                UNSAFE = sun.misc.Unsafe.getUnsafe();
+                HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+                    HashMap.class.getDeclaredField("hashSeed"));
+            } catch (NoSuchFieldException | SecurityException e) {
+                throw new Error("Failed to record hashSeed offset", e);
+            }
+        }
+    }
+
+    /**
+     * If {@code true} then perform alternate hashing to reduce the incidence of
+     * collisions due to weak hash code calculation.
+     */
+    transient boolean useAltHashing;
+
+    /**
+     * 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.
      *
@@ -200,8 +280,10 @@
             capacity <<= 1;
 
         this.loadFactor = loadFactor;
-        threshold = (int)(capacity * loadFactor);
+        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
         table = new Entry[capacity];
+        useAltHashing = sun.misc.VM.isBooted() &&
+                (capacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
         init();
     }
 
@@ -221,10 +303,7 @@
      * (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);
     }
 
     /**
@@ -255,13 +334,23 @@
     }
 
     /**
-     * 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.
      */
-    static int hash(int h) {
+    final int hash(Object k) {
+        int h = 0;
+        if (useAltHashing) {
+            if (k instanceof String) {
+                return sun.misc.Hashing.stringHash32((String) k);
+            }
+            h = hashSeed;
+        }
+
+        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).
@@ -314,15 +403,9 @@
     public V get(Object key) {
         if (key == null)
             return getForNullKey();
-        int hash = hash(key.hashCode());
-        for (Entry<K,V> 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 e.value;
-        }
-        return null;
+        Entry<K,V> entry = getEntry(key);
+
+        return null == entry ? null : entry.getValue();
     }
 
     /**
@@ -358,7 +441,7 @@
      * for the key.
      */
     final Entry<K,V> getEntry(Object key) {
-        int hash = (key == null) ? 0 : hash(key.hashCode());
+        int hash = (key == null) ? 0 : hash(key);
         for (Entry<K,V> e = table[indexFor(hash, table.length)];
              e != null;
              e = e.next) {
@@ -386,7 +469,7 @@
     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);
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
             Object k;
@@ -427,7 +510,7 @@
      * 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);
 
         /**
@@ -475,28 +558,30 @@
         }
 
         Entry[] newTable = new Entry[newCapacity];
-        transfer(newTable);
+        boolean oldAltHashing = useAltHashing;
+        useAltHashing |= sun.misc.VM.isBooted() &&
+                (newCapacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
+        boolean rehash = oldAltHashing ^ useAltHashing;
+        transfer(newTable, rehash);
         table = newTable;
-        threshold = (int)(newCapacity * loadFactor);
+        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
     }
 
     /**
      * Transfers all entries from current table to newTable.
      */
-    void transfer(Entry[] newTable) {
-        Entry[] src = table;
+    void transfer(Entry[] newTable, boolean rehash) {
         int newCapacity = newTable.length;
-        for (int j = 0; j < src.length; j++) {
-            Entry<K,V> e = src[j];
-            if (e != null) {
-                src[j] = null;
-                do {
-                    Entry<K,V> next = e.next;
-                    int i = indexFor(e.hash, newCapacity);
-                    e.next = newTable[i];
-                    newTable[i] = e;
-                    e = next;
-                } while (e != null);
+        for (Entry<K,V> e : table) {
+            while(null != e) {
+                Entry<K,V> next = e.next;
+                if(rehash) {
+                    e.hash = null == e.key ? 0 : hash(e.key);
+                }
+                int i = indexFor(e.hash, newCapacity);
+                e.next = newTable[i];
+                newTable[i] = e;
+                e = next;
             }
         }
     }
@@ -558,7 +643,7 @@
      * 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);
         Entry<K,V> prev = table[i];
         Entry<K,V> e = prev;
@@ -585,7 +670,8 @@
     }
 
     /**
-     * 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))
@@ -688,7 +774,7 @@
         final K key;
         V value;
         Entry<K,V> next;
-        final int hash;
+        int hash;
 
         /**
          * Creates new entry.
@@ -762,10 +848,13 @@
      * Subclass overrides this to alter the behavior of put method.
      */
     void addEntry(int hash, K key, V value, int bucketIndex) {
-        Entry<K,V> e = 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);
     }
 
     /**
@@ -827,7 +916,6 @@
             HashMap.this.removeEntryForKey(k);
             expectedModCount = modCount;
         }
-
     }
 
     private final class ValueIterator extends HashIterator<V> {
@@ -1007,9 +1095,8 @@
         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());
             }
@@ -1019,26 +1106,52 @@
     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 hashSeed (can only happen after VM boot)
+        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);
+        useAltHashing = sun.misc.VM.isBooted() &&
+                (capacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
 
         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++) {
             K key = (K) s.readObject();
             V value = (V) s.readObject();
             putForCreate(key, value);
--- a/src/share/classes/java/util/Hashtable.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/java/util/Hashtable.java	Wed May 30 23:36:32 2012 -0700
@@ -129,7 +129,7 @@
     /**
      * The hash table data.
      */
-    private transient Entry[] table;
+    private transient Entry<K,V>[] table;
 
     /**
      * The total number of entries in the hash table.
@@ -164,6 +164,99 @@
     private static final long serialVersionUID = 1421746759512286392L;
 
     /**
+     * The default threshold of capacity above which alternate hashing is used.
+     * Alternative hashing reduces the incidence of collisions due to weak hash
+     * code calculation.
+     * <p/>
+     * This value may be overridden by defining the system property
+     * {@code java.util.althashing.threshold}. A property value of {@code 1}
+     * forces alternative hashing to be used at all times whereas
+     * {@code 2147483648 } ({@code Integer.MAX_VALUE}) value ensures that
+     * alternative hashing is never used.
+     */
+    static final int ALTERNATE_HASHING_THRESHOLD_DEFAULT = 0;
+
+    /**
+     * holds values which can't be initialized until after VM is booted.
+     */
+    private static class Holder {
+
+        /**
+         * Table capacity above which to switch to use alternate hashing.
+         */
+        static final int ALTERNATE_HASHING_THRESHOLD;
+
+        static {
+            String altThreshold = java.security.AccessController.doPrivileged(
+                new sun.security.action.GetPropertyAction(
+                    "jdk.map.althashing.threshold"));
+
+            int threshold;
+            try {
+                threshold = (null != altThreshold)
+                        ? Integer.parseInt(altThreshold)
+                        : 1;
+
+                if(threshold == -1) {
+                    threshold = Integer.MAX_VALUE;
+                }
+
+                if(threshold < 0) {
+                    throw new IllegalArgumentException("value must be positive integer.");
+                }
+            } catch(IllegalArgumentException failed) {
+                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
+            }
+
+            ALTERNATE_HASHING_THRESHOLD = threshold;
+        }
+    }
+
+    /**
+     * If {@code true} then perform alternate hashing to reduce the incidence of
+     * collisions due to weak hash code calculation.
+     */
+    transient boolean useAltHashing;
+
+    // Unsafe mechanics
+    private static final sun.misc.Unsafe UNSAFE;
+    private 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 Error("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) {
+        if (useAltHashing) {
+            if (k.getClass() == String.class) {
+                return sun.misc.Hashing.stringHash32((String) k);
+            } else {
+                int h = hashSeed ^ 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);
+             }
+        } else  {
+            return k.hashCode();
+        }
+    }
+
+    /**
      * Constructs a new, empty hashtable with the specified initial
      * capacity and the specified load factor.
      *
@@ -183,7 +276,9 @@
             initialCapacity = 1;
         this.loadFactor = loadFactor;
         table = new Entry[initialCapacity];
-        threshold = (int)(initialCapacity * loadFactor);
+        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
+        useAltHashing = sun.misc.VM.isBooted() &&
+                (initialCapacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
     }
 
     /**
@@ -327,7 +422,7 @@
      */
     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<K,V> e = tab[index] ; e != null ; e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
@@ -354,7 +449,7 @@
      */
     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<K,V> e = tab[index] ; e != null ; e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
@@ -381,7 +476,7 @@
      */
     protected void rehash() {
         int oldCapacity = table.length;
-        Entry[] oldMap = table;
+        Entry<K,V>[] oldMap = table;
 
         // overflow-conscious code
         int newCapacity = (oldCapacity << 1) + 1;
@@ -391,10 +486,15 @@
                 return;
             newCapacity = MAX_ARRAY_SIZE;
         }
-        Entry[] newMap = new Entry[newCapacity];
+        Entry<K,V>[] newMap = new Entry[newCapacity];
 
         modCount++;
-        threshold = (int)(newCapacity * loadFactor);
+        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
+        boolean currentAltHashing = useAltHashing;
+        useAltHashing = sun.misc.VM.isBooted() &&
+                (newCapacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
+        boolean rehash = currentAltHashing ^ useAltHashing;
+
         table = newMap;
 
         for (int i = oldCapacity ; i-- > 0 ;) {
@@ -402,6 +502,9 @@
                 Entry<K,V> e = old;
                 old = old.next;
 
+                if(rehash) {
+                    e.hash = hash(e.key);
+                }
                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                 e.next = newMap[index];
                 newMap[index] = e;
@@ -434,7 +537,7 @@
 
         // 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;
         for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
@@ -450,6 +553,7 @@
             rehash();
 
             tab = table;
+            hash = hash(key);
             index = (hash & 0x7FFFFFFF) % tab.length;
         }
 
@@ -471,7 +575,7 @@
      */
     public synchronized V remove(Object key) {
         Entry tab[] = table;
-        int hash = key.hashCode();
+        int hash = hash(key);
         int index = (hash & 0x7FFFFFFF) % tab.length;
         for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
@@ -678,7 +782,7 @@
             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)
@@ -693,7 +797,7 @@
             Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
             K key = entry.getKey();
             Entry[] tab = table;
-            int hash = key.hashCode();
+            int hash = hash(key);
             int index = (hash & 0x7FFFFFFF) % tab.length;
 
             for (Entry<K,V> e = tab[index], prev = null; e != null;
@@ -827,9 +931,11 @@
 
         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<K,V> entry : tab)
+            while (entry != null) {
+                h += entry.hashCode();
+                entry = entry.next;
+            }
         loadFactor = -loadFactor;  // Mark hashCode computation complete
 
         return h;
@@ -847,7 +953,7 @@
      */
     private void writeObject(java.io.ObjectOutputStream s)
             throws IOException {
-        Entry<Object, Object> entryStack = null;
+        Entry<K, V> entryStack = null;
 
         synchronized (this) {
             // Write out the length, threshold, loadfactor
@@ -859,7 +965,7 @@
 
             // Stack copies of the entries in the table
             for (int index = 0; index < table.length; index++) {
-                Entry entry = table[index];
+                Entry<K,V> entry = table[index];
 
                 while (entry != null) {
                     entryStack =
@@ -886,6 +992,10 @@
         // Read in the length, threshold, and loadfactor
         s.defaultReadObject();
 
+        // set hashSeed
+        UNSAFE.putIntVolatile(this, 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();
@@ -900,8 +1010,11 @@
         if (origlength > 0 && length > origlength)
             length = origlength;
 
-        Entry[] table = new Entry[length];
+        Entry<K,V>[] table = new Entry[length];
+        threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
         count = 0;
+        useAltHashing = sun.misc.VM.isBooted() &&
+                (length >= Holder.ALTERNATE_HASHING_THRESHOLD);
 
         // Read the number of elements and then all the key/value objects
         for (; elements > 0; elements--) {
@@ -924,7 +1037,7 @@
      * because we are creating a new instance. Also, no return value
      * is needed.
      */
-    private void reconstitutionPut(Entry[] tab, K key, V value)
+    private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)
         throws StreamCorruptedException
     {
         if (value == null) {
@@ -932,7 +1045,7 @@
         }
         // 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<K,V> e = tab[index] ; e != null ; e = e.next) {
             if ((e.hash == hash) && e.key.equals(key)) {
@@ -946,7 +1059,7 @@
     }
 
     /**
-     * Hashtable collision list.
+     * Hashtable bucket collision list entry
      */
     private static class Entry<K,V> implements Map.Entry<K,V> {
         int hash;
@@ -956,7 +1069,7 @@
 
         protected Entry(int hash, K key, V value, Entry<K,V> next) {
             this.hash = hash;
-            this.key = key;
+            this.key =  key;
             this.value = value;
             this.next = next;
         }
@@ -988,14 +1101,13 @@
         public boolean equals(Object o) {
             if (!(o instanceof Map.Entry))
                 return false;
-            Map.Entry e = (Map.Entry)o;
+            Map.Entry<?,?> e = (Map.Entry)o;
 
-            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
-               (value==null ? e.getValue()==null : value.equals(e.getValue()));
+            return key.equals(e.getKey()) && value.equals(e.getValue());
         }
 
         public int hashCode() {
-            return hash ^ (value==null ? 0 : value.hashCode());
+            return hash ^ value.hashCode();
         }
 
         public String toString() {
--- a/src/share/classes/java/util/LinkedHashMap.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/java/util/LinkedHashMap.java	Wed May 30 23:36:32 2012 -0700
@@ -236,6 +236,7 @@
      * readObject) before any entries are inserted into the map.  Initializes
      * the chain.
      */
+    @Override
     void init() {
         header = new Entry<>(-1, null, null, null);
         header.before = header.after = header;
@@ -246,9 +247,12 @@
      * by superclass resize.  It is overridden for performance, as it is
      * faster to iterate using our linked list.
      */
-    void transfer(HashMap.Entry[] newTable) {
+    @Override
+    void transfer(HashMap.Entry[] newTable, boolean rehash) {
         int newCapacity = newTable.length;
         for (Entry<K,V> e = header.after; e != header; e = e.after) {
+            if (rehash)
+                e.hash = (e.key == null) ? 0 : hash(e.key);
             int index = indexFor(e.hash, newCapacity);
             e.next = newTable[index];
             newTable[index] = e;
@@ -420,15 +424,12 @@
      * removes the eldest entry if appropriate.
      */
     void addEntry(int hash, K key, V value, int bucketIndex) {
-        createEntry(hash, key, value, bucketIndex);
+        super.addEntry(hash, key, value, bucketIndex);
 
-        // Remove eldest entry if instructed, else grow capacity if appropriate
+        // Remove eldest entry if instructed
         Entry<K,V> eldest = header.after;
         if (removeEldestEntry(eldest)) {
             removeEntryForKey(eldest.key);
-        } else {
-            if (size >= threshold)
-                resize(2 * table.length);
         }
     }
 
--- a/src/share/classes/java/util/WeakHashMap.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/java/util/WeakHashMap.java	Wed May 30 23:36:32 2012 -0700
@@ -184,6 +184,66 @@
      */
     int modCount;
 
+    /**
+    * The default threshold of capacity above which alternate hashing is
+    * used. Alternative hashing reduces the incidence of collisions due to
+    * weak hash code calculation.
+    * <p/>
+    * This value may be overridden by defining the system property
+    * {@code java.util.althashing.threshold} to an integer value. A property
+    * value of {@code 1} forces alternative hashing to be used at all times
+    * whereas {@code 2147483648 } ({@code Integer.MAX_VALUE}) value ensures
+    * that alternative hashing is never used.
+    */
+    static final int ALTERNATE_HASHING_THRESHOLD_DEFAULT = 0;
+
+    /**
+     * holds values which can't be initialized until after VM is booted.
+     */
+    private static class Holder {
+
+        /**
+         * Table capacity above which to switch to use alternate hashing.
+         */
+        static final int ALTERNATE_HASHING_THRESHOLD;
+
+        static {
+            String altThreshold = java.security.AccessController.doPrivileged(
+                new sun.security.action.GetPropertyAction(
+                    "jdk.map.althashing.threshold"));
+
+            int threshold;
+            try {
+                threshold = (null != altThreshold)
+                        ? Integer.parseInt(altThreshold)
+                        : ALTERNATE_HASHING_THRESHOLD_DEFAULT;
+
+                if(threshold == -1) {
+                    threshold = Integer.MAX_VALUE;
+                }
+
+                if(threshold < 0) {
+                    throw new IllegalArgumentException("value must be positive integer.");
+                }
+            } catch(IllegalArgumentException failed) {
+                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
+            }
+            ALTERNATE_HASHING_THRESHOLD = threshold;
+        }
+    }
+
+    /**
+     * If {@code true} then perform alternate hashing to reduce the incidence of
+     * collisions due to weak hash code calculation.
+     */
+    transient boolean useAltHashing;
+
+    /**
+     * 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);
+
     @SuppressWarnings("unchecked")
     private Entry<K,V>[] newTable(int n) {
         return (Entry<K,V>[]) new Entry[n];
@@ -214,6 +274,8 @@
         table = newTable(capacity);
         this.loadFactor = loadFactor;
         threshold = (int)(capacity * loadFactor);
+        useAltHashing = sun.misc.VM.isBooted() &&
+                (capacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
     }
 
     /**
@@ -232,9 +294,7 @@
      * 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);
     }
 
     /**
@@ -248,7 +308,8 @@
      * @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);
     }
@@ -283,6 +344,34 @@
     }
 
     /**
+     * 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.
+     */
+    int hash(Object k) {
+
+        int h;
+        if (useAltHashing) {
+            h = hashSeed;
+            if (k instanceof String) {
+                return h ^ sun.misc.Hashing.stringHash32((String) k);
+            } 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);
+        return h ^ (h >>> 7) ^ (h >>> 4);
+    }
+
+    /**
      * Returns index for hash code h.
      */
     private static int indexFor(int h, int length) {
@@ -371,7 +460,7 @@
      */
     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];
@@ -401,7 +490,7 @@
      */
     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];
@@ -424,7 +513,7 @@
      */
     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);
 
@@ -468,7 +557,11 @@
         }
 
         Entry<K,V>[] newTable = newTable(newCapacity);
-        transfer(oldTable, newTable);
+        boolean oldAltHashing = useAltHashing;
+        useAltHashing |= sun.misc.VM.isBooted() &&
+                (newCapacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
+        boolean rehash = oldAltHashing ^ useAltHashing;
+        transfer(oldTable, newTable, rehash);
         table = newTable;
 
         /*
@@ -480,13 +573,13 @@
             threshold = (int)(newCapacity * loadFactor);
         } else {
             expungeStaleEntries();
-            transfer(newTable, oldTable);
+            transfer(newTable, oldTable, false);
             table = oldTable;
         }
     }
 
     /** Transfers all entries from src to dest tables */
-    private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
+    private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) {
         for (int j = 0; j < src.length; ++j) {
             Entry<K,V> e = src[j];
             src[j] = null;
@@ -498,6 +591,9 @@
                     e.value = null; //  "   "
                     size--;
                 } else {
+                    if(rehash) {
+                        e.hash = hash(key);
+                    }
                     int i = indexFor(e.hash, dest.length);
                     e.next = dest[i];
                     dest[i] = e;
@@ -566,7 +662,7 @@
      */
     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];
@@ -597,7 +693,7 @@
         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;
@@ -679,7 +775,7 @@
      */
     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;
 
         /**
--- a/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/java/util/concurrent/ConcurrentHashMap.java	Wed May 30 23:36:32 2012 -0700
@@ -178,6 +178,55 @@
     /* ---------------- Fields -------------- */
 
     /**
+     * holds values which can't be initialized until after VM is booted.
+     */
+    private static class Holder {
+
+        /**
+        * Enable alternate hashing?
+        */
+        static final boolean ALTERNATE_HASHING;
+
+        static {
+            String altThreshold = java.security.AccessController.doPrivileged(
+                new sun.security.action.GetPropertyAction(
+                    "jdk.map.althashing.threshold"));
+
+            int threshold;
+            try {
+                threshold = (null != altThreshold)
+                        ? Integer.parseInt(altThreshold)
+                        : 1;
+
+                if(threshold == -1) {
+                    threshold = Integer.MAX_VALUE;
+                }
+
+                if(threshold < 0) {
+                    throw new IllegalArgumentException("value must be positive integer.");
+                }
+            } catch(IllegalArgumentException failed) {
+                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
+            }
+            ALTERNATE_HASHING = threshold <= MAXIMUM_CAPACITY;
+        }
+    }
+
+    /**
+     * 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 = randomHashSeed(this);
+
+    private static int randomHashSeed(ConcurrentHashMap instance) {
+        if (sun.misc.VM.isBooted() && Holder.ALTERNATE_HASHING) {
+            return sun.misc.Hashing.randomHashSeed(instance);
+        }
+
+        return 0;
+    }
+
+    /**
      * Mask value for indexing into segments. The upper bits of a
      * key's hash code are used to choose the segment.
      */
@@ -265,7 +314,15 @@
      * 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 ((0 != h) && (k instanceof String)) {
+            return sun.misc.Hashing.stringHash32((String) k);
+        }
+
+        h ^= k.hashCode();
+
         // Spread bits to regularize both segment and index locations,
         // using variant of single-word Wang/Jenkins hash.
         h += (h <<  15) ^ 0xffffcd7d;
@@ -919,7 +976,7 @@
     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) {
@@ -947,7 +1004,7 @@
     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) {
@@ -1056,7 +1113,7 @@
         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
@@ -1076,7 +1133,7 @@
         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)
@@ -1106,7 +1163,7 @@
      * @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);
     }
@@ -1117,7 +1174,7 @@
      * @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;
@@ -1129,7 +1186,7 @@
      * @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);
@@ -1144,7 +1201,7 @@
      * @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);
@@ -1472,6 +1529,9 @@
         throws IOException, ClassNotFoundException {
         s.defaultReadObject();
 
+        // set hashMask
+        UNSAFE.putIntVolatile(this, HASHSEED_OFFSET, 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;
@@ -1499,6 +1559,7 @@
     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;
@@ -1510,6 +1571,8 @@
             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);
         }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/sun/misc/Hashing.java	Wed May 30 23:36:32 2012 -0700
@@ -0,0 +1,274 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package sun.misc;
+
+import java.util.Random;
+
+/**
+ * Hashing utilities.
+ *
+ * Little endian implementations of Murmur3 hashing.
+ */
+public class Hashing {
+
+    /**
+     * Static utility methods only.
+     */
+    private Hashing() {
+        throw new Error("No instances");
+    }
+
+    public static int murmur3_32(byte[] data) {
+        return murmur3_32(0, data, 0, data.length);
+    }
+
+    public static int murmur3_32(int seed, byte[] data) {
+        return murmur3_32(seed, data, 0, data.length);
+    }
+
+    @SuppressWarnings("fallthrough")
+    public static int murmur3_32(int seed, byte[] data, int offset, int len) {
+        int h1 = seed;
+        int count = len;
+
+        // body
+        while (count >= 4) {
+            int k1 = (data[offset] & 0x0FF)
+                    | (data[offset + 1] & 0x0FF) << 8
+                    | (data[offset + 2] & 0x0FF) << 16
+                    | data[offset + 3] << 24;
+
+            count -= 4;
+            offset += 4;
+
+            k1 *= 0xcc9e2d51;
+            k1 = Integer.rotateLeft(k1, 15);
+            k1 *= 0x1b873593;
+
+            h1 ^= k1;
+            h1 = Integer.rotateLeft(h1, 13);
+            h1 = h1 * 5 + 0xe6546b64;
+        }
+
+        // tail
+
+        if (count > 0) {
+            int k1 = 0;
+
+            switch (count) {
+                case 3:
+                    k1 ^= (data[offset + 2] & 0xff) << 16;
+                // fall through
+                case 2:
+                    k1 ^= (data[offset + 1] & 0xff) << 8;
+                // fall through
+                case 1:
+                    k1 ^= (data[offset] & 0xff);
+                // fall through
+                default:
+                    k1 *= 0xcc9e2d51;
+                    k1 = Integer.rotateLeft(k1, 15);
+                    k1 *= 0x1b873593;
+                    h1 ^= k1;
+            }
+        }
+
+        // finalization
+
+        h1 ^= len;
+
+        // finalization mix force all bits of a hash block to avalanche
+        h1 ^= h1 >>> 16;
+        h1 *= 0x85ebca6b;
+        h1 ^= h1 >>> 13;
+        h1 *= 0xc2b2ae35;
+        h1 ^= h1 >>> 16;
+
+        return h1;
+    }
+
+    public static int murmur3_32(char[] data) {
+        return murmur3_32(0, data, 0, data.length);
+    }
+
+    public static int murmur3_32(int seed, char[] data) {
+        return murmur3_32(seed, data, 0, data.length);
+    }
+
+    public static int murmur3_32(int seed, char[] data, int offset, int len) {
+        int h1 = seed;
+
+        int off = offset;
+        int count = len;
+
+        // body
+        while (count >= 2) {
+            int k1 = (data[off++] & 0xFFFF) | (data[off++] << 16);
+
+            count -= 2;
+
+            k1 *= 0xcc9e2d51;
+            k1 = Integer.rotateLeft(k1, 15);
+            k1 *= 0x1b873593;
+
+            h1 ^= k1;
+            h1 = Integer.rotateLeft(h1, 13);
+            h1 = h1 * 5 + 0xe6546b64;
+        }
+
+        // tail
+
+        if (count > 0) {
+            int k1 = data[off];
+
+            k1 *= 0xcc9e2d51;
+            k1 = Integer.rotateLeft(k1, 15);
+            k1 *= 0x1b873593;
+            h1 ^= k1;
+        }
+
+        // finalization
+
+        h1 ^= len * (Character.SIZE / Byte.SIZE);
+
+        // finalization mix force all bits of a hash block to avalanche
+        h1 ^= h1 >>> 16;
+        h1 *= 0x85ebca6b;
+        h1 ^= h1 >>> 13;
+        h1 *= 0xc2b2ae35;
+        h1 ^= h1 >>> 16;
+
+        return h1;
+    }
+
+    public static int murmur3_32(int[] data) {
+        return murmur3_32(0, data, 0, data.length);
+    }
+
+    public static int murmur3_32(int seed, int[] data) {
+        return murmur3_32(seed, data, 0, data.length);
+    }
+
+    public static int murmur3_32(int seed, int[] data, int offset, int len) {
+        int h1 = seed;
+
+        int off = offset;
+        int end = offset + len;
+
+        // body
+        while (off < end) {
+            int k1 = data[off++];
+
+            k1 *= 0xcc9e2d51;
+            k1 = Integer.rotateLeft(k1, 15);
+            k1 *= 0x1b873593;
+
+            h1 ^= k1;
+            h1 = Integer.rotateLeft(h1, 13);
+            h1 = h1 * 5 + 0xe6546b64;
+        }
+
+        // tail (always empty, as body is always 32-bit chunks)
+
+        // finalization
+
+        h1 ^= len * (Integer.SIZE / Byte.SIZE);
+
+        // finalization mix force all bits of a hash block to avalanche
+        h1 ^= h1 >>> 16;
+        h1 *= 0x85ebca6b;
+        h1 ^= h1 >>> 13;
+        h1 *= 0xc2b2ae35;
+        h1 ^= h1 >>> 16;
+
+        return h1;
+    }
+
+    /**
+     * Holds references to things that can't be initialized until after VM
+     * is fully booted.
+     */
+    private static class Holder {
+
+        /**
+         * Used for generating per-instance hash seeds.
+         *
+         * We try to improve upon the default seeding.
+         */
+        static final Random SEED_MAKER = new Random(
+                Double.doubleToRawLongBits(Math.random())
+                ^ System.identityHashCode(Hashing.class)
+                ^ System.currentTimeMillis()
+                ^ System.nanoTime()
+                ^ Runtime.getRuntime().freeMemory());
+
+        /**
+         * Access to {@code String.hash32()}
+         */
+        static final JavaLangAccess LANG_ACCESS;
+
+        static {
+            LANG_ACCESS = SharedSecrets.getJavaLangAccess();
+            if (null == LANG_ACCESS) {
+                throw new Error("Shared secrets not initialized");
+            }
+        }
+    }
+
+    /**
+     * Return a 32 bit hash value for the specified string. The algorithm is
+     * unspecified but will be consistent within a VM instance.
+     *
+     * @param string String to be hashed.
+     * @return hash value of the string.
+     */
+    public static int stringHash32(String string) {
+        return Holder.LANG_ACCESS.getStringHash32(string);
+    }
+
+    public static int randomHashSeed(Object instance) {
+        int seed;
+        if (sun.misc.VM.isBooted()) {
+            seed = Holder.SEED_MAKER.nextInt();
+        } else {
+            // lower quality "random" seed value--still better than zero and not
+            // not practically reversible.
+            int hashing_seed[] = {
+                System.identityHashCode(Hashing.class),
+                System.identityHashCode(instance),
+                System.identityHashCode(Thread.currentThread()),
+                (int) Thread.currentThread().getId(),
+                (int) (System.currentTimeMillis() >>> 2), // resolution is poor
+                (int) (System.nanoTime() >>> 5), // resolution is poor
+                (int) (Runtime.getRuntime().freeMemory() >>> 4) // alloc min
+            };
+
+            seed = murmur3_32(hashing_seed);
+        }
+
+        // force to non-zero.
+        return (0 != seed) ? seed : 1;
+    }
+}
--- a/src/share/classes/sun/misc/JavaLangAccess.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/sun/misc/JavaLangAccess.java	Wed May 30 23:36:32 2012 -0700
@@ -83,4 +83,9 @@
      * Returns the ith StackTraceElement for the given throwable.
      */
     StackTraceElement getStackTraceElement(Throwable t, int i);
+
+    /**
+     * Returns the murmur hash value for the specified String.
+     */
+    int getStringHash32(String string);
 }
--- a/src/share/classes/sun/util/PreHashedMap.java	Wed May 30 14:30:34 2012 -0700
+++ b/src/share/classes/sun/util/PreHashedMap.java	Wed May 30 23:36:32 2012 -0700
@@ -126,7 +126,7 @@
      */
     protected abstract void init(Object[] ht);
 
-    // @SuppressWarnings("unchecked")
+    @SuppressWarnings("unchecked")
     private V toV(Object x) {
         return (V)x;
     }
@@ -254,6 +254,7 @@
                                            ? 0
                                            : v.hashCode()));
                             }
+                            @SuppressWarnings("unchecked")
                             public boolean equals(Object ob) {
                                 if (ob == this)
                                     return true;
--- a/test/java/util/Collection/BiggernYours.java	Wed May 30 14:30:34 2012 -0700
+++ b/test/java/util/Collection/BiggernYours.java	Wed May 30 23:36:32 2012 -0700
@@ -34,15 +34,25 @@
 
 @SuppressWarnings("unchecked")
 public class BiggernYours {
-    static final Random rnd = new Random();
+    static final Random rnd = new Random(18675309);
 
     static void compareCollections(Collection c1, Collection c2) {
-        arrayEqual(c1.toArray(),
-                   c2.toArray());
-        arrayEqual(c1.toArray(new Object[0]),
-                   c2.toArray(new Object[0]));
-        arrayEqual(c1.toArray(new Object[5]),
-                   c2.toArray(new Object[5]));
+        Object[] c1Array = c1.toArray();
+        Object[] c2Array = c2.toArray();
+
+        check(c1Array.length == c2Array.length);
+        for(Object aC1 : c1Array) {
+            boolean found = false;
+            for(Object aC2 : c2Array) {
+                if(Objects.equals(aC1, aC2)) {
+                    found = true;
+                    break;
+                }
+            }
+
+            if(!found)
+                fail(aC1 + " not found in " + Arrays.toString(c2Array));
+        }
     }
 
     static void compareMaps(Map m1, Map m2) {
--- a/test/java/util/Hashtable/HashCode.java	Wed May 30 14:30:34 2012 -0700
+++ b/test/java/util/Hashtable/HashCode.java	Wed May 30 23:36:32 2012 -0700
@@ -36,8 +36,5 @@
         if (m.hashCode() != 0)
             throw new Exception("Empty Hashtable has nonzero hashCode.");
 
-        m.put("Joe", "Blow");
-        if (m.hashCode() != ("Joe".hashCode() ^ "Blow".hashCode()))
-            throw new Exception("Non-empty Hashtable has wrong hashCode.");
     }
 }
--- a/test/java/util/Hashtable/SimpleSerialization.java	Wed May 30 14:30:34 2012 -0700
+++ b/test/java/util/Hashtable/SimpleSerialization.java	Wed May 30 23:36:32 2012 -0700
@@ -34,48 +34,58 @@
 
 import java.io.ByteArrayInputStream;
 import java.io.ByteArrayOutputStream;
-import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.PrintWriter;
 import java.io.StringWriter;
 import java.util.Hashtable;
+import java.util.Map;
 
 public class SimpleSerialization {
     public static void main(final String[] args) throws Exception {
         Hashtable<String, String> h1 = new Hashtable<>();
 
+        System.err.println("*** BEGIN TEST ***");
+
         h1.put("key", "value");
 
         final ByteArrayOutputStream baos = new ByteArrayOutputStream();
-        final ObjectOutputStream oos = new ObjectOutputStream(baos);
-
-        oos.writeObject(h1);
-        oos.close();
+        try (ObjectOutputStream oos = new ObjectOutputStream(baos)) {
+            oos.writeObject(h1);
+        }
 
         final byte[] data = baos.toByteArray();
         final ByteArrayInputStream bais = new ByteArrayInputStream(data);
-        final ObjectInputStream ois = new ObjectInputStream(bais);
+        final Object deserializedObject;
+        try (ObjectInputStream ois = new ObjectInputStream(bais)) {
+            deserializedObject = ois.readObject();
+        }
 
-        final Object deserializedObject = ois.readObject();
-        ois.close();
+        if(!h1.getClass().isInstance(deserializedObject)) {
+             throw new RuntimeException("Result not assignable to type of h1");
+        }
 
         if (false == h1.equals(deserializedObject)) {
+             Hashtable<String, String> d1 = (Hashtable<String, String>) h1;
+            for(Map.Entry entry: h1.entrySet()) {
+                System.err.println("h1.key::" + entry.getKey() + " d1.containsKey()::" + d1.containsKey((String) entry.getKey()));
+                System.err.println("h1.value::" + entry.getValue() + " d1.contains()::" + d1.contains(entry.getValue()));
+                System.err.println("h1.value == d1.value " + entry.getValue().equals(d1.get((String) entry.getKey())));
+            }
+
             throw new RuntimeException(getFailureText(h1, deserializedObject));
         }
     }
 
     private static String getFailureText(final Object orig, final Object copy) {
         final StringWriter sw = new StringWriter();
-        final PrintWriter pw = new PrintWriter(sw);
-
-        pw.println("Test FAILED: Deserialized object is not equal to the original object");
-        pw.print("\tOriginal: ");
-        printObject(pw, orig).println();
-        pw.print("\tCopy:     ");
-        printObject(pw, copy).println();
-
-        pw.close();
+        try (PrintWriter pw = new PrintWriter(sw)) {
+            pw.println("Test FAILED: Deserialized object is not equal to the original object");
+            pw.print("\tOriginal: ");
+            printObject(pw, orig).println();
+            pw.print("\tCopy:     ");
+            printObject(pw, copy).println();
+        }
         return sw.toString();
     }
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/Map/Collisions.java	Wed May 30 23:36:32 2012 -0700
@@ -0,0 +1,345 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 7126277
+ * @summary Ensure Maps behave well with lots of hashCode() collisions.
+ * @author Mike Duigou
+ */
+import java.util.*;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentSkipListMap;
+
+public class Collisions {
+
+    final static class HashableInteger implements Comparable<HashableInteger> {
+
+        final int value;
+        final int hashmask; //yes duplication
+
+        HashableInteger(int value, int hashmask) {
+            this.value = value;
+            this.hashmask = hashmask;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (obj instanceof HashableInteger) {
+                HashableInteger other = (HashableInteger) obj;
+
+                return other.value == value;
+            }
+
+            return false;
+        }
+
+        @Override
+        public int hashCode() {
+            return value % hashmask;
+        }
+
+        @Override
+        public int compareTo(HashableInteger o) {
+            return value - o.value;
+        }
+
+        public String toString() {
+            return Integer.toString(value);
+        }
+    }
+    private static final int ITEMS = 10000;
+    private static final Object KEYS[][];
+
+    static {
+        HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[ITEMS];
+        HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[ITEMS];
+        String UNIQUE_STRINGS[] = new String[ITEMS];
+        String COLLIDING_STRINGS[] = new String[ITEMS];
+
+        for (int i = 0; i < ITEMS; i++) {
+            UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
+            COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
+            UNIQUE_STRINGS[i] = unhash(i);
+            COLLIDING_STRINGS[i] = (0 == i % 2)
+                    ? UNIQUE_STRINGS[i / 2]
+                    : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
+        }
+
+     KEYS = new Object[][] {
+            new Object[]{"Unique Objects", UNIQUE_OBJECTS},
+            new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
+            new Object[]{"Unique Strings", UNIQUE_STRINGS},
+            new Object[]{"Colliding Strings", COLLIDING_STRINGS}
+        };
+    }
+
+    /**
+     * Returns a string with a hash equal to the argument.
+     *
+     * @return string with a hash equal to the argument.
+     */
+    public static String unhash(int target) {
+        StringBuilder answer = new StringBuilder();
+        if (target < 0) {
+            // String with hash of Integer.MIN_VALUE, 0x80000000
+            answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
+
+            if (target == Integer.MIN_VALUE) {
+                return answer.toString();
+            }
+            // Find target without sign bit set
+            target = target & Integer.MAX_VALUE;
+        }
+
+        unhash0(answer, target);
+        return answer.toString();
+    }
+
+    private static void unhash0(StringBuilder partial, int target) {
+        int div = target / 31;
+        int rem = target % 31;
+
+        if (div <= Character.MAX_VALUE) {
+            if (div != 0) {
+                partial.append((char) div);
+            }
+            partial.append((char) rem);
+        } else {
+            unhash0(partial, div);
+            partial.append((char) rem);
+        }
+    }
+
+    private static void realMain(String[] args) throws Throwable {
+        for (Object[] keys_desc : KEYS) {
+            Map<Object, Boolean>[] MAPS = (Map<Object, Boolean>[]) new Map[]{
+                        new Hashtable<>(),
+                        new HashMap<>(),
+                        new IdentityHashMap<>(),
+                        new LinkedHashMap<>(),
+                        new ConcurrentHashMap<>(),
+                        new WeakHashMap<>(),
+                        new TreeMap<>(),
+                        new ConcurrentSkipListMap<>()
+                    };
+
+            for (Map<Object, Boolean> map : MAPS) {
+                String desc = (String) keys_desc[0];
+                Object[] keys = (Object[]) keys_desc[1];
+                testMap(map, desc, keys);
+            }
+        }
+    }
+
+    private static <T> void testMap(Map<T, Boolean> map, String keys_desc, T[] keys) {
+        System.err.println(map.getClass() + " : " + keys_desc);
+        testInsertion(map, keys_desc, keys);
+
+        if (keys[0] instanceof HashableInteger) {
+            testIntegerIteration((Map<HashableInteger, Boolean>) map, (HashableInteger[]) keys);
+        } else {
+            testStringIteration((Map<String, Boolean>) map, (String[]) keys);
+        }
+
+        testContainsKey(map, keys_desc, keys);
+
+        testRemove(map, keys_desc, keys);
+
+        check(map.isEmpty());
+    }
+
+    private static <T> void testInsertion(Map<T, Boolean> map, String keys_desc, T[] keys) {
+        check("map empty", (map.size() == 0) && map.isEmpty());
+
+        for (int i = 0; i < keys.length; i++) {
+            check(String.format("insertion: map expected size m%d != i%d", map.size(), i),
+                    map.size() == i);
+            check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], true));
+            check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
+        }
+
+        check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+                map.size() == keys.length);
+    }
+
+    private static void testIntegerIteration(Map<HashableInteger, Boolean> map, HashableInteger[] keys) {
+        check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+                map.size() == keys.length);
+
+        BitSet all = new BitSet(keys.length);
+        for (Map.Entry<HashableInteger, Boolean> each : map.entrySet()) {
+            check("Iteration: key already seen", !all.get(each.getKey().value));
+            all.set(each.getKey().value);
+        }
+
+        all.flip(0, keys.length);
+        check("Iteration: some keys not visited", all.isEmpty());
+
+        for (HashableInteger each : map.keySet()) {
+            check("Iteration: key already seen", !all.get(each.value));
+            all.set(each.value);
+        }
+
+        all.flip(0, keys.length);
+        check("Iteration: some keys not visited", all.isEmpty());
+
+        int count = 0;
+        for (Boolean each : map.values()) {
+            count++;
+        }
+
+        check(String.format("Iteration: value count matches size m%d != c%d", map.size(), count),
+                map.size() == count);
+    }
+
+    private static void testStringIteration(Map<String, Boolean> map, String[] keys) {
+        check(String.format("map expected size m%d != k%d", map.size(), keys.length),
+                map.size() == keys.length);
+
+        BitSet all = new BitSet(keys.length);
+        for (Map.Entry<String, Boolean> each : map.entrySet()) {
+            String key = each.getKey();
+            boolean longKey = key.length() > 5;
+            int index = key.hashCode() + (longKey ? keys.length / 2 : 0);
+            check("key already seen", !all.get(index));
+            all.set(index);
+        }
+
+        all.flip(0, keys.length);
+        check("some keys not visited", all.isEmpty());
+
+        for (String each : map.keySet()) {
+            boolean longKey = each.length() > 5;
+            int index = each.hashCode() + (longKey ? keys.length / 2 : 0);
+            check("key already seen", !all.get(index));
+            all.set(index);
+        }
+
+        all.flip(0, keys.length);
+        check("some keys not visited", all.isEmpty());
+
+        int count = 0;
+        for (Boolean each : map.values()) {
+            count++;
+        }
+
+        check(String.format("value count matches size m%d != k%d", map.size(), keys.length),
+                map.size() == keys.length);
+    }
+
+    private static <T> void testContainsKey(Map<T, Boolean> map, String keys_desc, T[] keys) {
+        for (int i = 0; i < keys.length; i++) {
+            T each = keys[i];
+            check("containsKey: " + keys_desc + "[" + i + "]" + each, map.containsKey(each));
+        }
+    }
+
+    private static <T> void testRemove(Map<T, Boolean> map, String keys_desc, T[] keys) {
+        check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
+                map.size() == keys.length);
+
+        for (int i = 0; i < keys.length; i++) {
+            T each = keys[i];
+            check("remove: " + keys_desc + "[" + i + "]" + each, null != map.remove(each));
+        }
+
+        check(String.format("remove: map empty. size=%d", map.size()),
+                (map.size() == 0) && map.isEmpty());
+    }
+    //--------------------- Infrastructure ---------------------------
+    static volatile int passed = 0, failed = 0;
+
+    static void pass() {
+        passed++;
+    }
+
+    static void fail() {
+        failed++;
+        (new Error("Failure")).printStackTrace(System.err);
+    }
+
+    static void fail(String msg) {
+        failed++;
+        (new Error("Failure: " + msg)).printStackTrace(System.err);
+    }
+
+    static void abort() {
+        fail();
+        System.exit(1);
+    }
+
+    static void abort(String msg) {
+        fail(msg);
+        System.exit(1);
+    }
+
+    static void unexpected(String msg, Throwable t) {
+        System.err.println("Unexpected: " + msg);
+        unexpected(t);
+    }
+
+    static void unexpected(Throwable t) {
+        failed++;
+        t.printStackTrace(System.err);
+    }
+
+    static void check(boolean cond) {
+        if (cond) {
+            pass();
+        } else {
+            fail();
+        }
+    }
+
+    static void check(String desc, boolean cond) {
+        if (cond) {
+            pass();
+        } else {
+            fail(desc);
+        }
+    }
+
+    static void equal(Object x, Object y) {
+        if (Objects.equals(x, y)) {
+            pass();
+        } else {
+            fail(x + " not equal to " + y);
+        }
+    }
+
+    public static void main(String[] args) throws Throwable {
+        Thread.currentThread().setName("Collisions");
+//        Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
+        try {
+            realMain(args);
+        } catch (Throwable t) {
+            unexpected(t);
+        }
+
+        System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
+        if (failed > 0) {
+            throw new Error("Some tests failed");
+        }
+    }
+}
--- a/test/java/util/Map/Get.java	Wed May 30 14:30:34 2012 -0700
+++ b/test/java/util/Map/Get.java	Wed May 30 23:36:32 2012 -0700
@@ -50,16 +50,16 @@
                             Character key, Boolean value,
                             Boolean oldValue) {
         if (oldValue != null) {
-            check(m.containsValue(oldValue));
-            check(m.values().contains(oldValue));
+            check("containsValue(oldValue)", m.containsValue(oldValue));
+            check("values.contains(oldValue)", m.values().contains(oldValue));
         }
         equal(m.put(key, value), oldValue);
         equal(m.get(key), value);
-        check(m.containsKey(key));
-        check(m.keySet().contains(key));
-        check(m.containsValue(value));
-        check(m.values().contains(value));
-        check(! m.isEmpty());
+        check("containsKey", m.containsKey(key));
+        check("keySet.contains", m.keySet().contains(key));
+        check("containsValue", m.containsValue(value));
+        check("values.contains",  m.values().contains(value));
+        check("!isEmpty", ! m.isEmpty());
     }
 
     private static void testMap(Map<Character,Boolean> m) {
@@ -71,7 +71,7 @@
                                         m instanceof Hashtable));
         boolean usesIdentity = m instanceof IdentityHashMap;
 
-        System.out.println(m.getClass());
+        System.err.println(m.getClass());
         put(m, 'A', true,  null);
         put(m, 'A', false, true);       // Guaranteed identical by JLS
         put(m, 'B', true,  null);
@@ -81,15 +81,15 @@
                 put(m, null, true,  null);
                 put(m, null, false, true);
             }
-            catch (Throwable t) { unexpected(t); }
+            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
         } else {
-            try { m.get(null); fail(); }
+            try { m.get(null); fail(m.getClass().getName() + " did not reject null key"); }
             catch (NullPointerException e) {}
-            catch (Throwable t) { unexpected(t); }
+            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
 
-            try { m.put(null, true); fail(); }
+            try { m.put(null, true); fail(m.getClass().getName() + " did not reject null key"); }
             catch (NullPointerException e) {}
-            catch (Throwable t) { unexpected(t); }
+            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
         }
         if (permitsNullValues) {
             try {
@@ -97,33 +97,35 @@
                 put(m, 'C', true, null);
                 put(m, 'C', null, true);
             }
-            catch (Throwable t) { unexpected(t); }
+            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
         } else {
-            try { m.put('A', null); fail(); }
+            try { m.put('A', null); fail(m.getClass().getName() + " did not reject null key"); }
             catch (NullPointerException e) {}
-            catch (Throwable t) { unexpected(t); }
+            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
 
-            try { m.put('C', null); fail(); }
+            try { m.put('C', null); fail(m.getClass().getName() + " did not reject null key"); }
             catch (NullPointerException e) {}
-            catch (Throwable t) { unexpected(t); }
+            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
         }
     }
 
     //--------------------- Infrastructure ---------------------------
     static volatile int passed = 0, failed = 0;
     static void pass() { passed++; }
-    static void fail() { failed++; Thread.dumpStack(); }
-    static void fail(String msg) { System.out.println(msg); fail(); }
-    static void unexpected(Throwable t) { failed++; t.printStackTrace(); }
+    static void fail() { failed++; (new Error("Failure")).printStackTrace(System.err); }
+    static void fail(String msg) { failed++; (new Error("Failure: " + msg)).printStackTrace(System.err); }
+    static void unexpected(String msg, Throwable t) { System.err.println("Unexpected: " + msg); unexpected(t); }
+    static void unexpected(Throwable t) { failed++; t.printStackTrace(System.err); }
     static void check(boolean cond) { if (cond) pass(); else fail(); }
+    static void check(String desc, boolean cond) { if (cond) pass(); else fail(desc); }
     static void equal(Object x, Object y) {
-        if (x == null ? y == null : x.equals(y)) pass();
-        else {System.out.println(x + " not equal to " + y); fail(); }}
+        if(Objects.equals(x,y)) pass(); else fail(x + " not equal to " + y);
+    }
 
     public static void main(String[] args) throws Throwable {
         try { realMain(args); } catch (Throwable t) { unexpected(t); }
 
         System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
-        if (failed > 0) throw new Exception("Some tests failed");
+        if (failed > 0) throw new Error("Some tests failed");
     }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/sun/misc/Hashing.java	Wed May 30 23:36:32 2012 -0700
@@ -0,0 +1,127 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test @summary Ensure that Murmur3 hash performs according to specification.
+ * @compile -XDignore.symbol.file Hashing.java
+ */
+public class Hashing {
+
+    static final byte ONE_BYTE[] = {
+        (byte) 0x80};
+    static final byte TWO_BYTE[] = {
+        (byte) 0x80, (byte) 0x81};
+    static final char ONE_CHAR[] = {
+        (char) 0x8180};
+    static final byte THREE_BYTE[] = {
+        (byte) 0x80, (byte) 0x81, (byte) 0x82};
+    static final byte FOUR_BYTE[] = {
+        (byte) 0x80, (byte) 0x81, (byte) 0x82, (byte) 0x83};
+    static final char TWO_CHAR[] = {
+        (char) 0x8180, (char) 0x8382};
+    static final int ONE_INT[] = {
+        0x83828180};
+    static final byte SIX_BYTE[] = {
+        (byte) 0x80, (byte) 0x81, (byte) 0x82,
+        (byte) 0x83, (byte) 0x84, (byte) 0x85};
+    static final char THREE_CHAR[] = {
+        (char) 0x8180, (char) 0x8382, (char) 0x8584};
+    static final byte EIGHT_BYTE[] = {
+        (byte) 0x80, (byte) 0x81, (byte) 0x82,
+        (byte) 0x83, (byte) 0x84, (byte) 0x85,
+        (byte) 0x86, (byte) 0x87};
+    static final char FOUR_CHAR[] = {
+        (char) 0x8180, (char) 0x8382,
+        (char) 0x8584, (char) 0x8786};
+    static final int TWO_INT[] = {
+        0x83828180, 0x87868584};
+    // per  http://code.google.com/p/smhasher/source/browse/trunk/main.cpp, line:72
+    static final int MURMUR3_32_X86_CHECK_VALUE = 0xB0F57EE3;
+
+    public static void testMurmur3_32_ByteArray() {
+        System.out.println("testMurmur3_32_ByteArray");
+
+        byte[] vector = new byte[256];
+        byte[] hashes = new byte[4 * 256];
+
+        for (int i = 0; i < 256; i++) {
+            vector[i] = (byte) i;
+        }
+
+        // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255}
+        for (int i = 0; i < 256; i++) {
+            int hash = sun.misc.Hashing.murmur3_32(256 - i, vector, 0, i);
+
+            hashes[i * 4] = (byte) hash;
+            hashes[i * 4 + 1] = (byte) (hash >>> 8);
+            hashes[i * 4 + 2] = (byte) (hash >>> 16);
+            hashes[i * 4 + 3] = (byte) (hash >>> 24);
+        }
+
+        // hash to get final result.
+        int final_hash = sun.misc.Hashing.murmur3_32(0, hashes);
+
+        if (MURMUR3_32_X86_CHECK_VALUE != final_hash) {
+            throw new RuntimeException(
+                    String.format("Calculated hash result not as expected. Expected %08X got %08X",
+                    MURMUR3_32_X86_CHECK_VALUE,
+                    final_hash));
+        }
+    }
+
+    public static void testEquivalentHashes() {
+        int bytes, chars, ints;
+
+        System.out.println("testEquivalentHashes");
+
+        bytes = sun.misc.Hashing.murmur3_32(TWO_BYTE);
+        chars = sun.misc.Hashing.murmur3_32(ONE_CHAR);
+        if (bytes != chars) {
+            throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x", bytes, chars));
+        }
+
+        bytes = sun.misc.Hashing.murmur3_32(FOUR_BYTE);
+        chars = sun.misc.Hashing.murmur3_32(TWO_CHAR);
+        ints = sun.misc.Hashing.murmur3_32(ONE_INT);
+        if ((bytes != chars) || (bytes != ints)) {
+            throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x != i:%08x", bytes, chars, ints));
+        }
+        bytes = sun.misc.Hashing.murmur3_32(SIX_BYTE);
+        chars = sun.misc.Hashing.murmur3_32(THREE_CHAR);
+        if (bytes != chars) {
+            throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x", bytes, chars));
+        }
+
+        bytes = sun.misc.Hashing.murmur3_32(EIGHT_BYTE);
+        chars = sun.misc.Hashing.murmur3_32(FOUR_CHAR);
+        ints = sun.misc.Hashing.murmur3_32(TWO_INT);
+        if ((bytes != chars) || (bytes != ints)) {
+            throw new RuntimeException(String.format("Hashes did not match. b:%08x != c:%08x != i:%08x", bytes, chars, ints));
+        }
+    }
+
+    public static void main(String[] args) {
+        testMurmur3_32_ByteArray();
+        testEquivalentHashes();
+    }
+}