what are hashmap

HashMap is one of the most widely used collection in java. As the name suggests, it is based on the hashing function and it is a collection of key value pairs represented by map. The collection is favorite question for an interviewer and hence it is critical to understand its functioning and its working.

As already told a HashMap is a collection of key value pairs. so unlike other collections where we store only one value, in a HashMap we store 2 values against each element of the collection. One being the key and other being a value.

So the concept itself is very simple and there is very little to understand here. The collection is unordered which means the order of retrieval is not guaranteed. These are mere basic of the map.

Lets now understand how they are stored and how the hashing function is used. So when we call put function on a map with a key and value pair, the map stores this at some part of the array and array in a map is collection of node.

The collection uses the hascode function of the object being stored to determine the index of the array within the hashmap where the object will be stored. Feels a little complicated ?

lets say we are storing employee details against employee id. So in our case, employee id is the key and employee details will be the value. Lets say we are storing “A101”,EmployeeDetail[“name:Sushil”,”email: sushil@gmail.com”]

So when we call put function with key “A101” which is String object, then the hashcode function of this object will be called to generate a number and this number will be used to determine the exact location of the pair within the map.

So why really is it done this way ? I can still store a pair in list if I create a class with key and value, isn’t it ?

The answer is to make retrieval faster. Lets see how the above mentioned storage method makes retrieval faster.

So at the time of retrieval, I present the collection with the key. In our case is “A101”, In order to determine the position of the value object, hashmap will again use the hashcode function to find our where it has stored the value of the key. So the hashcode function will help determine the index within the map and it can directly go that location to find out the value as it would be the same position which will be used for storing the pair initially.

So seems ok at this moment. So we have one key and one value and we can find the location within the map for our object and get the value. So it will be faster than traversing the list and then each time trying to find if the key in the list is equal to the key presented. So HashMap will be much faster in retrieval when we are looking for a specific object in the collection.

hashcode’s are not supposed to be unique, two objects can have the same hashcode and its logically permissible. We are supposed to make them as unique as possible but it may not be possible all the time.

So what happens when we have 2 objects with same hascode ? How will the HashMap manage the storing and retrieval. Lets see.

So during storage as earlier stated it will used the hashcode function to determine the index within the map and then against that index store the pair in a list, In this case its a linked list. For illustration look at the below example

So the bucket is really the linked list which stores the elements in a list having the same hashcode. So against each index there is a linked list where the key value pairs are stored.

So if there are more than one element with the same hascode then the element is stored in the linked list.

At the time of retrieval, the hashmap will first identify the index and then traverse through the linked list to find the element matching the key using the equals method in the object.

So the equals and hascode methods are very important when storing values in the Map. Java has provided the hashcode and equals methods for the wrapper classes but if you wish to use user defined objects as key in the HashMap then you must override the equals and hashcode methods for the HashMap to work correctly.

2 different objects can have the same hashcode. If the hashcode is same, then it does not mean that both the objects are equal. However if 2 objects are equal, they must evaluate to same hashcode. This is primary rule you must keep in mind while overriding these two methods.

You must also note that you must try and create unique hashcode for each object as it would help in the performance of the map. A hashcode which returns the same integer all the time is also a correct implementation but then it will affect the performance of the HashMap as all the elements will be stored in the same bucket.

When we try and store two objects which are logically not equal but evaluate to same hascode, a hash collision is said to be occurred. This scenario must be avoided to improve the performance of the HashMap.

If you find this tutorial helpful, Please like it and comment if you are looking of any additional information on HashMaps.