Java IdentityHashMap Internals: Reference Equality & Open Addressing Probing

Suppose you are writing a JSON serialization engine like Jackson or a deep object cloning library.

Your serializer traverses a complex graph of domain objects:

User Object (0x1A8F)
  |
  +---> Order Object (0x2B90)
           |
           +---> User Object (0x1A8F)  <--- Cyclic Reference Back to User!

To prevent infinite loops when serializing cyclic graphs, your serializer tracks visited objects inside a map: Map<Object, String> visited = new HashMap<>().

Suddenly, your serializer throws a StackOverflowError.

Why? Because two separate object instances override equals() to return true when their data fields match (user1.equals(user2) == true). Standard HashMap considers them the exact same key.

When serializing object graphs, you do not care if two separate objects have matching field values. You care about memory address identity: are these two variables pointing to the exact same object instance on the heap?

Java provides IdentityHashMap for this exact scenario.

Why You Need This in Real Life

IdentityHashMap intentionally breaks the standard Map contract:

Reference Equality (==): It compares keys using k1 == k2 instead of k1.equals(k2).
Identity Hash Codes: It ignores overridden hashCode() methods, using System.identityHashCode(k) to hash memory locations directly.
Open-Addressing Linear Probing: It discards node objects and bucket linked lists, storing keys and values side-by-side inside a single flat array.

Standard HashMap vs IdentityHashMap

Consider two distinct String object instances containing identical character sequences:

String key1 = new String("TOKEN");
String key2 = new String("TOKEN");

// key1.equals(key2) is TRUE, but (key1 == key2) is FALSE!

If you put both keys into a standard HashMap:

Map<String, String> standardMap = new HashMap<>();
standardMap.put(key1, "Alpha");
standardMap.put(key2, "Beta");

System.out.println(standardMap.size()); // Prints 1! key2 overwrote key1.

If you put both keys into an IdentityHashMap:

Map<String, String> identityMap = new IdentityHashMap<>();
identityMap.put(key1, "Alpha");
identityMap.put(key2, "Beta");

System.out.println(identityMap.size()); // Prints 2! Both key instances stored separately.

Flat Array Layout and Linear Probing

Standard HashMap allocates Node objects containing pointers to handle collisions.

IdentityHashMap uses a single flat array (Object[] table) where keys and values sit adjacent to each other:

FLAT ARRAY LAYOUT (IdentityHashMap):
Index:    [ 0 ]     [ 1 ]     [ 2 ]     [ 3 ]     [ 4 ]     [ 5 ]
Content:  [ KeyA  | ValueA  | KeyB  | ValueB  |  null  |  null  ]

Key at index i stores its corresponding value at index i + 1.

When a hash collision occurs, IdentityHashMap uses linear probing: it steps forward by 2 array slots (index = (index + 2) % len) until it finds an empty key slot.

Linear Probing Step on Collision at Index 2:
Index 2 occupied by KeyB ---> Move to Index 4 ---> Slot empty! Insert KeyC at 4, ValueC at 5.

Simplified `MyIdentityHashMap<K, V>` Implementation

public class MyIdentityHashMap<K, V> {
    private Object[] table;
    private int size = 0;
    private static final int DEFAULT_CAPACITY = 32; // Stores 16 key-value pairs

    public MyIdentityHashMap() {
        this.table = new Object[DEFAULT_CAPACITY];
    }

    public V put(K key, V value) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);

        while (true) {
            Object item = tab[i];
            if (item == null) {
                tab[i] = k;
                tab[i + 1] = value;
                size++;
                if (size * 2 >= len) {
                    resize();
                }
                return null;
            }
            if (item == k) { // Reference Equality Check (==)!
                @SuppressWarnings("unchecked")
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
            i = (i + 2) % len; // Linear probing step!
        }
    }

    @SuppressWarnings("unchecked")
    public V get(K key) {
        Object k = maskNull(key);
        Object[] tab = table;
        int len = tab.length;
        int i = hash(k, len);

        while (true) {
            Object item = tab[i];
            if (item == null) return null;
            if (item == k) return (V) tab[i + 1]; // Reference Equality Check!
            i = (i + 2) % len;
        }
    }

    private static int hash(Object key, int length) {
        int h = System.identityHashCode(key); // Hashes memory address directly!
        // Multiply by Fibonacci constant to spread hash bits evenly
        return ((h << 1) - (h << 8)) & (length - 1);
    }

    private static Object maskNull(Object key) {
        return (key == null) ? NULL_KEY : key;
    }

    private static final Object NULL_KEY = new Object();

    private void resize() {
        int newLen = table.length * 2;
        Object[] oldTable = table;
        table = new Object[newLen];
        size = 0;

        for (int j = 0; j < oldTable.length; j += 2) {
            Object key = oldTable[j];
            if (key != null) {
                @SuppressWarnings("unchecked")
                V val = (V) oldTable[j + 1];
                put((K) key, val);
            }
        }
    }
}

Quick Summary

IdentityHashMap uses reference equality (k1 == k2) and System.identityHashCode(), ignoring overridden equals() and hashCode() methods.
It eliminates Node allocations by storing keys and values side-by-side inside a flat Object[] array.
Hash collisions are resolved using linear probing (index + 2).
Essential for graph traversal, object cloning, and cycle detection.

References & Further Reading

Bloch, J. (2018). Effective Java (3rd Edition) — Item 14: Consider Implementing Comparable. Addison-Wesley.
Oracle Corporation. Java SE 21 API Documentation: java.lang.Comparable & java.util.Comparator. Oracle Docs.
Naftalin, M., & Wadler, P. (2006). Java Generics and Collections. O’Reilly Media.