IdentityHashMap in Java

IdentityHashMap is an implementation of Map, but it violates the general contract of a Map, which mandates the use of equals() method for comparing objects. This is a special purpose map designed for special cases where reference equality is required.

Unlike a general purpose Map which uses the hashCode() method to identify bucket location, IdentityHashMap uses the System.identityHashCode() method.

The System.identityHashCode() method would always return the default hash value that would be returned by the default hashCode() method, even if the object overrides the hashCode() method.

NOTE: IdentityHashMap is faster than HashMap since it doesn’t rely on the complex processing of equals() and hashCode().

Storing Data in IdentityHashMap

IndentityHashMap implements linear probing to handle collisions. This means each bucket can hold only one key-value pair, and in case a new element is mapping to a non-empty bucket, it is allocated the next free bucket.

Hence while storing any element in the bucket array, the System.identityHashCode() method identifies the bucket location, and the new element is added to the bucket array. If the bucket identified is not empty, the new element will take the next available empty slot in the bucket array.

Retrieving Data from IdentityHashMap

The similar process is followed while retrieving data from IdentityHashMap. System.identityHashCode() method identifies the bucket location where the key maps to. It searches for reference equality in the key stored at the bucket location. If the key references doesn’t match it search in the next bucket location till it finds the correct key. Once the correct key is searched it returns the value associated with it.


A simple example to demonstrate IdentityHashMap is shown below:

public class IdentityHashMapTest {
    public static void main(String[] args){
	Map<String, String> map = new IdentityHashMap<String, String>();
	String s1 = new String("key");
	String s2 = new String("key");
	map.put(s1, "Val3");
	map.put(s2, "Val4");

The above code print the following output:


Even if the two string are same their reference are different hence it will be stored as two different elements in the IdentityHashMap, since it works in referencial equality.


Internal Implementation of ArrayList

ArrayList is an implementation of List interface, used to store a list of objects. Unlike normal arrays, it is a dynamic data structure, its size dynamically increases when its capacity is exhausted.

View Article

Understanding equals() and hashCode() methods

The equals() and hashCode() are two primary methods of Java's Object Class which work together to uniquely identify any object in Java.

View Article

Internal Implementation of HashMap

HashMap is popular data structure in Java which stores data in key-value format. This article describes the internal implementation to store and retrieve data in a hashmap.

View Article

Internal Implementation of HashSet

HashSet is a member of the Java Collection Framework which is used to store unique entries. This article describes how a HashSet is internally implemented to store unique entries.

View Article

Iterator and ListIterator in Java

The Java API provides the Iterator and ListIterator that are used to iterate over a Collection. This article covers the difference between the two and discuss how Emumeration is different from Iterat.

View Article

Introduction to Java Collections

The Java collections framework is a library that provides commonly reusable collection data structures. It consists of a set of various interfaces, implementations and algorithms used to represent...

View Article

Understanding TreeMap

A TreeMap is an implementation of the Map interface used to store key-value pair in sorted order of their keys. This articles describe how a Treemap is implemented in Java.

View Article