src/share/classes/java/util/HashMap.java
Print this page
rev 5028 : 7126277: alternative hashing
*** 144,154 ****
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
! transient Entry[] table;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
--- 144,154 ----
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
! transient Entry<K,V>[] table;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
*** 174,183 ****
--- 174,263 ----
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient 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}. 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 {
+
+ // Unsafe mechanics
+ /**
+ *
+ */
+ static final sun.misc.Unsafe UNSAFE;
+
+ /**
+ * Offset of "final" hashmask field we must set in
+ * readObject() method.
+ */
+ static final long HASHSEED_OFFSET;
+
+ /**
+ * 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;
+
+ try {
+ UNSAFE = sun.misc.Unsafe.getUnsafe();
+ HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
+ HashMap.class.getDeclaredField("hashSeed"));
+ } catch (NoSuchFieldException | SecurityException e) {
+ throw new Error("Failed to record hashSeed offset", e);
+ }
+ }
+ }
+
+ /**
+ * 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);
+
+ /**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
*** 198,209 ****
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
! threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
--- 278,291 ----
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
! threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
+ useAltHashing = sun.misc.VM.isBooted() &&
+ (capacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
*** 219,232 ****
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
! this.loadFactor = DEFAULT_LOAD_FACTOR;
! threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
! table = new Entry[DEFAULT_INITIAL_CAPACITY];
! init();
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
--- 301,311 ----
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
! this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
*** 253,269 ****
*/
void init() {
}
/**
! * Applies a supplemental hash function to a given hashCode, 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.
*/
! static int hash(int h) {
// 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);
--- 332,358 ----
*/
void init() {
}
/**
! * 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.
*/
! final int hash(Object k) {
! int h = 0;
! if (useAltHashing) {
! if (k instanceof String) {
! return sun.misc.Hashing.stringHash32((String) k);
! }
! h = hashSeed;
! }
!
! 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);
*** 312,330 ****
* @see #put(Object, Object)
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
! int hash = hash(key.hashCode());
! for (Entry<K,V> e = table[indexFor(hash, table.length)];
! e != null;
! e = e.next) {
! Object k;
! if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
! return e.value;
! }
! return null;
}
/**
* Offloaded version of get() to look up null keys. Null keys map
* to index 0. This null case is split out into separate methods
--- 401,413 ----
* @see #put(Object, Object)
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
! Entry<K,V> entry = getEntry(key);
!
! return null == entry ? null : entry.getValue();
}
/**
* Offloaded version of get() to look up null keys. Null keys map
* to index 0. This null case is split out into separate methods
*** 356,366 ****
* Returns the entry associated with the specified key in the
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
final Entry<K,V> getEntry(Object key) {
! int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
--- 439,449 ----
* Returns the entry associated with the specified key in the
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
final Entry<K,V> getEntry(Object key) {
! int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
*** 384,394 ****
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
! int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
--- 467,477 ----
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
! int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
*** 425,435 ****
* pseudoconstructors (clone, readObject). It does not resize the table,
* check for comodification, etc. It calls createEntry rather than
* addEntry.
*/
private void putForCreate(K key, V value) {
! int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
--- 508,518 ----
* pseudoconstructors (clone, readObject). It does not resize the table,
* check for comodification, etc. It calls createEntry rather than
* addEntry.
*/
private void putForCreate(K key, V value) {
! int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
*** 473,504 ****
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
! transfer(newTable);
table = newTable;
! threshold = (int)(newCapacity * loadFactor);
}
/**
* Transfers all entries from current table to newTable.
*/
! void transfer(Entry[] newTable) {
! Entry[] src = table;
int newCapacity = newTable.length;
! for (int j = 0; j < src.length; j++) {
! Entry<K,V> e = src[j];
! if (e != null) {
! src[j] = null;
! do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
- } while (e != null);
}
}
}
/**
--- 556,589 ----
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
! boolean oldAltHashing = useAltHashing;
! useAltHashing |= sun.misc.VM.isBooted() &&
! (newCapacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
! boolean rehash = oldAltHashing ^ useAltHashing;
! transfer(newTable, rehash);
table = newTable;
! threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* Transfers all entries from current table to newTable.
*/
! void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
! for (Entry<K,V> e : table) {
! while(null != e) {
Entry<K,V> next = e.next;
+ if(rehash) {
+ e.hash = null == e.key ? 0 : hash(e.key);
+ }
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
/**
*** 556,566 ****
* Removes and returns the entry associated with the specified key
* in the HashMap. Returns null if the HashMap contains no mapping
* for this key.
*/
final Entry<K,V> removeEntryForKey(Object key) {
! int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
--- 641,651 ----
* Removes and returns the entry associated with the specified key
* in the HashMap. Returns null if the HashMap contains no mapping
* for this key.
*/
final Entry<K,V> removeEntryForKey(Object key) {
! int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
*** 583,593 ****
return e;
}
/**
! * Special version of remove for EntrySet.
*/
final Entry<K,V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
return null;
--- 668,679 ----
return e;
}
/**
! * Special version of remove for EntrySet using {@code Map.Entry.equals()}
! * for matching.
*/
final Entry<K,V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
return null;
*** 686,696 ****
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
! final int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
--- 772,782 ----
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
! int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
*** 760,773 ****
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
! Entry<K,V> e = table[bucketIndex];
! table[bucketIndex] = new Entry<>(hash, key, value, e);
! if (size++ >= threshold)
resize(2 * table.length);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
--- 846,862 ----
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
! if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
+ hash = hash(key);
+ bucketIndex = indexFor(hash, table.length);
+ }
+
+ createEntry(hash, key, value, bucketIndex);
}
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
*** 825,835 ****
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
-
}
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
--- 914,923 ----
*** 1005,1046 ****
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
! if (i != null) {
! while (i.hasNext()) {
! Map.Entry<K,V> e = i.next();
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
/**
! * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
! // Read in the threshold, loadfactor, and any hidden stuff
s.defaultReadObject();
// Read in number of buckets and allocate the bucket array;
! int numBuckets = s.readInt();
! table = new Entry[numBuckets];
! init(); // Give subclass a chance to do its thing.
! // Read in size (number of Mappings)
! int size = s.readInt();
// Read the keys and values, and put the mappings in the HashMap
! for (int i=0; i<size; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
--- 1093,1159 ----
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
! if (size > 0) {
! for(Map.Entry<K,V> e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
/**
! * Reconstitute the {@code HashMap} instance from a stream (i.e.,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
! // Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
+ if (loadFactor <= 0 || Float.isNaN(loadFactor))
+ throw new InvalidObjectException("Illegal load factor: " +
+ loadFactor);
+
+ // set hashSeed (can only happen after VM boot)
+ Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
+ sun.misc.Hashing.randomHashSeed(this));
// Read in number of buckets and allocate the bucket array;
! s.readInt(); // ignored
! // Read number of mappings
! int mappings = s.readInt();
! if (mappings < 0)
! throw new InvalidObjectException("Illegal mappings count: " +
! mappings);
!
! int initialCapacity = (int) Math.min(
! // capacity chosen by number of mappings
! // and desired load (if >= 0.25)
! mappings * Math.min(1 / loadFactor, 4.0f),
! // we have limits...
! HashMap.MAXIMUM_CAPACITY);
! int capacity = 1;
! // find smallest power of two which holds all mappings
! while (capacity < initialCapacity) {
! capacity <<= 1;
! }
!
! table = new Entry[capacity];
! threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
! useAltHashing = sun.misc.VM.isBooted() &&
! (capacity >= Holder.ALTERNATE_HASHING_THRESHOLD);
! init(); // Give subclass a chance to do its thing.
// Read the keys and values, and put the mappings in the HashMap
! for (int i=0; i<mappings; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}