間接サイクルでJavaのtoString（）ループが無限ループするのはなぜですか？

Question

toString()で印刷すると、Javaはコレクション内のダイレクトサイクルを検出しますが、間接サイクルでは検出されません（コレクションは別のコレクションを参照します）。最初のものを指すか、それ以上のステップを参照します）。 （それが直接のサイクルを捕まえたときに、私は驚いたので、私は、彼らは一般的に、チェックを実施していたことを間違って仮定）コレクションをプリントアウトするためのコードをデバッグする際に発生したため

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

これ

は、私にとって本当の落とし穴でした。なぜですか？

私が考えることができるのは、すでにコレクションを保存する必要があるだけであるため、自分自身を参照するコレクションをチェックするのは非常に安価ですが、長いサイクルでは、あなたが遭遇するすべてのコレクションは、ルートから始まります。さらに、のルートが何であるかを確実に伝えることができない場合があるので、システムにすべてのコレクションを格納する必要があります。これはあなたがやることですが、すべてのコレクションをすべて保存する必要がありますコレクション要素。サイクルの比較的まれなケース（ほとんどのプログラミングでは）は非常に高価です。 （私は）直接のサイクルをチェックする唯一の理由は、それがとても安価である（1つの参照比較）ためです。

OK ...私はちょっと自分の質問に答えました - しかし、私は何か重要なことを逃しましたか？誰でも何かを追加したいですか？

---

明確化：私は今、私が見た問題はコレクション（すなわちtoString()メソッド）を印刷に固有のものです実現。サイクルに問題はありませんそれ自体はです（私はそれを自分で使い、持っている必要があります）。問題はJavaがそれらを印刷できないことです。 編集Andrzej Doyleはコレクションだけでなく、toStringというオブジェクトを指摘しています。それは、この方法に制限されますことを考えると

は、ここでそれをチェックするためのアルゴリズムです：

• ルートは最初toString()がこれを決定するために（上で呼び出され、あなたがいるかどうかに状態を維持する必要があることをオブジェクトでありますtoStringが現在進行中であるかどうかはわかりませんので、これは不便です）。
  • 各オブジェクトをトラバースするときに、一意の識別子（増分インデックスなど）と共にIdentityHashMapに追加します。
  • このオブジェクトがすでにマップにある場合は、その識別子を代わりに書き出します。

このアプローチはまた、正しくmultirefs（回以上参照されるノード）をレンダリングします。

メモリコストは、IdentityHashMap（オブジェクトごとに1つの参照とインデックス）です。複雑さコストは、有向グラフ内の各ノード（すなわち、印刷される各オブジェクト）のハッシュ・ルックアップである。