Common problems in multi-threaded learning (I) ArrayList under high concurrency and weird hasmap under concurrency

High and sent ArrayList

• We all know ,ArrayList It's a thread unsafe container . If used in multithreading ArrayList, May cause program error . What kind of problems may arise ? Take a look at the following code :

public class ArrayListMultiThread{
    
static ArrayList<Integer> al = new ArrayList<Integer> (10);public static class AddThread implements Runnable {
    
eOverride
public void run(){
    
for (int i=0;i<1000000; i++){
    
al .add(i);
public static void main(String[] args) throws InterruptedException {
    
Thread tl=new Thread(new AddThread());
Thread t2=new Thread(new AddThread());t1.start();
t2.start();
t1.join();t2.join();
System.out.println(al.size();

• In the above code ,t1 and t2 Two threads are directed to one at the same time ArrayList Add container to . They each add 100 Ten thousand elements , So we expect to end up with 200 Ten thousand elements in ArrayList in . But if you execute this code , There are three possible outcomes .
• First of all , The program ends normally ,ArrayList The final size of is really 200 ten thousand . This shows that even if the parallel program has problems , It doesn't have to be shown every time .
• second , Exception thrown by program .

Exception in thread "Thread-0" java.lang.ArrayIndexOutOfBoundsException:22
at java.util.Arraylist.add(ArrayList.java: 441)
at geym.conc.ch2.notsafe.ArrayListMultiThread$AddThread.run(ArrayListMultiThread.java:12)
at java. lang. Thread.run (Thread.java:724)1000015

• This is because ArrayList In the process of capacity expansion , Internal consistency is broken , But because there's no lock protection , Another thread has access to an inconsistent internal state , Leading to cross-border problems .
• Third , There was a very subtle mistake , For example, print the following values as ArrayList Size .
  1246772
• This is due to multithreading access conflicts , This makes the variable that holds the size of the container accessed abnormally by multithreading , At the same time, two threads are also on ArrayList It is caused by the assignment of the same position in . If there is such a problem , So unfortunately , You get an error that doesn't have an error prompt . also , They may not be reproducible .
• Be careful : The way to improve is simple , Use thread safe Vector Instead of ArrayList that will do .

And then it's weird HasMap

• HashMap It's also not thread safe . When you use multithreading access HashMap when , You may also encounter unexpected mistakes . But and ArrayList Different ,HashMap The question seems to be even more bizarre .

public class HashMapMultiThread {
    
static Map<string,String> map = new HashMap<String, String>();
public static class AddThread implements Runnable {
    
int start=0;
public AddThread(int start){
    
this.start=start;
)
coverride
public void run(){
    
for (int i = start; i<100000; i+=2){
    
map.put(Integer.toString(i), Integer.toBinarystring(i));
public static void main(String[] args) throws InterruptedException{
    
Thread tl=new Thread (new HashMapMultiThread.AddThread(0));
Thread t2=new Thread (new HashMapMultiThread.AddThread(1));
t1.start();t2.start();
t1.join();t2.join();
System.out.printin (map.size());
}}

• The above code uses t1 and t2 Two threads are working on HashMap Conduct put() Method of operation . If everything goes well , Obtained map.size() The way is 100 000. But actually , You may get the following three situations （ Be careful , Use here JDK 7 Carry out experiments ）.
• First of all , The program ends normally , And the results are in line with expectations ,HashMap The size is 100 000.
• second , The program ends normally , But it didn't work out as expected , It's a smaller than 100 000 The number of , such as 98868. Third , The program never ends .
  The first two possibilities and ArrayList It's very similar , There is no need to explain too much .
• And for the third case , If it's the first time to see , I think you will be particularly surprised , Because of the seemingly normal program , How could it not be over ?
  Be careful : Please try the above code carefully , Because this code is likely to occupy two CPU nucleus , And make them CPU The share reaches 100%. If CPU Poor performance , May cause crash , So please save the information first , Try again .
• Open Task Manager , You'll find that , This code takes up a lot of CPU, The most likely indication is to occupy two CPU nucleus , And make these two nuclei CPU Utilization rate reaches 100%. It's very similar to the case of a dead loop .
• Use jstack The tool displays the thread information of the program , As shown below . among jps It can display all the... In the current system Java process , and jstack You can print a given Java The internal thread of a process and its stack .

C:AUserslgeym >jps
14240 HashMapMultiThread1192 Jps
C:Userslgeym >jstack 14240

• We'll find it easy t1、t2 and main Threads .

"Thread-1" prio=6 tid=0x00bb2800 nid=0x16e0 runnable [0x04baf000]java.lang.Thread.state: RUNNABLE
at java.util.HashMap.put(HashMap.java: 498)
at geym.conc.ch2.notsafe.HashMapMultiThread$AddThread.run
(HashMapMultiThread.java:26)
at java.lang. Thread.run(Thread.java:724)
"Thread-0" prio=6 tid=0x00bb0000 nid=0x1668 runnable [0x04d7000]java.lang. Thread.State: RUNNABLE
at java.util.HashMap.put (HashMap.java: 498)
at geym.conc.ch2.notsafe.HashMapMultiThread$AddThread.run(HashMapMultiThread.java:26)
at java.lang. Thread.run (Thread.java:724)
"main" prio=6 tid=0x00cOcc00 nid=0x16ec in 0bject.wait()[0x0102000]java.lang. Thread.state: WAITING (on object monitor)
at java.lang.0bject.wait (Native Method)
- waiting on <0x24930280>(a java.lang. Thread)at java.lang. Thread.join (Thread.java:1260)- locked <0x24930280> (a java.lang. Thread)at java.lang. Thread.join(Thread.java: 1334)
at geym. conc.ch2.notsafe.HashMapMultiThread.main(HashMapMultiThread.java:36)

You can see , The main thread main It's waiting , And the wait is due to join() Method induced , In line with our expectations . and t1 and t2 Both threads are in Runnable state , And the current execution statement is HashMap.put() Method . see put( Methods the first 498 Line code , As shown below :

for (Entry<K, V>e= table[i]; e != null;e= e.next){
    
0bject k;
if (e.hash == hash &&((k = e.key)-= key Il key.equals (k))){
    
v oldvalue = e.value;
e.value = value;
e.recordAccess(this);return oldvalue;

• You can see , These two threads are currently traversing HashMap The internal data of . At first glance, the current loop is an iterative traversal , It's like walking through a linked list . But at this moment , Due to multi thread conflicts , The structure of this list has been destroyed , The list is in a loop ! When a linked list is in a ring , The above iteration is equivalent to an endless loop , chart 2.9 It shows the simplest kind of ring structure ,key1 and key2 For each other next Elements . here , adopt next Reference traversal , It's going to be a dead circle .
• Once the problem of the dead circle appears , It can really make you depressed , But the problem with this dead cycle is that JDK 8 There is no longer . because JDK8 Yes HashMap The internal implementation of has been adjusted on a large scale , So it circumvents this problem . Even so , Rashly use in multithreading environment HashMap It will still lead to internal data inconsistency . The simplest solution is to use ConcurrentHashMap Instead of HashMap.

Excerpt from JAVA High concurrency programming , Recommend