src/share/classes/java/util/IdentityHashMap.java
Print this page
*** 1,7 ****
/*
! * Copyright (c) 2000, 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
--- 1,7 ----
/*
! * 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
*** 23,33 ****
* questions.
*/
package java.util;
- import java.io.*;
import java.lang.reflect.Array;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
--- 23,32 ----
*** 72,82 ****
* 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
* 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
--- 71,81 ----
* 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.
* 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
*** 155,172 ****
* MUST be a power of two.
*/
private static final int MINIMUM_CAPACITY = 4;
/**
! * 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.
*/
! private static final int MAXIMUM_CAPACITY = 1 << 29;
/**
! * The table, resized as necessary. Length MUST always be a power of two.
*/
transient Object[] table; // non-private to simplify nested class access
/**
* The number of key-value mappings contained in this identity hash map.
--- 154,180 ----
* MUST be a power of two.
*/
private static final int MINIMUM_CAPACITY = 4;
/**
! * The maximum capacity (1 << 29) + (1 << 28), used if a higher value
! * is implicitly specified by either of the constructors with arguments.
! * MAXIMUM_CAPACITY / 3 must be an integer and power of two.
*/
! private static final int MAXIMUM_CAPACITY = (1 << 29) + (1 << 28);
/**
! * The map can hold no more than MAXIMUM_SIZE items
! * because performance degrades if size grows much over 66% of capacity.
! * (because of serialization compatibility with older versions, we can
! * not hold more than (1 << 29) - 1 elements)
! */
! private static final int MAXIMUM_SIZE = (1 << 29) - 1;
!
! /**
! * The table, resized as necessary. Length MUST always be a power of two
! * or 2 * MAXIMUM_CAPACITY
*/
transient Object[] table; // non-private to simplify nested class access
/**
* The number of key-value mappings contained in this identity hash map.
*** 179,193 ****
* 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();
/**
--- 187,196 ----
*** 227,270 ****
+ 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;
}
/**
* Initializes object to be an empty map with the specified initial
* capacity, which is assumed to be a power of two between
* MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
*/
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
--- 230,270 ----
+ expectedMaxSize);
init(capacity(expectedMaxSize));
}
/**
! * 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;
! int capacity = Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
! return Math.min(
! MAXIMUM_CAPACITY,
! Math.max(
! MINIMUM_CAPACITY,
! capacity < 0 ? MAXIMUM_CAPACITY // overflow
! : capacity
! )
! );
}
/**
* Initializes object to be an empty map with the specified initial
* capacity, which is assumed to be a power of two between
* MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
*/
private void init(int initCapacity) {
! // assert initCapacity == MAXIMUM_CAPACITY ||
! // (initCapacity & -initCapacity) == initCapacity; // power of 2
// assert initCapacity >= MINIMUM_CAPACITY;
// assert initCapacity <= MAXIMUM_CAPACITY;
table = new Object[2 * initCapacity];
}
/**
* Constructs a new identity hash map containing the keys-value mappings
*** 302,320 ****
/**
* Returns index for Object x.
*/
private static int hash(Object x, int length) {
int h = System.identityHashCode(x);
! // Multiply by -127, and left-shift to use least bit as part of hash
! return ((h << 1) - (h << 8)) & (length - 1);
}
/**
* Circularly traverses table of size len.
*/
private static int nextKeyIndex(int i, int len) {
! return (i + 2 < len ? i + 2 : 0);
}
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
--- 302,330 ----
/**
* Returns index for Object x.
*/
private static int hash(Object x, int length) {
int h = System.identityHashCode(x);
! // multiply by -127
! h -= h << 7;
! if (length < MAXIMUM_CAPACITY * 2) { // length is 2^n
! // left-shift to use least bit as part of hash
! return (h << 1) & (length - 1);
! }
! // assert length == MAXIMUM_CAPACITY * 2
! // clamp
! h &= (MAXIMUM_CAPACITY / 3 * 4 - 1);
! // Multiply by 3/2 and reset 0th bit
! return (h + (h >> 1)) & ~1;
}
/**
* Circularly traverses table of size len.
*/
private static int nextKeyIndex(int i, int len) {
! int i2 = i + 2;
! return (i2 < len ? i2 : 0);
}
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*** 427,482 ****
* @see Object#equals(Object)
* @see #get(Object)
* @see #containsKey(Object)
*/
public V put(K key, V value) {
! Object k = maskNull(key);
! Object[] tab = table;
! int len = tab.length;
int i = hash(k, len);
! Object item;
! while ( (item = tab[i]) != null) {
if (item == k) {
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = value;
return oldValue;
}
- i = nextKeyIndex(i, len);
}
modCount++;
tab[i] = k;
tab[i + 1] = value;
! if (++size >= threshold)
! resize(len); // len == 2 * current capacity.
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) {
// 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 >= newLength)
! return;
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];
--- 437,498 ----
* @see Object#equals(Object)
* @see #get(Object)
* @see #containsKey(Object)
*/
public V put(K key, V value) {
! final Object k = maskNull(key);
!
! retryAfterResize: for (;;) {
! final Object[] tab = table;
! final int len = tab.length;
int i = hash(k, len);
! for (Object item; (item = tab[i]) != null;
! i = nextKeyIndex(i, len)) {
if (item == k) {
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = value;
return oldValue;
}
}
+ final int s = size + 1;
+ // Use optimized form of 3 * s.
+ // Next capacity is len, 2 * current capacity.
+ if (s + (s << 1) > len && resize(len))
+ continue retryAfterResize;
+
modCount++;
tab[i] = k;
tab[i + 1] = value;
! size = s;
return null;
}
+ }
/**
! * Resizes the table if necessary to hold given capacity.
*
* @param newCapacity the new capacity, must be a power of two.
+ * @return whether a resize did in fact take place
*/
! private boolean resize(int newCapacity) {
// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
Object[] oldTable = table;
int oldLength = oldTable.length;
! if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
! if (size == MAXIMUM_SIZE)
! throw new OutOfMemoryError("Capacity exhausted.");
! return false;
}
+ int newLength = Math.min(2 * MAXIMUM_CAPACITY, 2 * newCapacity);
if (oldLength >= newLength)
! return false;
Object[] newTable = new Object[newLength];
for (int j = 0; j < oldLength; j += 2) {
Object key = oldTable[j];
if (key != null) {
Object value = oldTable[j+1];
*** 488,497 ****
--- 504,514 ----
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,513 ****
*/
public void putAll(Map<? extends K, ? extends V> m) {
int n = m.size();
if (n == 0)
return;
! if (n > threshold) // conservatively pre-expand
! resize(capacity(n));
for (Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
--- 519,530 ----
*/
public void putAll(Map<? extends K, ? extends V> m) {
int n = m.size();
if (n == 0)
return;
! if (n > size)
! resize(capacity(n)); // conservatively pre-expand
for (Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
*** 540,550 ****
}
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
-
}
/**
* Removes the specified key-value mapping from the map if it is present.
*
--- 557,566 ----
*** 1264,1275 ****
private static final long serialVersionUID = 8188218128353913216L;
/**
! * Save the state of the <tt>IdentityHashMap</tt> instance to a stream
! * (i.e., serialize it).
*
* @serialData The <i>size</i> of the HashMap (the number of key-value
* mappings) (<tt>int</tt>), followed by the key (Object) and
* value (Object) for each key-value mapping represented by the
* IdentityHashMap. The key-value mappings are emitted in no
--- 1280,1291 ----
private static final long serialVersionUID = 8188218128353913216L;
/**
! * Saves the state of the <tt>IdentityHashMap</tt> instance to a stream
! * (i.e., serializes it).
*
* @serialData The <i>size</i> of the HashMap (the number of key-value
* mappings) (<tt>int</tt>), followed by the key (Object) and
* value (Object) for each key-value mapping represented by the
* IdentityHashMap. The key-value mappings are emitted in no
*** 1293,1315 ****
}
}
}
/**
! * Reconstitute the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
! * deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
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));
// 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();
--- 1309,1332 ----
}
}
}
/**
! * Reconstitutes the <tt>IdentityHashMap</tt> instance from a stream (i.e.,
! * deserializes it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden stuff
s.defaultReadObject();
// Read in size (number of Mappings)
int size = s.readInt();
! if (size < 0)
! throw new java.io.StreamCorruptedException
! ("Illegal mappings count: " + size);
! 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();
*** 1322,1332 ****
/**
* The put method for readObject. It does not resize the table,
* update modCount, etc.
*/
private void putForCreate(K key, V value)
! throws IOException
{
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
--- 1339,1349 ----
/**
* The put method for readObject. It does not resize the table,
* update modCount, etc.
*/
private void putForCreate(K key, V value)
! throws java.io.StreamCorruptedException
{
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);