src/share/classes/java/util/Hashtable.java

Print this page
rev 5431 : 7126277: Alternative hashing implementation

*** 161,170 **** --- 161,216 ---- 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,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). --- 227,237 ---- if (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; table = new Entry<?,?>[initialCapacity]; ! 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,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<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return true; } --- 371,381 ---- * @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<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return true; }
*** 353,363 **** * @see #put(Object, Object) */ @SuppressWarnings("unchecked") public synchronized V get(Object key) { 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.key.equals(key)) { return (V)e.value; } --- 399,409 ---- * @see #put(Object, Object) */ @SuppressWarnings("unchecked") public synchronized V get(Object key) { 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.key.equals(key)) { return (V)e.value; }
*** 394,404 **** 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 = (Entry<K,V>)oldMap[i] ; old != null ; ) { Entry<K,V> e = old; --- 440,450 ---- newCapacity = MAX_ARRAY_SIZE; } Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; modCount++; ! 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,444 **** 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; @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)) { --- 480,490 ---- 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; @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,461 **** --- 498,508 ---- 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,484 **** * 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; @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)) { --- 521,531 ---- * 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; @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,693 **** 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; --- 730,740 ---- 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;
*** 698,708 **** 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; @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)tab[index]; for(Entry<K,V> prev = null; e != null; prev = e, e = e.next) { --- 745,755 ---- 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; @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,845 **** 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; } --- 880,896 ---- if (count == 0 || loadFactor < 0) return h; // Returns zero loadFactor = -loadFactor; // Mark hashCode computation in progress Entry<?,?>[] tab = table; ! for (Entry<?,?> entry : tab) { ! while (entry != null) { ! h += entry.hashCode(); ! entry = entry.next; ! } ! } ! loadFactor = -loadFactor; // Mark hashCode computation complete return h; }
*** 892,901 **** --- 943,956 ---- 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,915 **** 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]; count = 0; // Read the number of elements and then all the key/value objects for (; elements > 0; elements--) { @SuppressWarnings("unchecked") --- 960,971 ---- int length = (int)(elements * loadFactor) + (elements / 20) + 3; if (length > elements && (length & 1) == 0) length--; if (origlength > 0 && length > origlength) length = origlength; ! 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,927 **** @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 --- 973,982 ----
*** 939,949 **** 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<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { throw new java.io.StreamCorruptedException(); } --- 994,1004 ---- 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<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { throw new java.io.StreamCorruptedException(); }
*** 954,967 **** 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; Entry<K,V> next; protected Entry(int hash, K key, V value, Entry<K,V> next) { --- 1009,1022 ---- 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> { ! final int hash; K key; V value; Entry<K,V> next; protected Entry(int hash, K key, V value, Entry<K,V> next) {