src/share/classes/java/util/IdentityHashMap.java
Print this page
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 2014, 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
@@ -72,11 +72,11 @@
* this parameter is used to determine the number of buckets initially
* comprising the hash table. The precise relationship between the expected
* maximum size and the number of buckets is unspecified.
*
* <p>If the size of the map (the number of key-value mappings) sufficiently
- * exceeds the expected maximum size, the number of buckets is increased
+ * exceeds the expected maximum size, the number of buckets is increased.
* Increasing the number of buckets ("rehashing") may be fairly expensive, so
* it pays to create identity hash maps with a sufficiently large expected
* maximum size. On the other hand, iteration over collection views requires
* time proportional to the number of buckets in the hash table, so it
* pays not to set the expected maximum size too high if you are especially
@@ -158,10 +158,14 @@
/**
* 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<<29.
+ *
+ * In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
+ * because it has to have at least one slot with the key == null
+ * in order to avoid infinite loops in get(), put(), remove()
*/
private static final int MAXIMUM_CAPACITY = 1 << 29;
/**
* The table, resized as necessary. Length MUST always be a power of two.
@@ -179,15 +183,10 @@
* The number of modifications, to support fast-fail iterators
*/
transient int modCount;
/**
- * The next size value at which to resize (capacity * load factor).
- */
- private transient int threshold;
-
- /**
* Value representing null keys inside tables.
*/
static final Object NULL_KEY = new Object();
/**
@@ -227,31 +226,23 @@
+ expectedMaxSize);
init(capacity(expectedMaxSize));
}
/**
- * Returns the appropriate capacity for the specified expected maximum
- * size. Returns the smallest power of two between MINIMUM_CAPACITY
- * and MAXIMUM_CAPACITY, inclusive, that is greater than
- * (3 * expectedMaxSize)/2, if such a number exists. Otherwise
- * returns MAXIMUM_CAPACITY. If (3 * expectedMaxSize)/2 is negative, it
- * is assumed that overflow has occurred, and MAXIMUM_CAPACITY is returned.
- */
- private int capacity(int expectedMaxSize) {
- // Compute min capacity for expectedMaxSize given a load factor of 2/3
- int minCapacity = (3 * expectedMaxSize)/2;
-
- // Compute the appropriate capacity
- int result;
- if (minCapacity > MAXIMUM_CAPACITY || minCapacity < 0) {
- result = MAXIMUM_CAPACITY;
- } else {
- result = MINIMUM_CAPACITY;
- while (result < minCapacity)
- result <<= 1;
- }
- return result;
+ * Returns the appropriate capacity for the given expected maximum size.
+ * Returns the smallest power of two between MINIMUM_CAPACITY and
+ * MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
+ * expectedMaxSize)/2, if such a number exists. Otherwise returns
+ * MAXIMUM_CAPACITY. If (3 * expectedMaxSize) is negative, it is assumed
+ * that overflow has occurred, and MAXIMUM_CAPACITY is returned.
+ */
+ private static int capacity(int expectedMaxSize) {
+ // assert expectedMaxSize >= 0;
+ return
+ (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
+ (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
+ Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
}
/**
* Initializes object to be an empty map with the specified initial
* capacity, which is assumed to be a power of two between
@@ -260,11 +251,10 @@
private void init(int initCapacity) {
// assert (initCapacity & -initCapacity) == initCapacity; // power of 2
// assert initCapacity >= MINIMUM_CAPACITY;
// assert initCapacity <= MAXIMUM_CAPACITY;
- threshold = (initCapacity * 2)/3;
table = new Object[2 * initCapacity];
}
/**
* Constructs a new identity hash map containing the keys-value mappings
@@ -443,40 +433,48 @@
return oldValue;
}
i = nextKeyIndex(i, len);
}
+ if (size == MAXIMUM_CAPACITY - 1)
+ throw new IllegalStateException("Capacity exhausted.");
+
+ int x = size + (size << 1) + 3; // Optimized form of 3 * (size + 1)
+ if (x > len) {
+ if (resize(len)) { // len == 2 * current capacity.
+ tab = table;
+ len = tab.length;
+ i = hash(key, len);
+ while (tab[i] != null)
+ i = nextKeyIndex(i, len);
+ }
modCount++;
tab[i] = k;
tab[i + 1] = value;
- if (++size >= threshold)
- resize(len); // len == 2 * current capacity.
+ size++;
+ }
return null;
}
/**
* Resize the table to hold given capacity.
*
* @param newCapacity the new capacity, must be a power of two.
*/
- private void resize(int newCapacity) {
+ private boolean resize(int newCapacity) {
// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
int newLength = newCapacity * 2;
Object[] oldTable = table;
int oldLength = oldTable.length;
- if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
- if (threshold == MAXIMUM_CAPACITY-1)
- throw new IllegalStateException("Capacity exhausted.");
- threshold = MAXIMUM_CAPACITY-1; // Gigantic map!
- return;
+ if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
+ return false;
}
if (oldLength >= newLength)
- return;
+ return false;
Object[] newTable = new Object[newLength];
- threshold = newLength / 3;
for (int j = 0; j < oldLength; j += 2) {
Object key = oldTable[j];
if (key != null) {
Object value = oldTable[j+1];
@@ -488,10 +486,11 @@
newTable[i] = key;
newTable[i + 1] = value;
}
}
table = newTable;
+ return true;
}
/**
* Copies all of the mappings from the specified map to this map.
* These mappings will replace any mappings that this map had for
@@ -502,11 +501,11 @@
*/
public void putAll(Map<? extends K, ? extends V> m) {
int n = m.size();
if (n == 0)
return;
- if (n > threshold) // conservatively pre-expand
+ if (n + (n << 1) > table.length) // conservatively pre-expand
resize(capacity(n));
for (Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
@@ -540,11 +539,10 @@
}
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
-
}
/**
* Removes the specified key-value mapping from the map if it is present.
*
@@ -1304,12 +1302,11 @@
s.defaultReadObject();
// Read in size (number of Mappings)
int size = s.readInt();
- // Allow for 33% growth (i.e., capacity is >= 2* size()).
- init(capacity((size*4)/3));
+ init(capacity(size));
// Read the keys and values, and put the mappings in the table
for (int i=0; i<size; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();