src/share/classes/java/util/Hashtable.java
Print this page
rev 5431 : 7126277: Alternative hashing implementation
@@ -161,10 +161,56 @@
private transient int modCount = 0;
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1421746759512286392L;
+ private static class Holder {
+ // Unsafe mechanics
+ /**
+ *
+ */
+ static final sun.misc.Unsafe UNSAFE;
+
+ /**
+ * Offset of "final" hashSeed field we must set in
+ * readObject() method.
+ */
+ 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 InternalError("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) {
+ int h = hashSeed;
+
+ if (k instanceof String) {
+ return ((String)k).hash32();
+ } 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);
+ }
+ }
+
/**
* Constructs a new, empty hashtable with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hashtable.
@@ -181,11 +227,11 @@
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);
}
/**
* Constructs a new, empty hashtable with the specified initial capacity
* and default load factor (0.75).
@@ -325,11 +371,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<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
@@ -353,11 +399,11 @@
* @see #put(Object, Object)
*/
@SuppressWarnings("unchecked")
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<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
@@ -394,11 +440,11 @@
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
- threshold = (int)(newCapacity * loadFactor);
+ threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
@@ -434,11 +480,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;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
@@ -452,10 +498,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.
@SuppressWarnings("unchecked")
@@ -474,11 +521,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;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@@ -683,11 +730,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;
@@ -698,11 +745,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;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) {
@@ -833,13 +880,17 @@
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<?,?> entry : tab) {
+ while (entry != null) {
+ h += entry.hashCode();
+ entry = entry.next;
+ }
+ }
+
loadFactor = -loadFactor; // Mark hashCode computation complete
return h;
}
@@ -892,10 +943,14 @@
throws IOException, ClassNotFoundException
{
// Read in the length, threshold, and loadfactor
s.defaultReadObject();
+ // set hashMask
+ Holder.UNSAFE.putIntVolatile(this, Holder.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
@@ -905,11 +960,12 @@
int length = (int)(elements * loadFactor) + (elements / 20) + 3;
if (length > elements && (length & 1) == 0)
length--;
if (origlength > 0 && length > origlength)
length = origlength;
- Entry<?,?>[] table = new Entry<?,?>[length];
+ table = new Entry<?,?>[length];
+ threshold = (int)Math.min(length * loadFactor, MAX_ARRAY_SIZE + 1);
count = 0;
// Read the number of elements and then all the key/value objects
for (; elements > 0; elements--) {
@SuppressWarnings("unchecked")
@@ -917,11 +973,10 @@
@SuppressWarnings("unchecked")
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
@@ -939,11 +994,11 @@
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<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
throw new java.io.StreamCorruptedException();
}
@@ -954,14 +1009,14 @@
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;
+ final int hash;
K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {