java - 在多个线程中混洗 ArrayList

Question

我有一个静态ArrayList。每个线程都运行来洗牌ArrayList，然后我得到了错误的结果。

public void collectoinTest() {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        list.add(i);
    }
    for (int i = 0; i < 100; i++) {
        new Thread(new Runnable() {
            public void run() {
                for (int j = 0; j < 10000; j++) {
                    Collections.shuffle(list);
                    System.out.println( list);
                }
            }
        }).start();
    }
}

有时输出看起来像这样:

[8, 9, 6, 5, 1, 7, 3, 4, 6, 0]

它有重复的元素，任何人都可以解释一下吗？

Answer 1

shuffle 内部工作的方式是交换列表元素:

T tmp = list.get(from);
list.set(from, list.get(to));
list.set(to, tmp);

如果您有多个线程，线程的操作可能会交错，例如:

T tmp1 = list.get(from1);
                                  T tmp2 = list.get(from2);
                                  list.set(from2, list.get(to2));
list.set(from1, list.get(to1));
                                  list.set(to2, tmp2);
list.set(to1, tmp1);

或

T tmp1 = list.get(from1);
                                  T tmp2 = list.get(from2);
list.set(from1, list.get(to1));
list.set(to1, tmp1);
                                  list.set(from2, list.get(to2));
                                  list.set(to2, tmp2);

但是交错的顺序是不确定的:它取决于许多难以预测的事情。当有 100 个线程在同一个列表上工作时尤其如此。

一些潜在的交错可能会导致写入不正确的值，因为 from 的值不再是您之前写入的值。

考虑一个非常简单的列表 [0, 1] 示例，以及两个尝试交换元素的线程(因此 from1 = from2 = 0; to1 = to2 = 1 ;)。如果它们像这样交错(仅作为一个示例；其他交错可能具有相同的效果):

                                  T tmp2 = list.get(0);
T tmp1 = list.get(0);
                                  list.set(0, list.get(1));
                                  list.set(1, tmp2);
list.set(0, list.get(1));
list.set(1, tmp1);

那么最终的列表将是[0, 0]。 Ideone demo

有两种方法可以避免这种情况:

• 最简单的就是不要在多线程中执行；那么线程与其自身之间就不能发生干扰。
• 使线程仅对列表的一部分进行操作(例如，使用list.subList来提取列表的一部分的 View )。那么线程就不会干扰，因为它们正在操作数据的不同部分。然而，那么改组将仅限于在这些子列表内交换；元素无法在列表内移动得像一次性打乱整个列表一样远。