src/share/classes/java/util/HashMap.java
Print this page
rev 6789 : 7143928: Optimize empty HashMap and ArrayList
Reviewed-by: mduigou
Contributed-by: Sergey Linetskiy <sergey.linetskiy@oracle.com>, John Rose <john.rose@oracle.com>, Mike Duigou <mike.duigou@oracle.com>
*** 1,7 ****
/*
! * Copyright (c) 1997, 2012, 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
--- 1,7 ----
/*
! * 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
*** 142,154 ****
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
! transient Entry<?,?>[] table;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
--- 142,159 ----
* 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 = EMPTY_TABLE;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
*** 185,201 ****
* 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);
}
}
}
/**
--- 190,214 ----
* Offset of "final" hashSeed field we must set in
* readObject() method.
*/
static final long HASHSEED_OFFSET;
+ /**
+ * Offset of "final" initialCapacity field we must set in
+ * readObject() method.
+ */
+ static final long INITIAL_CAPACITY_OFFSET;
+
static {
try {
UNSAFE = sun.misc.Unsafe.getUnsafe();
HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
HashMap.class.getDeclaredField("hashSeed"));
+ INITIAL_CAPACITY_OFFSET = UNSAFE.objectFieldOffset(
+ HashMap.class.getDeclaredField("initialCapacity"));
} catch (NoSuchFieldException | SecurityException e) {
! throw new InternalError("Failed to record field offset", e);
}
}
}
/**
*** 203,212 ****
--- 216,230 ----
* hash code of keys to make hash collisions harder to find.
*/
transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
/**
+ * The requested initial capacity increased to a power of two.
+ */
+ transient final int initialCapacity;
+
+ /**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
*** 222,238 ****
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];
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
--- 240,257 ----
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
! int capacity = (capacity = Integer.highestOneBit(initialCapacity)) != 0
! ? capacity
! : 1;
! capacity <<= (Integer.bitCount(initialCapacity) > 1) ? 1 : 0;
this.loadFactor = loadFactor;
! threshold = 0;
! this.initialCapacity = capacity;
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
*** 263,275 ****
--- 282,303 ----
* @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();
+
putAllForCreate(m);
}
+ /**
+ * Inflate the table
+ */
+ final void inflateTable() {
+ threshold = (int)Math.min(initialCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
+ table = new Entry[initialCapacity];
+ }
// internal utilities
/**
* Initialization hook for subclasses. This method is called
* in all constructors and pseudo-constructors (clone, readObject)
*** 367,376 ****
--- 395,408 ----
* 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,389 ****
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.
*
--- 411,420 ----
*** 393,402 ****
--- 424,436 ----
* <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();
+ }
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
@SuppressWarnings("unchecked")
*** 527,536 ****
--- 561,574 ----
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0)
return;
+ if (table == EMPTY_TABLE) {
+ inflateTable();
+ }
+
/*
* 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,
*** 561,570 ****
--- 599,611 ----
* <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 remove(Object key) {
+ if(isEmpty()) {
+ return null;
+ }
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
/**
*** 605,614 ****
--- 646,658 ----
* for matching.
*/
final Entry<K,V> removeMapping(Object o) {
if (!(o instanceof Map.Entry))
return null;
+ if(isEmpty()) {
+ return null;
+ }
Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
*** 639,651 ****
* 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;
size = 0;
}
/**
* Returns <tt>true</tt> if this map maps one or more keys to the
--- 683,693 ----
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
modCount++;
! Arrays.fill(table, null);
size = 0;
}
/**
* Returns <tt>true</tt> if this map maps one or more keys to the
*** 654,663 ****
--- 696,709 ----
* @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,701 ****
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
! result.table = new Entry<?,?>[table.length];
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
--- 737,749 ----
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
! 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,758 ****
}
return false;
}
public final int hashCode() {
! return (key==null ? 0 : key.hashCode()) ^
! (value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
--- 795,805 ----
}
return false;
}
public final int hashCode() {
! return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
*** 1015,1031 ****
* 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
s.writeInt(table.length);
// Write out size (number of Mappings)
s.writeInt(size);
--- 1062,1078 ----
* emitted in no particular order.
*/
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
+ if (table==EMPTY_TABLE)
+ s.writeInt(initialCapacity); // power of 2.
+ else
s.writeInt(table.length);
// Write out size (number of Mappings)
s.writeInt(size);
*** 1064,1090 ****
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")
--- 1111,1143 ----
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
! int mappingsCapacity = Math.max((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), 0);
! // Find a power of 2 >= mappingCapacity
! int capacity = (capacity = Integer.highestOneBit(mappingsCapacity)) != 0
! ? capacity
! : 1;
! capacity <<= (Integer.bitCount(mappingsCapacity) > 1) ? 1 : 0;
! Holder.UNSAFE.putIntVolatile(this, Holder.INITIAL_CAPACITY_OFFSET,
! capacity);
!
! if(mappings > 0) {
! inflateTable();
! } else {
! table = EMPTY_TABLE;
! threshold = 0;
}
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")