Internal Working of HashMap:
Since HashMap allows NULL key so the hash Code of NULL is always ZERO(0).
Hashing: - Hashing is a process of converting an object into integer by using method hashCode().
hashCode() method:
-hashCode() method is used to get the hash Code of an object.
-hashCode() method of object class returns the memory reference of object in integer form.
Buckets:
-A bucket is nothing but a one element of Array which is used to store node.
-If two or more node have same bucket then link list structure is used to connect the nodes.
Index Calculation in Hashmap
-hash code generated may be in the range of integer and if we create arrays for such a range, then it will easily cause
outOfMemoryException.
-So we generate index to minimize the size of array.
Index = hashCode(key) & (n-1)
where n is number of buckets or the size of array. In our example, I will consider n as default size that
is 16.
Override hashCode and equals in Student class
@Override
public int hashCode() {
return (int)this.name.charAt(0);
@Override
public boolean equals(Object obj) {
return this.name.equals((String)obj);
}
Example:
Map<Student,Integer> map=new HashMap<Student, Integer>();
Steps 1: map.put(new Student(“vishal”) , 20);
1 calculate hash code of key(“vishal”). Suppose it will generate 118.
2 calculate index by using index method it will be 6.
3 create node object as:
{
Hashcode = 118
Key = “vishal”
Value = 20
Next node = null
}
4 Place this object at index 6 if no other object is presented there.
Steps 2 : map.put(new Student(“sachin”),30);
1 calculate hash code of key(“sachin”). Suppose it will generate 115.
2 calculate index by using index method it will be 3.
3 create node object as:
{
Hashcode = 115
Key = “sachin”
Value = 30
Next node = null
}
4 place this object at index 3 if no other object is presented there.
Steps 3: In Case of collision: map.put(new Student(“vaibhav”),40);
1 calculate hash code of key(“vaibhav”). Suppose it will generate 118.
2 calculate index by using index method it will be 6.
3 create node object as:
{
Hashcode = 118
Key = “vaibhav”
Value = 40
Next node = null
}
4 place this object at index 6 if no other object is presented there.
5 In this case a node object is found at the index 6 – this is a case of collision.
6 In that case, check via hashCode() and equals() method that if both the keys are same.
7 If keys are same, replace the value with current value.
8 Otherwise connect this node object to the previous node object via linked list and both are stored at index 6.
Note : node at index 6 (vishal) is now start point to next node (vaibhav).now the next node element is
NOT NULL
Using get method() : get method is used to get value by its key.
Example : map.get(new Student(“sachin”));
Steps:
1. Calculate hash code of Key {“sachin”}. It will be generated as 115.
2. Calculate index by using index method it will be 3.
3. Go to index 3 of array and compare first element’s key with given key. If both are equals
then return the value, otherwise check for next element if it exists.
4. In our case it is found as first element and returned value is 30.
.
Example : map.get(“vaibhav”);
Steps:
1. Calculate hash code of Key {“vaibhav”}. It will be generated as 118.
2. Calculate index by using index method it will be 6.
3. Go to index 6 of array and compare first element’s key with given key. If both are equals
then return the value, otherwise check for next element if it exists.
4. In our case it is not found as first element and next of node object is not null.
5. If next of node is null then return null.
6. If next of node is not null traverse to the second element and repeat the process 3 until
key is not found or next is not null.
