为什么Java toString（）会在间接循环中无限循环？

问题描述：

这是我想分享的一个问题，而不是一个问题：当使用toString()进行打印时，Java将检测Collection中的直接循环（其中Collection是指其本身），但不是间接循环（其中Collection指另一个Collection指的是第一个 - 或者更多的步骤）。为什么Java toString（）会在间接循环中无限循环？

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! 
    } 
}

这对我是一个真正的疑难杂症，因为它发生在调试代码打印出来的集（我很惊讶，当它抓住了一个直接的循环，所以我认为不正确，他们已经实施了一般的检查）。有一个问题：为什么？

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

好的...我有点回答我自己的问题 - 但是我错过了什么重要的东西？任何人都想添加任何东西？

澄清：我现在意识到我看到的问题是特定于打印集合（即toString()方法）。周期本身没有问题（我自己使用它们，需要它们）;问题是Java不能打印它们。编辑 Andrzej Doyle指出，它不只是集合，还包括任何调用toString的对象。

由于它受限于这种方法，这里是一个算法来检查它：

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

这种方法也正确呈现multirefs（即称为不止一次的节点）。内存开销是IdentityHashMap（每个对象一个引用和索引）;复杂性成本是针对有向图中的每个节点（即打印的每个对象）的散列查找。

“...但不是直接循环...”的错字应该不是间接的吗？ – 2009-06-15 10:54:26

第一次我见过有人包装System.out.println ...请不要混淆示例代码（或生产代码！） – basszero 2009-06-15 11:03:24

@Stephen：是的，谢谢。 ysth似乎已经修复它 - 谢谢。 – 13ren 2009-06-15 11:18:54

答

我认为这基本上是因为虽然语言试图阻止你在脚下射击自己，但它不应该以昂贵的方式实现。因此，虽然几乎可以*比较对象指针（例如obj == this），但除此之外的任何事情都需要调用传递对象的方法。

而在这一点上，库代码并不知道任何有关对象的信息，例如，泛型实现不知道它们自己是否是Collection（或Iterable）的实例，虽然它可以通过instanceof找到它，但是谁可以说它是否是一个“类似集合”的对象实际上并不是一个集合，但仍包含一个延期的循环引用？其次，即使它是一个集合，也不知道它是什么实际的实现，因此行为是这样的。理论上可以有一个包含所有将要被懒惰使用的Longs的集合;但由于图书馆不知道这一点，对每一个条目进行迭代都会非常昂贵。或者事实上甚至可以用一个永不终止的Iterator来设计一个集合（尽管这在实践中很难使用，因为如此多的构造/库类别假设hasNext最终将返回false）。

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

答

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

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

答

你不能真正检测间接循环;这是停止问题的典型例子。

答

我只是想指出，这种说法：

用的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(", "); 
    } 
}

答

与您提出的算法的问题是，你需要通过IdentityHashMap所有涉及到的集合。这是不可能的，使用发布的收集API。 Collection接口没有定义toString(IdentityHashMap)方法。

我想，无论是谁把自己的参考检查纳入AbstractCollection.toString()方法思想的所有这一切，并（与他的同事一起）决定“总体解决方案”超过顶部。我认为目前的设计/实施是正确的。

Object.toString实现不是必需的，它是防弹的。

为什么Java toString（）会在间接循环中无限循环？

相关推荐