HashMap in Java Explained in Simple English with Examples.

HashMap in Java is a part of Java Collections Frameworks since Java 1.2 and provides the basic implementation of the Map interface in Java. It stores data in the form of Key and Value pairs where the key is a unique identifier used to associate each value on the Map. It means that every key is mapped to exactly one value and that we can use it to retrieve its corresponding value from the map.

One might ask, we already have so many data structures like Arrays, Linked List, etc, to store data, then what is the need to introduce a new one? The answer is simple, though the hashmap is used for the same thing as other data structures, it takes less time than them. 

HashMap takes a constant time to do every operation like add, delete, replace, etc whereas other data structures take the time equal to the amount of data stored in it – O(n) and O(log n) if the data is sorted. But everything comes at a price. The price we pay for using the hashmap is that it increases the amount of auxiliary space which will be equal to the number of items stored.

Now that we have a basic understanding of what a hashmap is and why was it introduced, let’s see how HashMap is different from others.

 Let’s begin… 

Index

1. What is HashMap in Java?
2. Initialization of HashMap in Java
3. Hierarchy of HashMap
4. Internal Structure of HashMap
5. Basic Operations of HashMap
   1. Adding Elements
   2. Changing Elements
   3. Removing Elements
   4. Iterating over HashMap
6. Different methods of HashMap
7. Factors affecting the performance of HashMap
   1. Initial Capacity
   2. Load Factor
   3. Threshold
8. Types of Constructors in HashMap
9. Sorting of HashMap
10. Summarizing
11. Conclusion

What is HashMap in Java?

As told above, it is a type of Data Structure that is used to store data in the form of key and value pairs where both key and value are initialized using object/wrapper classes of the primitive data types like Integer, Boolean, String – which is already a wrapper class.

While the values can also be initialized as other data structures like ArrayList, Linked List, etc, the keys can’t.

One important thing to note is that the key should always be unique thus we know but why? The reason is that they act as the index to store the respective values in their respective places, which is not fixed as HashMaps are unsynchronized.

This means that there can be multiple keys for the same value but vice versa is not possible. If something did happen of this sort, the initial value of the respective key will be updated by the new value we have introduced. We will understand this in more detail in the Basic Operations section.

Initialization of HashMap in Java

To use a HashMap in our Java Program, we first have to import it from java.util package, and then use the below syntax to initialize it in the program

HashMap<K, V> numbers = new HashMap<K, V>();

In the above code, we have created a hashmap named numbers. Here, K represents the data type that will be used for keys while V represents the data type or structure for values. 

Let’s understand thus with the help of an example –

HashMap<String, Integer> numbers = new HashMap<String Integer>();

In the above code, the String wrapper class has been used to initialize the keys while the Integer wrapper class has been used for values.

HashMaps are HashTable-based implementations of the Map interface. But as HashMaps are unsynchronized, they allow us to have any number of null values but only permit us to use one null key. 

The data in HashMap is unsynchronised as it does not take any guarantee that the order will remain the same as we store the data inside it over time. This is because the values are stored based on their hash values which makes it more efficient and is the reason for its constant time complexity.

Hierarchy of HashMap

HashMap implements Serializable, Cloneable, Map<K, V> interfaces. HashMap extends AbstractMap<K, V> class. The direct subclasses are LinkedHashMap, PrinterStateReasons

Syntax: Declaration

public class HashMap<K,V> extends AbstractMap<K,V>  implements Map<K,V>, Cloneable, Serializable

Parameters: It takes two parameters which are as follows:

• The type of keys maintained by this map
• The type of mapped values

Internal Structure of HashMap

HashMap contains an array of nodes, which is represented as a class. It uses an array and LinkedList data structure internally for storing Key and Value pairs. There are four fields in HashMap.

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

Basic Operations of HashMap

Adding Elements

To add a certain amount of elements to the HashMap, we have to use the put method but as HashMaps are unsynchronized they will be stored based on their hash values.

package com.Tekolio.HashMap;
 
import java.util.HashMap;
 
public class put_method {
   public static void main(String[] args) {
       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       map.put(1,11);  
       map.put(2,12);
       map.put(3,12);
       map.put(4,14);
       System.out.println(map);
   }
}

Output 

Mappings of HashMap (map) are : {1=11, 2=12, 3=12, 4=14}

In the above code, we have made a HashMap- a map with both key and value as Integers and added some value to it using the put method as discussed above.

It is quite clear from the above code that the put methods also require both the key and the value to add a particular element into the HashMap, and also that values can be repeated but keys have to be unique.

Changing Elements

We have seen how to add elements in a HashMap using the put method, but what if we want to change the value of the data we have added in the HashMap.

Since the elements in the map are indexed using the key, it can also be used to update a value, we just have to use the put method again as if we are adding a new value but with an already used index or key.

The process is very simple, as we add the new value with a repeating key, the value which was mapped initially with that key will be replaced with the new value and now our HashMap will have a new value that can either be unique or the same. 

Check the below code for a better understanding of this.

package com.Tekolio.HashMap;
 
import java.util.HashMap;
 
public class put_method {
   public static void main(String[] args) {
       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       map.put(1,11);  //Put elements in Map
       map.put(2,12);
       map.put(3,12);
       map.put(4,14);
        System.out.println("Original map values are : " + map);
        map.put(3, 23);
        System.out.println("Updated map values are : " + map);
   }
}

Output

Removing Element

We can easily remove an element from a HashMap just by using the remove() method. This method uses both the key and its value to work, and it removes the element from the HashMap simply by removing its mapping for that key.

package com.Tekolio.HashMap;
 
import java.util.HashMap;
 
public class remove_method {
   public static void main(String[] args) {
       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
       map.put(1,11);  //Put elements in Map
       map.put(2,12);
       map.put(3,12);
       map.put(4,14);
       System.out.println("Original map values are : " + map);
       map.remove(3, 12);
       System.out.println("Updated map values are : " + map);
   }
}

Output

It is clear from the above output that the value for the 3 rd key has been removed and is no longer mapped, this is due to the remove method.

Iterating over the HashMap

If we want to traverse over any data structure of the collections framework like ArrayList, LinkedList, hashmap, etc, we have to use the iterator interface, but for HashMaps we can’t just use it directly.

This is because iterators work with one type of data, but in HashMaps we have two of them – key and value. So we will use the Map.Entry<K, V> method which is the most common method used for iterating over the HashMap so that we can get both the keys and the values as it allows us to iterate over then as well.

This method returns a collection-view of the mappings contained so that we can iterate over key-value pairs using the getKey() and getValue() methods of Map.Entry<K, V>.

package com.Tekolio.HashMap;
 
import java.util.HashMap;
 
public class iterateHashMap {
    public static void main(String[] args) {
        // Initialization of a HashMap
        HashMap<String, Integer> map = new HashMap<>();
 
        // Add elements
        map.put("Apple", 100);
        map.put("Orange", 70);
        map.put("Banana", 50);
 
        // Iterating the map using for-each loop
        for (HashMap.Entry<String, Integer> m : map.entrySet())
            System.out.println("Key: " + m.getKey()
                            + " Value: " + m.getValue());
    }
}

Output

Different Methods of HashMap in Java

In the above section, we have already seen some of the methods of HashMap like put(), get(), remove(), etc. Here, are some of the other methods that the HashMap has provided us with

Factors affecting the Performance of HashMap in Java

The performance of the HashMap mainly depends on two factors – Initial Capacity and the Load Factor.

Rehashing is the process of creation of an array internally with twice the size of the initial one, and all the entries are moved into it. 

These are optional values that can be inserted while initializing a HashMap inside those empty parenthesis which is by default empty denoting the use of default values for them.

HashMap hm=new HashMap(int initialCapacity, float loadFactor);  

Lets take an example to understand this better – 

HashMap<K, V> numbers = new HashMap<>(16, 0.75f);

Here – 16 is the capacity with which the HashMap has been initialized, and 0.75 is its load factor which is always written with ‘f’ as the data type used for it is float. See the actual syntax below

Type of Constructors of HashMap in Java

HashMap provides us with 4 types of constructors and access modifiers based on the value of capacity and load factor – 

1. HashMap()
2. HashMap(int initialCapacity)
3. HashMap(int initialCapacity, float loadFactor)
4. HashMap(Map map)

Sorting of HashMaps in Java

We know that HashMaps are unsynchronized in nature – it means that it allows multiple threads to read and edit its data which as we know is stored in the form of key and value pairs, and we also know that the ordering of elements inside HashMap which depends upon their hash values which is the main reason for its constant time complexity for some of the basic operations.

But what if I tell you that it is possible to arrange these values in any order as we see fit using sorting and the comparator function. The thing that makes HashMap so useful in the real world is its ability to store the values in key and value pairs which have made life easier in more cases than one. And the same is also true when it comes to sorting. 

We can sort HashMaps based on their keys and values and there are different tricks to it as well, but in this blog, we will only be seeing one of those tricks that are to sort the HashMap using the Collection.sort and the LinkedList for both keys and values.

Sorting HashMap based on its values

Here sorting will be done by using the Collections.sort() method and that too with the help of a Comparator. The idea behind this process is to first all the values into a LinkedList which will then be sorted using the comparator functions and will be stored again but this time in a LinkedHashMap.

Algorithm

1. Copy the elements of the HashMap into a LinkedList as ArrayList is dynamic thus removing all possibility of memory loss.
2. Sort the LinkedList using the Collections.sort() method.
3. Copy the list items into a LinkedHashMap – the advantage of using a LinkedHashMap is that we can access the elements in their insertion order.
4. Return the LinkedHashMap 

We can also use the Arraylist as it is also dynamic. The only difference would have been that in ArrayList we have to use the @Override to get the sorting done.

package com.Tekolio.HashMap;
import java.util.*;
class sortHashMapByValue {
    public static void main(String[] args) {
        HashMap<String, Integer> hashmap = new HashMap<String, Integer>();
 
        hashmap.put("Apple", 5);
        hashmap.put("Mango", 7);
        hashmap.put("Orange", 3);
        hashmap.put("Grapes", 9);
        hashmap.put("Dates", 0);
        hashmap.put("Cherry", 8);
 
        Map<String, Integer> map = sortByValue(hashmap);
 
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key : " + entry.getKey()+ ", Value : "+ entry.getValue());
        };
    }
    static HashMap<String, Integer> sortByValue(HashMap<String, Integer> hm)
    {
        // Creating a list from elements of HashMap
        List<Map.Entry<String, Integer> > list
            = new LinkedList<Map.Entry<String, Integer> >(
                hm.entrySet());
 
        // Sorting the list using Collections.sort() method
        // using Comparator
        Collections.sort(
            list,
            new Comparator<Map.Entry<String, Integer> >() {
                public int compare(
                    Map.Entry<String, Integer> object1,
                    Map.Entry<String, Integer> object2)
                {
                    return (object1.getValue())
                        .compareTo(object2.getValue());
                }
            });
 
        // putting the data from sorted list back to hashmap
        HashMap<String, Integer> result = new LinkedHashMap<String, Integer>();
        for (Map.Entry<String, Integer> me : list) {
            result.put(me.getKey(), me.getValue());
        }
 
        // returning the sorted HashMap
        return result;
    }
}

Output

Sorting HashMap based on its keys

The process remains the same but this time rather than using a LinkedList we will use an ArrayList, but don’t get confused as long as there is no memory loss, we can use any of the two lists.

As told the process remains the same – 

1. Copy the elements of the HashMap into an ArrayList.
2. Sort the List using the Collections.sort() method.
3. Print the sorted HashMap

Its implementation is given below

package com.Tekolio.HashMap;
import java.util.*;
class sortHashMapByKey {
    // This map stores unsorted values
    static Map<String, Integer> hashmap = new HashMap<>();
 
    // Function to sort the map by Key
    public static void sortbykey()
    {
        ArrayList<String> sortedKeys = new ArrayList<String>(hashmap.keySet());
 
        Collections.sort(sortedKeys);
 
        // Display the TreeMap which is naturally sorted
        for (String x: sortedKeys)
            System.out.println("Key = " + x + ", Value = " + hashmap.get(x));
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // putting values in the Map
       hashmap.put("Apple", 5);
        hashmap.put("Mango", 7);
        hashmap.put("Orange", 3);
        hashmap.put("Grapes", 9);
        hashmap.put("Dates", 0);
        hashmap.put("Cherry", 8);
 
 
        // Calling the function to sortbyKey
        sortbykey();
    }
}

Output

Time and Space Complexity

Time Complexity – O(n log n) – 

Here we have performed the sorting operating inside a LinkedList which has the worst time of O(n log n) and by storing all the values into a LinkedHashMap it became O(n log n) + n which according to the rules of time complexity becomes O(n log n).

Space Complexity – O(n) – simply due to HashMap and lists

Summarizing

1. HashMap stores values in key and value pairs where value can be extracted using its key as it works as the index values for those values.
2. HashMap uses a process called hashing to store values depending upon their key values.
3. Because of this, every process that doesn’t require iterating through the entire HashMap has a time complexity of O(1).
4. HashMap doesn’t allow duplicate keys but allows duplicate values. 
5. HashMap allows one null key, but multiple null values.
6. This class makes no guarantees that the order will remain constant over time as it is unsynchronised.
7. HashMap extends an abstract class AbstractMap which also provides an incomplete implementation of the Map interface.
8. It also implements a Cloneable and Serializable interface. K and V in the above definition represent Key and Value respectively.
9. The initial default capacity of the Java HashMap class is 16 with a load factor of 0.75.

Conclusion

In this blog, we have learned many interesting things about HashMap it stores data in the form of keys and values where keys are unique and can be considered as its index value but the stored data don’t need to stay as it is as HashMaps are unsynchronised and the value is stored based on their hash value.

But this is not the reason for the popularity of HashMaps, it is because of the operations that these data structures perform and that too only in a constant time while other data structures like arrays, LinkedList, etc take a linear time to do them.

This is because in other data structures we over iterate over them completely just to add or remove a specific element from them but in HashMap as it uses a process called hashing, we dont have to iterate over it, just need to use the inbuilt methods as described in this blog. Making it one of the most used data structures.

Frequently Asked Questions