HashMaps in Java

Hi guys! Doing great? Today I brought a Java article for you. You may have already worked with Java HashMaps. Actually what is a HashMap? Simply, it's a data structure that stores data with unique keys as key value pairs. My focus is to share some deeper knowledge on how HashMap works internally. Compared to the other data structures like array, HashMap can be considered as the most efficient one for insertion and access of an element with time complexity of O(1).

How HashMap works internally?

Declare a HashMap

Map<Integer,Integer> map = new HashMap<>();

HashMap is implemented by Map interface in Java. HashMap is well known for storing unique keys when storing data. So before moving on I will tell you what is meant by hashing..

Hashing
It's a simple way to assign a unique code for any variable/object after applying any function/algorithm on its properties. This will output a  fixed length string. Java achieves this using hashCode method defined in the most super class of all classes called Object.

So when we declare a HashMap object, by default it will create a 16 bit space in the memory at back-end. This space is called as an array of buckets. Each bucket is a Node and that can be a LinkedList. So, when we take a Node, it has several properties. They are hash, key, value and pointer to the next node. I will explain the stuff using the operations in HashMap.

PUT operation

This operation takes a K key and V value as arguments to store a data point as a key value pair. Then key is taken and hashing function is performed on it. For this, Java uses inbuilt hashCode function. It gives a bit long string as the output. But holding large values takes more memory and slows down the searching. So, using this generated hash, index is calculated which should be in the range of 0-15. Because the data point should be assigned into a bucket with index within 0 to 15.

Let's assume we are going to store name and age of a person as a key value pair. Age is the value and name is the key here.

map.put("John", 27);

When map is going to insert this, it calculates hash of key - "John".  Let's say 123456. Then it is converted into an index - assume it's 4. Now map searches for the bucket with index 4. When it's found, data is stored as a Node in the bucket with the details - hash, key, value and pointer. If a particular node do not have next nodes, pointer is stored as null.

GET operation

When we need to get a particular value for a key, We have to specify the key in this method. It takes K key as the argument.

map.get("John");

What is happening in the back-end? Basically 2 things are happening. First this method generate hashCode for the key(here, 123456). And then calculate the index also as previous operation. Now the matching part is going to perform. After getting the index - in our case; map looks for index 4 in the bucket array. When an entry is found, it compares the  the hashCode of the key against the hashCode stored in the entry. If that matches, then it compares the key against the key stored in the entry using equals method in Java. If these both conditions become true, the value of the entry is returned.

NOTE:
HashMap allows us to store a key as NULL and it will always stored as the 0th(zero) indexed bucket.

Simply this is the way a HashMap works in Java. But there are few concerns to be raised.

1. What happens when two KEYS are similar?

Assume that we are going to put the following two data points.
1. map.put("Ben", 25)
2. map.put("Ben", 28)

Since the Key is same, hashCode will generate same vale for both instances. First Ben and 25 is stored in the map in a particular index. Then whatever the key comes with the same hashCode, updates the existing entry in the index and modify the value. Last entry stored in the map will be Ben with 28.

NOTE:
Here keys are similar. Therefore hashCodes, indexes are also similar.


2. What happens when two different keys are giving the same HASH value?

There we find a Hash Collision! Let's look into that..
Let's assume that we are going to put the following two data points.
1. map.put("John", 27)
2. map.put("Ben", 25)

Somehow, imagine the two keys - John and Ben are generating same hashCode. So the first record is stored without any issue. Then the second record is going to stored. Due to the generation of same hash, the index generated for second record will be the same as first. Now map looks for particular index(Let's say 5). There it finds there's an entry already in the 5th indexed bucket. So here the collision is occurred. 

When two different keys have same Hash and points to same index in array of buckets

In cases like this, Java uses a Resolution Technique to overcome this problem.

• Here, hashCode() and equals() methods are performed on the entries.
• If keys are same,old value is replaced with the new value.
• If keys are different, the second data point which is pointing to the same bucket index, will be added as the next Node in the existing LinkedList of first data point.

Previously I told that each Node stores the pointer to the next node. But when there's no next nodes, it is NULL. But now, we have an entry. So it is stored in the manner of LinkedLists. It can be shown like this.

NOTE:
Here keys are NOT similar. BUT hashCodes, indexes are similar.


Example:
Let's assume we are going to put the below records into a HashMap. Consider that 1 and 2 records have different keys but same hashCodes.

1. map.put("John", 27)
2. map.put("Ben", 25)
3. map.put("Jack", 28)
4. map.put("Mike", 30)
5. map.put("Bob", 29)
6. map.put(null, 24)

Practical Implementation with Java

        
        Map<String, Integer> map = new HashMap<>();

        // PUT OPERATION
        map.put("John",27);
        map.put("Ben",25);
        map.put("Jack",28);
        map.put("Mike",30);
        map.put("Bob",29);

        // GET OPERATION
        System.out.println(map.get("John"));
        System.out.println(map.get("Ben"));

        // ITERATE OVER THE MAP
        for (Map.Entry<String, Integer> entry: map.entrySet()){
            System.out.println(entry.getKey()+ " -> "+entry.getValue());
        }

        // CHECK THE EXISTENCE OF KEY AND VALUE
        System.out.println(map.containsKey("John"));
        System.out.println(map.containsValue(20));

        // PRINT MAP
        System.out.println(map);
        
        // PRINT ENTRIES
        System.out.println(map.entrySet());

        // GET ALL KEYS IN MAP
        System.out.println(map.keySet());

        // GET ALL VALUES IN MAP
        System.out.println(map.values());

So guys, this is the knowledge that I wanted to share with you. Look around and explore more about the map implementations by your own coding. It will help you to improve more.

That's all guys! Bye bye!!!