Introduction: We all know that HashMap is thread-unsafe and is not recommended for use in multithreaded environments, but this article will try to decipher the main thread unsafe aspects of it.
1. The jdk1.7 HashMap
In jdK1.7, there are several optimizations for HashMap. The following are some of the optimizations for HashMap:
1 public class HashMapTest { 2 3 public static void main(String[] args) { 4 HashMapThread thread0 = new HashMapThread(); 5 HashMapThread thread1 = new HashMapThread(); 6 HashMapThread thread2 = new HashMapThread(); 7 HashMapThread thread3 = new HashMapThread(); 8 HashMapThread thread4 = new HashMapThread(); 9 thread0.start(); 10 thread1.start(); 11 thread2.start(); 12 thread3.start(); 13 thread4.start(); 14 } 15 } 16 17 class HashMapThread extends Thread { 18 private static AtomicInteger ai = new AtomicInteger(); 19 private static Map<Integer, Integer> map = new HashMap<>(); 20 21 @Override 22 public voidrun() {23while(ai.get() < 1000000) { 24 map.put(ai.get(), ai.get()); 25 ai.incrementAndGet(); 26} 27} 28}Copy the codeThe above code is relatively simple: multiple threads are constantly put, and both HashMap and AtomicInteger are shared globally. After running the code a few more times, the following loop occurs:
In a few cases, arrays are out of bounds:
Here we focus on the analysis of why there is an infinite loop, through the JPS and jstack name to check the infinite loop, the results are as follows:
From the stack information, we can see the location where the dead loop occurs. From this information, we can clearly know that the dead loop occurs in the expansion function of HashMap, and the root is in the transfer function of HashMap. The transfer function of HashMap in JDK1.7 is as follows:
1 void transfer(Entry[] newTable, boolean rehash) {
2 int newCapacity = newTable.length;
3 for (Entry<K,V> e : table) {
4 while(null ! = e) { 5 Entry<K,V> next = e.next; 6if (rehash) { 7 e.hash = null == e.key ? Zero:hash(e.key); 8 } 9 int i = indexFor(e.hash, newCapacity); 10 e.next = newTable[i]; 11 newTable[i] = e; 12 e = next; 13} 14} 15}Copy the codeTo summarize the main functions of this function:
After the expansion of table to newTable, the original data needs to be transferred to newTable. Notice lines 10-12 here, it can be seen that in the process of transferring elements, the header method is used, that is, the order of the linked list will be reversed, which is also the key point of forming an infinite loop. The following is a detailed analysis.
1.1 Analysis process of Dead loop caused by Capacity Expansion
Prerequisites:
It is assumed that
#1. Hash algorithm for simple linked list size with key mod.
Hash table[1] size=2, key=3,7,5
#3. Then resize to make size 4.
The data structure before resize is as follows:
In a single-threaded environment, the final result is as follows:
I won’t go into detail here, but it should be easy to understand what the Transfer function is doing, its transfer process, and how to reverse the linked list.
And then in A multithreaded environment, let’s say we have two threads A and B both doing put. Thread A hangs at line 11 of the Transfer function, which is so important to analyze here that it is posted again.
The result of running in thread A is as follows:
After thread A is suspended, thread B can execute normally and complete the resize operation. The result is as follows:
A special note here: since thread B has finished executing, newTable and Entry in the table are now the latest values in main memory according to the Java memory model: 7.next=3, 3.next=null.
When thread A is suspended, the value in memory is as follows: e=3, next=7, newTable[3]=null. The code execution process is as follows:
newTable[3]=e ----> newTable[3]=3
e=next ----> e=7
Copy the codeThe result is as follows:
Continue the loop:
E =7 next= e.ext ----> next=3 [Value from main memory] E.ext =newTable[3] ----> E.ext =3 [value from main memory] newTable[3]=e ----> newTable[3]=7 e=next ----> e=3Copy the codeThe results are as follows:
Loop again:
E =3 next= e.ext ----> next=null e.ext =newTable[3] ----> e.ext =7 3.next=7 newTable[3]=e ----> newTable[3]=3 e=next ----> e=nullCopy the codeNote that this loop: e.ext =7, whereas in the last loop 7.next=3, the circular list appears and e=null completes the loop.
The results are as follows:
This is where an infinite loop will occur whenever polling the data structure of the HashMap is involved in subsequent operations, causing tragedy.
1.2 Analyzing Data Loss caused by Capacity Expansion
Following the above analysis process, initially:
Thread A and thread B put, and thread A suspends:
The running result of thread A is as follows:
Thread B has obtained the CPU time slice and completed the resize operation:
Also note that since thread B has completed, newTable and table are the latest values: 5. Next =null.
Switch to thread A at this point, when thread A is suspended: e=7, next=5, newTable[3]=null.
If newTable [I]=e, place **7 at table[3]** and next=5. Then proceed to the next loop:
E =5 next= e.ext ----> next=null, value from main memory e.ext =newTable[1] ----> e.ext =5, Values from the main memory newTable [1] = e -- -- -- -- > newTable [1] = 5 e = next -- -- -- -- > e = nullCopy the code5 is placed at table[1], at which point e=null loop ends, 3 elements are lost, and a circular linked list is formed. And creates an infinite loop for subsequent hashMap operations.
2. Jdk1.8 HashMap
In jdk1.8, HashMap is optimized to insert the end of a linked list directly into a hash collision, so there is no looped list, but it is still unsafe in multi-threaded situations.
1 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2 boolean evict) {
3 Node<K,V>[] tab; Node<K,V> p; int n, i;
4 if ((tab = table) == null || (n = tab.length) == 0)
5 n = (tab = resize()).length;
6 if ((p = tab[i = (n - 1) & hash]) == null) // If nohash7 TAB [I] = newNode(hash, key, value, null);
8 else {
9 Node<K,V> e; K k;
10 if (p.hash == hash&& 11 ((k = p.key) == key || (key ! = null && key.equals(k)))) 12 e = p; 13else if (p instanceof TreeNode)
14 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
15 else{16for (int binCount = 0; ; ++binCount) {
17 if ((e = p.next) == null) {
18 p.next = newNode(hash, key, value, null);
19 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
20 treeifyBin(tab, hash);
21 break; 22 23}if (e.hash == hash&& 24 ((k = e.key) == key || (key ! = null && key.equals(k)))) 25break; 26 p = e; 27} 28} 29if(e ! = null) { // existing mappingfor key
30 V oldValue = e.value;
31 if(! onlyIfAbsent || oldValue == null) 32 e.value = value; 33 afterNodeAccess(e); 34return oldValue;
35 }
36 }
37 ++modCount;
38 if (++size > threshold)
39 resize();
40 afterNodeInsertion(evict);
41 returnnull; 42}Copy the codeThis is the main function for the PUT operation in HashMap in JDK1.8. Note line 6 that the element is inserted directly if there is no hash collision. If thread A and thread B perform A put operation at the same time, the hash value of the two different data is the same, and the data is null, so thread A and thread B both go to line 6. Assume that thread A is suspended before data insertion after entering, thread B performs normally and inserts data normally. Then thread A obtains the CPU time slice, and thread A does not need to make hash judgment any more. The problem occurs: Thread A overwrites the data inserted by thread B, causing thread insecurity.
This is just a brief analysis of the thread insecurity problem with HashMap in JDK1.8. We will summarize the Collection framework in Java later.
conclusion
First of all, HashMap is thread unsafe, which mainly reflects:
#1. In jdk1.7, in a multi-threaded environment, capacity expansion causes loop chains or data loss.
#2. In jdk1.8, data overwriting occurs in a multithreaded environment.