Java Collections.sort() 缺少 ConcurrentModificationException

Question

我偶然发现了这个奇怪的错误。似乎 Collections.sort() 不会以一种在迭代同一列表时能够检测并发修改的方式修改排序列表。示例代码:

    List<Integer> my_list = new ArrayList<Integer>();

    my_list.add(2);
    my_list.add(1);

    for (Integer num : my_list) {

        /*
         * print list
         */
        StringBuilder sb = new StringBuilder();
        for (Integer i : my_list)
            sb.append(i).append(",");
        System.out.println("List: " + sb.toString());

        /*
         * sort list
         */
        System.out.println("CurrentElement: " + num);
        Collections.sort(my_list);
    }

输出

List: 2,1,
CurrentElement: 2
List: 1,2,
CurrentElement: 2

人们会期待一个 ConcurrentModificationException，但它没有被引发并且代码有效，尽管它不应该。

Answer 1

当您在迭代时没有从集合中添加/删除元素时，为什么会抛出 ConcurrentModificationException？

请注意，ConcurrentModificationException 只会在迭代时将新元素添加到您的集合或从您的集合中移除时发生。即，当您的 Collections 被结构修改时。

(Structural modifications are those that change the size of this list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.)

sort 不会在结构上修改您的集合，它所做的只是修改顺序。 下面的代码会抛出 ConcurrentModificationException，因为它在迭代时向集合中添加了一个额外的元素。

for(Integer num : my_list) {
    my_list.add(12);
    }

如果你查看 Collections 中排序方法的源代码类，它不会抛出 ConcurrentModificationException。

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

public static <T extends Comparable<? super T>> void sort(List<T> list) {
        Object[] a = list.toArray();
        Arrays.sort(a);
        ListIterator<T> i = list.listIterator();
        for (int j=0; j<a.length; j++) {
            i.next();
            i.set((T)a[j]);
        }
    }

摘自本书java Generics and Collections :

The policy of the iterators for the Java 2 collections is to fail fast, as described in Section 11.1: every time they access the backing collection, they check it for structural modification (which, in general, means that elements have been added or removed from the collection). If they detect structural modification, they fail immediately, throwing ConcurrentModificationException rather than continuing to attempt to iterate over the modified collection with unpredictable results.