HashMap works on the hashing technique. It uses the equals() and hashCode() methods on the key of the map to perform the get() and put() operations.
HashMap has an inner class called as Node Class which will hold the key, value pair of the map.
In HashMap we use the singly linked list to store the Entry<K, V> called as buckets.
put() Method :
When we call a put() operation on the HashMap, it will first check if the given key is null or not. If the given key is null then it will store it in the zeroth position since the hashCode value of null is always zero.
Otherwise the hashCode() value of the key is used to determine the bucket location for that particular entry.
After finding the bucket location for the Entry<K,V> it will check if there is already an entry in the bucket. If there is an Entry<K, V> then it calls the equals() method on the key to see if they are the same objects, if yes then it will replace that Entry<K,V>. If they are not same objects then it will add the new Entry<K,V> adjacent to the earlier Entry<K,V> in the same bucket.
get() Method:
For HashMap get() operation, when you call get(key) then if the key value is null then it fetches the value from the bucket zero, otherwise it will find the bucket location based on the hashCode() value of the key and then check if there are any entries in the bucket. If there is an Entry then it returns the Entry, but if there are multiple Entries in that bucket then it will use the equals() method to find out the Entry for that key and then return it. If no match is found for the key then it returns null.
Here is how the Node Class would like like:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
………………………………………
}
The next value here will always point to the next Entry in the bucket.
Implementing proper equals() and hashCode() methods is very important to avoid unwanted complexities.
Below image how the map would look like:
Lets look at an Example and see how it would work when we try to put and get the Elements
from the map.
Let's say we have the Employee class as below.
@Getter
@Setter
public class Employee {
private int id;
private String lname;
private String fname;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((fname == null) ? 0 : fname.hashCode());
result = prime * result + id;
result = prime * result + ((lname == null) ? 0 : lname.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
final Employee other = (Employee) obj;
if (fname == null) {
if (other.fname != null)
return false;
} else if (!fname.equals(other.fname))
return false;
if (id != other.id)
return false;
if (lname == null) {
if (other.lname != null)
return false;
} else if (!lname.equals(other.lname))
return false;
return true;
}
}
Now let's look at the below code snippet of operations on map.
final Employee e1= new Employee();
e1.setId(123);
e1.setFname("java");
e1.setLname("notes");
final Map<Employee,String> employeeMap= new HashMap<>();
employeeMap.put(e1, "developer");
here when we do the put() operation on the Employee e1, internally map will call the e1.hashCode() method and gets the hash value of "e1" based on the hash value generated it will find the bucket location for that entry. lets say we got a hash value of 7 from the hashCode method.
Now as shown in the below image it would look for the bucket 7 and see if there are already any entries in that bucket. since this is the first Entry that we have put in the map there are no Entry's yet, hence it would put the Entry of "e1" at bucket 7 as shown in below image.
Now let's create another Employee object and put it to the same map.
final Employee e2= new Employee();
e2.setId(123);
e2.setFname("java");
e2.setLname("notes");
employeeMap.put(e2, "tester");
In the above code snippet based on the equals() method that we have overridden in Employee class bot the "e1" and "e2" employee objects are equal here. hence there hashCode() values must be equal.
so when we put() operation on "e2" internally map calls the hashCode() method on the "e2" employee object and gets the hashCode() value and determines the bucket location. Here since the hashCode() value of "e1" is 7 the hashCode() value of "e2" also must be 7.
Hence it tries to put it int the bucket 7. before it puts it in the bucket 7 it checks if there are any entries already in the same bucket. since there is already an entry here "e1" as shown in the above image. it will check if both of them are equal by calling e1.equals(e2).
since both of them are equal here it will replace the existing value by the new value as shown in the figure(since the key values are already equal it doesn't touch it).
Now when you call
final String value1=employeeMap.get(e1);
final String value2=employeeMap.get(e2);
Both the value1 and value 2 will be "tester" here.
Now let's try to put() another Employee object.
final Employee e25= new Employee();
e25.setId(25);
e25.setFname("java25");
e25.setLname("notes25");
Now let's say Employee "e25" has the same hashCode value as "e1" ( This is called as collision, even the the objects are not equal there hashCode() values might be equal)
Now let's see how the behavior would be when we try to put() it in the map.
employeeMap.put(e25, "Manager");
Now as we put() "e25" in the map, internally map would call e25.hashCode() and determine the hashCode() value of "e25" and determine the bucket location.
As we discussed above , let's say the hashCode() value of "e25" is also 7, now it will try to put it in the bucket 7, but before putting it checks if there are already any entries in bucket 7.
In this case we have "e1" in bucket 7.
so it will check if both these objects are equal or not by calling e25.equals(e1).
It would return false here since both the objects are not equal.
since both the objects are not equal but there bucket locations are equal (since they have same hashCode()) it will put "e25" entry adjacent to the "e1" in the "linkedList" as shown in the below image.
Now let's try to put another Employee object.
final Employee e7= new Employee();
e7.setId(7);
e7.setFname("java7");
e7.setLname("notes7");
Now let's put employee "e7" in the map and see how it behaves.
employeeMap.put(e7, "BA");
As we put "e7" it checks for the hashCode() value of "e7" to determine the bucket location.
let's say the hashCode() value of "e7" is 3. It will try to put it in bucket 3 . A there are no other entries in bucket 3 it will just put it there with out any use of equals() method.
Now the map would be as shown in below image.
This is how the HashMap will work internally.