Java ArrayList内存使用递归

Question

我刚刚审查了一些代码并遇到了一个我无法最终解释的问题，很可能是因为我的 Java 有点生疏......代码正在采用节点的嵌套集合并展平。

这是原始片段:

private static List<NavigationNode> flatten(
        List<NavigationNode> nodes,
        List<NavigationNode> flattenedNodes) {
    if (nodes == null || nodes.isEmpty()) {
        return Collections.emptyList();
    }
    for (NavigationNode node : nodes) {
        flattenedNodes.add(node);
        flattenedNodes.addAll(flatten(node.getChildren(), flattenedNodes));
    }
    return flattenedNodes;
}

我看到的问题是，当嵌套列表增长到足够大时，会抛出 java.lang.OutOfMemoryError。

如果我新建扁平化列表而不是作为参数传递并重构为:

private static List<NavigationNode> flatten(
        List<NavigationNode> nodes) {
    if (nodes == null || nodes.isEmpty()) {
        return Collections.emptyList();
    }
    List<NavigationNode> flattenedNodes = new ArrayList<NavigationNode>();
    for (NavigationNode node : nodes) {
        flattenedNodes.add(node);
        flattenedNodes.addAll(flatten(node.getChildren()));
    }
    return flattenedNodes;
}

内存错误不再发生。

我们将不胜感激任何帮助、出色的描述或进一步的重构!

Answer 1

问题是在第一个片段中会尝试将 flattenedNodes 的内容添加到自身。

想一个简单的例子，node1 有一个 child ，叫做 node2。这里发生了什么？

for (NavigationNode node : nodes) {
    flattenedNodes.add(node);
    flattenedNodes.addAll(flatten(node.getChildren(), flattenedNodes));
}

1. 首先 node1 添加到 flattenedNodes
2. 然后在第二层调用flatten()。
3. node2 也被添加到 flattenedNodes。
4. 当 flatten() 完成时，它返回 flattenedNodes。
5. ...立即被 addAll() 编辑为 flattenedNodes 和 BANG!

每访问一个节点，列表的大小就会增加一倍，所以事情很快就会失控也就不足为奇了。

修复它的一种方法确实是你所做的，另一种方法是用 flatten( node.getChildren(), flattenedNodes). (现在您也可以将 flatten() 的返回类型更改为 void。)不过我不得不说，我更喜欢您的解决方案，它更具可读性，即使可能略有不同更浪费。