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 an identity hash 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 + * {@link Collections#synchronizedMap Collections.synchronizedMap} + * method. This is best done at creation time, to prevent accidental + * unsynchronized access to the map:
+ * Map m = Collections.synchronizedMap(new IdentityHashMap(...));+ * + *
The iterators returned by the iterator method of the + * collections 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 method, the iterator + * will throw a {@link 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 More formally, if this map contains a mapping from a key
+ * {@code k} to a value {@code v} such that {@code (key == k)},
+ * then this method returns {@code v}; otherwise it returns
+ * {@code null}. (There can be at most one such mapping.)
+ *
+ * A return value of {@code null} does not necessarily
+ * indicate that the map contains no mapping for the key; it's also
+ * possible that the map explicitly maps the key to {@code null}.
+ * The {@link #containsKey containsKey} operation may be used to
+ * distinguish these two cases.
+ *
+ * @see #put(Object, Object)
+ */
+ public V get(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 (V) tab[i + 1];
+ if (item == null)
+ return null;
+ i = nextKeyIndex(i, len);
+ }
+ }
+
+ /**
+ * Tests whether the specified object reference is a key in this identity
+ * hash map.
+ *
+ * @param key possible key
+ * @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 hash codes of each entry in the map's
+ * entrySet() view. This ensures that m1.equals(m2)
+ * implies that m1.hashCode()==m2.hashCode() for any two
+ * IdentityHashMap instances m1 and m2, 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#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 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.
+ */
+ 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 && tab[i - 1] != null)
+ 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 the 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 the 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 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.
+ *
+ * @param m mappings to be stored in this map
+ * @throws NullPointerException if the specified map is null
+ */
+ public void putAll(Map m) {
+ int n = m.size();
+ if (n == 0)
+ return;
+ if (n > threshold) // conservatively pre-expand
+ resize(capacity(n));
+
+ for (Entry e : m.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 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 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 true if and only if the specified key-value
+ * mapping was in the 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 of the mappings from this map.
+ * The map will be empty after this call returns.
+ */
+ 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
+ * this.entrySet().equals(m.entrySet()).
+ *
+ *