如何爲循環圖節點編寫hashCode（）函數？

我有以下類被用作圖的一部分：如何爲循環圖節點編寫hashCode（）函數？

public class MyNode { 

    private String name; 

    private Set<MyNode> parents; 

    private Set<MyNode> children; 

    // getters and setters 
}

當我使用Eclipse的Source/Generate hashCode() and equals()，它生成此方法：

@Override 
public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + ((children == null) ? 0 : children.hashCode()); 
    result = prime * result + ((name == null) ? 0 : name.hashCode()); 
    result = prime * result + ((parents == null) ? 0 : parents.hashCode()); 
    return result; 
}

的問題是，這種方法從進入當前對象給它的孩子，然後在計算第一個孩子的hashCode（）時，它通過parents.hashCode()回到原始節點，但不知道在那裏已經計算了hashCode（）。然後重新進入原始節點的children，並且它給出了一個美麗的無限循環。

問題：如何檢查MyNode的兩個實例是同一個對象，同時避免無限循環？這是可以接受的在MyNode類中添加一個visited布爾值，用於停止探索？還是有更好的解決方案？

謝謝！

來源

2013-12-19 Grégoire C

'visited'將不得不改回來。 –

實施hashCode和equals時，您不應該使用子節點或父節點。他們是可變屬性。計算hashCode在改變邊界後將會有所不同，並會導致地圖和集合集合失效。

實現hashCode和equals只使用不可變的字段，爲對象創建一個不同的自然鍵。名字可能是一個很好的候選人，除非可以改變。

如果沒有一成不變的領域存在，或者：

不要覆蓋hashCode和equals方法，默認將被罰款。它將使每個類實例都是唯一的。
做一些獨特的id字段（按sequance）並將其用作hashCode中的種子並在equals中比較。

來源

2013-12-19 16:01:42

但是，如果兩個節點具有相同的不可變字段而不在圖中的相同位置呢？ –

Um ...在大多數應用程序中，默認值是*不是很好，因爲默認實現基本上爲每個實例提供了不同的數字。即沒有兩個實例是相同的，即使它們具有完全相同的數據。 – Stroboskop

+1給Stropboskop。 equals（）和hashcode（）相互尊重它們的契約是非常重要的。在這種情況下，我認爲你只想散列節點名稱。 –

您可以檢查兩個對象是否使用== opearator相同的實例：

if(obj0 == obj1)

如果你想使用一個visited標誌，你應該使用查找（例如Map），因爲實現它在您的代碼運行後，您必須重置這些標誌。

我建議忽略parents/children，而是向每個節點添加一個唯一的id。

來源

2013-12-19 16:04:54

如果「訪問」標誌在try {/ * recurse * /}中被清除，那麼他可能會使用visited和緩存值，最後{visited = false;} –

hashCode()上唯一的硬性要求是兩個相等的對象必須返回相同的散列值。

此實現將遵守：

@Override 
public int hashCode() { 
    return 42; 
}

...因爲沒有說非相等的對象必須具有不同的散列碼。

當然，要正確地完成工作，如果價值可以分散，hashCode()會更好。只要你不打破平等對象的規則，你就可以做任何你喜歡的事情。在一般的通用代碼中，我不希望哈希對性能至關重要，我通常只是返回一個或兩個重要字段的哈希碼（例如，在這種情況下是名稱），前提是這些字段涉及計算相等的對象具有相同的散列。

問題是，你真的需要考慮equals和hashCode作爲一對，最好從等於你的定義開始。

來源

2013-12-19 17:10:15

@geceo請注意危險，您的Set節點將變得非常緩慢，因爲所有節點都將保存在Set實現內的散列表的一個桶內。 –

當然 - 我並不是建議他實際使用「42」實現，我只是用它作爲示例來演示hashCode不必很複雜。 –

如何爲循環圖節點編寫hashCode（）函數？

回答

相關問題