Internal Working of HashMap in Java. Does it really maintain an O(1) time complexity? What is the Difference between TreeMap, HashMap, LinkedHashMap, and HashTable?

Photo by Jefferson Santos on Unsplash

HashMap is one of the most popular collections frameworks in Java. Whenever someone asks us about the internal working of HashMap, we simply know the answer as it works on the hashing mechanism. Today we are going to go through the in-depth functioning of HashMap. In its simplest form, HashMap is a way to assign a unique code for any object after applying a formula and offers an O(1) insertion and retrieval time.

So how does HashMap internally work?

HashMap uses HashTable implementation internally and consists of two important data structures which are LinkedList and Array. There is a bucket of arrays with each element representing an individual LinkedList. The Inner Node class consists of a hash value, key, value, and the link to the next Node as seen below.

Internal Node Structure

Now, the question arises, how does HashMap know where to store the value in a bucket?

To store the values, HashMap uses a concept known as Hashing. Hashing is performed using a hashCode() function that converts an Object into HashCode. Based on the hash index results, a slot in the bucket is selected, and the value results are stored.

As you might think, there would be multiple objects which get hashed to the same bucket index. This is known as collision, and therefore we use a LinkedList to store the values which are linked with each other. This can be seen in the representation below.

fig (a) Internal working of HashMap prior to Java 8

A collision occurs when two different values hash to the same bucket index. Let’s consider an example that two integers “1000” and “500” gives us two hash values 100 and 50 respectively. If we consider the total array size as 10, both of them end up in the same bucket i.e. 100 % 10 and 50 % 10). What chaining does is whenever you call the function map.get( “100” );, you are able to retrieve the correct value associated with the key. To verify, we can also utilize the equals method in HashMap.

You can also override this hashcode function and provide your own implementation. A good hash function is one which distributes the objects evenly.

Changes in the Java 8 implementation:

To improve the working of HashMap, Java 8 made updates to the internal implementation workflow. Once a certain threshold level is reached, the values are now automatically stored in a tree manner rather than a linked list. So instead of O(n) retrieval time, we now have better O(log n) retrieval performance. Java only does this when there is a performance gain. This can be seen in the representation below.

fig (a) Internal working of HashMap from Java 8

How does HashMap provide a constant time (O(1)) retrieval when LinkedList/Tree data Structures are used to store the values?

In real life, the time complexity of HashMap is not O(1). It is Big O(average size of the collision structure) and is known as amortized O(1).

True O(1) is only achieved by collision-less hashing(also known as “perfect” hashing).

Difference between TreeMap, HashMap, LinkedHashMap, and HashTable in Java:

All of the above helps us to store data in key: value format. The important distinction is between the ordering and time complexity of the retrieval of data.

HashMap:

• HashMap offers O(1) insertion and retrieval time.
• It contains value based on keys.
• The ordering of keys is random
• It uses a linked list to store the data.
• It contains only unique elements
• It may have one null key and multiple null values
• It is not thread-safe

LinkedHashMap:

• LinkedHashMap is the same as HashMap but maintains the insertion order.
• The other properties align with that of HashMap.

TreeMap:

• TreeMap offers O(log N) insertion and retrieval time.
• It cannot have a null key but can have multiple null values.
• It maintains ascending order of keys.
• The rest of the properties align with that of HashMap.

Hashtable:

• It is thread-safe.
• Since it is thread-safe the performance might be low
• Null is not allowed for both key and value

Thanks for reading this article so far. If you liked the article then please share it with your friends and colleagues. If you have any questions please feel free to shoot them in the comments section below.