src/share/classes/java/util/Hashtable.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
*** 211,268 ****
ALTERNATIVE_HASHING_THRESHOLD = threshold;
}
}
/**
! * 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;
!
! // Unsafe mechanics
! /**
! * Unsafe utilities
*/
! private static final sun.misc.Unsafe UNSAFE;
/**
! * Offset of "final" hashSeed field we must set in readObject() method.
*/
! private static final long HASHSEED_OFFSET;
!
! static {
! try {
! UNSAFE = sun.misc.Unsafe.getUnsafe();
! HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
! Hashtable.class.getDeclaredField("hashSeed"));
! } catch (NoSuchFieldException | SecurityException e) {
! throw new Error("Failed to record hashSeed offset", e);
}
}
- /**
- * 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);
-
private int hash(Object k) {
! if (useAltHashing) {
! if (k.getClass() == String.class) {
! return sun.misc.Hashing.stringHash32((String) k);
! } else {
! int h = hashSeed ^ 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);
! }
! } else {
! return k.hashCode();
! }
}
/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
--- 211,244 ----
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.
*/
! transient int hashSeed;
/**
! * Initialize the hashing mask value.
*/
! 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;
}
private int hash(Object k) {
! // hashSeed will be zero if alternative hashing is disabled.
! return hashSeed ^ k.hashCode();
}
/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
*** 282,293 ****
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
! useAltHashing = sun.misc.VM.isBooted() &&
! (initialCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
}
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
--- 258,268 ----
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
! initHashSeedAsNeeded(initialCapacity);
}
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
*** 495,508 ****
}
Entry<K,V>[] newMap = new Entry[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
! boolean currentAltHashing = useAltHashing;
! useAltHashing = sun.misc.VM.isBooted() &&
! (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
! boolean rehash = currentAltHashing ^ useAltHashing;
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
--- 470,480 ----
}
Entry<K,V>[] newMap = new Entry[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
! boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
*** 997,1010 ****
throws IOException, ClassNotFoundException
{
// Read in the length, threshold, and loadfactor
s.defaultReadObject();
- // set hashSeed
- UNSAFE.putIntVolatile(this, HASHSEED_OFFSET,
- sun.misc.Hashing.randomHashSeed(this));
-
// Read the original length of the array and number of elements
int origlength = s.readInt();
int elements = s.readInt();
// Compute new size with a bit of room 5% to grow but
--- 969,978 ----
*** 1015,1038 ****
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
! Entry<K,V>[] table = new Entry[length];
threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
count = 0;
! useAltHashing = sun.misc.VM.isBooted() &&
! (length >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
// Read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
K key = (K)s.readObject();
V value = (V)s.readObject();
// synch could be eliminated for performance
! reconstitutionPut(table, key, value);
}
! this.table = table;
}
/**
* The put method used by readObject. This is provided because put
* is overridable and should not be called in readObject since the
--- 983,1005 ----
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
! Entry<K,V>[] newTable = new Entry[length];
threshold = (int) Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
count = 0;
! initHashSeedAsNeeded(length);
// Read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
K key = (K)s.readObject();
V value = (V)s.readObject();
// synch could be eliminated for performance
! reconstitutionPut(newTable, key, value);
}
! this.table = newTable;
}
/**
* The put method used by readObject. This is provided because put
* is overridable and should not be called in readObject since the