循環グラフノードのhashCode（）関数の記述方法は？

Question

私はグラフの一部として使用される次のクラスがあります。

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の2つのインスタンスが同じオブジェクトであり、同時に無限ループを回避する方法を確認するにはどうすればよいですか？探索を停止する目的で、MyNodeクラスにvisitedブール値を追加することは可能ですか？または、より良い解決策がありますか？

ありがとうございます！

Answer 1

hashCodeとequalsを実装するときは、ノードの子または親を使用しないでください。それらは変更可能なプロパティです。 hashCodeの計算は、エッジの変更後に異なるため、マップコレクションとセットコレクションが壊れてしまいます。

hashCodeおよびequalsは、オブジェクトに固有の自然キーを作成する不変フィールドのみを使用して実装します。名前が変更されない限り、名前は良い候補になるかもしれません。全く不変のフィールドが存在しない場合

、次のいずれか

1. がhashCodeとequalsメソッドをオーバーライドしないで、デフォルトは罰金になります。各クラスインスタンスは一意になります。
2. いくつかの一意のIDフィールドを（隔離によって）作成し、hashCodeのシードとして使用し、equalsで比較します。

   if(obj0 == obj1) 
   

   あなたがvisitedフラグを使用する場合は（たとえばMap）のルックアップを使用して、それを実装する必要がありますので、：あなたは2つのオブジェクトが== opearatorを使用して、同じインスタンスであるかどうかを確認することができます

Answer 2

コードが実行された後、これらのフラグをリセットする必要があります。

parents/childrenを無視して、代わりにidを各ノードに追加することをお勧めします。

Answer 3

hashCode()の唯一の厳しい要件は、等しい2つのオブジェクトが同じハッシュ値を返さなければならないことです。

この実装では、準拠していることになります

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

...何が等しくないオブジェクトが異なるハッシュコードを持たなければならないことを述べていないため。

もちろん、値を広げることができれば、hashCode()がうまく機能します。同じオブジェクトについてルールを破らない限り、好きなことをすることができます。通常の汎用コードでは、ハッシュがパフォーマンスにとって重要ではないと考えていますが、一般的に、重要なフィールドまたは2つのハッシュコード（この場合は名前）を返します。等しいオブジェクトが同じハッシュを持つような等価です。

ポイントは、実際にはequalsとhashCodeをペアとして考える必要があります。あなたの定義が最初から好きだと思います。