src/share/classes/java/util/HashMap.java
Print this page
rev 5810 : 8006593: Performance and compatibility improvements to hash based Map implementations.
Summary: Use ThreadLocalRandom for hash seed rather than shared Random. Initialize {HashMap|Hashtable}.hashSeed only as needed. Minor optimizations.
Reviewed-by: alanb, bchristi
*** 190,210 ****
/**
* holds values which can't be initialized until after VM is booted.
*/
private static class Holder {
- // Unsafe mechanics
- /**
- * Unsafe utilities
- */
- static final sun.misc.Unsafe UNSAFE;
-
- /**
- * Offset of "final" hashSeed field we must set in readObject() method.
- */
- static final long HASHSEED_OFFSET;
-
/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
--- 190,199 ----
*** 228,260 ****
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
- ALTERNATIVE_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 alternative hashing of String keys 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.
*
--- 217,237 ----
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
! ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
/**
* A randomizing value associated with this instance that is applied to
! * hash code of keys to make hash collisions harder to find. If 0 then
! * alternative hashing is disabled.
*/
! transient int hashSeed = 0;
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
*** 272,290 ****
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
! 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.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
--- 249,267 ----
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
! int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
! ? capacity
! : 1;
! capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
! initHashSeedAsNeeded(capacity);
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
*** 331,354 ****
*/
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
--- 308,345 ----
*/
void init() {
}
/**
+ * Initialize the hashing mask value. We defer initialization until we
+ * really need it.
+ */
+ final boolean initHashSeedAsNeeded(int capacity) {
+ boolean currentAltHashing = hashSeed != 0;
+ boolean useAltHashing = sun.misc.VM.isBooted() &&
+ (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
+ boolean switching = currentAltHashing ^ useAltHashing;
+ if (switching) {
+ hashSeed = useAltHashing
+ ? sun.misc.Hashing.randomHashSeed(this)
+ : 0;
+ }
+ return switching;
+ }
+
+ /**
* 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 = hashSeed;
! if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
*** 555,569 ****
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
! boolean oldAltHashing = useAltHashing;
! useAltHashing |= sun.misc.VM.isBooted() &&
! (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
! boolean rehash = oldAltHashing ^ useAltHashing;
! transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
--- 546,556 ----
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
! transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
*** 813,824 ****
}
return false;
}
public final int hashCode() {
! return (key==null ? 0 : key.hashCode()) ^
! (value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
--- 800,810 ----
}
return false;
}
public final int hashCode() {
! return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
*** 1115,1128 ****
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();
--- 1101,1110 ----
*** 1134,1153 ****
// 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.ALTERNATIVE_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++) {
--- 1116,1134 ----
// 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);
// find smallest power of two which holds all mappings
! int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
! ? capacity
! : 1;
! capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
table = new Entry[capacity];
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
! initHashSeedAsNeeded(capacity);
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++) {