src/share/classes/java/util/WeakHashMap.java
Print this page
rev 5380 : 7126277: Alternative hashing implementation
@@ -182,10 +182,16 @@
*
* @see ConcurrentModificationException
*/
int modCount;
+ /**
+ * 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];
}
@@ -230,13 +236,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 +250,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 +286,42 @@
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 = hashMask;
+ if (0 == hashMask) {
+ if (k instanceof Hashable32) {
+ h ^= ((Hashable32) k).hash32();
+ } 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 +406,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 +436,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 +459,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())) {
@@ -564,11 +601,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 +632,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 +714,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.
*/