Collection of articles: gitee.com/mydb/interv…

HashMap dead loop is a common and classic problem, which occurs frequently in daily interviews. Therefore, let’s take you to understand the cause of the dead loop thoroughly by means of diagrams.

Front knowledge

The dead loop problem occurred in JDK 1.7, and is mainly caused by the operation mechanism of HashMap itself, combined with concurrent operations, resulting in dead loops. The underlying data implementation of HashMap in JDK 1.7 is an array + linked list, as shown in the figure below:HashMap, on the other hand, uses header inserts for data addition, as shown below:The normal capacity expansion of HashMap is as shown in the figure below:The nodes of the old HashMap are transferred to the new HashMap in order of A, B, and C, while the new HashMap uses header interpolation, so the final order in the new HashMap is C, B, and A, as shown in the figure above. With that in mind, how does the loop come about?

Perform Step 1 in an infinite loop

In the first step of concurrent expansion, thread T1 and thread T2 need to expand HashMap. At this point, T1 and T2 point to the head node of the linked list element A, and the next node of T1 and T2, That is, T1.next and T2.next point to node B, as shown below:

Perform Step 2 in an infinite loop

The second step of the infinite loop is that thread T2 runs out of time slices and enters the hibernation state, while thread T1 begins to perform capacity expansion. Thread T2 is not awakened until the capacity expansion of thread T1 is completed. The scene after capacity expansion is shown as follows:As you can see from the figure above, the order of the HashMap has changed since thread T1 executes because of the header method, but thread T2 is unknowable to everything that happens, so its pointing element remains the same. As shown in the figure above, T2 points to element A and T2. Next points to element B.

Perform Step 3 in an infinite loop

When thread T1 completes and thread T2 resumes, an infinite loop is established, as shown below:After T1 completes expansion, the next node of node B is A, while the first node that T2 threads point to is A and the second node is B, which is exactly the opposite of the sequence of nodes after T1 completes expansion and capacity.T1 runs from B to A, and T2 runs from A to B, so node A and node B form an infinite loopThis is where the HashMap loop comes in.

The solution

There are three common solutions to the HashMap infinite loop:

  • Use the thread-safe container ConcurrentHashMap instead (recommended).
  • Use the thread-safe container Hashtable instead (low performance and not recommended).
  • Locking a HashMap with synchronized or Lock is equivalent to multi-threaded queueing (cumbersome and not recommended).

conclusion

In JDK 1.7, HashMap uses header interpolation, linked list, multi-threaded concurrency, and HashMap expansion. These points add up to form an infinite loop of HashMap. Deadlocks can be resolved using the thread-safe container ConcurrentHashMap instead.

Judge right and wrong from yourself, praise to listen to others, gain and loss in the number.

Public account: Java Chinese Community