☕ Java

IdentityHashMap

IdentityHashMap is a Map implementation that uses reference equality (==) instead of object equality (equals()) to compare keys. Two keys are considered equal only if they are the exact same object — if k1 == k2. This violates the general Map contract (which requires equals()-based comparison) intentionally, for specific use cases where object identity is meaningful. Common uses include object graph traversal, serialisation, and maintaining object-to-object mappings where distinct objects with equal values should map to different entries.

Reference Equality vs Object Equality in Maps

Every standard Map in Java (HashMap, LinkedHashMap, TreeMap) uses equals() to determine whether two keys are the same. This means two different String objects with the same content ("hello" and new String("hello")) are considered the same key. This is object equality — equality based on the objects' values. IdentityHashMap uses == instead of equals() to compare keys. Two keys are the same only if they are literally the same object in memory. Two different String objects with identical content are different keys in an IdentityHashMap. This is reference equality or object identity. IdentityHashMap also uses System.identityHashCode() instead of hashCode() for computing bucket indices. System.identityHashCode() returns the default Object hashCode based on memory address, regardless of whether hashCode() is overridden. This ensures that the identity-based comparison is consistent — two objects that are equal by == will always have the same identity hash code. The primary use cases for IdentityHashMap are: topology-preserving object graph traversals (deep copy, serialisation, cycle detection) where you need to track which specific objects have been visited, not which logically-equal objects; proxy frameworks and instrumentation where each proxy object is distinct even if they wrap equal-valued underlying objects; and interning registries where you explicitly track canonical object instances. IdentityHashMap intentionally violates the Map contract (which requires equals()-based key comparison) and its Javadoc explicitly documents this violation. Using IdentityHashMap where an equals()-based map is expected can produce correct-looking but incorrect behaviour.
Java
// ── IdentityHashMap — == comparison, not equals(): ───────────────────
IdentityHashMap<String, Integer> idMap = new IdentityHashMap<>();

String s1 = new String("hello");
String s2 = new String("hello");   // same content, different object

System.out.println(s1.equals(s2));  // true  — same content
System.out.println(s1 == s2);       // false — different objects

idMap.put(s1, 1);
idMap.put(s2, 2);   // s2 != s1 — treated as DIFFERENT keys

System.out.println(idMap.size());    // 2 — two distinct entries!
System.out.println(idMap.get(s1));   // 1
System.out.println(idMap.get(s2));   // 2

// ── Contrast with HashMap: ────────────────────────────────────────────
HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put(s1, 1);
hashMap.put(s2, 2);   // equals() → same key — replaces

System.out.println(hashMap.size());  // 1 — s1 and s2 treated as same key
System.out.println(hashMap.get(s1)); // 2 — second put replaced first

// ── Object graph deep copy — classic IdentityHashMap use case: ────────
public static <T> T deepCopy(T original,
        IdentityHashMap<Object, Object> visited) {

    if (original == null) return null;
    if (visited.containsKey(original)) {
        return (T) visited.get(original);  // already copied — return same copy
        // Without IdentityHashMap, equal objects with different identities
        // would all share one copy, breaking the graph structure.
    }

    T copy = createEmptyCopy(original);
    visited.put(original, copy);   // register before recursing (handles cycles)
    copyFields(original, copy, visited);
    return copy;
}

// ── Cycle detection in object graphs: ────────────────────────────────
public static void printGraph(Node node, IdentityHashMap<Node, Boolean> seen) {
    if (node == null || seen.containsKey(node)) return;
    seen.put(node, Boolean.TRUE);    // mark this specific node as visited
    System.out.println("Visiting: " + node.value);
    for (Node neighbour : node.neighbours) {
        printGraph(neighbour, seen);
    }
}

// CORRECT: uses IdentityHashMap so two distinct Nodes with the same value
// are tracked independently.
// WRONG: using HashMap would conflate distinct nodes with equal .value fields.

Related Topics in Collections Framework

HashMap
HashMap is the most widely used Map implementation in Java. It stores key-value pairs in a hash table, providing average O(1) performance for get, put, remove, and containsKey operations. Keys are stored in no guaranteed order. HashMap permits one null key and multiple null values. It is not thread-safe. Understanding how HashMap uses hash codes, handles collisions, and resizes is foundational knowledge for writing efficient Java code.
LinkedHashMap
LinkedHashMap extends HashMap and maintains a doubly-linked list running through all its entries, preserving the order in which entries were inserted. Iteration over a LinkedHashMap always returns entries in insertion order. Optionally, it can be constructed in access-order mode where entries are ordered by most-recently accessed, making it the perfect foundation for implementing a Least Recently Used (LRU) cache. LinkedHashMap has slightly higher memory overhead than HashMap due to the extra linked list pointers.
TreeMap
TreeMap is a Red-Black tree implementation of the NavigableMap interface. It stores key-value pairs in sorted order — either the natural ordering of keys (requiring them to implement Comparable) or a custom Comparator provided at construction. All basic operations (get, put, remove, containsKey) are O(log n). TreeMap provides rich navigation operations: finding the closest key, extracting sub-maps, and headMap/tailMap views.
Hashtable
Hashtable is a legacy hash table implementation that predates the Collections Framework. Like Vector for lists, Hashtable was Java's original hash map from Java 1.0. It is thread-safe because all its methods are synchronised, but it does not permit null keys or null values. Hashtable has been retrofitted to implement the Map interface but should never be used in new code — HashMap is the non-concurrent replacement and ConcurrentHashMap is the concurrent replacement.
Prev
WeakHashMap
Next
EnumMap