爲什麼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 13ren

「...但不是直接循環...」的錯字應該不是間接的嗎？ – 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）。

所以它基本上歸結爲一個未知的，可能無限的成本，以阻止你做一些實際上可能不是問題的事情。

來源

2009-06-15 11:04:05

你是對的，你已經回答了你自己的問題。檢查更長的週期（特別是非常長的週期，如週期長度1000）將會產生過多的開銷，並且在大多數情況下不需要。如果有人想要它，他必須自己檢查它。

但是，直接循環的情況很容易檢查，並且會更頻繁地發生，所以它是由Java完成的。

來源

2009-06-15 10:58:44 schnaader

你不能真正檢測間接循環;這是停止問題的典型例子。

來源

2009-06-15 10:59:09 alamar

我只是想指出，這種說法：

用的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-16 04:42:46

與您提出的算法的問題是，你需要通過IdentityHashMap所有涉及到的集合。這是不可能的，使用發佈的收集API。 Collection接口沒有定義toString(IdentityHashMap)方法。

我想，無論是誰把自己的參考檢查納入AbstractCollection.toString()方法思想的所有這一切，並（與他的同事一起）決定「總體解決方案」超過頂部。我認爲目前的設計/實施是正確的。

Object.toString實現不是必需的，它是防彈的。

來源

2009-09-26 23:26:49

爲什麼Java toString（）會在間接循環中無限循環？

回答

相關問題