這是我想分享的一個問題,而不是一個問題:當使用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