What is IdentityHashMap?

• Reference equality – keys are compared with == (same object in memory), not equals() (same content)
• System.identityHashCode() – the hash is computed from the object's memory identity, not from the overridden hashCode() method
• Flat array with linear probing – internally stores keys and values in alternating slots of a single Object[], not in Node buckets
• Intentional contract violation – the Javadoc explicitly states this class violates the Map contract by design
• Special-purpose only – meant for scenarios where object identity matters, such as serialization, deep copy, and topology-preserving transformations

What is IdentityHashMap?

IdentityHashMap is a Map implementation in java.util that compares keys using == (reference equality) instead of equals() (content equality). Two key objects are considered equal only when they are the exact same object in memory.

This is the opposite of HashMap, where two different String objects containing "SAV2001" map to the same key because equals() returns true.

package com.bank.demo;

import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;

public class IdentityHashMapBasicDemo {
    public static void main(String[] args) {
        String key1 = new String("SAV2001");
        String key2 = new String("SAV2001");

        // HashMap: equals-based
        Map<String, String> hashMap = new HashMap<>();
        hashMap.put(key1, "Rajesh");
        hashMap.put(key2, "Priya");
        System.out.println("HashMap size: " + hashMap.size());

        // IdentityHashMap: ==-based
        Map<String, String> idMap = new IdentityHashMap<>();
        idMap.put(key1, "Rajesh");
        idMap.put(key2, "Priya");
        System.out.println("IdentityHashMap size: " + idMap.size());
    }
}

HashMap size: 1
IdentityHashMap size: 2

Why does IdentityHashMap exist?

IdentityHashMap exists for scenarios where you need to distinguish between distinct object instances, even when their content is identical. The JDK created it specifically for tasks like serialization, deep copy, and object graph traversal.

Consider a banking deep-copy service. Rajesh needs to clone an object graph where two fields point to the same Account object. A HashMap-based tracker would treat two Account objects with the same ID as one. An IdentityHashMap correctly tracks whether the exact same Account instance has already been cloned.

package com.bank.demo;

import java.util.IdentityHashMap;
import java.util.Map;

public class DeepCopyTrackerDemo {
    static class Account {
        String id;
        Account(String id) { this.id = id; }
        @Override public String toString() { return "Account(" + id + ")"; }
    }

    public static void main(String[] args) {
        Account shared = new Account("SAV2001");
        Account separate = new Account("SAV2001");

        Map<Account, Account> cloneTracker = new IdentityHashMap<>();
        cloneTracker.put(shared, new Account("SAV2001-clone"));

        System.out.println("Same instance found: " + cloneTracker.containsKey(shared));
        System.out.println("Different instance found: " + cloneTracker.containsKey(separate));
    }
}

Same instance found: true
Different instance found: false

How does IdentityHashMap work internally?

Unlike HashMap, which uses an array of bucket chains (linked lists or trees), IdentityHashMap uses a flat Object[] array with linear probing. Keys and values are stored in alternating slots: table[2*i] holds the key and table[2*i+1] holds the value.

The hash is computed using System.identityHashCode(key), which returns the default identity hash regardless of any hashCode() override. On collision, the map probes forward linearly until it finds an empty slot.

• Lookup: compute index from identityHashCode, probe forward comparing with == until a match or empty slot is found.
• Insertion: same probing, then store key and value in the two adjacent slots.
• Deletion: requires cleanup of the probe chain (unlike chained hashing).

package com.bank.demo;

public class IdentityHashCodeDemo {
    public static void main(String[] args) {
        String a = new String("SAV2001");
        String b = new String("SAV2001");

        System.out.println("a.hashCode(): " + a.hashCode());
        System.out.println("b.hashCode(): " + b.hashCode());
        System.out.println("Same hashCode: " + (a.hashCode() == b.hashCode()));

        System.out.println("identityHashCode(a): " + System.identityHashCode(a));
        System.out.println("identityHashCode(b): " + System.identityHashCode(b));
        System.out.println("Same identity hash: " + (System.identityHashCode(a) == System.identityHashCode(b)));
    }
}

a.hashCode(): -1808287924
b.hashCode(): -1808287924
Same hashCode: true
identityHashCode(a): 1234567890
identityHashCode(b): 987654321
Same identity hash: false

How is IdentityHashMap different from HashMap?

| Feature | HashMap | IdentityHashMap |
|---|---|---|
| Key comparison | equals() | == (reference equality) |
| Hash function | key.hashCode() | System.identityHashCode(key) |
| Internal structure | Bucket array with chains/trees | Flat Object[] with linear probing |
| Map contract | Compliant | Intentionally violates |
| Use case | General-purpose | Serialization, deep copy, cycle detection |
| String literal keys | Two new String("SAV2001") collapse to one key | Two new String("SAV2001") are two keys |

package com.bank.demo;

import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;

public class ComparisonDemo {
    public static void main(String[] args) {
        String s1 = new String("SAV2001");
        String s2 = new String("SAV2001");

        Map<String, String> hm = new HashMap<>();
        hm.put(s1, "first");
        hm.put(s2, "second");

        Map<String, String> im = new IdentityHashMap<>();
        im.put(s1, "first");
        im.put(s2, "second");

        System.out.println("HashMap: " + hm);
        System.out.println("IdentityHashMap: " + im);
    }
}

HashMap: {SAV2001=second}
IdentityHashMap: {SAV2001=first, SAV2001=second}

What are common mistakes?

Mistake: Using IdentityHashMap as a general-purpose Map

// WRONG: IdentityHashMap for normal key-value storage
Map<String, String> accounts = new IdentityHashMap<>();
accounts.put(new String("SAV2001"), "Rajesh");
String lookup = new String("SAV2001");
System.out.println(accounts.get(lookup)); // null! Different object!

// CORRECT: Use HashMap for content-based lookup
Map<String, String> accounts = new HashMap<>();
accounts.put(new String("SAV2001"), "Rajesh");
String lookup = new String("SAV2001");
System.out.println(accounts.get(lookup)); // Rajesh

Mistake: Forgetting that String literals are interned

// SURPRISING: String literals share the same reference
Map<String, String> idMap = new IdentityHashMap<>();
idMap.put("SAV2001", "Rajesh");
idMap.put("SAV2001", "Priya"); // Same reference (interned) -> replaces!
System.out.println(idMap.size()); // 1, not 2

What are the edge cases?

package com.bank.demo;

import java.util.IdentityHashMap;
import java.util.Map;

public class IdentityEdgeCasesDemo {
    public static void main(String[] args) {
        Map<Integer, String> idMap = new IdentityHashMap<>();

        // Edge case: Integer cache (-128 to 127)
        Integer a = 100;
        Integer b = 100;
        idMap.put(a, "first");
        idMap.put(b, "second");
        System.out.println("Cached Integer (100) size: " + idMap.size()); // 1

        Integer c = 200;
        Integer d = 200;
        idMap.put(c, "third");
        idMap.put(d, "fourth");
        System.out.println("Uncached Integer (200) size: " + idMap.size()); // 3
    }
}

Cached Integer (100) size: 1
Uncached Integer (200) size: 3

Integers from -128 to 127 are cached by the JVM, so Integer a = 100 and Integer b = 100 are the same reference. Beyond that range, autoboxing creates new objects, so they become different keys in an IdentityHashMap.

When should you use IdentityHashMap?

Use IdentityHashMap for object graph traversal (cycle detection), serialization frameworks (tracking serialized instances), deep-copy services, topology-preserving transformations, and proxy/decorator tracking where you need to know the exact object, not just its content.

When should you NOT use IdentityHashMap?

Do not use it for normal key-value storage. Any code that expects content-based equality will break. Do not use it when you want String keys looked up by value, which is the vast majority of map use cases.

What should a senior engineer know?

• Linear probing has poor worst-case performance with high load factors. IdentityHashMap resizes aggressively to keep the load factor low.
• Iteration order is not insertion order and not sorted. It depends on internal array positions.
• No tree promotion. Unlike HashMap (which converts long chains to red-black trees at threshold 8), IdentityHashMap's linear probing has no such optimisation.
• Memory layout. The flat array is more cache-friendly than HashMap's Node objects, making IdentityHashMap faster for small maps.

What are common interview follow-up questions?

• "When would you use IdentityHashMap over HashMap?" : When you need to track distinct object instances, not content equality, such as in serialization or cycle detection.
• "Does it violate the Map contract?" : Yes, intentionally. The Javadoc documents this.
• "What hash function does it use?" : System.identityHashCode(), which ignores any hashCode() override.
• "What happens with String literals?" : Interned literals share references, so they collapse to one key.