src/share/classes/java/util/Hashtable.java
Print this page
rev 5028 : 7126277: alternative hashing
*** 127,137 ****
implements Map<K,V>, Cloneable, java.io.Serializable {
/**
* The hash table data.
*/
! private transient Entry[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
--- 127,137 ----
implements Map<K,V>, Cloneable, java.io.Serializable {
/**
* The hash table data.
*/
! private transient Entry<K,V>[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
*** 162,171 ****
--- 162,265 ----
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;
/**
+ * 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 {
+
+ /**
+ * 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)
+ : 1;
+
+ 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;
+ }
+ }
+
+ /**
+ * If {@code true} then perform alternate hashing to reduce the incidence of
+ * collisions due to weak hash code calculation.
+ */
+ transient boolean useAltHashing;
+
+ // Unsafe mechanics
+ private static final sun.misc.Unsafe UNSAFE;
+ 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) {
+ int h = hashSeed;
+ if (k.getClass() == String.class) {
+ return h ^ sun.misc.Hashing.stringHash32((String) k);
+ } 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);
+ }
+ } else {
+ return k.hashCode();
+ }
+ }
+
+ /**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hashtable.
* @param loadFactor the load factor of the hashtable.
*** 181,191 ****
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
! threshold = (int)(initialCapacity * loadFactor);
}
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
--- 275,287 ----
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.ALTERNATE_HASHING_THRESHOLD);
}
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
*** 325,335 ****
* @throws NullPointerException if the key is <code>null</code>
* @see #contains(Object)
*/
public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
! int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
--- 421,431 ----
* @throws NullPointerException if the key is <code>null</code>
* @see #contains(Object)
*/
public synchronized boolean containsKey(Object key) {
Entry tab[] = table;
! int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
*** 352,362 ****
* @throws NullPointerException if the specified key is null
* @see #put(Object, Object)
*/
public synchronized V get(Object key) {
Entry tab[] = table;
! int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
--- 448,458 ----
* @throws NullPointerException if the specified key is null
* @see #put(Object, Object)
*/
public synchronized V get(Object key) {
Entry tab[] = table;
! int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
*** 379,409 ****
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
protected void rehash() {
int oldCapacity = table.length;
! Entry[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
! Entry[] newMap = new Entry[newCapacity];
modCount++;
! threshold = (int)(newCapacity * loadFactor);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
--- 475,513 ----
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
protected void rehash() {
int oldCapacity = table.length;
! Entry<K,V>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
! 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.ALTERNATE_HASHING_THRESHOLD);
! boolean rehash = currentAltHashing ^ useAltHashing;
!
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
+ if(rehash) {
+ e.hash = hash(e.key);
+ }
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
*** 432,442 ****
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
! int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
--- 536,546 ----
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
! int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
*** 448,457 ****
--- 552,562 ----
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
+ hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
*** 469,479 ****
* or <code>null</code> if the key did not have a mapping
* @throws NullPointerException if the key is <code>null</code>
*/
public synchronized V remove(Object key) {
Entry tab[] = table;
! int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
--- 574,584 ----
* or <code>null</code> if the key did not have a mapping
* @throws NullPointerException if the key is <code>null</code>
*/
public synchronized V remove(Object key) {
Entry tab[] = table;
! int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
if (prev != null) {
*** 676,686 ****
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = table;
! int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return true;
--- 781,791 ----
if (!(o instanceof Map.Entry))
return false;
Map.Entry entry = (Map.Entry)o;
Object key = entry.getKey();
Entry[] tab = table;
! int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry e = tab[index]; e != null; e = e.next)
if (e.hash==hash && e.equals(entry))
return true;
*** 691,701 ****
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
K key = entry.getKey();
Entry[] tab = table;
! int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
--- 796,806 ----
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
K key = entry.getKey();
Entry[] tab = table;
! int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index], prev = null; e != null;
prev = e, e = e.next) {
if (e.hash==hash && e.equals(entry)) {
*** 825,837 ****
if (count == 0 || loadFactor < 0)
return h; // Returns zero
loadFactor = -loadFactor; // Mark hashCode computation in progress
Entry[] tab = table;
! for (int i = 0; i < tab.length; i++)
! for (Entry e = tab[i]; e != null; e = e.next)
! h += e.key.hashCode() ^ e.value.hashCode();
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
}
--- 930,944 ----
if (count == 0 || loadFactor < 0)
return h; // Returns zero
loadFactor = -loadFactor; // Mark hashCode computation in progress
Entry[] tab = table;
! for (Entry<K,V> entry : tab)
! while (entry != null) {
! h += entry.hashCode();
! entry = entry.next;
! }
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
}
*** 845,855 ****
* for each key-value mapping represented by the Hashtable
* The key-value mappings are emitted in no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
! Entry<Object, Object> entryStack = null;
synchronized (this) {
// Write out the length, threshold, loadfactor
s.defaultWriteObject();
--- 952,962 ----
* for each key-value mapping represented by the Hashtable
* The key-value mappings are emitted in no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
! Entry<K, V> entryStack = null;
synchronized (this) {
// Write out the length, threshold, loadfactor
s.defaultWriteObject();
*** 857,867 ****
s.writeInt(table.length);
s.writeInt(count);
// Stack copies of the entries in the table
for (int index = 0; index < table.length; index++) {
! Entry entry = table[index];
while (entry != null) {
entryStack =
new Entry<>(0, entry.key, entry.value, entryStack);
entry = entry.next;
--- 964,974 ----
s.writeInt(table.length);
s.writeInt(count);
// Stack copies of the entries in the table
for (int index = 0; index < table.length; index++) {
! Entry<K,V> entry = table[index];
while (entry != null) {
entryStack =
new Entry<>(0, entry.key, entry.value, entryStack);
entry = entry.next;
*** 884,893 ****
--- 991,1004 ----
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
*** 898,909 ****
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
! Entry[] table = new Entry[length];
count = 0;
// 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();
--- 1009,1023 ----
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.ALTERNATE_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();
*** 922,940 ****
* checking for rehashing is necessary since the number of elements
* initially in the table is known. The modCount is not incremented
* because we are creating a new instance. Also, no return value
* is needed.
*/
! private void reconstitutionPut(Entry[] tab, K key, V value)
throws StreamCorruptedException
{
if (value == null) {
throw new java.io.StreamCorruptedException();
}
// Makes sure the key is not already in the hashtable.
// This should not happen in deserialized version.
! int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
throw new java.io.StreamCorruptedException();
}
--- 1036,1054 ----
* checking for rehashing is necessary since the number of elements
* initially in the table is known. The modCount is not incremented
* because we are creating a new instance. Also, no return value
* is needed.
*/
! private void reconstitutionPut(Entry<K,V>[] tab, K key, V value)
throws StreamCorruptedException
{
if (value == null) {
throw new java.io.StreamCorruptedException();
}
// Makes sure the key is not already in the hashtable.
// This should not happen in deserialized version.
! int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
throw new java.io.StreamCorruptedException();
}
*** 944,954 ****
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
/**
! * Hashtable collision list.
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
--- 1058,1068 ----
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
/**
! * Hashtable bucket collision list entry
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
*** 986,1003 ****
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
! Map.Entry e = (Map.Entry)o;
! return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
! (value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
! return hash ^ (value==null ? 0 : value.hashCode());
}
public String toString() {
return key.toString()+"="+value.toString();
}
--- 1100,1116 ----
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
! Map.Entry<?,?> e = (Map.Entry)o;
! return key.equals(e.getKey()) && value.equals(e.getValue());
}
public int hashCode() {
! return hash ^ value.hashCode();
}
public String toString() {
return key.toString()+"="+value.toString();
}