--- a/jdk/src/share/classes/java/util/HashMap.java Fri Apr 12 10:02:33 2013 -0700
+++ b/jdk/src/share/classes/java/util/HashMap.java Wed Apr 10 12:43:18 2013 -0700
@@ -129,7 +129,7 @@
/**
* 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
@@ -144,9 +144,14 @@
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.
@@ -157,6 +162,8 @@
* The next size value at which to resize (capacity * load factor).
* @serial
*/
+ // If table == EMPTY_TABLE then this is the initial capacity at which the
+ // table will be created when inflated.
int threshold;
/**
@@ -223,14 +230,8 @@
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();
}
@@ -265,9 +266,33 @@
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) {
+ // assert number >= 0 : "number must be non-negative";
+ int rounded = number >= MAXIMUM_CAPACITY
+ ? MAXIMUM_CAPACITY
+ : (rounded = Integer.highestOneBit(number)) != 0
+ ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
+ : 1;
+
+ return rounded;
+ }
+
+ /**
+ * Inflates the table.
+ */
+ private void inflateTable(int toSize) {
+ // Find a power of 2 >= toSize
+ int capacity = roundUpToPowerOf2(toSize);
+
+ threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
+ table = new Entry[capacity];
+ }
+
// internal utilities
/**
@@ -305,6 +330,7 @@
* 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);
}
@@ -369,6 +395,10 @@
*/
@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;
@@ -381,7 +411,6 @@
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
@@ -395,6 +424,9 @@
* 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);
@@ -529,6 +561,10 @@
if (numKeysToBeAdded == 0)
return;
+ if (table == EMPTY_TABLE) {
+ inflateTable((int) Math.max(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
@@ -573,6 +609,9 @@
* 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")
@@ -605,7 +644,7 @@
* 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;
@@ -641,9 +680,7 @@
*/
public void clear() {
modCount++;
- Entry<?,?>[] tab = table;
- for (int i = 0; i < tab.length; i++)
- tab[i] = null;
+ Arrays.fill(table, null);
size = 0;
}
@@ -693,7 +730,14 @@
} catch (CloneNotSupportedException e) {
// assert false;
}
- result.table = new Entry<?,?>[table.length];
+ if (result.table != EMPTY_TABLE) {
+ result.inflateTable(Math.min(
+ (int) Math.min(
+ size * Math.min(1 / loadFactor, 4.0f),
+ // we have limits...
+ HashMap.MAXIMUM_CAPACITY),
+ table.length));
+ }
result.entrySet = null;
result.modCount = 0;
result.size = 0;
@@ -749,8 +793,7 @@
}
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() {
@@ -1017,14 +1060,15 @@
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
- s.writeInt(table.length);
+ if (table==EMPTY_TABLE) {
+ s.writeInt(roundUpToPowerOf2(threshold));
+ } else {
+ s.writeInt(table.length);
+ }
// Write out size (number of Mappings)
s.writeInt(size);
@@ -1049,16 +1093,18 @@
{
// 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 and allocate the bucket array;
- s.readInt(); // ignored
+ // Read in number of buckets
+ s.readInt(); // ignored.
// Read number of mappings
int mappings = s.readInt();
@@ -1066,23 +1112,21 @@
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;
+ // capacity chosen by number of mappings and desired load (if >= 0.25)
+ int capacity = (int) Math.min(
+ mappings * Math.min(1 / loadFactor, 4.0f),
+ // we have limits...
+ HashMap.MAXIMUM_CAPACITY);
+
+ // 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")