src/share/classes/java/util/WeakHashMap.java
Print this page
rev 5028 : 7126277: alternative hashing
*** 182,191 ****
--- 182,251 ----
*
* @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 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];
}
*** 212,221 ****
--- 272,283 ----
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,242 ****
/**
* 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);
}
/**
* Constructs a new <tt>WeakHashMap</tt> with the same mappings as the
* specified map. The <tt>WeakHashMap</tt> is created with the default
--- 292,302 ----
/**
* Constructs a new, empty <tt>WeakHashMap</tt> with the default initial
* capacity (16) and load factor (0.75).
*/
public WeakHashMap() {
! 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,256 ****
* @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),
DEFAULT_LOAD_FACTOR);
putAll(m);
}
// internal utilities
--- 306,317 ----
* @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,
! DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR);
putAll(m);
}
// internal utilities
*** 281,290 ****
--- 342,382 ----
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 = 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) {
return h & (length-1);
}
*** 369,379 ****
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Object k = maskNull(key);
! int h = HashMap.hash(k.hashCode());
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()))
--- 461,471 ----
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Object k = maskNull(key);
! 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,409 ****
* 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());
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;
--- 491,501 ----
* 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 = 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,432 ****
* (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());
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())) {
--- 514,524 ----
* (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 = 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,476 ****
threshold = Integer.MAX_VALUE;
return;
}
Entry<K,V>[] newTable = newTable(newCapacity);
! transfer(oldTable, newTable);
table = newTable;
/*
* If ignoring null elements and processing ref queue caused massive
* shrinkage, then restore old table. This should be rare, but avoids
--- 558,572 ----
threshold = Integer.MAX_VALUE;
return;
}
Entry<K,V>[] newTable = newTable(newCapacity);
! 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,494 ****
*/
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
expungeStaleEntries();
! transfer(newTable, oldTable);
table = oldTable;
}
}
/** Transfers all entries from src to dest tables */
! private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest) {
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;
--- 574,590 ----
*/
if (size >= threshold / 2) {
threshold = (int)(newCapacity * loadFactor);
} else {
expungeStaleEntries();
! 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, 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,505 ****
--- 592,604 ----
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,574 ****
* @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());
Entry<K,V>[] tab = getTable();
int i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
--- 663,673 ----
* @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 = 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,605 ****
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 i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
while (e != null) {
--- 694,704 ----
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 = hash(k);
int i = indexFor(h, tab.length);
Entry<K,V> prev = tab[i];
Entry<K,V> e = prev;
while (e != null) {
*** 677,687 ****
* 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;
Entry<K,V> next;
/**
* Creates new entry.
*/
--- 776,786 ----
* 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;
! int hash;
Entry<K,V> next;
/**
* Creates new entry.
*/