HashMap in Java was introduced in Java 1.2 release along with all other Collection utilities. HashMap in Java provides the basic implementation of Map interface of Java. It stores the data in Key, Value pairs. Key is unique in Map whereas value can be duplicate. Values are accessed by their associated key.

HashMap in Java uses a technique called Hashing in its implementation. Hashing is a technique, used in Java, of converting a large String to small String that can be used to represents the same String.

public class HashMap<K,V>

extends AbstractMap<K,V>

implements Map<K,V>, Cloneable, Serializable

Important things to remember about HashMap :

• HashMap is a part of java.util package.
• HashMap class is the implementation class of Map interface.
• A HashMap cannot contain duplicate keys but it can contain duplicate values.
• Java HashMap allows null values and only one null key.
• HashMap does not guarantee the order. It is an unordered collection.
• Java HashMap is not thread-safe. In order to make it thread-safe, you may have to implement synchronization technique explicitly.

Internal Working of HashMap in Java

In this article, we will see how hashmap’s get and put method works internally. What operations are performed. How the hashing is done. How the value is fetched by key. How the key-value pair is stored.

HashMap contains an array of Node and Node can represent a class having following objects :

1. int hash
2. K key
3. V value
4. Node next

Hashing is a process of converting an object into integer form by using the method hashCode(). Its necessary to write hashCode() method properly for better performance of HashMap.

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. Definition of hashCode() method is public native hashCode(). It indicates the implementation of hashCode() is native because there is not any direct method in java to fetch the reference of object. It is possible to provide your own implementation of hashCode().
In HashMap, hashCode() is used to calculate the bucket and therefore calculate the index.

equals() method is used to check that 2 objects are equal or not. This method is provided by Object class. You can override this in your class to provide your own implementation.
HashMap uses equals() to compare the key whether the are equal or not. If equals() method return true, they are equal otherwise not equal.

A bucket is one element of HashMap array. It is used to store nodes. Two or more nodes can have the same bucket. In that case link list structure is used to connect the nodes. Buckets are different in capacity.

A single bucket can have more than one nodes, it depends on hashCode() method. The better your hashCode() method is, the better your buckets will be utilized.

Index Calculation in Hashmap

Hash code of key may be large enough to create an array. 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. Basically following operation is performed to calculate index.

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.

What Is Entry Class?

HashMap has an inner class called an Entry Class which holds the key and values.

There is also something called next, which you will get to know a bit later.

 static class Entry<K,V> implements Map.Entry<K,V> 
{

final K key;

V value;

Entry<K,V> next;

final int hash;

........
}

You know that the HashMap stores the Entry instances in an array and not as key-value pairs. In order to store a value, you will use the put() method of the HashMap. Let’s dig into that and see how it works.

How Does the Put() Method Work Internally?

First, it checks if the key given is null or not. If the given key is null, it will be stored in the zero position, as the hashcode of null will be zero.

Then it applies the hashcode to the key .hashCode() by calling the hashcode method. In order to get the value within the limits of an array, the hash(key.hashCode()) is called, which performs some shifting operations on the hashcode.

The indexFor() method is used to get the exact location to store the Entry object.

Then comes the most important part — if two different objects have the same hashcode (e.g. Aa and BB will have the same hashcode), will it be stored in the same bucket? To handle this, let’s think of the LinkedList in the data structure. It will have a “next” attribute, which will always point to the next object, the same way the next attribute in the Entry class points to the next object. Using this different objects with the same hashcode will be placed next to each other.

In the case of the Collision, the HashMap checks for the value of the next attribute. If it is null, it inserts the Entry object in that location. If the next attribute is not null, then it keeps the loop running until the next attribute is null then stores the Entry object there.

How Does the Get() Method Work Internally?

Almost the same logic applied in the put() method will be used to retrieve the value.

1. First, it gets the hash code of the key object, which is passed, and finds the bucket location.
2. If the correct bucket is found, it returns the value.
3. If no match is found, it returns null.

What Happens If Two Keys Have the Same Hashcode?

The same collision resolution mechanism will be used here. key.equals(k) will check until it is true, and if it is true, it returns the value of it.

HashMap Changes in Java 8

As we know now that in case of hash collision entry objects are stored as a node in a linked-list and equals() method is used to compare keys. That comparison to find the correct key with in a linked-list is a linear operation so in a worst case scenario the complexity becomes O(n).
To address this issue, Java 8 hash elements use balanced trees instead of linked lists after a certain threshold is reached. Which means HashMap starts with storing Entry objects in linked list but after the number of items in a hash becomes larger than a certain threshold, the hash will change from using a linked list to a balanced tree, which will improve the worst case performance from O(n) to O(log n).

Obtaining the entrySet, keySet, and values from a HashMap

The Map interface provides methods to retrieve the set of entries (key-value pairs), the set of keys, and the collection of values.

The following example shows how to retrieve them from a HashMap –

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class HashMapEntryKeySetValuesExample {
    public static void main(String[] args) {
        Map<String, String> countryISOCodeMapping = new HashMap<>();

        countryISOCodeMapping.put("India", "IN");
        countryISOCodeMapping.put("United States of America", "US");
        countryISOCodeMapping.put("Russia", "RU");
        countryISOCodeMapping.put("Japan", "JP");
        countryISOCodeMapping.put("China", "CN");

        // HashMap's entry set
        Set<Map.Entry<String, String>> countryISOCodeEntries = countryISOCodeMapping.entrySet();
        System.out.println("countryISOCode entries : " + countryISOCodeEntries);

        // HashMap's key set
        Set<String> countries = countryISOCodeMapping.keySet();
        System.out.println("countries : " + countries);

        // HashMap's values
        Collection<String> isoCodes = countryISOCodeMapping.values();
        System.out.println("isoCodes : " + isoCodes);
    }
}

# Output
countryISOCode entries : [United States of America=US, Japan=JP, China=CN, India=IN, Russia=RU]
countries : [United States of America, Japan, China, India, Russia]
isoCodes : [US, JP, CN, IN, RU]

Iterating over a HashMap

The following example shows different ways of iterating over a HashMap –

1. Iterating over a HashMap using Java 8 forEach and lambda expression.
2. Iterating over the HashMap’s entrySet using iterator().
3. Iterating over the HashMap’s entrySet using Java 8 forEach and lambda expression.
4. Iterating over the HashMap’s entrySet using simple for-each loop.
5. Iterating over the HashMap’s keySet.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class IterateOverHashMap {
    public static void main(String[] args) {
        Map<String, Double> employeeSalary = new HashMap<>();
        employeeSalary.put("David", 76000.00);
        employeeSalary.put("John", 120000.00);
        employeeSalary.put("Mark", 95000.00);
        employeeSalary.put("Steven", 134000.00);

        System.out.println("=== Iterating over a HashMap using Java 8 forEach and lambda ===");
        employeeSalary.forEach((employee, salary) -> {
            System.out.println(employee + " => " + salary);
        });

        System.out.println("\n=== Iterating over the HashMap's entrySet using iterator() ===");
        Set<Map.Entry<String, Double>> employeeSalaryEntries = employeeSalary.entrySet();
        Iterator<Map.Entry<String, Double>> employeeSalaryIterator = employeeSalaryEntries.iterator();
        while (employeeSalaryIterator.hasNext()) {
            Map.Entry<String, Double> entry = employeeSalaryIterator.next();
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }

        System.out.println("\n=== Iterating over the HashMap's entrySet using Java 8 forEach and lambda ===");
        employeeSalary.entrySet().forEach(entry -> {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        });

        System.out.println("\n=== Iterating over the HashMap's entrySet using simple for-each loop ===");
        for(Map.Entry<String, Double> entry: employeeSalary.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }

        System.out.println("\n=== Iterating over the HashMap's keySet ===");
        employeeSalary.keySet().forEach(employee -> {
            System.out.println(employee + " => " + employeeSalary.get(employee));
        });
    }
}

# Output
=== Iterating over a HashMap using Java 8 forEach and lambda ===
David => 76000.0
John => 120000.0
Mark => 95000.0
Steven => 134000.0

=== Iterating over the HashMap's entrySet using iterator() ===
David => 76000.0
John => 120000.0
Mark => 95000.0
Steven => 134000.0

=== Iterating over the HashMap's entrySet using Java 8 forEach and lambda ===
David => 76000.0
John => 120000.0
Mark => 95000.0
Steven => 134000.0

=== Iterating over the HashMap's entrySet using simple for-each loop ===
David => 76000.0
John => 120000.0
Mark => 95000.0
Steven => 134000.0

=== Iterating over the HashMap's keySet ===
David => 76000.0
John => 120000.0
Mark => 95000.0
Steven => 134000.0

That’s all readers. Thanks a lot for reading this article. I hope you find it useful. Please do post your comments / suggestions / questions / feedback in below comment box.

You can also connect with me directly through social media accounts. Stay Tuned!!!!