☕ 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

Collections Overview
The Java Collections Framework (JCF) is a unified architecture for representing and manipulating groups of objects. It provides a set of interfaces that define the operations a collection must support, a set of abstract classes that provide partial implementations, and a set of concrete implementations optimised for different use cases. Every Java developer uses collections daily — lists for sequences, sets for uniqueness, maps for key-value pairs, and queues for ordering — and choosing the right implementation for the right use case is one of the most fundamental practical skills in Java.
Iterable
Iterable<E> is the root interface of the Java Collections hierarchy. Any class that implements Iterable can be used in a for-each loop. It declares a single abstract method: iterator(), which returns an Iterator<E> that the for-each loop uses to traverse the elements. Implementing Iterable is all that is required to make a custom data structure work with Java's enhanced for loop, the Stream API, and any method that accepts an Iterable.
Collection Interface
Collection<E> is the root interface of the main collection hierarchy, extending Iterable<E>. It defines the common operations that all collection types must support: adding elements, removing elements, checking containment, querying size, clearing, converting to an array, and bulk operations. List, Set, and Queue all extend Collection. Map does not extend Collection because a map operates on key-value pairs rather than individual elements.
ArrayList
ArrayList is a resizable-array implementation of the List interface. It is the most commonly used collection in Java, providing dynamic sizing on top of a standard array. Elements are stored in contiguous memory, enabling O(1) random access by index. When the internal array is full, ArrayList automatically allocates a larger array and copies all elements. ArrayList is not thread-safe and preserves insertion order, allowing duplicates.
Prev
WeakHashMap
Next
EnumMap