为什么Java toString()在间接循环中无限循环？

Question

这更像是一个我想分享的问题而不是一个问题:当打印时toString(),Java将检测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(当它遇到直接循环时我感到很惊讶,所以我错误地认为他们已经实现了一般的检查).有一个问题:为什么？

我能想到的解释是,检查一个引用自身的集合是非常便宜的,因为你只需要存储集合(你已经存在),但是对于更长的周期,你需要存储所有的集合你遭遇,从根开始.此外,您可能无法确切地回答什么的根,所以你必须存储在系统中的每个集合-你无论如何做-但你也不得不做的每集合元素的哈希查找.对于相对罕见的周期(在大多数编程中),这是非常昂贵的.(我认为)它检查直接循环的唯一原因是因为它如此便宜(一个参考比较).

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

---

澄清:我现在意识到我看到的问题特定于打印 Collection(即toString()方法).循环本身没有问题(我自己使用它们并需要它们); 问题是Java无法打印它们.编辑 Andrzej Doyle指出它不仅仅是集合,而是任何toString被称为的对象.

鉴于它受此方法的限制,这里有一个检查它的算法:

• root是第一个toString()被调用的对象(为了确定这一点,你需要保持关于toString当前是否正在进行的状态;所以这很不方便).
  • 在遍历每个对象时,将其添加到IdentityHashMap,以及唯一标识符(例如递增的索引).
  • 但如果此对象已在Map中,请写出其标识符.

此方法还可以正确呈现multirefs(一个多次引用的节点).

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

Answer 1

我认为从根本上说这是因为当语言试图阻止你在脚下射击时,它不应该以一种昂贵的方式这样做.因此,虽然几乎可以自由地比较对象指针(例如确实如此obj == this),但除此之外的任何事情都涉及在您传入的对象上调用方法.

此时,库代码对您传入的对象一无所知.例如,泛型实现不知道它们是否是Collection(或Iterable)自身的实例,而它可以通过instanceof,谁说它是否是一个"集合式"对象,实际上不是一个集合,但仍然包含一个延迟的循环引用？其次,即使它是一个集合,也不知道它的实际实现是什么,因此行为就像.从理论上讲,人们可以拥有一个包含所有Longs的集合,这些集合将被懒惰地使用; 但由于图书馆不知道这一点,因此迭代每个条目会非常昂贵.或者实际上甚至可以设计一个永远不会终止的迭代器集合(虽然这在实践中很难使用,因为很多构造/库类假设hasNext最终会返回false).

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