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
The HashMap internally stores key-value pairs in buckets. We shall explore bucket’s a bit more in depth soon.
Capacity specifies number of buckets in the hash table
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.
It’s an internal interface to hold a Key-Value pair. The concrete implementation is used internally by the HashMap class.
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
transient Node<K,V> table;
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
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.