src/share/classes/java/util/WeakHashMap.java
Print this page
rev 5382 : 7126277: Alternative hashing implementation
*** 182,191 ****
--- 182,197 ----
*
* @see ConcurrentModificationException
*/
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];
}
*** 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
--- 236,246 ----
/**
* 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
--- 250,261 ----
* @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 ****
--- 286,321 ----
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 = hashSeed;
+ if (k instanceof String) {
+ h ^= ((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) {
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()))
--- 400,410 ----
*
* @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;
--- 430,440 ----
* 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())) {
--- 453,463 ----
* (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())) {
*** 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;
--- 595,605 ----
* @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) {
--- 626,636 ----
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) {