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
--- a/jdk/make/java/java/FILES_java.gmk Thu May 17 10:06:19 2012 -0700
+++ b/jdk/make/java/java/FILES_java.gmk Wed May 30 22:18:37 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/jdk/src/share/classes/java/lang/String.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/src/share/classes/java/lang/String.java Wed May 30 22:18:37 2012 -0700
@@ -25,7 +25,6 @@
package java.lang;
-import java.io.ObjectStreamClass;
import java.io.ObjectStreamField;
import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
@@ -3021,4 +3020,100 @@
*/
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 hashing algorithm result
+ */
+ private transient int hash32 = 0;
+
+ /**
+ * Return a 32-bit hash code value for this object.
+ * <p>
+ * The general contract of {@code hash32} is:
+ * <ul>
+ * <li>Whenever it is invoked on the same object more than once during
+ * an execution of a Java application, the {@code hash32} method
+ * must consistently return the same integer, provided no information
+ * used in {@code equals} comparisons on the object is modified.
+ * This integer need not remain consistent from one execution of an
+ * application to another execution of the same application.
+ * <li>If two objects are equal according to the {@code equals(Object)}
+ * method, then calling the {@code hash32} method on each of
+ * the two objects must produce the same integer result.
+ * <li>It is <em>not</em> required that if two objects are unequal
+ * according to the {@link java.lang.Object#equals(java.lang.Object)}
+ * method, then calling the {@code hash32} method on each of the
+ * two objects must produce distinct integer results. However, the
+ * programmer should be aware that producing distinct integer results
+ * for unequal objects may improve the performance of hash tables.
+ * </ul>
+ * <p/>
+ * The hash value will never be zero.
+ *
+ * @return a hash code value for this object.
+ * @see java.lang.Object#equals(java.lang.Object)
+ */
+ public int hash32() {
+ int h = hash32;
+ if (0 == h) {
+ // harmless data race on hash32 here.
+ h = sun.misc.Hashing.murmur3_32(HASHING_SEED, value, 0, value.length);
+
+ // ensure result is not zero to avoid recalcing
+ h = (0 != h) ? h : 1;
+
+ hash32 = h;
+ }
+
+ return h;
+ }
+
}
--- a/jdk/src/share/classes/java/util/HashMap.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/src/share/classes/java/util/HashMap.java Wed May 30 22:18:37 2012 -0700
@@ -175,6 +175,35 @@
*/
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.
@@ -200,7 +229,7 @@
capacity <<= 1;
this.loadFactor = loadFactor;
- threshold = (int)(capacity * loadFactor);
+ threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
init();
}
@@ -221,10 +250,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 +281,20 @@
}
/**
- * 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 ((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).
@@ -313,32 +346,9 @@
*/
@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();
}
/**
@@ -360,7 +370,7 @@
*/
@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) {
@@ -388,7 +398,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);
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)table[i];
@@ -433,7 +443,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);
/**
@@ -484,7 +494,7 @@
Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
transfer(newTable);
table = newTable;
- threshold = (int)(newCapacity * loadFactor);
+ threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
@@ -494,19 +504,17 @@
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 {
- Entry<K,V> next = e.next;
- int i = indexFor(e.hash, newCapacity);
- e.next = (Entry<K,V>)newTable[i];
- newTable[i] = e;
- e = next;
- } while (e != null);
+ 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];
+ newTable[i] = e;
+ e = next;
}
}
+ Arrays.fill(table, null);
}
/**
@@ -566,7 +574,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);
@SuppressWarnings("unchecked")
Entry<K,V> prev = (Entry<K,V>)table[i];
@@ -594,7 +602,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))
@@ -773,11 +782,13 @@
* 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);
}
/**
@@ -841,7 +852,6 @@
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
-
}
private final class ValueIterator extends HashIterator<V> {
@@ -1021,9 +1031,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());
}
@@ -1033,26 +1042,50 @@
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")
--- a/jdk/src/share/classes/java/util/Hashtable.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/src/share/classes/java/util/Hashtable.java Wed May 30 22:18:37 2012 -0700
@@ -163,6 +163,52 @@
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;
+ private static class Holder {
+ // Unsafe mechanics
+ /**
+ *
+ */
+ static final sun.misc.Unsafe UNSAFE;
+
+ /**
+ * Offset of "final" hashSeed field we must set in
+ * readObject() method.
+ */
+ static final long HASHSEED_OFFSET;
+
+ static {
+ try {
+ UNSAFE = sun.misc.Unsafe.getUnsafe();
+ HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+ Hashtable.class.getDeclaredField("hashSeed"));
+ } catch (NoSuchFieldException | SecurityException e) {
+ throw new InternalError("Failed to record hashSeed offset", e);
+ }
+ }
+ }
+
+ /**
+ * A randomizing value associated with this instance that is applied to
+ * hash code of keys to make hash collisions harder to find.
+ */
+ transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+
+ private int hash(Object k) {
+ int h = hashSeed;
+
+ if (k instanceof String) {
+ return ((String)k).hash32();
+ } else {
+ h ^= k.hashCode();
+
+ // This function ensures that hashCodes that differ only by
+ // constant multiples at each bit position have a bounded
+ // number of collisions (approximately 8 at default load factor).
+ h ^= (h >>> 20) ^ (h >>> 12);
+ return h ^ (h >>> 7) ^ (h >>> 4);
+ }
+ }
+
/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
@@ -183,7 +229,7 @@
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
- threshold = (int)(initialCapacity * loadFactor);
+ threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
/**
@@ -327,7 +373,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<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@@ -355,7 +401,7 @@
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@@ -396,7 +442,7 @@
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
- threshold = (int)(newCapacity * loadFactor);
+ threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
@@ -436,7 +482,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;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
@@ -454,6 +500,7 @@
rehash();
tab = table;
+ hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
@@ -476,7 +523,7 @@
*/
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
- int hash = key.hashCode();
+ int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
@@ -685,7 +732,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)
@@ -700,7 +747,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;
@SuppressWarnings("unchecked")
@@ -835,9 +882,13 @@
loadFactor = -loadFactor; // Mark hashCode computation in progress
Entry<?,?>[] tab = table;
- for (int i = 0; i < tab.length; i++)
- for (Entry<?,?> e = tab[i]; e != null; e = e.next)
- h += e.key.hashCode() ^ e.value.hashCode();
+ for (Entry<?,?> entry : tab) {
+ while (entry != null) {
+ h += entry.hashCode();
+ entry = entry.next;
+ }
+ }
+
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
@@ -894,6 +945,10 @@
// Read in the length, threshold, and loadfactor
s.defaultReadObject();
+ // set hashMask
+ Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
+ sun.misc.Hashing.randomHashSeed(this));
+
// Read the original length of the array and number of elements
int origlength = s.readInt();
int elements = s.readInt();
@@ -907,7 +962,8 @@
length--;
if (origlength > 0 && length > origlength)
length = origlength;
- Entry<?,?>[] table = new Entry<?,?>[length];
+ table = new Entry<?,?>[length];
+ threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
count = 0;
// Read the number of elements and then all the key/value objects
@@ -919,7 +975,6 @@
// synch could be eliminated for performance
reconstitutionPut(table, key, value);
}
- this.table = table;
}
/**
@@ -941,7 +996,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<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@@ -956,17 +1011,17 @@
}
/**
- * Hashtable collision list.
+ * Hashtable bucket collision list entry
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
- int hash;
+ final int hash;
K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
- this.key = key;
+ this.key = key;
this.value = value;
this.next = next;
}
--- a/jdk/src/share/classes/java/util/LinkedHashMap.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/src/share/classes/java/util/LinkedHashMap.java Wed May 30 22:18:37 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,6 +247,7 @@
* by superclass resize. It is overridden for performance, as it is
* faster to iterate using our linked list.
*/
+ @Override
@SuppressWarnings("unchecked")
void transfer(HashMap.Entry[] newTable) {
int newCapacity = newTable.length;
@@ -421,15 +423,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/jdk/src/share/classes/java/util/WeakHashMap.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/src/share/classes/java/util/WeakHashMap.java Wed May 30 22:18:37 2012 -0700
@@ -184,6 +184,12 @@
*/
int modCount;
+ /**
+ * 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];
@@ -232,9 +238,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 +252,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 +288,28 @@
}
/**
+ * 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 = hashSeed;
+ if (k instanceof String) {
+ return ((String) k).hash32();
+ } else {
+ h ^= k.hashCode();
+ }
+
+ // This function ensures that hashCodes that differ only by
+ // constant multiples at each bit position have a bounded
+ // number of collisions (approximately 8 at default load factor).
+ h ^= (h >>> 20) ^ (h >>> 12);
+ return h ^ (h >>> 7) ^ (h >>> 4);
+ }
+
+ /**
* Returns index for hash code h.
*/
private static int indexFor(int h, int length) {
@@ -371,7 +398,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 +428,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 +451,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);
@@ -566,7 +593,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 +624,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;
--- a/jdk/src/share/classes/java/util/concurrent/ConcurrentHashMap.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/src/share/classes/java/util/concurrent/ConcurrentHashMap.java Wed May 30 22:18:37 2012 -0700
@@ -175,6 +175,12 @@
/* ---------------- 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.
*/
@@ -262,7 +268,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 (k instanceof String) {
+ return ((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;
@@ -917,7 +931,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) {
@@ -945,7 +959,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) {
@@ -1054,7 +1068,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
@@ -1074,7 +1088,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)
@@ -1104,7 +1118,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);
}
@@ -1115,7 +1129,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;
@@ -1127,7 +1141,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);
@@ -1142,7 +1156,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);
@@ -1473,6 +1487,10 @@
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;
@@ -1500,6 +1518,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;
@@ -1511,6 +1530,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/jdk/src/share/classes/sun/misc/Hashing.java Wed May 30 22:18:37 2012 -0700
@@ -0,0 +1,251 @@
+/*
+ * 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());
+ }
+
+ 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/jdk/test/java/util/Collection/BiggernYours.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/test/java/util/Collection/BiggernYours.java Wed May 30 22:18:37 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/jdk/test/java/util/Hashtable/HashCode.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/test/java/util/Hashtable/HashCode.java Wed May 30 22:18:37 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/jdk/test/java/util/Hashtable/SimpleSerialization.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/test/java/util/Hashtable/SimpleSerialization.java Wed May 30 22:18:37 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/jdk/test/java/util/Map/Collisions.java Wed May 30 22:18:37 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/jdk/test/java/util/Map/Get.java Thu May 17 10:06:19 2012 -0700
+++ b/jdk/test/java/util/Map/Get.java Wed May 30 22:18:37 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/jdk/test/sun/misc/Hashing.java Wed May 30 22:18:37 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();
+ }
+}