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) {