Class IdentityHashMap<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
java.util.IdentityHashMap<K,V>
Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values
All Implemented Interfaces:
Serializable,Cloneable,Map<K,V>
public classIdentityHashMap<K,V>extendsAbstractMap<K,V>implementsMap<K,V>,Serializable,Cloneable
This class implements theMap interface with a hash table, using reference-equality in place of object-equality when comparing keys (and values). In other words, in anIdentityHashMap, two keysk1 andk2 are considered equal if and only if(k1==k2). (In normalMap implementations (likeHashMap) two keysk1 andk2 are considered equal if and only if(k1==null ? k2==null : k1.equals(k2)).)

This class isnot a general-purposeMap implementation! While this class implements theMap interface, it intentionally violatesMap's general contract, which mandates the use of theequals method when comparing objects. This class is designed for use only in the rare cases wherein reference-equality semantics are required.

The view collections of this map also have reference-equality semantics for their elements. See thekeySet,values, andentrySet methods for further information.

A typical use of this class istopology-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 maintainproxy 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 permitsnull values and thenull 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 andput), assuming the system identity hash function (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, itmust 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 theCollections.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 theiterator method of the collections returned by all of this class's "collection view methods" arefail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's ownremove method, the iterator will throw aConcurrentModificationException. 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 throwConcurrentModificationException 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.

This class is a member of the Java Collections Framework.

Implementation Note:

This is a simplelinear-probe hash table, as described for example in texts by Sedgewick and Knuth. The array contains alternating keys and values, with keys at even indexes and values at odd indexes. (This arrangement has better locality for large tables than does using separate arrays.) For many Java implementations and operation mixes, this class will yield better performance thanHashMap, which useschaining rather than linear-probing.

Since:
1.4
See Also:

  • Nested Class Summary

    Nested classes/interfaces declared in class java.util.AbstractMap

    AbstractMap.SimpleEntry<K,V>,AbstractMap.SimpleImmutableEntry<K,V>

    Nested classes/interfaces declared in interface java.util.Map

    Map.Entry<K,V>

  • Constructor Summary

    Constructors
    Constructor
    Description
    Constructs a new, empty identity hash map with a default expected maximum size (21).
    IdentityHashMap(int expectedMaxSize)
    Constructs a new, empty map with the specified expected maximum size.
    IdentityHashMap(Map<? extendsK, ? extendsV> m)
    Constructs a new identity hash map containing the key-value mappings in the specified map.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    Removes all of the mappings from this map.
    Returns a shallow copy of this identity hash map: the keys and values themselves are not cloned.
    boolean
    Tests whether the specified object reference is a key in this identity hash map.
    boolean
    Tests whether the specified object reference is a value in this identity hash map.
    Returns aSet view of the mappings contained in this map.
    boolean
    Compares the specified object with this map for equality.
    get(Object key)
    Returns the value to which the specified key is mapped, ornull if this map contains no mapping for the key.
    int
    Returns the hash code value for this map.
    boolean
    Returnstrue if this identity hash map contains no key-value mappings.
    Returns an identity-based set view of the keys contained in this map.
    put(K key,V value)
    Associates the specified value with the specified key in this identity hash map.
    void
    putAll(Map<? extendsK, ? extendsV> m)
    Copies all of the mappings from the specified map to this map.
    Removes the mapping for this key from this map if present.
    boolean
    remove(Object key,Object value)
    Removes the entry for the specified key only if it is currently mapped to the specified value (optional operation).
    boolean
    replace(K key,V oldValue,V newValue)
    Replaces the entry for the specified key only if currently mapped to the specified value (optional operation).
    int
    Returns the number of key-value mappings in this identity hash map.
    Returns aCollection view of the values contained in this map.

    Methods declared in class java.util.AbstractMap

    toString

    Methods declared in class java.lang.Object

    finalize,getClass,notify,notifyAll,wait,wait,wait

  • Constructor Details

    • IdentityHashMap

      public IdentityHashMap()
      Constructs a new, empty identity hash map with a default expected maximum size (21).

    • IdentityHashMap

      public IdentityHashMap(int expectedMaxSize)
      Constructs a new, empty map with the specified expected maximum size. Putting more than the expected number of key-value mappings into the map may cause the internal data structure to grow, which may be somewhat time-consuming.
      Parameters:
      expectedMaxSize - the expected maximum size of the map
      Throws:
      IllegalArgumentException - ifexpectedMaxSize is negative

    • IdentityHashMap

      public IdentityHashMap(Map<? extendsK, ? extendsV> m)
      Constructs a new identity hash map containing the key-value mappings in the specified map.
      Parameters:
      m - the map whose mappings are to be placed into this map
      Throws:
      NullPointerException - if the specified map is null

  • Method Details

    • size

      public int size()
      Returns the number of key-value mappings in this identity hash map.
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class AbstractMap<K,V>
      Returns:
      the number of key-value mappings in this map

    • isEmpty

      public boolean isEmpty()
      Returnstrue if this identity hash map contains no key-value mappings.
      Specified by:
      isEmpty in interface Map<K,V>
      Overrides:
      isEmpty in class AbstractMap<K,V>
      Returns:
      true if this identity hash map contains no key-value mappings

    • get

      public V get(Object key)
      Returns the value to which the specified key is mapped, ornull if this map contains no mapping for the key.

      More formally, if this map contains a mapping from a keyk to a valuev such that(key == k), then this method returnsv; otherwise it returnsnull. (There can be at most one such mapping.)

      A return value ofnull does notnecessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key tonull. ThecontainsKey operation may be used to distinguish these two cases.

      Specified by:
      get in interface Map<K,V>
      Overrides:
      get in class AbstractMap<K,V>
      Parameters:
      key - the key whose associated value is to be returned
      Returns:
      the value to which the specified key is mapped, ornull if this map contains no mapping for the key
      See Also:

    • containsKey

      public boolean containsKey(Object key)
      Tests whether the specified object reference is a key in this identity hash map. Returnstrue if and only if this map contains a mapping with keyk such that(key == k).
      Specified by:
      containsKey in interface Map<K,V>
      Overrides:
      containsKey in class AbstractMap<K,V>
      Parameters:
      key - possible key
      Returns:
      true if the specified object reference is a key in this map
      See Also:

    • containsValue

      public boolean containsValue(Object value)
      Tests whether the specified object reference is a value in this identity hash map. Returnstrue if and only if this map contains a mapping with valuev such that(value == v).
      Specified by:
      containsValue in interface Map<K,V>
      Overrides:
      containsValue in class AbstractMap<K,V>
      Parameters:
      value - value whose presence in this map is to be tested
      Returns:
      true if this map maps one or more keys to the specified object reference
      See Also:

    • put

      public V put(K key,V value)
      Associates the specified value with the specified key in this identity hash map. If this map alreadycontains a mapping for the key, the old value is replaced, otherwise, a new mapping is inserted into this map.
      Specified by:
      put in interface Map<K,V>
      Overrides:
      put in class AbstractMap<K,V>
      Parameters:
      key - the key with which the specified value is to be associated
      value - the value to be associated with the specified key
      Returns:
      the previous value associated withkey, ornull if there was no mapping forkey. (Anull return can also indicate that the map previously associatednull withkey.)
      See Also:

    • putAll

      public void putAll(Map<? extendsK, ? extendsV> m)
      Copies all of the mappings from the specified map to this map. For each mapping in the specified map, if this map alreadycontains a mapping for the key, its value is replaced with the value from the specified map; otherwise, a new mapping is inserted into this map.
      Specified by:
      putAll in interface Map<K,V>
      Overrides:
      putAll in class AbstractMap<K,V>
      Parameters:
      m - mappings to be stored in this map
      Throws:
      NullPointerException - if the specified map is null

    • remove

      public V remove(Object key)
      Removes the mapping for this key from this map if present. The mapping is removed if and only if the mapping has a keyk such that (key == k).
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class AbstractMap<K,V>
      Parameters:
      key - key whose mapping is to be removed from the map
      Returns:
      the previous value associated withkey, ornull if there was no mapping forkey. (Anull return can also indicate that the map previously associatednull withkey.)

    • clear

      public void clear()
      Removes all of the mappings from this map. The map will be empty after this call returns.
      Specified by:
      clear in interface Map<K,V>
      Overrides:
      clear in class AbstractMap<K,V>

    • equals

      public boolean equals(Object o)
      Compares the specified object with this map for equality. Returnstrue 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 mapm if and only ifthis.entrySet().equals(m.entrySet()). See theentrySet method for the specification of equality of this map's entries.

      Owing to the reference-equality-based semantics of this map it is possible that the symmetry and transitivity requirements of theObject.equals contract may be violated if this map is compared to a normal map. However, theObject.equals contract is guaranteed to hold amongIdentityHashMap instances.

      Specified by:
      equals in interface Map<K,V>
      Overrides:
      equals in class AbstractMap<K,V>
      Parameters:
      o - object to be compared for equality with this map
      Returns:
      true if the specified object is equal to this map
      See Also:

    • hashCode

      public int hashCode()
      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 of this map. See theentrySet method for a specification of the hash code of this map's entries.

      This specification ensures thatm1.equals(m2) implies thatm1.hashCode()==m2.hashCode() for any twoIdentityHashMap instancesm1 andm2, as required by the general contract ofObject.hashCode().

      Owing to the reference-equality-based semantics of theMap.Entry instances in the set returned by this map'sentrySet method, it is possible that the contractual requirement ofObject.hashCode mentioned in the previous paragraph will be violated if one of the two objects being compared is anIdentityHashMap instance and the other is a normal map.

      Specified by:
      hashCode in interface Map<K,V>
      Overrides:
      hashCode in class AbstractMap<K,V>
      Returns:
      the hash code value for this map
      See Also:

    • clone

      public Object clone()
      Returns a shallow copy of this identity hash map: the keys and values themselves are not cloned.
      Overrides:
      clone in class AbstractMap<K,V>
      Returns:
      a shallow copy of this map
      See Also:

    • keySet

      public Set<K> keySet()
      Returns an identity-based set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via theIterator.remove,Set.remove,removeAll,retainAll, andclear methods. It does not support theadd oraddAll methods.

      While the object returned by this method implements theSet interface, it doesnot obeySet'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 itscontains,remove,containsAll,equals, andhashCode methods.

      Theequals method of the returned set returnstrue only if the specified object is a set containing exactly the same object references as the returned set. The symmetry and transitivity requirements of theObject.equals contract may be violated if the set returned by this method is compared to a normal set. However, theObject.equals contract is guaranteed to hold among sets returned by this method.

      ThehashCode method of the returned set returns the sum of theidentity hashcodes of the elements in the set, rather than the sum of their hashcodes. This is mandated by the change in the semantics of theequals method, in order to enforce the general contract of theObject.hashCode method among sets returned by this method.

      Specified by:
      keySet in interface Map<K,V>
      Overrides:
      keySet in class AbstractMap<K,V>
      Returns:
      an identity-based set view of the keys contained in this map
      See Also:

    • values

      public Collection<V> values()
      Returns aCollection 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 theIterator.remove,Collection.remove,removeAll,retainAll andclear methods. It does not support theadd oraddAll methods.

      While the object returned by this method implements theCollection interface, it doesnot obeyCollection'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 itscontains,remove andcontainsAll methods.

      Specified by:
      values in interface Map<K,V>
      Overrides:
      values in class AbstractMap<K,V>
      Returns:
      a collection view of the values contained in this map

    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      Returns aSet view of the mappings contained in this map. Each element in the returned set is a reference-equality-basedMap.Entry. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via theIterator.remove,Set.remove,removeAll,retainAll andclear methods. It does not support theadd oraddAll methods.

      Like the backing map, theMap.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 theequals andhashCode methods of theseMap.Entry objects. A reference-equality basedMap.Entry e is equal to an objecto if and only ifo is aMap.Entry ande.getKey()==o.getKey() && e.getValue()==o.getValue(). To accommodate these equals semantics, thehashCode method returnsSystem.identityHashCode(e.getKey()) ^ System.identityHashCode(e.getValue()). (While the keys and values are compared using reference equality, theMap.Entry objects themselves are not.)

      Owing to the reference-equality-based semantics of theMap.Entry instances in the set returned by this method, it is possible that the symmetry and transitivity requirements of theObject.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, theObject.equals contract is guaranteed to hold among identity-based map entries, and among sets of such entries.

      Specified by:
      entrySet in interface Map<K,V>
      Returns:
      a set view of the identity-mappings contained in this map

    • remove

      public boolean remove(Object key,Object value)
      Removes the entry for the specified key only if it is currently mapped to the specified value (optional operation).

      More formally, if this map contains a mapping from a keyk to a valuev such that(key == k) and(value == v), then this method removes the mapping for this key and returnstrue; otherwise it returnsfalse.

      Specified by:
      remove in interface Map<K,V>
      Parameters:
      key - key with which the specified value is associated
      value - value expected to be associated with the specified key
      Returns:
      true if the value was removed

    • replace

      public boolean replace(K key,V oldValue,V newValue)
      Replaces the entry for the specified key only if currently mapped to the specified value (optional operation).

      More formally, if this map contains a mapping from a keyk to a valuev such that(key == k) and(oldValue == v), then this method associatesk withnewValue and returnstrue; otherwise it returnsfalse.

      Specified by:
      replace in interface Map<K,V>
      Parameters:
      key - key with which the specified value is associated
      oldValue - value expected to be associated with the specified key
      newValue - value to be associated with the specified key
      Returns:
      true if the value was replaced