IdentityHashMap

#Introduction

IdentityHashMap is a specialized Map implementation that intentionally breaks away from normal Java Map equality semantics. The key idea:

HashMap compares keys using equals(), while IdentityHashMap compares keys using reference identity (==).

This makes IdentityHashMap useful when you care about "Are these the exact same object?" rather than "Are these two objects logically equal?"

#What Is IdentityHashMap?

Package:

java.util.IdentityHashMap

Map<String, Integer> map = new IdentityHashMap<>();

#== vs equals()

This is the foundation of the entire chapter.

String a = new String("Java");
String b = new String("Java");

System.out.println(a.equals(b));
System.out.println(a == b);

true
false

equals() is true because both contain the same characters; == is false because they are different objects.

HashMap Behaviour

Map<String, Integer> map = new HashMap<>();

map.put(a, 100);
map.put(b, 200);

Because a.equals(b) == true, the second insertion replaces the first mapping. Final: one logical key → 200.

IdentityHashMap Behaviour

Map<String, Integer> map = new IdentityHashMap<>();

map.put(a, 100);
map.put(b, 200);

Here a == b is false, so both keys coexist: a → 100, b → 200. This is the defining difference.

Side-by-Side

#Why Would Anyone Want This?

Most business applications care about logical equality — two Employee objects representing ID 101 might logically be the same employee, so HashMap is appropriate.

But some algorithms care about object identity: "Have I already encountered this exact object instance?" That's where IdentityHashMap becomes useful.

Object Graph Traversal

One important use case is processing object graphs. Suppose Object A → Object B → Object A — there is a cycle. If you're traversing the graph and want to detect whether you've already visited the same object instance, identity semantics are useful:

Map<Object, Boolean> visited = new IdentityHashMap<>();

if (visited.put(object, Boolean.TRUE) == null) {
    // first time seeing this exact object
}

The identity of the object matters, not its equals() implementation.

Why HashMap Can Be Wrong for Identity-Based Algorithms

Suppose two different objects implement equals() such that objectA.equals(objectB) == true. A HashMap would treat them as the same key. But your algorithm might need objectA != objectB to mean different objects. IdentityHashMap gives you that behaviour.

#Identity Comparison and Hashing

IdentityHashMap Uses ==

The rule to remember: IdentityHashMap key comparison uses reference equality (==), not equals().

What About hashCode()?

IdentityHashMap also uses identity-based hashing. Conceptually, it uses:

System.identityHashCode(object)

rather than relying on the object's overridden object.hashCode(). Why? Because the Map wants hashing to correspond to object identity rather than logical equality.

System.identityHashCode()

Java provides System.identityHashCode(object), which returns the identity-based hash associated with the object. Even if the class overrides hashCode(), System.identityHashCode() provides identity-based hash semantics.

Example

class Employee {

    int id;

    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public boolean equals(Object o) {
        // ...
    }
}

Two Employees may have the same id, and therefore the same equals() and same hashCode(). But IdentityHashMap still distinguishes them if they are different object instances.

#Internal Structure

IdentityHashMap does not simply behave like "HashMap + replace equals() with ==". Its internal representation is specialized. Conceptually, it uses an array-based table containing alternating keys and values:

This avoids creating separate Node objects for each mapping, rather than using the normal HashMap bucket-node structure.

Open Addressing

Unlike HashMap's bucket → Node → Node → Node, IdentityHashMap uses an array and searches for a suitable slot when collisions occur. The implementation uses open-addressing-style probing.

IdentityHashMap vs HashMap Internals

This is a major implementation difference — IdentityHashMap doesn't use HashMap-style linked bucket chains.

Why Open Addressing?

In an open-addressed table (slot 0, slot 1, slot 2, slot 3, …), if the preferred slot is occupied, try another slot. This continues until the appropriate key is found or an empty slot is found.

Conceptual Lookup

For map.get(key), think:

The key comparison is storedKey == key, not storedKey.equals(key).

#The Map Contract

Why IdentityHashMap Doesn't Use equals()

Object a = new Object();
Object b = new Object();

Even if a custom class says a.equals(b) == true, IdentityHashMap wants a == b. The semantic contract is different, which makes it appropriate for identity-sensitive operations.

An Intentional Departure from the Map Contract

The Java Map contract is normally based on logical equality. IdentityHashMap intentionally uses reference equality instead. The JDK documentation explicitly describes this as a deliberate departure from the general Map contract. This is why IdentityHashMap is a specialized collection rather than a normal replacement for HashMap.

containsKey()

containsKey(key) checks identity. So if a != b — even when a.equals(b) == true — then map.containsKey(a) and map.containsKey(b) can produce different results depending on which exact object was inserted.

remove()

map.remove(a);

removes the mapping associated with the exact object reference a. A distinct but equal object b won't remove it.

containsValue()

The identity semantics aren't limited only to keys. The documentation specifies identity-based comparisons for keys and values where applicable.

#Keys, Values and Null

Null Keys and Values

IdentityHashMap allows a null key (map.put(null, "Hello");) — there can be one null key mapping — and null values (map.put(object, null);).

Duplicate Keys?

IdentityHashMap doesn't allow duplicate identical references. But it can contain multiple distinct objects that are equal according to equals() (a.equals(b) → true, a == b → false → both can exist as keys).

Duplicate Values

Values can be duplicated: map.put(a, "Java"); map.put(b, "Java"); is valid.

IdentityHashMap and Mutable Objects

IdentityHashMap behaves differently from HashMap regarding mutation of an object's overridden hashCode():

class Employee {

    int id;

    @Override
    public int hashCode() {
        return id;
    }
}

Changing employee.id doesn't change the identity hash used by IdentityHashMap. So the classic HashMap problem involving a mutable logical hash is not the same here.

Identity Is Stable

An object's identity remains associated with that object instance during its lifetime — same instance → same identity, even if fields change. This is exactly what identity-based structures need.

equals() vs Identity

class Person {

    String name;

    @Override
    public boolean equals(Object o) {
        Person p = (Person) o;
        return name.equals(p.name);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

Person p1 = new Person("John");
Person p2 = new Person("John");

p1.equals(p2) → true, p1 == p2 → false. HashMap: p1 and p2 are the same logical key. IdentityHashMap: p1 and p2 are different keys.

#Graph Copying and Serialization

One legitimate use case is supporting algorithms where object identity must be preserved. Suppose an object graph contains A → B and another reference to B, where both references point to the same B object. An identity map can record original B → copied B, so that both references can point to the same copied object. This prevents accidentally creating two separate copies of the same original object.

#When Not to Use IdentityHashMap

Don't use IdentityHashMap just because it is another Map. For ordinary business logic, HashMap is almost always the more natural choice. Use IdentityHashMap only when object identity is genuinely part of the requirement.

Why equals() Can Matter Here

Suppose a class has equals() based on business identity (employeeId). Two different object instances may represent the same employee:

• HashMap → same employee → same key
• IdentityHashMap → different object instances → different keys

That can be exactly what an object-graph algorithm needs.

#Comparisons

IdentityHashMap vs HashMap

IdentityHashMap vs WeakHashMap

These solve completely different problems:

IdentityHashMap vs TreeMap

• TreeMap asks "How do keys compare?" using Comparator / Comparable.
• IdentityHashMap asks "Are these the same object?" using ==.

Completely different semantics.

entrySet() and Iteration Order

You can still use map.entrySet() like other Maps, but key equality remains identity-based — entry.getKey() is the exact object reference used as the key.

IdentityHashMap does not provide insertion-order or sorted-order guarantees. For insertion order use LinkedHashMap; for sorted keys use TreeMap.

Capacity

new IdentityHashMap<>(100);

The parameter represents an expected maximum number of entries rather than behaving exactly like HashMap's initial bucket capacity — another subtle API distinction.

Performance

Average basic operations are generally O(1) because it uses hashing and open addressing. However, performance depends on hash distribution, table occupancy and probing. It should not be selected solely because it uses an array — the primary reason to select it is identity semantics.

#Decision Framework

Complete Map Selection

Final Mental Model

Given a.equals(b) → true and a == b → false: HashMap holds one logical key; IdentityHashMap holds two identity keys.