How HashMap works in Java ?
I will explain put and get operation done in HashMap in
pictorial representation so that you will get clear idea what
exactly happens inside.
What is HashMap ?
HashMap is in the java.util package. This package provides
lot of inbuilt data structure so the we need not to implement it by our own.
So maps are associated arrays that let programmer stores
the key-value pairs. We need key and value to store in the hash map and later on
we need that key to look for the stored value in the hash map.
HashMap is the implementation of the Map interface. It is
based on a function called Hashing.
Hashing is a technique by which you can short a big length
String or Object into a fixed length number or representation. Eg, a long
string, hashing can convert this string in a number.That helps in indexing and faster lookup.
As we know, each object in java has hash code method
available.So this method is supposed to return hash code of the object.
Also there is a equal and hash code contract in java. If two
objects are equal, there hash code should be same. So it is very important that there should be a robust implementation of hash code in class.
Why this hashcode is so important?
It is important because hash code
is used in storing values into the HashMap. If we lookup a value in the
corresponding given key and if the hash code is not consistent you wont be able
to lookup the corresponding value.
 |
| Map Hierarchy |
 |
| Node of the HashMap and its fields |
Lower level details:
HashMap has a table as an array of Node as show in the
diagram.
Node has integer hash, K as key of the HashMap, V as the
value of the corresponding key of the HashMap and Node<K, V> next as the
next pointer to the next node of the linked list.Basically the node itself is a
linked list.
So as in blue array diagram, each index of it is a Node of
linked list and we call it bucket.Each index is a bucket and each bucket is a
node or can be a linked list of nodes.
Implementation of the put method of the HashMap:
As I said a HashMap comprises of a table and a table is
bydefault of size 16.
 |
| HashMap Tabular Structure (defauld size is 16) |
So for example we need to put below student entries in this table, lets
see how does it put in this table:
Eg.
HashMap student = new HashMap();
student.put(“AJAY”,12);
student.put(“VIJAY”,32);
student.put(“SHARMA”,22);
Case 1:
Lets put AJAY as key and 12 as value of this key in hashmap
student.put(“AJAY”,12);
put(K k, V v){
hash(k); => hash(“AJAY”) = 23462031
index = hash &
(n-1); => index = 4
}
Here suppose hash code generated by hash(k) method of AJAY is 2346031.So we can not have
array of this size because if each and every hash is going to have this much
big number array with in it, soon we will run out of memory.
So we need to
compute index to find out where we can put the value in given 2 raise to power
n array which is 0 to 15 indexed.
That's why index is computed using modular operator. So basically we
divided the hash to the maximum value of the range of array and we will get the
reminder which will fit in the array range.
Suppose the index calculated here is 4. So the entry will
go under index 4 as a node as shown below:
 |
| Put Node values at index 4 |
Case 2:
student.put(“VIJAY”,32);
put(K k, V v){
hash(k); => hash(“VIJAY”) = 25462032
index = hash &
(n-1); => index = 4
}
Case 3:
student.put(“SHARMA”,22);
put(K k, V v){
hash(k); => hash(“SHARMA”) = 6416803
index = hash &
(n-1); => index = 9
}
after inserting all 3 cases, we will form below hashmap structure. At array index 4 there would be two nodes added as linked list.
 |
| After inserting all key-value pairs |
So in case of AJAY and VIJAY keys, we have collision because
we have same index. So the next will point to the new node added in the linked
list of existing node.
This is how the hashmap will look like at the end of the put
operation
So here we have seen if there is same index of the key, then
those node will be stored in the bucket as linked list nodes.
Java HashMap allows null key, which always goes to index 0
as hash of null is 0.
How get method works in HashMap ?
Suppose we need to get key: SHARMA from hash map.
V get(Objcet key){
hash(key) => 23462031
index = hash & (n-1) => 9
}
 |
| checking hash code and key value of map |
In the get operation, we do the same set of operations to
calculate the hash and find index of the key where it could have store the
value in the array.
So it will compare the hash code which is 23462031 and if it
matches then we will compare the key using equal method which is SHARMA in
this case.If both matches, it will get the value.
Now we need to get key VIJAY
V get(Objcet key){
hash(key) => 25462032
index = hash & (n-1) => 4
}
 |
| get operation on hash map |
Same thing happens in case of VIJAY but at index 4, we have
two nodes in the bucket.
It will first compare hash code with first node which is not
same, so it skip this node.Then It will check next nodes hash code which matched
and then compare the key of with the same node using equal method which matched
and returns the value 32 of this node.
