Using ArrayList to lose data in multithreaded scenarios

Preface

ArrayList Not thread safe

ArrayList Of add Operation source code

  /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
    public boolean add(E e) {
    
      //  Judge the of the list capacity Whether the capacity is enough , Is it necessary to expand capacity 
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      //  Add elements to the element array of the list 
      elementData[size++] = e;
      return true;
}

Possible problems

Array out of bounds exception ArrayIndexOutOfBoundsException

because ArrayList Add elements as above In two steps , You can see the first hidden danger of insecurity , stay Multiple threads add operation May be Lead to elementData An array .

The specific logic is as follows ：

 The list size is 9, namely size=9
 Threads A  Begin to enter add Method , Then it gets  size  The value of is 9, call  ensureCapacityInternal  Method to judge the capacity .
 Threads B  Also enter add Method , It gets  size  Values are 9, Also start calling  ensureCapacityInternal  Method .
 Threads A  It is found that the requirement size is 10, and  elementData  The size of 10, It can hold . So it will not be expanded , return .
 Threads B  It is also found that the requirement size is 10, Can also accommodate , return .
 Threads A  Start setting value operation , elementData[size++] = e  operation . here size Turn into 10.

 Threads B  Also start setting value operation , It tries to set  elementData[10] = e
 and  elementData  No expansion has been carried out , Its maximum subscript is 9
 Therefore, an array out of bounds exception will be reported ArrayIndexOutOfBoundsException.

Element value coverage and null problem

elementData[size++] = e The operation of setting the value will also lead to thread insecurity . It can be seen from here that , This step is also It's not an atomic operation , It consists of the following two steps ：

elementData[size] = e;
size = size + 1;

There is no problem in executing these two codes in a single thread , But when Execute in a multithreaded environment when , It could happen The value of one thread overrides the value added by another thread , The specific logic is as follows ：

 The list size is 0, namely size=0
 Threads A  Start adding an element , The value is A. At this point it performs the first operation , take  A  On the  elementData  Subscript to be 0  Location .
 next   Threads B  Just as well   Start adding a value of  B  The elements of , And went to the first step of operation . here   Threads B  Get  size  Value   Still 0, So it will B also   On the elementData Subscript to be 0  Location .

 Threads A  Begin to size The value of is increased to  1
 Threads B  Begin to size The value of is increased to  2
 This thread AB After execution , Ideally, it would be size by 2,elementData Subscript 0  The location of the for A, Subscript 1  The location of the for B.

 And the reality is  size  by 2,elementData Subscript to be 0  The position of the position becomes  B, Subscript 1  There's nothing in my position .
 And unless subsequently used set Method to modify the value of this location , Otherwise, it will always be null
 because size by 2, When you add an element, the subscript will be 2 Starting from the position of .

Code example

@SneakyThrows
public static void threadTest() {
    
    final List<Integer> list = new ArrayList<>();
    new Thread(() -> {
    
        for (int i = 1; i < 1000; i++) {
    
            list.add(i);
            System.out.println(" Add para  " + i + " Elements  :" + i);
            try {
    
                Thread.sleep(1);
            } catch (InterruptedException e) {
    
                e.printStackTrace();
            }
        }
    }).start();

    new Thread(() -> {
    
        for (int i = 1001; i < 2000; i++) {
    
            list.add(i);
            System.out.println(" Add para  " + i + " Elements  :" + i);
            try {
    
                Thread.sleep(1);
            } catch (InterruptedException e) {
    
                e.printStackTrace();
            }
        }
    }).start();

    Thread.sleep(3000);
    System.out.println("list size:" + list.size());
}

In the process of execution , Two situations occur as follows ：

1、 Element value coverage and null problem 
2、 The array is out of bounds  ArrayIndexOutOfBoundsException  error 

Code example 2

public static void main(String[] args) {
    
    List<Integer> list = new ArrayList<>();
     for (int i = 10000000; i >= 1; i--) {
    
         list.add(0);
     }
     System.out.println(" Number of source collections ："+list.size());
     List<Integer> newList = new ArrayList<>();
     long start = System.currentTimeMillis();

     ExecutorService executor = Executors.newFixedThreadPool(100);
     for (Integer integer : list) {
    
         executor.submit(()->{
    
             newList.add(integer+1);
         });
     }
     executor.shutdown();
     try {
    
         executor.awaitTermination(6, TimeUnit.MINUTES);
     } catch (InterruptedException e) {
    
         e.printStackTrace();
     }
     long end = System.currentTimeMillis();
     System.out.println(" Time :"+(end-start)+"ms");

     System.out.println(" Number of new collections :"+newList.size());
}

public static void main(String[] args) {
    
    ArrayList<Integer> list = Lists.newArrayList();
    for (int i = 10000000; i >= 1; i--) {
    
        list.add(0);
    }
    System.out.println(" Number of source collections ：" + list.size());
    Stopwatch started = Stopwatch.createStarted();
    List<Integer> newList = new ArrayList<>();
    ForkJoinPool forkJoinPool = new ForkJoinPool(100, ForkJoinPool.defaultForkJoinWorkerThreadFactory, null, true);
    list.forEach(item ->
            CompletableFuture.runAsync(() -> {
    
                newList.add(item + 1);
            }, forkJoinPool)
    );
    System.out.println(" Time :" + started.elapsed(TimeUnit.SECONDS));
    System.out.println(" Number of new collections :" + newList.size());
}

Use the thread pool to ArrayList Add 10 million elements . Look at the results ：

The data will be less than 10million

 because  ArrayList  Not thread safe , In the case of high concurrency list Adding data will result in data loss .
 also   A thread is traversing List ,  Another thread   modify List , Will be submitted to the  ConcurrentModificationException ( Concurrent modification exception ) error 

ArrayList Thread safe handling

Collections.synchronizedList

The most common way is through Collections Of synchronizedList Methods will ArrayList Convert to a thread safe container Reuse later

List<Object> list = Collections.synchronizedList(new ArrayList<>());
list.add() Methods locking 

Code example 2 Use synchronizedList, Time and Vector There is not much difference , Due to giving ArrayList After packaging, it is equivalent to giving ArrayList Inside All the methods are added synchronized, and Vector The effect is almost

list Methods locking

synchronized(list.get()) {
    
      list.get().add(model);
}

Vector

Use Vector Class to replace , Put the above public static List arrayList = new ArrayList(); Replace with public static List arrayList = new Vector<>();

principle : Used synchronized Keyword is locked

public synchronized boolean add(E e) {
    
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
 }

Code example 2 Use Vector , Time should be Longer than ArrayList

CopyOnWriteArrayList

Use thread safe CopyOnWriteArrayList Instead of thread unsafe ArrayList

List<Object> list = new CopyOnWriteArrayList<Object>();

principle : Use mutex Object to carry out maintain Handle ,Object mutex = new Object() Namely Created a temporary space be used for Auxiliary exclusive processing

ThreadLocal

Use ThreadLocal Use ThreadLocal Variable Ensure thread closure ( Closed threads are often safer , But because of the use of ThreadLocal Encapsulate variables , It is equivalent to throwing variables into the execution thread , Every time new A new thread , Variables will also new once , To some extent, it will cause performance [ Memory ] loss , But it's The mechanism of destruction after execution makes ThreadLocal Become a more optimized concurrency solution ).

ThreadLocal<List<Object>> threadList = new ThreadLocal<List<Object>>() {
    
        @Override
         protected List<Object> initialValue() {
    
              return new ArrayList<Object>();
         }
 };

other

When it comes to concurrency Reference resources CountDownLatch