4

这更像是一个我想分享的问题而不是一个问题：当使用 打印时toString()，Java 将检测 Collection 中的直接循环（Collection 引用自身），但不会检测间接循环（Collection 引用另一个 Collection 引用第一个 - 或更多步骤）。

import java.util.*;
public class ShonkyCycle {
  static public void main(String[] args) {
    List a = new LinkedList();
    a.add(a);                      // direct cycle
    System.out.println(a);         // works:  [(this Collection)]

    List b = new LinkedList();
    a.add(b);
    b.add(a);                      // indirect cycle
    System.out.println(a);         // shonky:  causes infinite loop!
  }
}

这对我来说是一个真正的问题，因为它发生在调试代码以打印出 Collection 时（当它捕捉到一个直接循环时我很惊讶，所以我错误地假设他们已经实现了一般的检查）。有一个问题：为什么？

我能想到的解释是，检查引用自身的集合非常便宜，因为您只需要存储集合（您已经拥有），但是对于更长的周期，您需要存储所有集合相遇，从根源开始。此外，您可能无法确定根是什么，因此您必须将每个集合存储在系统中 - 无论如何您都会这样做 - 但您还必须对每个集合元素进行哈希查找. 对于相对罕见的循环情况（在大多数编程中），这是非常昂贵的。（我认为）它检查直接循环的唯一原因是因为它非常便宜（一个参考比较）。

好的......我已经回答了我自己的问题 - 但我错过了什么重要的事情吗？有人想添加什么吗？

澄清：我现在意识到我看到的问题是特定于打印集合（即toString()方法）。循环本身没有问题（我自己使用它们并且需要拥有它们）；问题是Java无法打印它们。编辑Andrzej Doyle 指出它不仅仅是集合，而是任何toString被调用的对象。

鉴于它受限于此方法，这里有一个算法来检查它：

  • 根是调用第一个对象的对象toString()（要确定这一点，您需要维护 toString 当前是否正在进行的状态；所以这很不方便）。
    • 当您遍历每个对象时，您将其添加到 IdentityHashMap 以及唯一标识符（例如递增索引）。
    • 但是如果这个对象已经在 Map 中，写出它的标识符。

这种方法还可以正确渲染多引用（一个被多次引用的节点）。

内存成本是 IdentityHashMap（每个对象一个引用和索引）；复杂性成本是有向图中每个节点（即打印的每个对象）的哈希查找。

4

5 回答 5

5

我认为从根本上说，这是因为虽然语言试图阻止你在脚下开枪，但它不应该以一种昂贵的方式这样做。因此，尽管比较对象指针（例如 dos obj == this）几乎是免费的，但除此之外的任何事情都涉及调用您传入的对象的方法。

此时库代码对您传入的对象一无所知。一方面，泛型实现不知道它们是否是Collection（或Iterable）自身的实例，虽然它可以通过以下方式找到它instanceof，谁能说它是否是一个实际上不是集合但仍包含延迟循环引用的“类集合”对象？其次，即使它是一个集合，也不知道它的实际实现是什么，因此行为是什么样的。从理论上讲，可以有一个包含所有将被懒惰使用的 Long 的集合；但是由于图书馆不知道这一点，因此迭代每个条目的成本会非常高。或者实际上，甚至可以设计一个带有永不终止的迭代器的集合（尽管这在实践中很难使用，因为很多构造/库类都假设hasNext最终会返回false）。

所以它基本上归结为一个未知的，可能是无限的成本，以阻止你做一些实际上可能不是问题的事情。

于 2009-06-15T11:04:05.990 回答
3

我只想指出这个声明：

当使用 toString() 打印时，Java 将检测集合中的直接循环

具有误导性。

Java（JVM、语言本身等）没有检测到自引用。相反，这是 的toString()方法/覆盖的属性java.util.AbstractCollection。

如果您要创建自己的Collection实现，语言/平台不会自动保护您免受这样的自我引用 - 除非您扩展AbstractCollection，否则您必须确保自己涵盖此逻辑。

我可能会在这里分裂头发，但我认为这是一个重要的区别。仅仅因为 JDK 中的一个基础类做了某事并不意味着“Java”作为一个整体可以做到。

以下是 中的相关源代码AbstractCollection.toString()，关键行注释：

public String toString() {
    Iterator<E> i = iterator();
    if (! i.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = i.next();
        // self-reference check:
        sb.append(e == this ? "(this Collection)" : e); 
        if (! i.hasNext())
            return sb.append(']').toString();
        sb.append(", ");
    }
}
于 2009-06-16T04:42:46.557 回答
1

您提出的算法的问题是您需要将 IdentityHashMap 传递给所有涉及的集合。使用已发布的 Collection API 无法做到这一点。Collection 接口没有定义toString(IdentityHashMap)方法。

我想 Sun 的任何人都将自我参考检查纳入AbstractCollection.toString()考虑所有这些的方法，并且（与他的同事一起）认为“全面解决方案”是最重要的。我认为当前的设计/实现是正确的。

It is not a requirement that Object.toString implementations be bomb-proof.

于 2009-09-26T23:26:49.913 回答
0

你是对的，你已经回答了你自己的问题。检查更长的周期（尤其是像周期长度 1000 这样的非常长的周期）会产生过多的开销，并且在大多数情况下不需要。如果有人想要它，他必须自己检查。

然而，直接循环的情况很容易检查并且会更频繁地发生，所以它是由Java完成的。

于 2009-06-15T10:58:44.333 回答
0

您无法真正检测到间接循环；这是停机问题的典型示例。

于 2009-06-15T10:59:09.557 回答