Java.util.Sublist抛出StackOverFlowError

Question

我们在生产环境中偶尔会遇到与SubList操作相关的StackOverFlowError错误。有人之前遇到过这种情况并知道是什么原因引起的吗？

以下是触发错误的代码：

  FacesContext context = FacesContext.getCurrentInstance();
    String newViewID = context.getViewRoot().getViewId();

    if (newViewID != null) {
     if (breadCrumbs.contains(newViewID)) {
      // Trims the list upon going back to allow for multiple back button requests.  
      // This is lightweight and not intended for a complex circular navigation.
      breadCrumbs = breadCrumbs.subList(0, breadCrumbs.indexOf(newViewID) + 1);
     } else {
      breadCrumbs.add(newViewID);
     }
    }

结果如下：

Caused By: java.lang.StackOverflowError
 at java.util.SubList$1.<init>(AbstractList.java:688)
 at java.util.SubList.listIterator(AbstractList.java:687)
 at java.util.SubList$1.<init>(AbstractList.java:688)
 at java.util.SubList.listIterator(AbstractList.java:687)
 ...

- BestPractices

---

你使用的JDK版本是哪个？从open JDK中获取的SubList似乎没有这个无限循环的问题：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/AbstractList.java#SubList - Colin Hebert

以下是原因（可变列表的子列表），但你想做的似乎是从crumb列表中删除尾部元素，而不是创建一个隐藏它们的旧列表的新视图（sublist所做的）。 - j flemm

Answer 1

subList()方法返回的是由原始列表支持的视图。

根据Javadoc：

如果通过返回的列表以外的任何方式对支持列表（即此列表）进行结构修改，则此方法返回的列表的语义变得未定义。（结构修改是那些改变此列表大小或以其他方式扰动它的修改，这样正在进行的迭代可能会产生不正确的结果。）

您正在对列表进行结构更改，因此所有赌注都关闭了 - 任何事情都可能发生，包括似乎发生的无限递归。

- Jim Garrison

---

换句话说，你应该这样做：breadCrumbs = new ArrayList(breadCrumbs.subList(0, breadCrumbs.indexOf(newViewID) + 1));，这会使代码更加简洁高效。 - Powerlord

Answer 2

我曾经使用LinkedList标准库和fastutil objectarraylist遇到过完全相同的问题（fastutil是Java集合框架的快速高效内存实现）。

使用

window = window.subList(index+1, window.size());

导致stackoverflow错误。我替换为

。

window = new LinkedList<>( window.subList(index+1, window.size()) );

一切都正常工作。

希望能有所帮助。

- besil

Answer 3

这是相关源代码的摘录：

681    public ListIterator<E> listIterator(final int index) {
...
687        return new ListIterator<E>() {
688            private ListIterator<E> i = l.listIterator(index+offset);

这个 StackOverflowError 表明 l 在某种程度上指向当前的子列表，因此在无限循环中调用了自己的 listIterator()。

breadCrumbs 来自哪里？它的 getClass() 返回什么？

- BalusC

---

@Colin：你忘记了 $1 部分吗？ - BalusC

Answer 4

问题在于AbstractList.java（ArrayList的基类）实现了subList方法的方式。它通过一个父指针、一个偏移量和一个大小来创建子列表（也称为视图）。

如果在这样的子列表上调用subList，则会得到指向列表的父指针，该列表本身具有一个父指针（依此类推）。

一些操作（例如add）在子列表上递归工作。如果您有非常深层次的父指针层次结构，则会导致StackOverflowError。

以下代码片段显示了问题的隔离部分：

public static void main(String[] args) {
    List<String> lst = new ArrayList<String>();
    lst.add(""); 
    for (int i = 0; i < 50000; i++) {
        lst.set(0, "test");
        lst = lst.subList(0, 1);
    }

    lst.add("test2");       
}

结论：不要像这样递归使用子列表：

breadCrumbs = breadCrumbs.subList(0, breadCrumbs.indexOf(newViewID) + 1);

可以通过从末尾删除元素来设置长度。

更详细的分析请参考我的博客：http://programmingtipsandtraps.blogspot.com/2013/05/javautillistsublist-stackoverflowerror.html

- rli

---

我们不会递归地使用subList或在“一个subList上调用subList”。 - BestPractices

Answer 5

我不认为这是因为 LinkedList 引起的。在对同一个列表进行递归调用 subList 时，我曾经遇到过相同的错误。我认为每次调用 subList 方法时，它的开始/结束索引都会被推入堆栈中。如果该列表很大，因此该方法被调用的次数太多，就会发生 StackOverFlowError 错误。

- chance

Answer 6

问题是由于breadCrumbs是一个LinkedList引起的——我们向LinkedList添加了太多的项，并调用subList暴露了这个问题。

- BestPractices