Java:递归函数中出现意外的运行时错误

Question

这个问题已经有答案了:

ConcurrentModificationException Occuring When Retrieving List Size (2 个回答)

已关闭 5 年前。

我正在尝试编写我自己的 MergeSort 版本并编写了以下类:

import java.util.List;
import java.util.LinkedList;
import java.lang.Comparable;

public class Sort<E extends Comparable<E>> {
  private List<E> list;

  public void setList(List<E> inList) {list = inList;}
  public List<E> getList() {return list;}

  public List<E> mergeSortRec(List<E> inList) {
    if (inList == null) return null;
    if (inList.size() < 2) return inList;
    int mdpt = inList.size()/2;
    List<E> left = inList.subList(0,mdpt);
    List<E> right = inList.subList(mdpt,inList.size());
    left = mergeSortRec(left);
    right = mergeSortRec(right);
    List<E> out = new LinkedList<E>();
    while (left.size()>0 && right.size()>0) {
      if (left.get(0).compareTo(right.get(0)) < 0) {
        out.add(left.remove(0));
      } else {
        out.add(right.remove(0));
      }
    }
    if (left.size()==0) {
      while (right.size()>0) {
        out.add(right.remove(0));
      }
    } else {
      while (left.size()>0) {
        out.add(left.remove(0));
      }
    }
    return out;
  }
  public void mergeSort() {list = mergeSortRec(list);}
}

但是，下面的主类，

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    System.out.println("Input list:");
    LinkedList<Integer> lst = new LinkedList<Integer>();
    lst.add(3);
    lst.add(1);
    lst.add(5);
    Sort<Integer> s = new Sort<Integer>();
    s.setList(lst);
    s.mergeSort();
  }
}

导致以下错误，

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.SubList.checkForComodification(AbstractList.java:769)
    at java.util.SubList.size(AbstractList.java:645)
    at Sort.mergeSortRec(Sort.java:69)
    at Sort.mergeSortRec(Sort.java:59)
    at Sort.mergeSort(Sort.java:79)
    at Main.main(Main.java:12)

插入打印行后，我发现问题来自对 left.size() 的调用在if (left.size()==0) { ，我相信它发生在递归调用的“零级”，也就是说，它发生在 inList 时。是整个原始列表，并且 left是 3 且 right是1,5。我不明白为什么要调用 left 的方法会导致错误。我只是模糊地理解如何可能存在一些并发问题，但我几乎没有这方面的经验，并且我认为left这一事实可以避免它。是函数的返回值，因此不应由多个变量引用 - 如果这与问题有关。

Answer 1

这里的问题是由于从正在迭代的列表中删除了一个项目:

 while (left.size()>0 && right.size()>0) { // iteration on left/right lists
      if (left.get(0).compareTo(right.get(0)) < 0) {
        out.add(left.remove(0)); // modification of the left list
      } else {
        out.add(right.remove(0)); // modification of the right list
      }
 }

在 while 迭代期间删除项目违反了列表对象的约定并导致异常 - ConcurrentModificationException .

有多种方法可以处理此问题 -

• 使用将要修改的列表的副本，同时迭代原始列表。在这种情况下，您可以使用大小计数器而不是调用列表大小方法。
• 使用 Iterator以及迭代器的专用 remove() 方法。
• 对于 Java 8，您可以使用 Collection.removeIf方法。

引用文献:

• How to avoid ConcurrentModificationException / How to remove an item from an ArrayList while iterating over it
• Iterating through a Collection, avoiding ConcurrentModificationException when removing in loop
• Java 8 – Collection.removeIf method tutorial with examples