Shulou(Shulou.com)06/03 Report--

This article mainly explains the "HashMap is the embodiment of thread unsafe", the content of the explanation is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "HashMap is the embodiment of thread unsafe" bar!

HashMap in 1.jdk1.7

Many optimizations have been made to HashMap in jdk1.8. Here we first analyze the problems in jdk1.7. I believe we all know that HashMap is prone to endless loops in jdk1.7 multithreaded environment. Here, we first use code to simulate the situation of endless loops:

Public class HashMapTest {public static void main (String [] args) {HashMapThread thread0 = new HashMapThread (); HashMapThread thread1 = new HashMapThread (); HashMapThread thread2 = new HashMapThread (); HashMapThread thread3 = new HashMapThread (); HashMapThread thread4 = new HashMapThread (); thread0.start (); thread1.start (); thread2.start (); thread3.start () Thread4.start ();}} class HashMapThread extends Thread {private static AtomicInteger ai = new AtomicInteger (); private static Map map = new HashMap (); @ Override public void run () {while (ai.get ()

< 1000000) { map.put(ai.get(), ai.get()); ai.incrementAndGet(); } } } 上述代码比较简单，就是开多个线程不断进行put操作，并且HashMap与AtomicInteger都是全局共享的。在多运行几次该代码后，出现如下死循环情形：

There are several cases where the array is out of bounds:

Here we focus on analyzing why there is an endless loop, and check the situation through jps and jstack naming. The results are as follows:

You can see the location of the dead loop in the stack information. From this information, you can clearly know that the dead loop occurs in the expansion function of HashMap, which is rooted in the transfer function. The transfer function of HashMap in jdk1.7 is as follows:

Void transfer (Entry [] newTable, boolean rehash) {int newCapacity = newTable.length; for (Entry e: table) {while (null! = e) {Entry next = e.next; if (rehash) {e.hash = null = = e.key? 0: hash (e.key) } int I = indexFor (e.hash, newCapacity); e.next = newTable [I]; newTable [I] = e; e = next;}

Summarize the main functions of this function:

After expanding the capacity of table to newTable, you need to transfer the original data to newTable. Pay attention to 10-12 lines of code. Here, you can see that headline insertion is used in the process of transferring elements, that is, the order of linked lists will be reversed. This is also the key point for the formation of an endless loop. The following is a detailed analysis.

1.1 Analysis process of endless cycle caused by capacity expansion

Prerequisites:

It is assumed here

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

The hash algorithm simply uses the size of the key mod linked list.

At first, the hash table size=2,key=3,7,5 is all in table [1].

Then resize so that the size becomes 4.

The data structure before resize is as follows:

In a single-threaded environment, the final result is as follows:

The transfer process here will not be described in detail, but it should not be difficult to understand what the transfer function is doing, its transfer process, and how to reverse the linked list.

Then in a multithreaded environment, assume that two threads An and B are performing put operations. Thread A hangs when it executes to line 11 of the transfer function, because the function's parsing position is very important here, so it is posted again.

At this point, the running result in thread An is as follows:

After thread An is suspended, thread B executes normally and completes the resize operation. The result is as follows:

One thing to pay special attention to here: because thread B has finished executing, according to the Java memory model, the Entry in newTable and table is now the latest value in main memory: 7.nextaccount3.nextmemory null.

At this point, switch to thread A, and when thread An is suspended, the value in memory is as follows: eCoherent 3MaginnextNotTable [3] = null. The code execution process is as follows:

NewTable [3] = e-> newTable [3] = 3 e=next-> eBay 7

The results are as follows:

Continue the cycle:

EBay 7 next=e.next-> next=3 [take value from main memory] e.next=newTable [3]-> e.next=3 [take value from main memory] newTable [3] = e-> newTable [3] = 7 e=next-> eBay 3

The results are as follows:

Cycle again:

EBay 3 next=e.next-> next=null e.next=newTable [3]-> e.next=7: 3.next=7 newTable [3] = e-> newTable [3] = 3 e=next-> e=null

Notice that this loop: e.next=7, while in the last loop 7.next=3, a circular linked list appears, and the e=null loop ends.

The results are as follows:

As long as the data structure of polling hashmap is involved in subsequent operations, an endless loop will occur here, resulting in tragedy.

1.2 Analysis process of data loss caused by capacity expansion

Following the above analysis process, at the beginning:

Thread An and thread B perform put operations, and thread A hangs as well:

At this point, thread A runs as follows:

At this point, thread B has obtained the CPU time slice and completed the resize operation:

Also note that because thread B execution is complete, both newTable and table are the latest values: 5.next=null.

At this point, switch to thread A, and when thread A hangs: eBay 7 Magi NextTable 5 Magi newTable [3] = null.

Execute newtable [I] = e, and 7 is placed in the position of table [3], where next=5. Then proceed to the next loop:

ECo5 next=e.next-> next=null, take the value e.next=newTable [1]-> e.next=5 from the main memory, and take the value newTable [1] = e-> newTable [1] = 5 e=next-> e=null from the main memory

Place 5 in the table [1] position, where the e=null loop ends, 3 elements are lost, and a circular linked list is formed. And cause an endless loop during subsequent operations of the hashmap.

HashMap in 2.jdk1.8

HashMap is optimized in jdk1.8. In the event of hash collisions, the head insertion method is no longer used, but is directly inserted into the tail of the linked list, so the circular linked list will not occur, but it is still not safe in the case of multithreading. Here we take a look at the put operation source code of HashMap in jdk1.8:

Final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node [] tab; Node p; int n, I; if ((tab = table) = = null | | (n = tab.length) = = 0) n = (tab = resize ()) .length If ((p = tab [I = (n-1) & hash]) = = null) / / insert the element tab [I] = newNode (hash, key, value, null) directly if there is no hash collision; else {Node e; K k If (p.hash = = hash & & (k = p.key) = = key | | (key! = null & & key.equals (k) e = p; else if (p instanceof TreeNode) e = ((TreeNode) p) .putTreeVal (this, tab, hash, key, value) Else {for (int binCount = 0;; + + binCount) {if ((e = p.next) = = null) {p.next = newNode (hash, key, value, null) If (binCount > = TREEIFY_THRESHOLD-1) / /-1 for 1st treeifyBin (tab, hash); break } if (e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k) break; p = e }} if (e! = null) {/ / existing mapping for key V oldValue = e.value; if (! onlyIfAbsent | | oldValue = = null) e.value = value; afterNodeAccess (e); return oldValue } + + modCount; if (+ + size > threshold) resize (); afterNodeInsertion (evict); return null;}

This is the main function of the put operation in HashMap in jdk1.8. Note the sixth line of code, which inserts the element directly if there is no hash collision. If thread An and thread B perform put operations at the same time, the two different data hash values happen to be the same, and the location data is null, so both threads An and B will go into line 6 of the code.

Suppose that thread A hangs after entering without data insertion, and thread b executes normally, thus inserting data normally, and then thread an obtains cpu time slice, thread A no longer needs to make hash judgment, and the problem arises: thread A will overwrite the data inserted by thread B, resulting in thread unsafe.

This is only a brief analysis of the thread unsafe problems in HashMap in jdk1.8. The collection framework of java will be summarized and analyzed in detail.

Thank you for your reading, the above is the content of "HashMap is the embodiment of thread unsafe", after the study of this article, I believe you have a deeper understanding of what is the embodiment of HashMap is thread unsafe, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.