Delve into HashMap: IdentityHashMap walkthrough

IdentityHashMap implements Map interface, that means it stores key value pairs similar to HashMap. What is the difference then you say? As the name suggests, IdentityHashMap compares the identity of the key object instead of checking object equality. In other words, IdentityHashMap uses reference equality (==) to compare keys while HashMap uses object equality.
Before starting IdentityHashMap, You can go through https://delveintojava.blogspot.com/2019/11/hashmap-walkthrough.html before starting this section to understand implementation of HashMap.

Unlike HashMap, IdentityHashMap stores just keys and values in an array - keys in even array index positions and values in the next adjacent odd indexed position. So, there are no nodes required and there is no need of buckets or we can say a bucket consists of single key value pair.

IdentityHashMap uses System.identityHashCode(Object) to find the index location in the table array instead of hashCode(). identityHashCode method always returns the same value returned by the default implementation of hashCode method. In other words, value returned by identityHashCode does not change throughout the life of an object.

The shift operations for calculating the return index value ensures that only even values between 0 to (length - 1) are returned. The even index stores the keys, and the next odd index stores values.

Let's check the put implementation for IdentityHashMap.

As you can see, there is no implementation to create new nodes to store key value pairs. The index search implementation is pretty straight forward. The for loop checks whether the key is already present. If the location of index does not have any key (empty), then the for loop exits and puts the key in the same index and value in the next index.

Algorithm for put:
1. Find the index for the new key and value using hash method.
2. If the index of the array is empty, put the new key in the same location, and it's corresponding value in the next index.
3. If the index of the array is not empty, then move to next index (current index + 2) and check
a. If the next index is null, insert the key in that index, and value in the next index
b. If the next index has the same key object (reference equality) as the one to be inserted, replace the value in the next index with the new value. And return the old value.
c. If a and b does not satisfy, move to next index (current index + 2) and return a and b.

One last thing in put method - maskNull. It allows values to be inserted for null keys. If you pass a null key, then maskNull method returns a final dummy object. The dummy key object is then used to calculate the index for storing the corresponding value for null key. If the key is not null, maskNull returns the same key object.

You can now easily guess the implementation for get method. Yes, for the given key, index is calculated with the same hash method. Then the key to be inserted is compared with the key present in the index using reference equality. If the key matches, then return the value stored in the next index, else move to next index. If the key in the index is null, that means the key was never inserted, and so return null.

Easy, right !

If you wondered enough, there is one important case that we are missing. Think what will happen if we remove any key value pair from the identityHashMap. Think what will happen if we removed one of the key value pairs that were mapped to the same index.

In the example below, let's say, key1, key2, and key3 maps to the same index 0. Since the index 0 was already occupied by key1, other two keys - key2 and key3 were inserted in the next subsequent locations. After the removal of key2, if get method is called for key3, what would it return ? Since the next subsequent index after index 0 has null key, it should return null, which is wrong.