Home » Interviews » Java » Infinite loop in HashMap

Infinite loop in HashMap

in , - on 09:17:00 - No comments

Why HashMap should not be used in multi threaded environment?
Can it cause infinite loop as well?
When get method go to infinite loop in HashMap?

If HashMap is used in Multi threading environment, there are chances that Get and Put operation can lead you to Infinite loop.
 

Overview

Before going into details on how Hashmap get/put operation can lead you to infinte loop,  Let's understand Rehashing.

What is Rehashing?

Default capacity of HashMap is 16 and Load factor is 0.75, which means HashMap will double its capacity when 13th Key-Value pair enters in map (16 * 0.75 = 12).

Till 12th Key-value pair, Hashmap will keep putting items in map and as soon as you try to put 13th key-value pair, rehashing process starts.

Load factor: Load factor is a measure "Till what load, hashmap can allow elements to put in it before its size is increased."

For more details on Load Factor and Rehashing, Please refer, What is Load factor and Rehashing in Hashmap?


Rehasing reverses ordering of the nodes

In Rehashing process, 
  1. Hashmap creates a New Array(Buckets) of double size first.
  2. Hashmap transfers key-value pairs from Old buckets to New buckets.  
  3. Key-value pairs will be reversed in New buckets because Hashmap will add key-value pairs at the start in the New bucket and not at the end. 
  4. Hashmap adds new key-value pairs at start to avoid traversing linked list every time and keep constant performance.

Let's see how Transferring process works with example,



What will happen when 2 Threads try to put 13th Key-Value pair in Hashmap?

When 2 Thread tries to access HashMap simultaneously, then you may encounter infinite Loop.
Let see how it happens,

For clarity, Lets name 2 Threads as Thread 1 and Thread 2, and both try to put 13th key-value pair.
It is obvious that before putting 13th key-value pair, Hashmap has to first do Rehashing process as 13th key-value pair crossed the load factor limit. 
Also, Hashmap here is accessed by Thread1 and Thread2, So it is not guaranteed which Thread will get access first.

We assume that both Threads reach to a place, where they both identify that Load factor limit has crossed and maps needs Rehashing. That is where both Threads will try to call below method for transferring key-value pairs from Old buckets to New buckets.

Method transfer() is called for transferring key-value pairs from
Old buckets to New buckets 

void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) {
        Entry<k> e = src[j];
        if (e != null) {
            src[j] = null;

            // --------- Below piece of code creates a problem  --------- 
            do {
    
                Entry<k> next = e.next; 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;

            } while (e != null);
            // --------- Till Here  --------- 

        }
    }
}

Lets see how Hashmap ends in Infinite loop.

Below you will see Thread 1 and Thread 2 Steps in short for quick go through. 

Note: In case if you find difficulty in understanding Thread steps, you can go to later section, where transfer() method and Thread Steps is explained in much detail.

Thread 1 got a chance for execution.

  1. After executing first line inside loop(in transfer() method), Thread 1 points to first key-value pair and next(second) key-value pair to start transfer process.  

    Before it execute any steps, Thread 1 loose the control and Thread 2 got chance for execution.

  2. So, Current state of Thread 1 is,  e = Node 90 and next = Node 1.


Thread 2 got a chance for execution.

  1. Fortunately, Thread 2 executed complete transfer() method without loosing control to other Thread.

  2. While transferring key-value pairs from old buckets to new buckets, key-value pairs will be reversed in New buckets because hashmap will add key-value pairs at the start and not at the end. It does this to avoid traversing linked list every time and keep constant performance.

  3. Thread 2 will transfer all key-value pairs from Old buckets to New buckets and Thread 1 will get chance for execution.
After Thread 2 execution, Hashmap state will be as shown below, 


Thread 1 again got a chance for execution.

Now Thread 1 will resume transfer() process, but it will end up Nodes in Infinte loop.
This happen becaused Thread 2 has actually reverse the Node links. 
Any further request for get/put will end up in Infinite loop.

Still not clear how it ends up in Infinite loop?

Lets understand each step of both Threads in detailed going through Algorithm step by step.

 

 Before going into details Lets understand what transfer() method does:


STEP 1:  Entry<k> next = e.next;

STEP 2:  int i = indexFor(e.hash, newCapacity);

STEP 3:  e.next = newTable[i];



STEP 4:  newTable[i] = e;

Note:

STEP 5:  e = next;



Too much code.... Now let's start with Race condition....


Thread 1 Steps.

Thread 1 got a chance for execution, and it executed below steps,
  1. Thread 1 try to put 13th key-value pair,

  2. Thread 1 founds that Threshold limit is reached and it creates new Buckets of increased capacity. So map's capacity is increased from 16 to 32.

  3. Thread 1 now starts the transfer process for transferring key-value pairs present at bucket 0 from old array to new array at bucket 0
    (Assume index evaluated for storing key-value pairs in new array is same that is index 0).

    For transferring, it calls the transfer() method and enters in loop.

  4. After executing first line inside loop(in transfer() method), Thread 1 points to first key-value pair and next(second) key-value pair to start transfer process.  

    Before it execute any steps, Thread 1 loose the control and Thread 2 got chance for execution.

  5. So, Current state of Thread 1 is,  e = Node 90 and next = Node 1.


Thread 1 after pointing to key-value pairs and before starting the transfer process, loose the control and Thread 2 got a chance for execution.



Thread 2 Steps.

Thread 2 got a chance for execution, and it executed below steps, 

  1. Thread 2 try to put 13th key-value pair,

  2. Thread 2 founds that Threshold limit is reached and it creates new Buckets of increased capacity. So map's capacity is increased from 16 to 32.

  3. Thread 2 now starts the transfer process for transferring key-value pairs present at bucket 0 from old array to new array at bucket 0
    (Assume index evaluated for storing key-value pairs in new array is same that is index 0).

    For transferring, it calls the transfer() method and enters in loop.

  4. Thread 2 points to first key-value pair and next(second) key-value pair to start transfer process. 

  5. Fortunately, Thread 2 executed complete transfer() method without loosing control to other Thread. 

  6. While transferring key-value pairs from old buckets to new buckets, key-value pairs will be reversed in New buckets because hashmap will add key-value pairs at the start and not at the end. It does this to avoid traversing linked list every time and keep constant performance.

  7. Thread 2 will transfer all key-value pairs from Old buckets to New buckets and Thread 1 will get chance for execution.

After Thread 2 execution, Hashmap state will be as shown below, 



Thread 1 Steps.

Thread 1 now got a chance for execution.
 Let see how Hashmap looks like now from Thread 1 perspective and in actual how it is.



  1. Thread 1 will execute,  int i = indexFor(e.hash, newCapacity);  & e.next = newTable[i]; 
    Hashmap will look like below.

  2. Thread 1 will execute,  newTable[i] = e;  , Hashmap will look like below.

  3. Thread 1 will execute,  e = next; , Hashmap will look like below.


  4. Thread 1 will execute, Entry next = e.next  , Hashmap will look like below.




  5. Thread 1 will execute,  int i = indexFor(e.hash, newCapacity);  & e.next = newTable[i]; Hashmap will look like below.



  6. Thread 1 will execute,  newTable[i] = e;  , Hashmap will look like below.




  7. Thread 1 will execute,  e = next;  , Hashmap will look like below.


  8. Thread 1 will execute, Entry next = e.next , Hashmap will look like below. 



  9. Thread 1 will execute,  int i = indexFor(e.hash, newCapacity);  & e.next = newTable[i]; Hashmap will look like below.


  10. Thread 1 will execute,  e = next; , Hashmap will look like below.




  11. What will happen if any get or put request will come now on index 0; That request will go in infinite loop.



HashMap Infinite loop Method call Stack trace



You may also like to see

What is Hashmap data structure? What is the need of Hashmap? How Hashmap data structure works in Java? What is Hashcode? Can 2 objects have same hashcode?

How Hashmap data structure works internally? How hashcode and equals method is used in hashmap? Explain with real time example.

How time complexity of Hashmap get() and put() operation is O(1)? Is it O(1) in any condition?

What is Load factor and Rehashing in Hashmap?



Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.
Categories: ,

Post a Comment