我不能在添加元素的同时从 Java 共享 ArrayList 中删除元素吗

Question

首先我在这里没有使用迭代器。

我在共享 ArrayList 上使用 2 个线程，第一个用于将值添加到 ArrayList 中，另一个用于制作它的临时副本并对其执行一些操作，然后从原始列表中删除所有临时元素。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArraylistTest {

    public static void main(String...ar){
        new AddingThread().start();
        new RemovalThread().start();
    }
}

class RemovalThread extends Thread{
    static List<Integer> originalBigList = new ArrayList<>();

    @Override
    public void run(){
        System.out.println("RemovalThread started");
        while(true){
            try {
                sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("creating copy of originalBigList");
            List<Integer> tempList = new ArrayList<>(originalBigList);
            System.out.println("copied list");
            //
            //some operations on copied temp list
            //
            System.out.println("removing tempList elements after completing operations");
            System.out.println("originalBigList before removing size "+originalBigList.size());
            originalBigList.removeAll(tempList);
            System.out.println("removed!!");
            System.out.println("after size "+originalBigList.size());
        }
    }
}

class AddingThread extends Thread{

    @Override
    public void run(){
        System.out.println("Adding thread started");
        int ctr = 0;
        while(true){
            RemovalThread.originalBigList.add(ctr);
            ctr++;
        }
    }
}

输出：-

Adding thread started
RemovalThread started
creating copy of originalBigList
copied list
removing tempList elements after completing operations
originalBigList before removing size 4102267
Exception in thread "Thread-0" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:3210)
    at java.util.Arrays.copyOf(Arrays.java:3181)
    at java.util.ArrayList.grow(ArrayList.java:261)
    at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:235)
    at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:227)
    at java.util.ArrayList.add(ArrayList.java:458)
    at AddingThread.run(ArraylistTest.java:47)

现在我的问题是，我在输出中看到正在执行复制列表的语句，它正在从原始列表中创建临时列表，但是删除语句没有执行，也没有给出任何异常，我'我使用简单的数组列表未同步，为什么会这样？

删除或添加操作是否有任何内部锁定？如果是，那么 Collections.synchronised( arraylist ) 有什么用？

Answer 1

下面一行

            List<Integer> tempList = new ArrayList<>(originalBigList);

将在 originalBigList 上迭代列表构造函数以创建你的 tempList，如果 AddingThread 将运行并行，它将抛出 ConcurrentModificationException 杀死你的 RemovalThread 也许你没有在控制台中看到它但它可能在那里.我建议将 CopyOnWriteArrayList 用于您的 originalBigList

Answer 2

我发现你的问题看下面的代码

 public static void main(String ...args){
    long start = System.currentTimeMillis();
    List<Integer> l1 = new ArrayList<>();
    List<Integer> l2 = new ArrayList<>();

    for(int i = 0 ; i < Integer.MAX_VALUE/10000;i++){
        l1.add(i);
        l2.add(i);
    }

    System.out.println(String.format("Field both arrays in %s seconds",(System.currentTimeMillis()-start)/1000) );
    start = System.currentTimeMillis();
    l1.removeAll(l2);

    System.out.println(String.format("Removed one array from other %s seconds",(System.currentTimeMillis()-start)/1000) );

}

在 0 秒内完成两个阵列

从其他 34 秒中删除了一个数组

这是一个巨大的数组，现在看看输出删除花费了大量的时间，在你的情况下，AddingThread 使数组变得巨大，所以它正在工作它只需要很多时间，同时，AddingThread 保持 working.By 这样，就可以理解为什么需要首先找到每个值需要这么长时间所以它是 O(n^2)。看看当我使用 HashSet 而不是 List 时它是如何工作的（注意：HashSet 搜索是 O(1) )

public class HashSetTest {
public static Object obj = new Object();
public static void main(String... ar) {
    new AddingThread().start();
    new RemovalThread().start();
}

}

class RemovalThread extends Thread {
static Set<Integer> originalBigSet = new HashSet<>();
@Override
public void run() {
    System.out.println("RemovalThread started");
    while (true) {
        try {
            sleep(1000);
            System.out.println("creating copy of originalBigSet");
            Set<Integer> tempList;
            synchronized (HashSetTest.obj) {
                tempList = new HashSet<>(originalBigSet);
            }
            System.out.println("copied list");
            //
            //some operations on copied temp list
            //
            System.out.println("removing tempList elements after completing operations");
            System.out.println("originalBigSet before removing size " + originalBigSet.size());
            synchronized (HashSetTest.obj) {
                originalBigSet.removeAll(tempList);
            }
            System.out.println("removed!!");
            System.out.println("after size " + originalBigSet.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

}

class AddingThread extends Thread {

@Override
public void run() {
    System.out.println("Adding thread started");
    int ctr = 0;
    while (true) {
        synchronized (HashSetTest.obj) {
            RemovalThread.originalBigSet.add(ctr);
        }
        ctr++;
    }
}

}

Answer 3

类似@urag的回答（特别是O(n²)的备注），修改AddingThread就可以看到效果，所以只增加了有限的项：

class AddingThread extends Thread{

    @Override
    public void run(){
        System.out.println("Adding thread started");
        int ctr = 0;
        while(true){

          if (ctr < 100_000) {
            RemovalThread.originalBigList.add(ctr);
            ctr++;
           }
      }
  }
}

这导致：

Adding thread started
RemovalThread started
creating copy of originalBigList
copied list
removing tempList elements after completing operations
originalBigList before removing size 100000
removed!!
after size 0

现在，把100_000改成1_000_000，等很久，只能看到::

Adding thread started
RemovalThread started
creating copy of originalBigList
copied list
removing tempList elements after completing operations
originalBigList before removing size 1000000

我不能在添加元素的同时从 Java 共享 ArrayList 中删除元素吗

Can't I remove element from Java shared ArrayList while simultaneously adding into it

java

arraylist

synchronized