How Remove Method Works Internally in HashMap with Example

This is one of the new hottest  technical java interview  question, how remove method works  internally in hashmap or explain the internal implementation of remove method in hashmap. Thanks to one of the Java Hungry readers Sarika , for pointing out this question. If you do not know how hashmap works in java , then please read it before reading this post.

Read Also :   How ConcurrentHashMap works internally in Java

How Remove method works internally in Java

 In HashMap we need key and value to add element to the HashMap object.
So if we add element to the HashMap object then the code will be like this :

public class JavaHungry {
    
    public static void main(String[] args)
    {
        HashMap hashmap = new HashMap();
        hashmap.put("Java", 1);
        hashmap.put("Hungry" , 2);
        hashmap.put("Blogspot" , 3);

        Iterator iteratorobject = hashmap.keySet().iterator(); 
        while(iteratorobject.hasNext()){
              String hashmapkey = iteratorobject.next(); 
              System.out.print(hashmap.get(hashmapkey));
        } 
    }
}


It will print the result :  [321]

Remember the result can be any order , so if you run the above code , then output could also be
[123] [231] [132] [213] [312]
as the HashMap is unordered.


Till now , we have added three key-value pairs to the hashmap object , now let us remove one key-value pair from the hashmap object.


public class JavaHungry {
    
    public static void main(String[] args)
    {
        HashMap hashmap = new HashMap();
        hashmap.put("Java", 1);
        hashmap.put("Hungry" , 2);
        hashmap.put("Blogspot" , 3);
        hashmap.remove("Java");
 
        Iterator iteratorobject = hashmap.keySet().iterator(); 
        while(iteratorobject.hasNext()){
              String hashmapkey = iteratorobject.next(); 
              System.out.print(hashmap.get(hashmapkey));
        } 
    }
}


It will print the result :  [32] 


As HashMap is unordered , the result could also be [23] but the main point to note that hashmap.remove("Java")  would remove the "Java" key and value associated with the key that is 1 .

So far so good , But the main question is how remove method removes key-value pair in the hashmap object .

Before moving onto the internal implementation of remove method of HashMap we need to understand the Entry object.

What is Entry Object

Map.Entry is the static nested class that stores the key/value pair that forms one element of HashMap.
Entry object stores in the bucket in the following way (hash,key,value,bucketindex)
The main point to note from the above line is that we need hashvalue and bucketindex besides key to get access to the desired Entry object in HashMap.


When you open the HashMap implementation  of the remove(key) method in Java Apis that is rt.jar , you will find the following code in it :

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
{
    // SOME CODE ,i.e Other methods in HashMap 

 1.   public V remove (Object key){
 2.       Entry<K,V> e =  removeEntryForKey(key);
 3.       return (e==null ? null : e.value);
    }
 
   // SOME CODE ,i.e Other methods in HashMap
 
}   


In the line 2 of remove(key) we are calling method removeEntryForKey(key). The main purpose of removeEntryForKey(key) method is it removes and returns the entry associated with the specified key in the HashMap. So let us understand how removeEntryForKey(key)  removes the entry object .

How remove method works in HashMap with Example




There are two possible scenarios for the key object ,

1. If key is not null
2. If key is null





Interviewer : How remove(key) method works internally in Java ?

As we know to find the desired Entry object which is to be removed in the HashMap we need hashValue , key and bucketindex . So remove(key) method calls  removeEntryForKey(key) method  internally , which calculate the final hashValue of the key object , and then use that hashValue in the indexFor(int,int) method to find the first entry object in the appropriate bucket. 
Since bucket(table) is a LinkedList effectively  , we start traversing from the first entry object which we got by using indexFor(int,int) method in the bucket. For each entry object in the bucket we compare whether  hashValue and the key is equal to the calculated hashValue in the first step and the key passed as a parameter in the remove(key) method.
If desired Entry object is found , then we removed that single entry object from the LinkedList.
Removing a single Entry object from the LinkedList is implemented just like removing a single object from the LinkedList.

Entry object returned by the removeEntryForKey(key) method is then  stored in the local variable e of type Entry in the remove(key) method.

If(e==null)
     return null
else
    return value of removed Entry object.



public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
{

   // SOME CODE ,i.e Other methods in HashMap 
 
 

    final Entry<K,V>  removeEntryForKey(Object key) {
         
   // Calculate hash value of the key passed as a parameter in remove method 
 
   1.   int hash = (key == null) ? 0 : hash(key. hashCode()); 
      
   // index for returns the first Entry in the appropriate bucket
   // Here , table is an array of Entry objects ,i.e.  Entry[] table
  
   2.   int i = indexFor(hash, table.length);
         
   // Below Code to remove a single object from the  simple LinkedList that is 
   // removing the desired Entry object from the LinkedList 
 
   3.     Entry<K,V> prev = table[i];
   4.     Entry<K,V> e = prev;
   5.     while (e != null) {
   6.         Entry<K,V> next = e.next;
              Object k; 
  
  // If Entry object's key and hash value equal to the above hashvalue and key
 
   7.        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
   8.              modCount++; 
 
   // Reduce size of Entry[] table by 1
 
   9.              size--;
 
    // Remove the Entry object : Two case to remove 
   // Case 1 :  only single element in the bucket , then prev==e        
 
   10.             if (prev == e)
   11.              table[i] = next; 
  
   // Case 2 : if more than one element present in the bucket ,   
 
   12.             else
   13.              prev.next = next; 
 
   // recordRemoval() method is invoked whenever entry is removed from the table
 
   14.             e.recordRemoval(this);
   15.             return e;
            }
   16.         prev = e;
   17.         e = next;
        } 
   18.    return e;
    } 
 
 
    
 
  }
 
     // SOME CODE ,i.e Other methods in HashMap 
}  




 
Interviewer : What is the purpose of calling recordRemoval() method in the removeEntryForKey(key)  since it is the concrete method without any body.

recordRemoval() method is a concrete method without any body. It is invoked whenever the Entry is removed from the table . Since LinkedHashMap extends HashMap , thus this method is overridden in the LinkedHashMap's Entry in order to maintain its linked list of entries.

Interviewer : What is the time complexity of  performing remove operation in HashMap using  remove(key)

Best Case time complexity of remove(key)  : O(1)  
Worst Case time complexity of remove(key) : O(n)

Interviewer: What happens if the null key is passed in the remove(key) method ?

The following lines will be executed in the removeEntryForKey(key) method

In line 1 , the value of hash will be 0 .
In line 2 , the value of indexFor will return 0 thus i=0.
In line 3 , Entry prev = table[0]
                Entry prev = null
In line 4,  Entry e = null
In line 5 , while loop condition returns false
In line 18 , return e (which is null)

thus null is returned to the remove(key) method , which will in turn return null. 

Interviewer : Explain the removeEntryForKey(key) method in HashMap in detail , considering key is not null?  


In the line 1 of removeEntryForKey(key),  if the key passed as a parameter is not null then , it will call hashfunction on the key object , so after key.hashCode() returns hashValue , so line 1 will look like
     int hash = hash (hashValue) 
we are now applying returned hashvalue into its own hashfunction. To defend against poor quality hash functions , we are calculating the hashValue again using hash(hashValue) in the above line.

We have hashValue and key , now we need to find the bucketindex of the desired Entry object

In line 2 , indexFor(int,int) , for the given hashValue, returns the first entry in the appropriate bucket.

So we get the first entry of the desired bucket.

In line 3 , we start traversing from the first entry in the bucket ,till we get the desired Entry object, prev is used to store the first entry in the bucket . Here table is an array of Entry objects i.e Entry[] table .

In line 4,  We created an Entry instance variable e which holds the prev value ,i.e, the first entry in the appropriate bucket.

Below Explanation is about removing a single object from the simple LinkedList that is removing the desired Entry object from the LinkedList

In line 5 , We iterate thorugh the Entry[] starting from the e ,till we get the desired Entry object
To check if we get the desired Entry object ,we need hashValue , key and bucketindex. We need to iterate through the bucket and its index one by one and comparing the hashValue and key of each Entry object.

In line 7  , If condition is true then we get the desired Entry object which we need to remove from the hashmap object .

Then two cases arises , whether bucket has single Entry object or it has more than one Entry object ,

If bucket has single Entry object , then,
       In line 10 , (prev==e) condition will be true
else bucket has more than one Entry object
       In line 12 else condition will be run

In line 14  , recordRemoval() method is called on the desired Entry object whenever the Entry is removed from the table.

In line 15 , the removed Entry object is returned to the remove(key) method.


Read Also :  How HashSet works internally in Java

If you still have any doubts regarding how remove method works internally in java then please mention in the comments.



About The Author

Subham Mittal has worked in Oracle for 3 years .
For more java articles ,Click here to Subscribe JavaHungry