What is IdentityHashMap and how does its notion of key equality differ from a normal HashMap?
answer
- == not .equals; System.identityHashCode
- Deliberately violates the Map contract
- Use: serialization, deep copy, graph/cycle detection
- Array-backed, linear probing; allows nulls
- Trap: keying on String/Integer expecting value match
basics
~10 sIdentityHashMap treats two keys as the same only when they are literally the same object (==), not when they are merely equal (.equals()). So two distinct strings with identical text are two different keys.
solid answer
~40 sIdentityHashMap is a Map that deliberately violates the normal Map contract: it compares keys with reference equality (==) and uses System.identityHashCode() instead of the keys' equals() and hashCode(). Two objects are the same key only if they are the very same instance in memory. This is the opposite of HashMap, where two distinct objects that are .equals() collapse to one entry. Its main uses are: serialization and deep-copy/graph algorithms that must track 'have I already visited this exact object?', and topology-preserving transformations where object identity matters. It is array-backed using linear probing rather than buckets-with-chaining. It accepts null keys and values. You should not use it as a general-purpose map; using it by accident (e.g. keying on Strings or boxed Integers expecting value semantics) produces subtle bugs because logically-equal keys won't match.
code
java · 11 linesInteger x = new Integer(1000);
Integer y = new Integer(1000); // equal value, distinct objects
Map<Integer,String> hm = new HashMap<>();
hm.put(x, "a"); hm.put(y, "b");
System.out.println(hm.size()); // 1 (x.equals(y))
Map<Integer,String> im = new IdentityHashMap<>();
im.put(x, "a"); im.put(y, "b");
System.out.println(im.size()); // 2 (x != y)
System.out.println(im.get(1000));// null (a fresh boxed 1000 is a new object)go deeper
Knows IdentityHashMap compares keys by == (same object) rather than .equals().
Explains identity vs logical equality, that it uses System.identityHashCode, and gives a use case like graph traversal or serialization.
Discusses that it deliberately violates the Map contract, its linear-probing array layout, the autoboxing/String identity pitfalls, and when identity semantics are genuinely required.
Reasons about object-identity tracking in framework-level code (serializers, deep-copy, IdentityHashMap in JDK internals), correctness vs equals contracts, and the risks of identity semantics leaking into APIs.
## Two kinds of "equal" In Java there are two different questions you can ask about two object references `a` and `b`: 1. **Reference (identity) equality — `a == b`:** are these the *same object*, occupying the same place in memory? 2. **Logical equality — `a.equals(b)`:** do these objects *represent the same value*, even if they are two separate instances? For example, two separate `String` objects both containing "hi" are **not** `==` (different instances) but **are** `.equals()` (same text). A normal `HashMap` uses **logical equality**: it locates a key's bucket with `key.hashCode()` and then confirms a match with `key.equals()`. So if you `put("hi", 1)` and later `get(new String("hi"))`, you get `1` back — different instance, same value, same key. ## What IdentityHashMap changes `IdentityHashMap` **intentionally** breaks the usual Map rule. It compares keys (and values, in `remove`-style checks) with **`==`** and hashes them with **`System.identityHashCode(key)`** — the identity hash, derived from the object's identity, *not* its overridden `hashCode()`. Consequence: two keys are "the same" **only if they are literally the same instance**. ``` String a = new String("hi"); String b = new String("hi"); // equal text, different instance Map<String,Integer> hm = new HashMap<>(); hm.put(a, 1); hm.put(b, 2); // size 1 — b overwrites a (they're .equals) Map<String,Integer> im = new IdentityHashMap<>(); im.put(a, 1); im.put(b, 2); // size 2 — a and b are different objects ``` Because of this it is documented as a class that *deliberately violates* the general `Map` contract (which says comparison must use `equals`). That is not a bug; it is its whole purpose. ## How it is built (internally) Unlike `HashMap` (an array of buckets, collisions chained in lists/trees), `IdentityHashMap` stores keys and values in a **single flat array** at alternating positions and resolves collisions by **linear probing** (if a slot is taken, try the next one). This makes it compact and fast for its niche. It permits `null` keys and `null` values. ## Why it exists — real uses - **Graph / object-graph traversal:** algorithms like serialization, deep copy, or cycle detection must answer "have I already processed *this exact node*?" Using value equality would wrongly merge distinct-but-equal nodes. Java's own serialization uses identity-based tracking. - **Topology-preserving transforms:** when you map an old object graph to a new one and must keep the same sharing/aliasing structure. - **Avoiding expensive or wrong `equals`:** when keys have a costly or semantically wrong `equals`, identity comparison is correct and cheap. ## Pitfalls - **Do not use it as a general map.** Keying on `String`, boxed `Integer` outside the cache range, or any value-typed key leads to "lookups mysteriously miss" because a logically-equal-but-different instance is a different key. - **Autoboxing trap:** `Integer` values from `-128..127` are cached (so `==` happens to work), but outside that range each boxing creates a new object — identity differs, so an `IdentityHashMap` keyed on `Integer` behaves inconsistently across the cache boundary. - It is **not** thread-safe. ## One-line summary IdentityHashMap = "a map where keys match only if they're the *same object* (`==`), using identity hashing" — perfect for object-graph bookkeeping, dangerous as a default map.
- Name a concrete situation where IdentityHashMap is the correct choice over HashMap.Deep-copying or serializing an object graph with shared/cyclic references: you must track which exact objects you've already cloned/written so shared nodes stay shared and cycles don't loop forever. Value equality would incorrectly merge distinct-but-equal nodes.
- Why does keying an IdentityHashMap on Integer behave inconsistently?Because Integer autoboxing caches values in -128..127, so within that range == coincidentally works; outside it each boxing yields a new object, so identity differs and lookups miss. Relying on this is fragile.
HashMap recognizes you by your name (anyone with the same name is 'you'). IdentityHashMap recognizes you only by your fingerprint — an identical twin with the same name is a different person.
saying these in an interview costs you the question
- Saying it's just a faster HashMap — it has different (identity) semantics, not just performance.
- Using it as a general-purpose map keyed on value types.
- Believing it calls the key's equals()/hashCode() (it uses == and System.identityHashCode).
- Assuming it's thread-safe.