IdentityHashMap

Key comparison

The first and the main feature to be aware of is the way IdentityHashMap checks the equality of keys. It uses identity comparison, which means reference equality by the == operator, instead of comparing it by the equals() method like a HashMap does.
A good example that shows the reference comparison feature is a map where the key is an instance of a class. Suppose we have a class Person that has two fields and its getters/setters, parameterized constructor accepting both fields, and an overridden toString() method.

class Person {
    private String name;
    private int birthYear;

    public Person(String name, int birthYear) {
        this.name = name;
        this.birthYear = birthYear;
    }

    // getters and setters

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return birthYear == person.birthYear && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, birthYear);
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", birthYear=" + birthYear +
                '}';
    }
}

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Map<Person, String> map = new IdentityHashMap<>();
        map.put(new Person("James Gosling", 1955), "Java");
        map.put(new Person("Guido van Rossum", 1956), "Python");

        System.out.println(map.get(new Person("James Gosling", 1955))); // null
    }
}

The application will print null. It is possible that we searched using an instance of the Person class, whose fields are equal to the values of the existing element's fields, but they refer to different objects in memory. Performing the same operation with HashMap coupled with overridden hashcode() and equals() methods inside a Person class, the application would print Java. In this case, if you want to get the element from the map, you should first create a Person class variable and use it as a key.

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Person james = new Person("James Gosling", 1955);
        Person guido = new Person("Guido van Rossum", 1956);

        Map<Person, String> map = new IdentityHashMap<>();
        map.put(james, "Java");
        map.put(guido, "Python");

        System.out.println(map.get(james)); // Java
    }
}

Let's see another case where IdentityHashMap behaves differently from HashMap due to comparing keys by reference. It happens when we add a new element with a key that already exists in the map.

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Map<Person, String> map = new IdentityHashMap<>();
        map.put(new Person("James Gosling", 1955), "Java");
        map.put(new Person("James Gosling", 1955), "Sun Microsystems");
        map.put(new Person("Guido van Rossum", 1956), "Python");
    }
}

If we print the size of this map using the size() method, its value will be 3. In the same situation, the HashMap size would be 2. When you add a new element to HashMap and its key is equal to the already existing element key by hashcode() and equals() methods, HashMap does not add it but replaces the existing element value with the new element value.
Now, let's modify our code:

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Person james = new Person("James Gosling", 1955);
        Person guido = new Person("Guido van Rossum", 1956);

        Map<Person, String> map = new IdentityHashMap<>();
        map.put(james, "Java");
        map.put(james, "Sun Microsystems");
        map.put(guido, "Python");

        System.out.println(map.get(james)); // Sun Microsystems
    }
}

By now, you can already guess what will happen. Our map size will be 2. IdentityHashMap will notice the addition of a duplicate key and behave like a HashMap. The second element value with the key james will replace the first one. In the end, the application will print Sun Microsystems.

Mutable keys

Another important advantage of IdentityHashMap is that its operation is not affected by mutations of keys. The state of a key is not important. What matters is the object it refers to. Suppose we have the same Person class from the previous section and the following code:

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Person james = new Person("James Gosling", 1955);
        Person guido = new Person("Guido van Rossum", 1956);

        Map<Person, String> map = new IdentityHashMap<>();
        map.put(james, "Java");
        map.put(guido, "Python");

        james.setName("J. Gosling");

        System.out.println(map.get(james)); // Java
    }
}

Using a HashMap in the same situation, we would face a data loss issue:

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Person james = new Person("James Gosling", 1955);
        Person guido = new Person("Guido van Rossum", 1956);

        Map<Person, String> map = new HashMap<>();
        map.put(james, "Java");
        map.put(guido, "Python");

        james.setName("J. Gosling");

        System.out.println(map.get(james)); // null
        System.out.println(map.get(new Person("James Gosling", 1955))); // null
        System.out.println(map.get(new Person("J. Gosling", 1955))); // null

        System.out.println(map.size()); // 2
    }
}

We have an element with the key new Person("J. Gosling", 1955) but we can't obtain it.
If you understand why it is not possible to get the element value in the given example, you are welcome to explain it in the comments!

String as a key

When working with String keys, you should remember an important feature of Strings. If you declare two String literals with the same value, they refer to the same object in the String pool, which is a section in a Heap. When you declare a String via a new operator, you create a new object in the Heap, not in the String pool. Let's analyze the following snippet:

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new IdentityHashMap<>();
        map.put("Java", 1);

        System.out.println(map.get("Java")); // 1
        System.out.println(map.get(new String("Java"))); // null
    }
}

In this example, two Strings on lines 4 and 6 with Java values refer to the same String pool object so you will have no issues when getting a value. On the seventh line, the situation is different. The key in the map and the String declared on line 7 refer to different objects, so the result will be null. However, it is possible for a String declared via a new operator to refer to an object in the String pool using the intern() method.

public class IdentityHashMapDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new IdentityHashMap<>();
        map.put("Java", 1);

        System.out.println(map.get("Java")); // 1
        System.out.println(map.get(new String("Java").intern())); // 1
    }
}

Now, the String key in the map and the String declared on line 7 refer to the same object and we can easily get the element value.

Collision resolution

You are already familiar with the part of Java collections based on hash tables, with the collisions that can appear during their work, and with some ways of solving such problems. To deal with collisions, IdentityHashMap uses the open addressing approach based on the linear probing algorithm, while regular HashMap uses a separate chaining approach. Open addressing stores elements directly in the hash table, whereas separate chaining requires external data structure in the form of an array, where elements are linked lists that store the data.

Use cases

IdentityHashMap is used rarely, in specific cases. Java Documentation lists serialization or deep-copying and maintaining proxy objects as typical use cases of this map. These are more advanced topics a newbie specialist is rather unlikely to encounter. A more likely situation that you can deal with is using a class object in the form of a key. Imagine you have a class with five fields. Comparing such objects with the equals() method means that the values of all fields will be compared. Identity comparison will be faster than comparing all five variables. We mentioned one use case earlier in this topic: when you know that the state of keys can change during the execution of the program, it will help you avoid problems with accessing elements.

Conclusion

In this topic, you learned about the implementation of IdentityHashMap, which is useful in certain cases. Its main features are that it uses identity comparison when checking the equality of keys, is not affected by key mutations, and resolves collisions using the open addressing approach. It is a rare species, and you may not encounter it very often, but if you do come across it, the basic knowledge gained in this topic will come in handy!