HASHMAP IN JAVA – Everything You Need to Know About

INTRODUCTION

In Java, you might have heard about the Map interface (which extends the Collection Interface). There are some implementation classes of map interface, out of which one such class is HashMap (present in?java. util?package). It is denoted as?HashMap<K, V>?where K stands for Key and V for value. In simpler terms,?HashMap<K, V>?is a data structure that stores elements in the form of a key-value pair. These key-value pairs are also termed as an?Entry?of HashMap. Keys are unique, and duplicate keys are not allowed. It stores values based on keys, and it can be accessed using keys. Hashmap allows multiple null values and only one null key.

HashMaps are non-synchronized, meaning that they are not thread-safe. If multiple threads access the hashmap at the same time, they will modify the map structurally. HashMaps are an unordered collection of key-value pairs. They do not maintain the insertion order. They are much faster in terms of retrieving data as compared to arrays and linked-list, with constant time performance for the basic operations. Its initial default capacity(number of elements that can be stored) of hashmap is 16, and the default load factor is 0.75. We will discuss the capacity and load factor a little later in the coming sections.

Check the hierarchy diagram above; the HashMap class extends the AbstractMap class and implements the Map, Serializable and Cloneable interfaces.

Check the hierarchy diagram above; the HashMap class extends the AbstractMap class and implements the Map, Serializable and Cloneable interfaces.

Declaration of Hashmap class :?

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

K: type of Key

V: type of Value

CONSTRUCTORS IN HASHMAP

There are four constructors of the hashmap, all of which have public access specifiers.

1.?Hashmap()?

????It is the default constructor that creates an instance of a hashmap with the initial capacity of??

???16 and load factor 0.75.

???HashMap<K,V> hm = new HashMap<K,V>();??????// instance creation?

???Program to demonstrate default Hashmap Constructor :

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

      HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
	    System.out.println(hm);
    }
}        

???Output?: {Red=1, Blue=2, Yellow=4, Green=3}?[order of insertion is not preserved]

?2.?HashMap(int initialCapacity)

?????This constructor creates an instance of a hashmap with the specified initial capacity and

??????default load factor 0.75.

?????HashMap<K,V> hm = new HashMap<K,V>(int initialCapacity);????// instance creation?

?????Program to demonstrate above Hashmap Constructor :

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>(5);
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
	    System.out.println(hm);

    }
}           

??Output?: {Red=1, Blue=2, Yellow=4, Green=3}??

3.?HashMap(int initialCapacity, float loadFactor)

????This constructor creates an instance of a hashmap with the specified initial capacity and the?

????specified load factor.?

????HashMap<K,V> hm = new HashMap<K,V>(int initialcapacity, float loadfactor);????

????Program to demonstrate above Hashmap Constructor :

import java.io.*;
import java.util.*;

public class Hashmap {
    public static void main(String args[]) {
        HashMap<String, Integer> hm = new HashMap<String, Integer>(5,0.75f);
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
	    System.out.println(hm);
    }
}        

Output?:

{Red=1, Blue=2, Yellow=4, Green=3}

4. HashMap(Map map)

????This constructor creates an instance of a hashmap with similar mappings as the given Map.

????HashMap<K,V> hm = new HashMap<K,V>(Map m);?//instance creation

????Program to demonstrate above Hashmap Constructor :

import java.io.*;
import java.util.*;

public class Hashmap {

    public static void main(String args[]) {

      	 Map<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
	    System.out.println(hm);

	  HashMap<String, Integer> hm1 = new HashMap<String, Integer>(hm);
	  System.out.println(hm1);
    }
}        

?????Output?:?

?????{Red=1, Blue=2, Yellow=4, Green=3}

?????{Red=1, Blue=2, Yellow=4, Green=3}

OPERATIONS OF HASHMAP

The hashmap includes basic operations like add, get, update and delete the elements, just like any other data structure. Following are the basic operations :?

1. Add Elements??

To insert the elements or an entry in a Hashmap, the?put(K, V)?method?is used.

K:?type of key

V:?type of value

Program to demonstrate put method :?

import java.io.*; 
import java.util.*; 

public class Hashmap {

    public static void main(String args[]) {

      	 Map<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
    
            System.out.println(hm);
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

2. Remove Elements

The?remove(K)?method takes the key as the argument and deletes the entry for the given key if it is present on the map. We also have one more?remove(K, V)?method to delete the entry.

?Program to demonstrate remove operation using remove ():?

import java.io.*; 
import java.util.*; 

public class Hashmap {

    public static void main(String args[]) {

      	 Map<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
    
            System.out.println(hm);
	    hm.remove("Blue");    //remove Blue key
	    System.out.println(hm);

	    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Yellow=4, Green=3}

remove(K, V):?This method?takes key and value as the argument and removes the entry only if both the key and value match.

Program to remove the entry using remove(K, V) :

import java.io.*; 
import java.util.*; 

public class Hashmap {
    
    public static void main(String args[]) {

        Map<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
    
            System.out.println(hm);
	    hm.remove("Blue",3);
	    System.out.println(hm);;
	    hm.remove("Blue",2);
	    System.out.println(hm);

	    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Yellow=4, Green=3}

3. Access elements and Traverse hashmap

????3.1?Access one particular value associated with a key using get(K)

????The value present in a hashmap can be accessed using the method?get(K). The key must be passed in the argument, and the value stored in that key will be fetched.

Program to access the value using the get(K) method:?

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

       HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    System.out.println(hm.get("Green"));
    }
}
        

????Output?:?

???{Red=1, Blue=2, Yellow=4, Green=3}

???3

3.2 Access only the keys of elements?

If you want to retrieve only the?set of keys, the?keySet()?method will return just the set of keys in hashmaps.

Program to show usage of method keySet():?

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    System.out.println(hm.keySet());
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

[Red, Blue, Yellow, Green]

3.3?Access only the values of elements??

The?values()?method helps to obtain the?set of values.?

Program to show usage of values() :

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    System.out.println(hm.values());
    }
}
        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

[1, 2, 4, 3]

3.4 Access the entries of HashMap

The?entrySet()?method will return the?set of entries(<K, V>) in a hashmap.

Program to show usage of entrySet()?:?

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    System.out.println(hm.entrySet());
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

[Red=1, Blue=2, Yellow=4, Green=3]????????????????

3.5 Traverse the HashMap

After knowing how to access the elements in a hashmap, let us see how to iterate or?traverse the hashmap. The idea is to iterate over the set of entries using the for-each loop and then access the key and values in an entry using the?getKey()?and?getValue()?methods. We use Map.Entry(K, V) allows us to access the entries of a map.

Program to traverse the entries of a hashmap :?

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    for(Map.Entry<String, Integer> e: hm.entrySet())
	    {
	        System.out.println(e.getKey()+","+e.getValue());
	        
	    }
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

Red,1

Blue,2

Yellow,4

Green,3

4.?Update the value

????If you want to update the value stored in a given key, you can either use?put(K, V)?or?

????replace() method.

????Program to update the value using put():

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    hm.put("Yellow",5);    //updates the value of key Yellow
            System.out.println(hm);
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=5, Green=3}

Program to update using replace(K,V):?

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    hm.replace("Yellow",6);
                System.out.println(hm);
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=6, Green=3}???

FEATURES OF HASHMAP

Hashmap is a Map-based collection class that contains the values based on a key.?Let us discuss some key features of it :

• It is an unordered collection; that is to say, it does not maintain the keys and values in the same order in which they were inserted.
• It cannot have duplicate keys; however, it can have duplicate values.
• It allows one null key and multiple null values.
• HashMap uses an inner class?Entry<K, V>?to store data in nodes of a multiple singly linked list.
• Its initial default capacity is 16, and its load factor is 0.75
• They are not synchronized (not thread-safe) as multiple threads can modify their structure when accessing it. So, we must externally synchronize these concurrent modifications. We can use?Collections.synchronizedMap(Hashmap)?to synchronize it.
• It makes use of a technique called?Hashing?to transform a key into a shorter hash key which makes it easier to insert and retrieve data from a hashmap. We will learn about the working of Hashmap in detail in the coming sections.

Internal Working of HashMap in Java

What is HashMap?

Basically,?HashMap?is one of the most popular Collection classes in java. HashMap internally uses?HashTable?implementation. This HashMap class extends?AbstractMap?class that implements the?Map?interface.

Few important points to about?HashMap?:

1. HashMap?uses its static inner class?Node<K,V>?for storing the entries into the map.
2. HashMap?allows at most one?null?key and multiple?null?values.
3. The?HashMap?class does not preserve the order of insertion of entries into the map.
4. HashMap?has multiple buckets or bins which contain a head reference to a singly linked list. That means there would be as many linked lists as there are buckets. Initially, it has a bucket size of 16 which grows to 32 when the number of entries in the map crosses the 75%. (That means after inserting in 12 buckets bucket size becomes 32)
5. HashMap?is almost similar to Hashtable except that it’s?unsynchronized?and allows at max one null key and multiple null values.
6. HashMap?uses?hashCode()?and?equals()?methods on keys for the?get?and?put?operations. So HashMap key objects should provide a good implementation of these methods.
7. That’s why the?Wrapper?classes like?Integer?and?String?classes are a good choice for keys for HashMap?as they are?immutable?and their object state won’t change over the course of the execution of the program.

Note: Java?HashMap?is not thread-safe and hence it should not be used in multithreaded application. For the multi-threaded application, we should use?ConcurrentHashMap?class.

How to Initialize the Constructor with Our Own Capacity and Load factor?

There are mostly 4 different constructors that can be used while creating the hashmap.

These are as follows :

Frequently Used Hashmap Methods:

• public boolean containsKey(Object key): Returns?true?if this map contains a mapping for the specified key.
• public boolean containsValue(Object value): Returns true if this map maps one or more keys to the specified value.
• public V get(Object key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
• public V put(K key, V value): Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value.
• public void putAll(Map<? extends K, ? extends V> m): Copies all of the mappings from the specified map to this map. These mappings will replace any mappings that this map had for any of the keys currently in the specified map.
• public V remove(Object key): Removes the mapping for a key from this map if it is present (optional operation).
• public boolean isEmpty(): A utility method returning true if no key-value mappings are present in the map.
• public int size(): Returns the number of key-value mappings in this map. If the map contains more than?Integer.MAX_VALUE?elements return?Integer.MAX_VALUE.
• public Set<K> keySet(): Returns a Set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa.
• public Set<Map.Entry<K,V>> entrySet(): This method returns a Set view of the HashMap mappings. This set is backed by the map, so changes to the map are reflected in the set, and vice-versa.

Let’s See an Example of Hashmap and Its Functions:

Let’s say we want to have a mapping of all the contacts of our friends and relatives. We’ll have a myPhoneBook map of a name (String type ) as a key and a number(Long) as a value.

Output:

 — — — — -: Contacts in my Phone List : — — — — — 
Name : John Number : 8923535110
Name : Vikram Number : 8149535110
Name : Mark Number : 7080535110
 — — — — — — — — — — — — — — — — — — — — — — — — 
No of contacts in myPhoneBook : 3
Contact number of Vikram : 8149535110
Delete Mark’s contact : 7080535110        

Now Let’s Look at the Internal Working Of hashmap:

• HashMap uses its?static inner class? Node<K,V>?for storing map entries. That means each entry in hashMap is a?Node. Internally HashMap uses a?hashCode?of the key Object and this hashCode is further used by the?hash function?to find the index of the bucket where the new entry can be added.
• HashMap uses multiple buckets and each bucket points to a?Singly Linked List?where the entries (nodes) are stored.
• Once the bucket is identified by the hash function using hashcode, then hashCode is used to check if there is already a key with the same hashCode or not in the bucket(singly linked list).
• If there already exists a key with the?same?hashCode, then the?equals()?method is used on the?keys.?If the equals method returns?true, that means there is already a node with the same key and hence the value against that key is?overwritten?in the entry(node), otherwise, a new node is created and added to this Singly Linked List of that bucket.
• If there is no key with the same hashCode in the bucket found by the hash function then the new Node is added into the bucket found.

Each Node Has the Following Structure:

final int hash;
final K key;
V value;
Node<K,V> next;
        

In the above example, we assume that all these five keys have the same hashCode, then the bucket number or index returned by hash function would be the same for these five keys (in this case bucket 4) and hence they are put into the same bucket. Later the keys are compared using the equals() method to check whether the key is already present or not. But we assumed these five keys are having different key content and hence 5 nodes are there in the list.

To have a high-performance hashMap we need good implementation of hashCode() and equals() method along with hash function.

A Very Important Note That You Must Know:

Before java 8, singly-linked lists were used for storing the nodes. But this implementation has changed to self-balancing BST after a thresold is crossed (static final int?TREEIFY_THRESHOLD?= 8;). The motive behind this change is that HashMap buckets normally use linked lists, but for the linked lists the worst-case time is O(n) for lookup. Also note that Ordinary binary search trees have pathological cases where they become O(n) [basically BST becomes skewed], but red-black/AVL trees are specifically designed to prevent these cases. In a HashMap with linked lists, if we have a really really awful hash function, we could end up with all the items hashing to the same bucket and get O(n) lookup, But it seems like with this red-black/AVL tree scheme, even if all the items hashed into the same bucket, we would get O(logn) lookup in worst of worst scenario.

Let’s See This Mechanism Diagrammatically:

For this example, I have assumed the threshold value as 5 but ideally, it should be by default 8.

In this example, we assume all the?five keys key1 to key5?have the?same value of hashCode?and hence Hash function returns the same bucket number that is 4. Also equals method on all these five keys returns false which means the object content of these keys is different and hence 5 nodes are created and added to the tree.

Re-Hashing :

Whenever the number of entries in the hashmap crosses the?threshold value?then the bucket size of the hashmap is doubled and rehashing is performed and all the already existing entries of the map are copied and new entries are added to this increased hashmap.

Threshold value = Bucket size * Load factor        

Eg. If bucket size is 16 and the load factor is 0.75 then the threshold value is 12.

Time Complexity:

1. In a fairly distributed hashMap where the entries go to all the buckets in such a scenario, the hashMap has?O(1)?time for search, insertion, and deletion operations.
2. In the worst case, where all the entries go to the same bucket and the singly linked list stores these entries, O?(n)?time is required for operations like search, insert, and delete.
3. In a case where the?threshold?for converting this linked list to a self-balancing binary search tree(i.e. AVL/Red black) is used then for the operations, search, insert and delete?O(logN)?is required as AVL/Red Black tree has a max length of?logN?in the worst case.

Why Hashmap Should Not Be Used for Multi-threaded Environments?

Output:

Exception in thread “main” java.util.ConcurrentModificationException
 at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)
 at java.util.HashMap$KeyIterator.next(HashMap.java:1469)
 at ExceptionExample.main(ExceptionExample.java:16)        

When a new entry got inserted into the HashMap, the Iterator for the keys is failing. Actually, the Iterator on Collection objects is?fail-fast?i.e any modification in the structure or the number of entries in the collection object(in our case phoneBook) will trigger the exception. And hence the exception?ConcurrentModificationException?is thrown. Basically, HashMap contains a variable to count the number of modifications and the iterator uses it when you call its next() function to get the next entry.

Now let’s understand, if we’re iterating a map, why does?phoneBook.remove()?cause a?ConcurrentModificationException?to be thrown whereas?keyIterator.remove()?does not?

Consider this example:

Map<String, Long> phoneBook = new HashMap<String, Long>();
phoneBook.put("Vikram",8149101254L);
phoneBook.put("Mike",9020341211L);
phoneBook.put("Jim",7788111284L);

Iterator<String> keyIterator = phoneBook.keySet().iterator();

while (keyIterator.hasNext()){
    String key = keyIterator.next();
    if ("Vikram".equals(key)){
        //keyIterator.remove();#1
        //phoneBook.remove("John");#2
    }
}        

If we uncomment line?#1, it will work fine. If we uncomment line #2 (but leave?#1?commented) then it will cause the subsequent call to?keyIterator.next()?to throw?ConcurrentModificationException.

The reason is that an iterator is a separate object that has some references to the internal state of the underlying map object. If we modify the map while the iterator is in operation, it could cause the iterator to behave badly, e.g. by skipping elements, repeating elements, indexing off the end of the array, etc. It attempts to detect such modifications and so it throws?ConcurrentModificationException?.

Another point to note is that removing elements through the iterator works and does not cause exceptions. This updates the underlying map and the iterator’s state that refers to the internals of the map, so everything can stay consistent.

However, there is nothing special about?keyIterator.remove()?that makes it work in all cases. If multiple iterators are iterating over the same map, modifications made by one will cause problems for the others. Consider:

Iterator<String> keyIterator1 = phoneBook.keySet().iterator();
Iterator<String> keyIterator2 = phoneBook.keySet().iterator();
keyIterator1.remove();
keyIterator2.remove();        

We now have two iterators pointing to the same map. If we modify the map using one of them, it disrupts the operation of the second, so the call to?keyIterator2.remove();?will result in?ConcurrentModificationException.

The above scenario can be overcome using?ConcurrentHashMap?and hence it’s advised not to use hashmap for multi-threading applications

INTERNAL STRUCTURE OF HASHMAP

Considering the internal structure of the hashmap, it has a?Node<K, V>?which represents the inner class?Entry<K, V>?that stores the mappings of the hashmap. Each key-value pair is stored in an object of Entry<K, V> class. This class is a static inner class of Hashmap. Each node has four fields in it, namely :

1. Hash key (shorter key obtained post hashing)
2. Key
3. Value
4. The node next (a reference to another Entry, just like a singly linked list)

Points to know about a node in a HashMap:

• The hash attribute stores the hashcode of the key.
• The Key attribute stores the key, and it is of final type.
• Value attribute holds the value of the element.
• Entry<K, V> next holds the pointer to the next key-value pair.

Declaration of inner class Entry<K,V>?:?

static class Entry<K,V> implements Map.Entry<K,V>{
	int hash; 
	final K key;
	V value;
	Entry<K,V> next;
}        

Concept of Buckets in HashMap?

Buckets?are the array of nodes or entries that store elements. Many nodes can have similar buckets. The hashmap stores the elements just like a singly linked list, and a list of entries are termed as?Buckets.?These nodes are connected through a linked list. The capacity of hashmap and the number of buckets have a relation :?

The Capacity of HashMap = Number of buckets * Load factor

Structure of hashmap?

Internal Working of a HashMap

Hashmap uses a technique called?Hashing.?It is a process to convert a given key into a hash-key using the?hashCode()?method. Hashing also involves the?equals()?method to check if the keys are equal. Hashing is used to index and retrieve items faster.?The performance of a hashmap is based on the hashcode() method, so this method should be carefully chosen.?Let us discuss the hashCode and equals method below.

1. hashCode(): This method generates the hashcode of an object and returns the memory reference of the object passed in the integer form. It returns a random integer unique to each instance. The result of this method is termed a?hash.

?????????????????????????????????????????????????Syntax: public int hashCode()

2. equals():?Hashmap uses this method to check if two objects are equal or not. If this method returns true, they are equal, else they are not.?

Syntax:?boolean equals (Object ob)

Program to show usage of equals() :

import java.io.*;
import java.util.*;
public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
        HashMap<String, Integer> hm1 = new HashMap<String, Integer>();
	   
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);
            System.out.println(hm);
        
	    hm1.put("Red",1);
	    hm1.put("Blue",2);
	    hm1.put("Green",3);
	    hm1.put("Yellow",4);
	    System.out.println(hm1);
	   
	    System.out.println(hm.equals(hm1));
	   
    }
}
        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Green=3}

true

Collisions?

Collisions occur when distinct keys produce the same hashcode value, and the element is already present at that index value. To avoid or reduce collisions, a good hash function should be used, ensuring the best distribution of values throughout the hashmap. When a collision occurs, we use the chaining technique, as shown in the 2nd example above, to distribute the values.

Calculating Index in Hashing

Indexes are generated in hashing to reduce the size of an array.?If the hashcode of the key is used as an index, the integer value obtained might be large, and it can increase the size of the array.?

The Index is calculated using the formula :?

Index =?hashCode(Key) & (n-1)

n =?the size of array/bucket

?(n = 16 in case of default)

Hashing for Put() operations

Let us consider an empty hashmap with the default capacity of 16 (n=16).

1.?No Collision: Suppose you want to?put?the entry (“welcome”,15)?in a newly created map.

• As per the concept of hashing, the hash will be generated first using the hashCode(key)?
• Calculate hash = hashCode(“welcome”);?[suppose it is 200]
• Calculate index = hash & (16-1),????????[evaluates to 8]
• Create a node/Entry object with hash, key, value, and reference pointer.
• Place this object at index value 8 if it is empty.

2.?Collision: Sometimes, a scenario might come where the index will be the same, and collision can occur. Let’s try inserting (“wait”,16) in the hashmap now.

• Calculate hash = hashCode(“wait”);?[suppose it is 120]
• Calculate index = hash & (16-1),???[evaluates to 8]
• Create a node object with hash, key, value, and reference pointer.
• Place this object at index value 8 if no other value is placed there.
• If some value is placed there, like in our case, it is a state of collision.
• In case of collision, check through?equals()?if the keys are similar.
• If the equals() method returns true, replace the value with the current value.?
• If the equals() method returns false, then point this new node object to the previous node through a linked list at the same index value. (Chaining?method)
• In our case, since the keys, welcome and wait are different, we will place a new node using a link list.

Hashing for the Get() operation

Let us see how to use hashing to implement the get operation. The get(Key) is used to get the value at the given key.

Example:?No Collision

Let’s say you want to find the value of a key ”welcome”, follow the below steps of hashing.

• Calculate hash = hashCode(“welcome”);?[assume 200]
• Calculate index = hash & (n-1) , n=16???[index evaluates to 8]
• Check the index 8; if this key matches with the element’s key using the equals() method, then return the value.
• If the key does not match, then check the next element’s key and so on.
• In our case, the key matches, so the value of the key “welcome”, i.e. 15, will be returned.?????????????????????????????????????????????????????????????

Example:?Collision

Let’s say you want to find the value of a key ”wait” :

• Calculate hash = hashCode(“wait”);????[assume 120]
• Calculate index = hash & (n-1) , n=16???[index evaluates to 8]
• Check that index; if this key matches with the element’s key using the equals() method, then return the value.
• Here, it does not match, so check the next element (next node) in the list. The next key at this index is waiting. Recheck the keys; they match now, so the value of the key “wait” [i.e. 16] will be returned.
• If the next reference of the Node is null, return null, else move to the next node and repeat the key matching process.

PERFORMANCE OF HASHMAP

The performance of the hashmap is based upon two significant factors :

1. Initial Capacity
2. Load Factor

Initial Capacity:?The initial number of buckets a hashmap has when its instance is created. Its default value is 16. That is, initially, the hash map can store 16 key-value elements.

Load Factor:?It is a measure of how much percentage the hashmap is allowed to fill before its capacity increases. The default load factor value is 0.75, ranging between 0 to 1 usually.

Some other terms related to performance are :

Threshold:?It is the product of the load factor and the capacity of the hashmap. Default threshold value is 0.75*16= 12. When 12 elements are filled in the hashmap, we need to stop inserting more elements into it. Rehashing will be done, which will double the capacity of the hashmap.

Rehashing:?It is a way of doubling the capacity when the threshold value is reached. When the threshold value is crossed, the rehashing is done so that the bucket now has twice the capacity and the operation takes less time.

Time Complexity of HashMap

Talking about the time complexity, the?performance of a HashMap?operation depends upon the?hash function implementation. If the hashcode implementation is good (no hash collision), then the best, worst and average time complexity is?O(1). In a situation where the hashcode implementation is bad (hash which gives a collision), complexity would be?O(n). Also, the iteration over a hashmap depends upon its capacity and the key-value pairs. If the capacity is high, the iterations will increase, which will increase the time complexity and affect the performance.

Performance Improvement

Regarding performance improvement in Hashmap, two factors that must be chosen appropriately are the?optimized hash function?and?capacity. The hash function implementation should be such that the hashcode gives no to fewer collisions. Keeping the capacity high will increase the iterations and the time complexity, so both these factors must be carefully chosen.

The changes that have been done in JAVA 8 :?

Some hashmap performance improvement changes have been done in JAVA 8 to handle the hash collisions. Before Java 8, the hashmap performance was low in the case of hash collisions which had an impact on the complexity. Due to collisions, both the keys and values were placed in a node, and in the worst case, the complexity was O(n) due to link list traversal. Changes are as follows:

• Initially, the hash map will store the entries in a singly linked list, but when the threshold value is reached, the self-balancing BST trees will be used instead of a linked list. The benefit of using BST is that we get the worst-case complexity is O(log n).

METHODS IN HASHMAP

Some examples of the other essential functions of hashmap that are defined above :

Program to show the size of the hashmap :

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	    
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    System.out.println(hm.size());
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

4

Program to show putAll() and putIfAbsent() method?:

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	   
	   
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    HashMap<String, Integer> hm1 = new HashMap<String, Integer>();
	    hm1.putAll(hm);  //putAll
	    System.out.println(hm1);
	    hm.putIfAbsent("Orange",7);  //putIfAbsent
	    System.out.println(hm);
	   
    }
}        

Output?:?

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Green=3}

{Red=1, Blue=2, Yellow=4, Orange=7, Green=3}

Program to show containsKey() and containsValue() methods?:

import java.io.*;
import java.util.*;

public class Hashmap{
    public static void main(String args[]) {

        HashMap<String, Integer> hm = new HashMap<String, Integer>();
	   
	   
	    hm.put("Red",1);
	    hm.put("Blue",2);
	    hm.put("Green",3);
	    hm.put("Yellow",4);

	    System.out.println(hm);
	    System.out.println(hm.containsKey("Green"));
	    System.out.println(hm.containsKey("Orange"));
	    System.out.println(hm.containsValue(3));
	    System.out.println(hm.containsValue(7));
    }
}        

Output:?

{Red=1, Blue=2, Yellow=4, Green=3}

true

false

true

false

Synchronized HashMap

As already stated above, Hashmaps are unsynchronised, meaning they are not thread-safe. When simultaneously accessing the hashmap, multiple threads can change it structurally, and then it has to be synchronized externally. External synchronization can be done in the following way :?

Map m = Collections.synchronizedMap(Hashmap map);

Thank you for reading it.

KEEP LEARNING KEEP GROWING!!!

Thanks To: javarevisited & mygreatlearning