Introduction

In simple terms, HashMap is the class of the Java collection framework that provides the functionality of hash table data structures.

It is a basic implementation of the Map interface. HashMap stores data in (Key, Value) pairs. One key and any number of values are allowed to be Null. We need to import java.util.HashMap to use this class and its methods.

Many of you are wondering what is a hash table data structure.

It's the best way to store data in array format. Insertion, searching, and deletion of data become efficient due to the hashing technique used in this data structure.

Some gist of the Hashing technique and which function it uses inside:

Two functions →

1. one to one →h(x) = x space might be left unused

2. Many to one h(x) = x% size will create a collision

For removing collision →

1. Linear Probing → h(x) = x%size

h’(x)=[h(x)+f(i)%size] ,,, f(i) = i where i=0,1,2→ it will create clustering and takes time in searching

1. Quadratic Probing →h(x) = x%size

h(x)=[h(x)+f(i)%size] ,,, f(i) = i^2 where i=0,1,2→ It will avoid the problem caused by Linear probing

Now let's jump into the topic

Implementation of HashMap

1) Creating

In the below code, we have created a hashmap named data. Here, Integer represents the key type and String represents the type of values. For example,

HashMap<Integer, String> data = new HashMap<>()

Sample Program:

In this program, we are traditionally implementing the HashMap and inserting the elements by the put() method.

import java.util.HashMap;

 public class SampleProgram  {
  public static void main(String[] args) {
    HashMap<Integer, String> data = new HashMap<>();
    data.put(1, "Python");
    data.put(2, "JavaScript");
    data.put(3, "Golang");
    System.out.println("HashMap: " + languages);
  }
}

Output:

HashMap: {1=Python, 2=JavaScript, 3=Golang}

Basic Methods of HashMap

2)Traversing

We have used the Map.Entry in the below example. It is the nested class of the Map interface that returns a view (elements) of the map. For this, we need to import the java.util.Map.Entry package to use this class.

import java.util.HashMap;
import java.util.Map;

public class HashMapTraversal {
    public static void main(String[] args)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(1,10);
        map.put(2,20);
        map.put(3,30);
        for (Map.Entry<String, Integer> entry : map.entrySet())
            System.out.println("Key: " + entry.getKey()
                               + " Value: " + e.getValue());
    }
}

Output:

Key: 1 Value: 10
Key: 2 Value: 20
Key: 3 Value: 30

Here, we are using the Iterator interface as it works with one type of data, so we used Entry<K, V> to convert the two separate types into a compatible format.

Time Complexity

HashMap has the complexity of O(1) for insertion and lookup.

Different Types of HashMaps

1) LinkedHashMap

It is an implementation that combines HashMap and LinkedList implementation. Unlike HashMap, it does maintain the insertion order of the Key and Value pair.

We can also define the order of its entries

LinkedHashMap<Key, Value> data = new LinkedHashMap<>(capacity, loadFactor, accessOrder);

Here accessOrder is a boolean value. The default value is false. In this case, it will keep the order as inputted initially.

But if the user alters it to true then it will keep the order from least recently accessed to most recently accessed.

Sample Program:

In this program, we are traditionally implementing the LinkedHashMap and inserting the elements by the put() method.

import java.util.LinkedHashMap;

 public class LinkedHashMapImpl {
    public static void main(String[] args) {
        LinkedHashMap<String, Integer> oddNumbers = new LinkedHashMap<>();
        evenNumbers.put("three", 3);
        evenNumbers.put("five", 5);
        System.out.println("LinkedHashMap1: " + oddNumbers);
    }
}

Output:

LinkedHashMap1: {three=3, five=5}

Time Complexity

LinkedHashMap has the complexity of O(1) for insertion and lookup.

2) IdentityHashMap

This class implements the AbstractMap. It intentionally violates the Map's general contract means it mandates the use of an equals method when it comes to comparing objects.

This class is designed for use only in rare cases wherein reference-equality semantics are required.

Sample Program:

In this program, we are traditionally implementing the IdentityHashMap and inserting the elements by the put() method.

import java.util.IdentityHashMap;

public class IdentityHashMapExample {
 public static void main(final String[] args) {
 IdentityHashMap<String, String> identity = new IdentityHashMap<String, String>();
         identity.put("a", "Java");
         identity.put(new String("a"), "J2EE");
         identity.put("b", "J2SE");
         identity.put(new String("b"), "Spring");
           System.out.println("Here 'a' and new String('a') are considered as separate keys");

         for (String string : identity.keySet()) {
             System.out.println("Key : " + string + " and Value : " + identityHashMap.get(string));
         }
 }
}

Output:

Here 'a' and new String('a') are considered as separate keys
Key : a and Value : Java
Key : b and Value : J2SE
Key : b and Value : Spring
Key : a and Value : J2EE

Time Complexity

IdentityHashMap has the complexity of O(1) for insertion and lookup.

3) WeakHashMap

As we all know that the key in HashMap is not eligible for garbage collection even if it does not have any reference which means HashMap dominates over Garbage collector.

But it's the opposite in the case of WeakHashMap, if the key does not contain any reference then it is automatically eligible for garbage collection which means the Garbage collector dominates over WeakHashMap.

Sample Program:

In this program, we are traditionally implementing the IdentityHashMap and inserting the elements by the put() method.

System.gc(): method runs the garbage collector does not return any value.

import java.util.WeakHashMap;

 public class WeakHashMapImpl {
    public static void main(String[] args) {
        WeakHashMap<String, Integer> numbers = new WeakHashMap<>();
        String two = new String("Two");
        Integer twoValue = 2;
        numbers.put(two, twoValue);
        System.out.println("Before making (two) a weak reference " + numbers);
        two = null;
        System.gc();
        System.out.println("WeakHashMap after garbage collection: " + numbers);
    }
}

Output:

Before making (two) a weak reference: {Two=2}
WeakHashMap after garbage collection: {}

Time Complexity

WeakHashMap has the complexity of O(1) for insertion and lookup.

4) EnumMap

It is an implementation of a Map interface for enumeration types and is much faster than HashMap. It maintains the collection in the natural order of their keys. EnumMap does not allow null keys and throws NullPointerException if we try to insert the null key.

An EnumMap is an efficient, and fast alternative to using a HashMap with enum keys and it is not synchronized.

Sample Program:

In this program, we are traditionally implementing the EnumMap and inserting the elements by the put() method.

import java.util.EnumMap;

 public class EnumMapImpl {

    enum Sizes {
        small, medium
    }
    public static void main(String[] args) {
        EnumMap<Sizes, Integer> sizes1 = new EnumMap<>(Sizes.class);
        sizes1.put(Size.small, 78);
        sizes1.put(Size.medium, 110);
        System.out.println("EnumMap: " + sizes1);
    }
}

EnumMap: {small=78, medium=110}

Time Complexity

EnumMap has the complexity of O(1) for insertion and lookup.

5) ConcurrentHashMap

The concurrentHashMap implements the ConcurrentMap Interface. It’s a hash table implementation, which supports concurrent retrieval and updates. It’s used in a multi-threaded environment to avoid ConcurrentModificationException. It does not allow null for keys and values and allows modification while iteration.

The concurrent hashmap is divided into 16 segments by default. The outcome is that 16 threads can concurrently modify the map at the same time. However, multiple threads can access the map at a time.

Sample Program:

In this program, we are traditionally implementing the ConcurrentHashMap and inserting the whole HashMap by using the syntax [new ConcurrentHashMap<>(data)]

import java.util.concurrent.ConcurrentHashMap;
import java.util.HashMap;

 public class ConcurrentHashMapImpl {
    public static void main(String[] args) {
        HashMap<String, Integer> data = new HashMap<>();
        data.put("Two", 2);
        data.put("Four", 4);
        ConcurrentHashMap<String, Integer> data1 = new ConcurrentHashMap<>(data);
        numbers.put("Three", 3);
        System.out.println("ConcurrentHashMap: " + data1);
    }
}

Output:

ConcurrentHashMap: {Four=4, Two=2, Three=3}

Time Complexity

ConcurrentHashMap has the complexity of O(1) for insertion and lookup.

In a Nutshell

1. Basic HashMap: the basic implementation of HashMap in Java, which stores key-value pairs in a hash table and offers constant-time performance for insertion, deletion, and retrieval operations.

2. LinkedHashMap: It maintains the order of entries by maintaining a doubly-linked list in addition to the hash table.

3. IdentityHashMap: It offers better performance for certain use cases where keys are mutable.

4. WeakHashMap: It allows keys to be garbage-collected if they are not referenced elsewhere, making it space efficient.

5. EnumMap: It is a specialized implementation of the hash map for use with enum keys, offering better performance than HashMap.

6. ConcurrentHashMap: It is a thread-safe implementation of the hash map that allows multiple threads to access the map concurrently without causing concurrency issues.

Conclusion

In this article, we looked at hashmaps with code and time complexity. We have also discussed the implementation of hashmaps followed by the different types. In short, choosing the right type of HashMap is critical because it can impact the application's performance and efficiency.

Each HashMap type has its unique features and use cases, and selecting the wrong type can result in suboptimal results.

Therefore, it is imperative to choose the appropriate HashMap that meets the specific requirements of the application. This can lead to better performance and more efficient use of resources.