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 **** /* ! * 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
*** 127,137 **** { /** * The default initial capacity - MUST be a power of two. */ ! static final int DEFAULT_INITIAL_CAPACITY = 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. --- 127,137 ---- { /** * The default initial capacity - MUST be a power of two. */ ! 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,162 **** * 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; /** ! * The next size value at which to resize (capacity * load factor). * @serial */ int threshold; /** --- 142,169 ---- * 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; /** ! * 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,238 **** 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]; init(); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial --- 228,239 ---- initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; ! threshold = initialCapacity; init(); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial
*** 263,275 **** --- 264,299 ---- * @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,312 **** --- 327,337 ---- /** * 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,376 **** --- 392,405 ---- * 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. * --- 408,417 ----
*** 393,402 **** --- 421,433 ---- * <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,536 **** --- 558,571 ---- 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,580 **** --- 606,618 ---- * 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,613 **** /** * 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; Map.Entry<?,?> entry = (Map.Entry<?,?>) o; Object key = entry.getKey(); int hash = (key == null) ? 0 : hash(key); --- 641,651 ---- /** * Special version of remove for EntrySet using {@code Map.Entry.equals()} * for matching. */ final Entry<K,V> removeMapping(Object o) { ! 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,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 --- 677,687 ---- * 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 **** --- 690,703 ---- * @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); --- 731,743 ---- 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(); } --- 789,799 ---- } return false; } public final int hashCode() { ! return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); }
*** 1015,1032 **** * 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); // Write out keys and values (alternating) --- 1056,1074 ---- * 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(roundUpToPowerOf2(threshold)); + } else { s.writeInt(table.length); + } // Write out size (number of Mappings) s.writeInt(size); // Write out keys and values (alternating)
*** 1047,1090 **** 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") --- 1089,1141 ---- 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 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); + } ! bucketsCapacity = roundUpToPowerOf2(bucketsCapacity); // Read number of mappings int mappings = s.readInt(); if (mappings < 0) throw new InvalidObjectException("Illegal mappings count: " + mappings); ! // 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); ! ! // 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; } 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")