How HashMap works in Java?

HashMap is an implementation of Map interface, which maps keys to values. A Map cannot contain duplicate keys.

We know we can put and get Key-values into HashMap. So, how does HashMap actually works in Java. This post explores a bit about the internal working. Before we jump into details, let’s see some basic terminology

Basic Terminology

Buckets

The HashMap internally stores key-value pairs in buckets. We shall explore bucket’s a bit more in depth soon.

Capacity

Capacity specifies number of buckets in the hash table

Load Factor

Load factor indicates, how full the hash map implementation is allowed for grow, before the capacity is increased. The default is 0.75, meaning, once the hash map grows above 75%, the capacity shall be increased.

Map.Entry Interface

It’s an internal interface to hold a Key-Value pair. The concrete implementation is used internally by the HashMap class.

Inner Working

Now that we have seen some basic terminology, let’s dive into the internal implementation.

The HashMap implementation maintains an array of implementation of Map.Entry interface aka Node or buckets. Something like this

Node is concrete implementation of Map.Entry interface and is used internally. This table is actually the bucket that we had talked about earlier.

Put API working

Now let’s see how the put works

map-put

The put API uses the hashcode() of the key and applies a mathematical operation (modules or AND) to arrive at the bucket in which the element is to be added. Now if the bucket is empty, an instance of Node is created and added as first entry. If it’s not empty, new instance of Node is created and chained to the existing Node. Keep this in mind as this shall be useful to answer a very popular interview question.

Get API Working

While using get(), we pass a Key and try to get a value, if present. So let’s see the steps

  • hashcode() on the key is used and applied to with mathematical operator to get the bucket
  • Once we get the bucket, we start iterating through the Node list
  • During iteration, we check if the key hashes are equal or not, if they are equal, we check for the equality of the Key using equals() method
  • As soon as we find a match we return the value

Now hopefully it’s clear why hashcode() and equals() methods are so important to Map implementations. Once you understand how it works, you can take on various questions around it.

One thought on “How HashMap works in Java?

Leave a Reply

Your email address will not be published. Required fields are marked *