src/share/classes/java/util/HashMap.java
Print this page
rev 6845 : 80111200: (coll) Optimize empty HashMap and ArrayList
Reviewed-by: mduigou, alanb, bchristi, martin
Contributed-by: Sergey Linetskiy <sergey.linetskiy@oracle.com>, John Rose <john.r.rose@oracle.com>, Mike Duigou <mike.duigou@oracle.com>
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
@@ -127,11 +127,11 @@
{
/**
* The default initial capacity - MUST be a power of two.
*/
- static final int DEFAULT_INITIAL_CAPACITY = 16;
+ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
@@ -142,21 +142,28 @@
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
+ * An empty table instance to share when the table is not inflated.
+ */
+ static final Entry<?,?>[] EMPTY_TABLE = {};
+
+ /**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
- transient Entry<?,?>[] table;
+ transient Entry<?,?>[] table = EMPTY_TABLE;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
- * The next size value at which to resize (capacity * load factor).
+ * The next size value at which to resize (capacity * load factor). If
+ * table == EMPTY_TABLE then this is the initial capacity at which the
+ * table will be created when inflated.
* @serial
*/
int threshold;
/**
@@ -221,18 +228,12 @@
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
- // Find a power of 2 >= initialCapacity
- int capacity = 1;
- while (capacity < initialCapacity)
- capacity <<= 1;
-
this.loadFactor = loadFactor;
- threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
- table = new Entry<?,?>[capacity];
+ threshold = initialCapacity;
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
@@ -263,13 +264,36 @@
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
+ inflateTable(threshold);
+
putAllForCreate(m);
}
+ private static int roundUpToPowerOf2(int number) {
+ int rounded = number >= MAXIMUM_CAPACITY
+ ? MAXIMUM_CAPACITY
+ : (rounded = Integer.highestOneBit(number)) != 0
+ ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
+ : 1;
+
+ return rounded;
+ }
+
+ /**
+ * Inflate the table
+ */
+ private void inflateTable(int toSize) {
+ // Find a power of 2 >= initialCapacity
+ int capacity = roundUpToPowerOf2(toSize);
+
+ threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
+ table = new Entry[capacity];
+ }
+
// internal utilities
/**
* Initialization hook for subclasses. This method is called
* in all constructors and pseudo-constructors (clone, readObject)
@@ -303,10 +327,11 @@
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
+ // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
/**
* Returns the number of key-value mappings in this map.
@@ -367,10 +392,14 @@
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
@SuppressWarnings("unchecked")
final Entry<K,V> getEntry(Object key) {
+ if (isEmpty()) {
+ return null;
+ }
+
int hash = (key == null) ? 0 : hash(key);
for (Entry<?,?> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
@@ -379,11 +408,10 @@
return (Entry<K,V>)e;
}
return null;
}
-
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
@@ -393,10 +421,13 @@
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
+ if (table == EMPTY_TABLE) {
+ inflateTable(threshold);
+ }
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
@@ -527,10 +558,14 @@
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
+ if (table == EMPTY_TABLE) {
+ inflateTable(Math.max((int) (numKeysToBeAdded * loadFactor), threshold));
+ }
+
/*
* Expand the map if the map if the number of mappings to be added
* is greater than or equal to threshold. This is conservative; the
* obvious condition is (m.size() + size) >= threshold, but this
* condition could result in a map with twice the appropriate capacity,
@@ -571,10 +606,13 @@
* 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) {
+ if (isEmpty()) {
+ return null;
+ }
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;
@@ -603,11 +641,11 @@
/**
* 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))
+ if (isEmpty() || !(o instanceof Map.Entry))
return null;
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key);
@@ -639,13 +677,11 @@
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
modCount++;
- Entry<?,?>[] tab = table;
- for (int i = 0; i < tab.length; i++)
- tab[i] = null;
+ Arrays.fill(table, null);
size = 0;
}
/**
* Returns <tt>true</tt> if this map maps one or more keys to the
@@ -654,10 +690,14 @@
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
public boolean containsValue(Object value) {
+ if (isEmpty()) {
+ return false;
+ }
+
if (value == null)
return containsNullValue();
Entry<?,?>[] tab = table;
for (int i = 0; i < tab.length ; i++)
@@ -691,11 +731,13 @@
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
- result.table = new Entry<?,?>[table.length];
+ result.table = (table == EMPTY_TABLE)
+ ? EMPTY_TABLE
+ : new Entry<?,?>[table.length];
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
@@ -747,12 +789,11 @@
}
return false;
}
public final int hashCode() {
- return (key==null ? 0 : key.hashCode()) ^
- (value==null ? 0 : value.hashCode());
+ return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
@@ -1015,18 +1056,19 @@
* emitted in no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
- Iterator<Map.Entry<K,V>> i =
- (size > 0) ? entrySet0().iterator() : null;
-
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
+ if (table==EMPTY_TABLE) {
+ s.writeInt(roundUpToPowerOf2(threshold));
+ } else {
s.writeInt(table.length);
+ }
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
@@ -1047,44 +1089,53 @@
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))
+ if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
+ }
- // set hashMask
+ // set other fields that need values
Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
sun.misc.Hashing.randomHashSeed(this));
+ table = EMPTY_TABLE;
+
+ // Read in number of buckets
+ int bucketsCapacity = s.readInt();
+
+ if (bucketsCapacity < 0) {
+ throw new InvalidObjectException("Illegal capacity: " + bucketsCapacity);
+ }
- // Read in number of buckets and allocate the bucket array;
- s.readInt(); // ignored
+ bucketsCapacity = roundUpToPowerOf2(bucketsCapacity);
// 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)
+ // capacity chosen by number of mappings and desired load (if >= 0.25)
+ int mappingsCapacity = (int) Math.min(
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;
+
+ // capacity is greater of that suggested by loading and buckets
+ int capacity = Math.max(mappingsCapacity, bucketsCapacity);
+
+ // allocate the bucket array;
+ if (mappings > 0) {
+ inflateTable(capacity);
+ } else {
+ threshold = capacity;
}
- 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")