HashMap in JAVA

Hashing

Hashing is the process of converting an object into an integer value. For indexing and faster searches, this is helpful.

HashMap

We all know about Java collection framework and HashMap is part of it. It uses Hashing technique and implements map interface. A pair of key and value can be stored by using it.

HashMap is popular in between programmers. You will get an array of nodes there in a HashMap where the node is represented as a class. To Store Key and Value, HashMap uses an array and LinkedList data structure. Four fields exist in HashMap.

It is vital to know properly about hashCode() and equals() method before knowing the working principle of HashMap.

• equals():
  • It checks whether the two objects are equal or not.
  • It compares the Key of two objects.
  • It is a method of the Object class.
  • It can be overridden. Overriding equals() method is equally important compared to override the hashCode() method, at the same time.
• hashCode():
  • This is the method of the object class.
  • This method returns integer value of the memory reference of the object.
  • The value received from the method is used as the bucket number.
  • The bucket number is the address of the element inside the map.
  • Hash code of null Key is 0.
• Buckets:
  • Array of the node is called buckets.
  • Each node has a data structure like a LinkedList.
  • More than one node can share the same bucket. It may be different in capacity.

Insert (Key, Value) pair in HashMap

put() method is used to insert the Key and Value pair in the HashMap. The default size of HashMap is 16 (0 to 15).

Example

In the following example, we want to insert four (Key, Value) pair in the HashMap.

1. HashMap<String, Integer> map = newHashMap<>();  
2. put(“Sukanta”, 18);  
3. put(“Souvan”, 28);  
4. put(“Asad”, 38);  

Let’s see how (Key, value) pair will be saved into HashMap. After calling the put() method, it calculates the hash code of the Key “Sukanta.” Suppose the hash code of “Sukanta” is 4527859. To store the Key in memory, we need to calculate the index.

Calculating Index

This is useful and interesting. Index minimizes the size of the array. The Formula for calculating the index is:

Index = hashcode(Key) & (n-1)  

here, n is the size of the array. The index value for “Sukanta” is:

Index = 4527859 & (16-1) =4  

The value 4 is the computed index value and in this position, the Key and value will store in HashMap.

Hash Collision

When calculated index value results same for two or more keys, this is known as Hash Collision. Let’s calculate the hash code for another Key “Souvan.” Suppose the hash code for “Souvan” is 36829104. To store the Key in the memory, we have to calculate index by using the index formula.

Index=36829104 & (16-1) = 4  

Computed index value is also 4 for this key. In this case, equals() method will check whether both Keys are equal or not. If Keys are same, replace the value with the current value. Otherwise, connect this node object to the existing node object using the LinkedList. Hence both Keys will be stored at index 4.

Similarly, we will store the Key “Asad” Suppose hash code for the Key is 3249873. The index value will be 1. Hence this Key will be stored at index 1.

get() method in HashMap

To get the value by its key, get method is used. If the key is not familiar, it will not fetch the key.

When get(K Key) method is called, the hash code of the Key is caluclated.

Suppose we have to fetch the Key “Sukanta” The following method will be called.

get(newKey(“Sukanta”));  

It generates the hash code as 4527859. By using index formula, we calculate the index value of 4527859 . The index value will be 4, as we have calculated above. get() method search for the index value 4. It compares the first element Key with the given Key. If both keys are equal, then it returns the value else check for the next element in the node if it exists. It is found as the first element of the node and return the value 18.

Let’s consider another Key “Souvan”

The hash code of the Key “Souvan” is 36829104. The calculated index value of 36829104 is 4. Now, it will go to index 4 of the array and compare the first element’s Key with the given Key. It also compares Keys. In this circumstances, the given Key is the second element, and the next of the node is null. It compares the second element Key with the specified Key and returns the value 28. It returns null if the next of the node is null.