How the HashMap works in Java or working of the HashMap ?

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.