src/share/classes/java/util/HashMap.java

Print this page
rev 5382 : 7126277: Alternative hashing implementation

*** 173,182 **** --- 173,211 ---- * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */ transient int modCount; + private static class Holder { + /** + * + */ + 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( + HashMap.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); + /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity
*** 198,208 **** int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; ! threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); } /** --- 227,237 ---- int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; ! threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; init(); } /**
*** 219,232 **** /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { ! this.loadFactor = DEFAULT_LOAD_FACTOR; ! threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); ! table = new Entry[DEFAULT_INITIAL_CAPACITY]; ! init(); } /** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with --- 248,258 ---- /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { ! this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
*** 253,269 **** */ void init() { } /** ! * Applies a supplemental hash function to a given hashCode, which ! * defends against poor quality hash functions. This is critical ! * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ ! * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ ! static int hash(int h) { // 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); --- 279,302 ---- */ void init() { } /** ! * Retrieve object hash code and applies a supplemental hash function to the ! * result hash, which defends against poor quality hash functions. This is ! * critical because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ ! * in lower bits. */ ! final int hash(Object k) { ! int h = hashSeed; ! if (k instanceof String) { ! return h ^ ((String)k).hash32(); ! } ! ! 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);
*** 311,346 **** * * @see #put(Object, Object) */ @SuppressWarnings("unchecked") public V get(Object key) { ! if (key == null) ! return (V)getForNullKey(); ! int hash = hash(key.hashCode()); ! for (Entry<?,?> e = table[indexFor(hash, table.length)]; ! e != null; ! e = e.next) { ! Object k; ! if (e.hash == hash && ((k = e.key) == key || key.equals(k))) ! return (V)e.value; ! } ! return null; ! } ! /** ! * Offloaded version of get() to look up null keys. Null keys map ! * to index 0. This null case is split out into separate methods ! * for the sake of performance in the two most commonly used ! * operations (get and put), but incorporated with conditionals in ! * others. ! */ ! private Object getForNullKey() { ! for (Entry<?,?> e = table[0]; e != null; e = e.next) { ! if (e.key == null) ! return e.value; ! } ! return null; } /** * Returns <tt>true</tt> if this map contains a mapping for the * specified key. --- 344,356 ---- * * @see #put(Object, Object) */ @SuppressWarnings("unchecked") public V get(Object key) { ! Entry<K,V> entry = getEntry(key); ! return null == entry ? null : entry.getValue(); } /** * Returns <tt>true</tt> if this map contains a mapping for the * specified key.
*** 358,368 **** * HashMap. Returns null if the HashMap contains no mapping * for the key. */ @SuppressWarnings("unchecked") final Entry<K,V> getEntry(Object key) { ! int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry<?,?> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && --- 368,378 ---- * HashMap. Returns null if the HashMap contains no mapping * for the key. */ @SuppressWarnings("unchecked") final Entry<K,V> getEntry(Object key) { ! int hash = (key == null) ? 0 : hash(key); for (Entry<?,?> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash &&
*** 386,396 **** * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { if (key == null) return putForNullKey(value); ! int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)table[i]; for(; e != null; e = e.next) { Object k; --- 396,406 ---- * previously associated <tt>null</tt> with <tt>key</tt>.) */ public V put(K key, V value) { if (key == null) return putForNullKey(value); ! int hash = hash(key); int i = indexFor(hash, table.length); @SuppressWarnings("unchecked") Entry<K,V> e = (Entry<K,V>)table[i]; for(; e != null; e = e.next) { Object k;
*** 431,441 **** * pseudoconstructors (clone, readObject). It does not resize the table, * check for comodification, etc. It calls createEntry rather than * addEntry. */ private void putForCreate(K key, V value) { ! int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); /** * Look for preexisting entry for key. This will never happen for * clone or deserialize. It will only happen for construction if the --- 441,451 ---- * pseudoconstructors (clone, readObject). It does not resize the table, * check for comodification, etc. It calls createEntry rather than * addEntry. */ private void putForCreate(K key, V value) { ! int hash = null == key ? 0 : hash(key); int i = indexFor(hash, table.length); /** * Look for preexisting entry for key. This will never happen for * clone or deserialize. It will only happen for construction if the
*** 482,514 **** } Entry<?,?>[] newTable = new Entry<?,?>[newCapacity]; transfer(newTable); table = newTable; ! threshold = (int)(newCapacity * loadFactor); } /** * Transfers all entries from current table to newTable. */ @SuppressWarnings("unchecked") void transfer(Entry<?,?>[] newTable) { Entry<?,?>[] src = table; int newCapacity = newTable.length; ! for (int j = 0; j < src.length; j++) { ! Entry<K,V> e = (Entry<K,V>)src[j]; ! if (e != null) { ! src[j] = null; ! do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); ! e.next = (Entry<K,V>)newTable[i]; newTable[i] = e; e = next; - } while (e != null); } } } /** * Copies all of the mappings from the specified map to this map. * These mappings will replace any mappings that this map had for --- 492,522 ---- } Entry<?,?>[] newTable = new Entry<?,?>[newCapacity]; transfer(newTable); table = newTable; ! threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } /** * Transfers all entries from current table to newTable. */ @SuppressWarnings("unchecked") void transfer(Entry<?,?>[] newTable) { Entry<?,?>[] src = table; int newCapacity = newTable.length; ! for (int j = 0; j < src.length; j++ ) { ! Entry<K,V> e = (Entry<K,V>) src[j]; ! while(null != e) { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); ! e.next = (Entry<K,V>) newTable[i]; newTable[i] = e; e = next; } } + Arrays.fill(table, null); } /** * Copies all of the mappings from the specified map to this map. * These mappings will replace any mappings that this map had for
*** 564,574 **** * Removes and returns the entry associated with the specified key * in the HashMap. Returns null if the HashMap contains no mapping * for this key. */ final Entry<K,V> removeEntryForKey(Object key) { ! int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); @SuppressWarnings("unchecked") Entry<K,V> prev = (Entry<K,V>)table[i]; Entry<K,V> e = prev; --- 572,582 ---- * Removes and returns the entry associated with the specified key * in the HashMap. Returns null if the HashMap contains no mapping * for this key. */ final Entry<K,V> removeEntryForKey(Object key) { ! int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); @SuppressWarnings("unchecked") Entry<K,V> prev = (Entry<K,V>)table[i]; Entry<K,V> e = prev;
*** 592,602 **** return e; } /** ! * Special version of remove for EntrySet. */ final Entry<K,V> removeMapping(Object o) { if (!(o instanceof Map.Entry)) return null; --- 600,611 ---- return e; } /** ! * Special version of remove for EntrySet using {@code Map.Entry.equals()} ! * for matching. */ final Entry<K,V> removeMapping(Object o) { if (!(o instanceof Map.Entry)) return null;
*** 771,785 **** * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { ! @SuppressWarnings("unchecked") ! Entry<K,V> e = (Entry<K,V>)table[bucketIndex]; ! table[bucketIndex] = new Entry<>(hash, key, value, e); ! if (size++ >= threshold) resize(2 * table.length); } /** * Like addEntry except that this version is used when creating entries * as part of Map construction or "pseudo-construction" (cloning, --- 780,796 ---- * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { ! if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); + hash = hash(key); + bucketIndex = indexFor(hash, table.length); + } + + createEntry(hash, key, value, bucketIndex); } /** * Like addEntry except that this version is used when creating entries * as part of Map construction or "pseudo-construction" (cloning,
*** 839,849 **** Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } - } private final class ValueIterator extends HashIterator<V> { public V next() { return nextEntry().value; --- 850,859 ----
*** 1019,1060 **** // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating) ! if (i != null) { ! while (i.hasNext()) { ! Map.Entry<K,V> e = i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } } private static final long serialVersionUID = 362498820763181265L; /** ! * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e., * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { ! // Read in the threshold, loadfactor, and any hidden stuff s.defaultReadObject(); // Read in number of buckets and allocate the bucket array; ! int numBuckets = s.readInt(); ! table = new Entry[numBuckets]; init(); // Give subclass a chance to do its thing. - // Read in size (number of Mappings) - int size = s.readInt(); // Read the keys and values, and put the mappings in the HashMap ! for (int i=0; i<size; i++) { @SuppressWarnings("unchecked") K key = (K) s.readObject(); @SuppressWarnings("unchecked") V value = (V) s.readObject(); putForCreate(key, value); --- 1029,1093 ---- // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating) ! if (size > 0) { ! for(Map.Entry<K,V> e : entrySet0()) { s.writeObject(e.getKey()); s.writeObject(e.getValue()); } } } private static final long serialVersionUID = 362498820763181265L; /** ! * Reconstitute the {@code HashMap} instance from a stream (i.e., * deserialize it). */ private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException { ! // Read in the threshold (ignored), loadfactor, and any hidden stuff s.defaultReadObject(); + if (loadFactor <= 0 || Float.isNaN(loadFactor)) + throw new InvalidObjectException("Illegal load factor: " + + loadFactor); + + // set hashMask + Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET, + sun.misc.Hashing.randomHashSeed(this)); // Read in number of buckets and allocate the bucket array; ! s.readInt(); // ignored + // Read number of mappings + int mappings = s.readInt(); + if (mappings < 0) + throw new InvalidObjectException("Illegal mappings count: " + + mappings); + + int initialCapacity = (int) Math.min( + // capacity chosen by number of mappings + // and desired load (if >= 0.25) + mappings * Math.min(1 / loadFactor, 4.0f), + // we have limits... + HashMap.MAXIMUM_CAPACITY); + int capacity = 1; + // find smallest power of two which holds all mappings + while (capacity < initialCapacity) { + capacity <<= 1; + } + + table = new Entry[capacity]; + threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); init(); // Give subclass a chance to do its thing. // Read the keys and values, and put the mappings in the HashMap ! for (int i=0; i<mappings; i++) { @SuppressWarnings("unchecked") K key = (K) s.readObject(); @SuppressWarnings("unchecked") V value = (V) s.readObject(); putForCreate(key, value);