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

Print this page
rev 6816 : 80111200: (coll) Optimize empty HashMap and ArrayList
Reviewed-by: mduigou
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

@@ -142,13 +142,18 @@
      * 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;

@@ -221,18 +226,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 +262,34 @@
      * @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 = (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 +323,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 +388,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 +404,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 +417,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 +554,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 +602,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 +637,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 +673,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 +686,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 +727,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 +785,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();
         }

@@ -1006,27 +1043,28 @@
     /**
      * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
      * serialize it).
      *
      * @serialData The <i>capacity</i> of the HashMap (the length of the
-     *             bucket array) is emitted (int), followed by the
+     *             bucket array, a power of 2) is emitted (int), followed by the
      *             <i>size</i> (an int, the number of key-value
      *             mappings), followed by the key (Object) and value (Object)
      *             for each key-value mapping.  The key-value mappings are
      *             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 +1085,54 @@
     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
         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
+        table = EMPTY_TABLE;
+
+        int buckets = s.readInt();
+
+        if ((buckets < 0) || // negative
+            (buckets > HashMap.MAXIMUM_CAPACITY) || // too big
+            (Integer.bitCount(buckets) > 1)) /* not power of 2 or zero */ {
+            throw new InvalidObjectException("Illegal capacity: " + buckets);
+        }
 
         // Read number of mappings
         int mappings = s.readInt();
         if (mappings < 0)
             throw new InvalidObjectException("Illegal mappings count: " +
                                                mappings);
 
-        int initialCapacity = (int) Math.min(
+        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);
-        int capacity = 1;
-        // find smallest power of two which holds all mappings
-        while (capacity < initialCapacity) {
-            capacity <<= 1;
+                    HashMap.MAXIMUM_CAPACITY),
+                // maybe they want extra buckets.
+                buckets);
+
+        if (mappings > 0) {
+            inflateTable(mappingsCapacity);
+        } else {
+            threshold = mappingsCapacity;
         }
 
-        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")