src/share/classes/java/util/Hashtable.java
Print this page
@@ -127,11 +127,11 @@
implements Map<K,V>, Cloneable, java.io.Serializable {
/**
* The hash table data.
*/
- private transient Entry[] table;
+ private transient Entry<K,V>[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
@@ -162,10 +162,107 @@
/** 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 HASHMASK_OFFSET;
+
+ static {
+ try {
+ UNSAFE = sun.misc.Unsafe.getUnsafe();
+ HASHMASK_OFFSET = UNSAFE.objectFieldOffset(
+ Hashtable.class.getDeclaredField("hashMask"));
+ } catch (NoSuchFieldException | SecurityException e) {
+ throw new Error(e);
+ }
+ }
+
+ /**
+ * A random mask value that is used for hashcode values associated with this
+ * instance to make hash collisions harder to find.
+ */
+ transient final int hashMask = sun.misc.Hashing.makeHashMask(this);
+
+ private int hash(Object k) {
+ int h;
+ if (useAltHashing) {
+ if (k.getClass() == String.class) {
+ 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);
+ h ^= (h >>> 7) ^ (h >>> 4);
+ }
+ h ^= hashMask;
+ } else {
+ h = k.hashCode();
+ }
+
+ return h;
+ }
+
+ /**
* 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,11 +278,13 @@
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
- threshold = (int)(initialCapacity * loadFactor);
+ 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,11 +424,11 @@
* @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 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,11 +451,11 @@
* @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 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,31 +478,39 @@
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
protected void rehash() {
int oldCapacity = table.length;
- Entry[] oldMap = table;
+ 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[] newMap = new Entry[newCapacity];
+ Entry<K,V>[] newMap = new Entry[newCapacity];
modCount++;
- threshold = (int)(newCapacity * loadFactor);
+ 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,11 +539,11 @@
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
- int hash = key.hashCode();
+ 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,10 +555,11 @@
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,11 +577,11 @@
* 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 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,11 +784,11 @@
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 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,11 +799,11 @@
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 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,13 +933,15 @@
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();
+ for (Entry<K,V> entry : tab)
+ while (entry != null) {
+ h += entry.hashCode();
+ entry = entry.next;
+ }
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
}
@@ -845,11 +955,11 @@
* 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;
+ Entry<K, V> entryStack = null;
synchronized (this) {
// Write out the length, threshold, loadfactor
s.defaultWriteObject();
@@ -857,11 +967,11 @@
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];
+ Entry<K,V> entry = table[index];
while (entry != null) {
entryStack =
new Entry<>(0, entry.key, entry.value, entryStack);
entry = entry.next;
@@ -884,10 +994,14 @@
throws IOException, ClassNotFoundException
{
// Read in the length, threshold, and loadfactor
s.defaultReadObject();
+ // set hashMask
+ UNSAFE.putIntVolatile(this, HASHMASK_OFFSET,
+ sun.misc.Hashing.makeHashMask(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,12 +1012,15 @@
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
- Entry[] table = new Entry[length];
+ 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,19 +1039,19 @@
* 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)
+ 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 = key.hashCode();
+ 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,11 +1061,11 @@
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
/**
- * Hashtable collision list.
+ * Hashtable bucket collision list entry
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
int hash;
K key;
V value;
@@ -986,18 +1103,17 @@
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
- Map.Entry e = (Map.Entry)o;
+ 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()));
+ return key.equals(e.getKey()) && value.equals(e.getValue());
}
public int hashCode() {
- return hash ^ (value==null ? 0 : value.hashCode());
+ return hash ^ value.hashCode();
}
public String toString() {
return key.toString()+"="+value.toString();
}