src/share/classes/java/util/WeakHashMap.java
Print this page
@@ -182,10 +182,70 @@
*
* @see ConcurrentModificationException
*/
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 random mask value that is used for hashcode values associated with this
+ * instance to make hash collisions harder to find.
+ */
+ transient final int hashMask = sun.misc.Hashing.makeHashMask(this);
+
@SuppressWarnings("unchecked")
private Entry<K,V>[] newTable(int n) {
return (Entry<K,V>[]) new Entry[n];
}
@@ -212,10 +272,12 @@
while (capacity < initialCapacity)
capacity <<= 1;
table = newTable(capacity);
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
+ useAltHashing = sun.misc.VM.isBooted() &&
+ (capacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
}
/**
* Constructs a new, empty <tt>WeakHashMap</tt> with the given initial
* capacity and the default load factor (0.75).
@@ -230,13 +292,11 @@
/**
* Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
* 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);
}
/**
* Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
* specified map. The <tt>WeakHashMap</tt> is created with the default
@@ -246,11 +306,12 @@
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
* @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);
}
// internal utilities
@@ -281,10 +342,43 @@
private static boolean eq(Object x, Object y) {
return x == y || x.equals(y);
}
/**
+ * 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.
+ */
+ int hash(Object k) {
+ if (null == k) {
+ return 0;
+ }
+
+ int h;
+ if (useAltHashing) {
+ h = hashMask;
+ 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);
+ h ^= (h >>> 7) ^ (h >>> 4);
+
+ return h;
+ }
+
+ /**
* Returns index for hash code h.
*/
private static int indexFor(int h, int length) {
return h & (length-1);
}
@@ -369,11 +463,11 @@
*
* @see #put(Object, Object)
*/
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];
while (e != null) {
if (e.hash == h && eq(k, e.get()))
@@ -399,11 +493,11 @@
* Returns the entry associated with the specified key in this map.
* Returns null if the map contains no mapping for this key.
*/
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];
while (e != null && !(e.hash == h && eq(k, e.get())))
e = e.next;
@@ -422,11 +516,11 @@
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
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);
for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
if (h == e.hash && eq(k, e.get())) {
@@ -466,11 +560,15 @@
threshold = Integer.MAX_VALUE;
return;
}
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;
/*
* If ignoring null elements and processing ref queue caused massive
* shrinkage, then restore old table. This should be rare, but avoids
@@ -478,17 +576,17 @@
*/
if (size >= threshold / 2) {
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;
while (e != null) {
Entry<K,V> next = e.next;
@@ -496,10 +594,13 @@
if (key == null) {
e.next = null; // Help GC
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;
}
e = next;
@@ -564,11 +665,11 @@
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>
*/
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];
Entry<K,V> e = prev;
@@ -595,11 +696,11 @@
if (!(o instanceof Map.Entry))
return false;
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;
while (e != null) {
@@ -677,11 +778,11 @@
* The entries in this hash table extend WeakReference, using its main ref
* field as the key.
*/
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;
/**
* Creates new entry.
*/