An overview of the

HashMap is a thread – unsafe data structure. In the case of multiple threads, HashMap can cause an infinite loop of references. Java8 introduced red-black trees. How does that improve efficiency? This article first fills in the first hole, or in the form of the diagram to deepen the understanding.

Java 7 analysis

As you learned in the previous article, when the number of stored key-value pairs exceeds the HashMap threshold, the HashMap expands by creating a new array and “moving” the key-value pairs from the original array into the new array. When you “move”, you recalculate the position of the key in the new array based on the new array length and the key to be moved. Revisit the code responsible for the “transfer” function in Java7

void transfer(Entry[] newTable, boolean rehash) {// Get the length of the new array int newCapacity = newtable.length; // Iterate over the key-value pairs in the old arrayfor (Entry<K,V> e : table) {
        while(null ! = e) { Entry<K,V> next = e.next;if (rehash) { e.hash = null == e.key ? Zero:hash(e.key); Int I = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code

To understand this, let me draw a picture like this

It is assumed that the hash value of pit 5, Galen, and Mundo before and after expansion is still 5 after modulo operation with the length of the old and new arrays. As summarized in the previous article, Java7 lists are inverted before and after capacity expansion. This is all well and good when only a single thread operates on a hashMap, but when multiple threads operate on a hashMap at the same time, a problem arises. Let’s take a look at how multi-threading a hashMap can cause an endless loop of references in Java7 source code.

Foreplay looks like this: Two threads, Thread1 and Thread2, each have the right to operate on the same hashMap, assuming that there are 12 key-value pairs in the hashMap, and that the hash value before and after the stone and Galen expansion is still 5 modulo the length of the old and new arrays. The simulated heap memory before capacity expansion is shown in the figure

Thread1 creates a new array and does not have time to transfer the old key-value pairs. When Thread1 puts the 13th key-value pair into the hashMap, it determines that it has exceeded the threshold. The system time slice is backhanded to Thread2(Thread1 is suspended) and the whole process is graphically represented

Thread1 creates a new array and suspends it before it can be transferred. The new array has no contents. From Thread1’s point of view, e is a stone and next is galen. The simulated memory map at this point

Thread2 creates a new array when it puts the 13th key pair into the hashMap. However, Thread2 is lucky enough to finish the transfer before the time slice rotation. First traversal

Let’s do it the second time

The simulated memory condition at this point

You can see that for Galen at this point, his next is stone; In the case of a rock, its next is null, and the danger is there. Next, the slice is cut to Thread1(after a long pause it’s my turn to appear), and let’s take a look at Thread1’s position

The code analysis is as follows

The first step:

The second step:

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

Step 8:

Step 9:

Step 10:

Here we finally see Galen and the stone pointing at each other.

So what are the consequences of this? Subsequent operations on pit 5 of the new array go into an infinite loop (note that there is no problem manipulating other pits), such as the Java7 PUT operation

The Java7 GET operation executes getEntry, again causing an infinite loop.

At this point, Java7 multi-threaded operation HashMap may form an infinite loop analysis is completed.

Java8 analysis

As you learned in the previous article, Java7 transposes key and value pairs, while Java8 transposes key and value pairs. Same foreplay. Look at the code

Simulate heap memory at this point

The condition of the Thread1

Java8 will create two linked lists, i.e. Lo chain without adding the length of the original array, and HI chain with adding the length of the original array, assuming that stone and Galen are in pit 5 before and after the expansion. This is an LO chain (in fact, it does not matter if it is not in the same pit, because the chain order is the same before and after the expansion of Java8). Thread2 traverses the first time

The second time

Thread2 does not modify the reference relationship between stone and galen. Next is Galen, galen.next is null. Thread1 then gets execution authority and essentially repeats the work of Thread2.

conclusion

Through source code analysis, Java7 may cause an infinite loop when multithreading hashmap, because the order of the linked list is inverted after expansion and transfer, and the reference relationship of nodes in the original linked list is modified in the transfer process. Java8 does not cause an infinite loop on the same premise, because the order of the linked list remains the same after expansion and migration, and the reference relationship between the previous nodes remains. Does that mean that Java8 can use HashMap in multithreading? ConcurrentHashMap is recommended for use in multi-threaded situations where the put/ GET method cannot be guaranteed to have the same value for the next get.

Thank you

Talk about HashMap multithreaded dead loop most detailed foreign brother