/* * @(#)IdentityHashMap.java 1.23 05/09/02 * * Copyright 2004 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; import java.io.*; /** * This class implements the Map interface with a hash table, using * reference-equality in place of object-equality when comparing keys (and * values). In other words, in an IdentityHashMap, two keys * k1 and k2 are considered equal if and only if * (k1==k2). (In normal Map implementations (like * HashMap) two keys k1 and k2 are considered equal * if and only if (k1==null ? k2==null : k1.equals(k2)).) * *
This class is not a general-purpose Map * implementation! While this class implements the Map interface, it * intentionally violates Map's general contract, which mandates the * use of the equals method when comparing objects. This class is * designed for use only in the rare cases wherein reference-equality * semantics are required. * *
A typical use of this class is topology-preserving object graph * transformations, such as serialization or deep-copying. To perform such * a transformation, a program must maintain a "node table" that keeps track * of all the object references that have already been processed. The node * table must not equate distinct objects even if they happen to be equal. * Another typical use of this class is to maintain proxy objects. For * example, a debugging facility might wish to maintain a proxy object for * each object in the program being debugged. * *
This class provides all of the optional map operations, and permits * null values and the null key. This class makes no * guarantees as to the order of the map; in particular, it does not guarantee * that the order will remain constant over time. * *
This class provides constant-time performance for the basic * operations (get and put), assuming the system * identity hash function ({@link System#identityHashCode(Object)}) * disperses elements properly among the buckets. * *
This class has one tuning parameter (which affects performance but not * semantics): expected maximum size. This parameter is the maximum * number of key-value mappings that the map is expected to hold. Internally, * 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. * *
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 * concerned with iteration performance or memory usage. * *
Note that this implementation is not synchronized. If multiple * threads access this map concurrently, and at least one of the threads * modifies the map structurally, it must be synchronized externally. * (A structural modification is any operation that adds or deletes one or * more mappings; merely changing the value associated with a key that an * instance already contains is not a structural modification.) This is * typically accomplished by synchronizing on some object that naturally * encapsulates the map. If no such object exists, the map should be * "wrapped" using the Collections.synchronizedMap method. This is * best done at creation time, to prevent accidental unsynchronized access to * the map:
* Map m = Collections.synchronizedMap(new HashMap(...)); ** *
The iterators returned by all of this class's "collection view methods" * are fail-fast: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own * remove or add methods, the iterator will throw a * ConcurrentModificationException. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the * future. * *
Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw ConcurrentModificationException on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: fail-fast iterators should be used only * to detect bugs. * *
Implementation note: This is a simple linear-probe hash table, * as described for example in texts by Sedgewick and Knuth. The array * alternates holding keys and values. (This has better locality for large * tables than does using separate arrays.) For many JRE implementations * and operation mixes, this class will yield better performance than * {@link HashMap} (which uses chaining rather than linear-probing). * *
This class is a member of the
*
* Java Collections Framework.
*
* @see System#identityHashCode(Object)
* @see Object#hashCode()
* @see Collection
* @see Map
* @see HashMap
* @see TreeMap
* @author Doug Lea and Josh Bloch
* @since 1.4
*/
public class IdentityHashMap
*
* @param t mappings to be stored in this map.
* @throws NullPointerException if the specified map is null.
*/
public void putAll(Map extends K, ? extends V> t) {
int n = t.size();
if (n == 0)
return;
if (n > threshold) // conservatively pre-expand
resize(capacity(n));
for (Entry extends K, ? extends V> e : t.entrySet())
put(e.getKey(), e.getValue());
}
/**
* Removes the mapping for this key from this map if present.
*
* @param key key whose mapping is to be removed from the map.
* @return previous value associated with specified key, or null
* if there was no entry for key. (A null return can
* also indicate that the map previously associated null
* with the specified key.)
*/
public V remove(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
while (true) {
Object item = tab[i];
if (item == k) {
modCount++;
size--;
V oldValue = (V) tab[i + 1];
tab[i + 1] = null;
tab[i] = null;
closeDeletion(i);
return oldValue;
}
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}
/**
* Removes the specified key-value mapping from the map if it is present.
*
* @param key possible key.
* @param value possible value.
* @return Owing to the reference-equality-based semantics of this map it is
* possible that the symmetry and transitivity requirements of the
* Object.equals contract may be violated if this map is compared
* to a normal map. However, the Object.equals contract is
* guaranteed to hold among IdentityHashMap instances.
*
* @param o object to be compared for equality with this map.
* @return true if the specified object is equal to this map.
* @see Object#equals(Object)
*/
public boolean equals(Object o) {
if (o == this) {
return true;
} else if (o instanceof IdentityHashMap) {
IdentityHashMap m = (IdentityHashMap) o;
if (m.size() != size)
return false;
Object[] tab = m.table;
for (int i = 0; i < tab.length; i+=2) {
Object k = tab[i];
if (k != null && !containsMapping(k, tab[i + 1]))
return false;
}
return true;
} else if (o instanceof Map) {
Map m = (Map)o;
return entrySet().equals(m.entrySet());
} else {
return false; // o is not a Map
}
}
/**
* Returns the hash code value for this map. The hash code of a map
* is defined to be the sum of the hashcode of each entry in the map's
* entrySet view. This ensures that t1.equals(t2) implies
* that t1.hashCode()==t2.hashCode() for any two
* IdentityHashMap instances t1 and t2, as
* required by the general contract of {@link Object#hashCode()}.
*
* Owing to the reference-equality-based semantics of the
* Map.Entry instances in the set returned by this map's
* entrySet method, it is possible that the contractual
* requirement of Object.hashCode mentioned in the previous
* paragraph will be violated if one of the two objects being compared is
* an IdentityHashMap instance and the other is a normal map.
*
* @return the hash code value for this map.
* @see Object#hashCode()
* @see Object#equals(Object)
* @see #equals(Object)
*/
public int hashCode() {
int result = 0;
Object[] tab = table;
for (int i = 0; i < tab.length; i +=2) {
Object key = tab[i];
if (key != null) {
Object k = unmaskNull(key);
result += System.identityHashCode(k) ^
System.identityHashCode(tab[i + 1]);
}
}
return result;
}
/**
* Returns a shallow copy of this identity hash map: the keys and values
* themselves are not cloned.
*
* @return a shallow copy of this map.
*/
public Object clone() {
try {
IdentityHashMap While the object returned by this method implements the
* Set interface, it does not obey Set's general
* contract. Like its backing map, the set returned by this method
* defines element equality as reference-equality rather than
* object-equality. This affects the behavior of its contains,
* remove, containsAll, equals, and
* hashCode methods.
*
* The equals method of the returned set returns true
* only if the specified object is a set containing exactly the same
* object references as the returned set. The symmetry and transitivity
* requirements of the Object.equals contract may be violated if
* the set returned by this method is compared to a normal set. However,
* the Object.equals contract is guaranteed to hold among sets
* returned by this method.
*
* The hashCode method of the returned set returns the sum of
* the identity hashcodes of the elements in the set, rather than
* the sum of their hashcodes. This is mandated by the change in the
* semantics of the equals method, in order to enforce the
* general contract of the Object.hashCode method among sets
* returned by this method.
*
* @return an identity-based set view of the keys contained in this map.
* @see Object#equals(Object)
* @see System#identityHashCode(Object)
*/
public Set Returns a collection view of the values contained in this map. The
* collection is backed by the map, so changes to the map are reflected in
* the collection, and vice-versa. If the map is modified while an
* iteration over the collection is in progress, the results of the
* iteration are undefined. The collection supports element removal,
* which removes the corresponding mapping from the map, via the
* Iterator.remove, Collection.remove,
* removeAll, retainAll and clear methods.
* It does not support the add or addAll methods.
*
* While the object returned by this method implements the
* Collection interface, it does not obey
* Collection's general contract. Like its backing map,
* the collection returned by this method defines element equality as
* reference-equality rather than object-equality. This affects the
* behavior of its contains, remove and
* containsAll methods.
*
* @return a collection view of the values contained in this map.
*/
public Collection Like the backing map, the Map.Entry objects in the set
* returned by this method define key and value equality as
* reference-equality rather than object-equality. This affects the
* behavior of the equals and hashCode methods of these
* Map.Entry objects. A reference-equality based Map.Entry
* e is equal to an object o if and only if o is a
* Map.Entry and e.getKey()==o.getKey() &&
* e.getValue()==o.getValue(). To accommodate these equals
* semantics, the hashCode method returns
* System.identityHashCode(e.getKey()) ^
* System.identityHashCode(e.getValue()).
*
* Owing to the reference-equality-based semantics of the
* Map.Entry instances in the set returned by this method,
* it is possible that the symmetry and transitivity requirements of
* the {@link Object#equals(Object)} contract may be violated if any of
* the entries in the set is compared to a normal map entry, or if
* the set returned by this method is compared to a set of normal map
* entries (such as would be returned by a call to this method on a normal
* map). However, the Object.equals contract is guaranteed to
* hold among identity-based map entries, and among sets of such entries.
*
*
* @return a set view of the identity-mappings contained in this map.
*/
public Settrue
if the specified object reference is a key
* in this map.
* @see #containsValue(Object)
*/
public boolean containsKey(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
while (true) {
Object item = tab[i];
if (item == k)
return true;
if (item == null)
return false;
i = nextKeyIndex(i, len);
}
}
/**
* Tests whether the specified object reference is a value in this identity
* hash map.
*
* @param value value whose presence in this map is to be tested.
* @return true if this map maps one or more keys to the
* specified object reference.
* @see #containsKey(Object)
*/
public boolean containsValue(Object value) {
Object[] tab = table;
for (int i = 1; i < tab.length; i+= 2)
if (tab[i] == value)
return true;
return false;
}
/**
* Tests if the specified key-value mapping is in the map.
*
* @param key possible key.
* @param value possible value.
* @return true
if and only if the specified key-value
* mapping is in map.
*/
private boolean containsMapping(Object key, Object value) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
while (true) {
Object item = tab[i];
if (item == k)
return tab[i + 1] == value;
if (item == null)
return false;
i = nextKeyIndex(i, len);
}
}
/**
* Associates the specified value with the specified key in this identity
* hash map. If the map previously contained a mapping for this key, the
* old value is replaced.
*
* @param key the key with which the specified value is to be associated.
* @param value the value to be associated with the specified key.
* @return the previous value associated with key, or
* null if there was no mapping for key. (A
* null return can also indicate that the map previously
* associated null with the specified key.)
* @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) {
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];
oldTable[j] = null;
oldTable[j+1] = null;
int i = hash(key, newLength);
while (newTable[i] != null)
i = nextKeyIndex(i, newLength);
newTable[i] = key;
newTable[i + 1] = value;
}
}
table = newTable;
}
/**
* Copies all of the mappings from the specified map to this map
* These mappings will replace any mappings that
* this map had for any of the keys currently in the specified map.true
if and only if the specified key-value
* mapping was in map.
*/
private boolean removeMapping(Object key, Object value) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
while (true) {
Object item = tab[i];
if (item == k) {
if (tab[i + 1] != value)
return false;
modCount++;
size--;
tab[i] = null;
tab[i + 1] = null;
closeDeletion(i);
return true;
}
if (item == null)
return false;
i = nextKeyIndex(i, len);
}
}
/**
* Rehash all possibly-colliding entries following a
* deletion. This preserves the linear-probe
* collision properties required by get, put, etc.
*
* @param d the index of a newly empty deleted slot
*/
private void closeDeletion(int d) {
// Adapted from Knuth Section 6.4 Algorithm R
Object[] tab = table;
int len = tab.length;
// Look for items to swap into newly vacated slot
// starting at index immediately following deletion,
// and continuing until a null slot is seen, indicating
// the end of a run of possibly-colliding keys.
Object item;
for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
i = nextKeyIndex(i, len) ) {
// The following test triggers if the item at slot i (which
// hashes to be at slot r) should take the spot vacated by d.
// If so, we swap it in, and then continue with d now at the
// newly vacated i. This process will terminate when we hit
// the null slot at the end of this run.
// The test is messy because we are using a circular table.
int r = hash(item, len);
if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
tab[d] = item;
tab[d + 1] = tab[i + 1];
tab[i] = null;
tab[i + 1] = null;
d = i;
}
}
}
/**
* Removes all mappings from this map.
*/
public void clear() {
modCount++;
Object[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}
/**
* Compares the specified object with this map for equality. Returns
* true if the given object is also a map and the two maps
* represent identical object-reference mappings. More formally, this
* map is equal to another map m if and only if
* map this.entrySet().equals(m.entrySet()).
*
*