HashMapのキーと値の両方と同じオブジェクトを使用

Question

私はできると思って何回もこの検索を書き直しましたが、何も出てこなかったので、これは前に尋ねられていません、または私は聞く方法を知らない。

私は、開始状態から終了状態までの最短経路を見つけようとすることに至るまで、個人的なプロジェクトに取り組んでいます。

状態が多すぎる（2^64以上）ので、グラフ全体を生成できません。しかし、各状態には、それに隣接するすべての状態を決定するのに十分な情報が含まれています。州ごとに（無限に）多くの道があり、私は最短でしか興味がありません。これは、私が以前の状態になったかどうか、また初めて私がそこにいかに来たかを知る必要があります。

私の状態オブジェクトには、すべての状態情報、そこにつながるパスの深さ、およびそのパスの前の状態からそこに到達するための移動が含まれています。別のパスの後に同じ状態になると、状態情報は同じになりますが、深さと前の移動フィールドは異なります。

私は以前にその状態に行ったことがあるかどうかを教えてくれるデータ構造が必要です。もしあれば、そこから深さと前の状態情報を取得します。 myHashMap.put(myState, myState)

：

私は今のところ出ている最善の解決策は、のように、状態に状態をマップHashMapを使用して、キーと値の両方と同じ状態のオブジェクトを使用することです私はhashCode（）とequals（）を実装しています。つまり、どのように私がそこに着いたかに関係なく、状態情報が同じ（つまり、私たちは前にこの部屋にいました）場合、2つの状態は "等しい"部屋に入るのに使用された）。

これはむしろ愚かなようだが、私は状態になって、どのように私はそこに持っているかどうかについての情報を格納する（高速ストレージ/アクセス権を持つ）別の方法を考えることはできません。

私の計画は意味があるのですか、それとも良い方法がありますか？

Answer 1

キーと値を同じ値として保存している場合は、実際に必要なのはSetです。

Set<State> set = new HashSet<>(); 
set.put(stat1); 

そして、あなたのソリューションは非常に遠いことからHashSetはHashSetのはHashMapのものと性能特性を持ち、equalsとhashCode方法に依存している意味舞台裏HashMapによってバックアップされていない道によります。

Answer 2

あなたは、「私は私の前にその状態を訪問しているなら、私に教えて、私が持っている場合は、それからの深さと、以前の状態情報を取得するデータ構造をしたい。」と言います

Set（HashSetは、あなたが記述したもののTreeSetより優れている可能性が高い）は、最初の部分を行います。さて、私はあなたが情報を取得している後半を行うためにマップを使用しようとしていることがわかります。しかし、あなたが既に州を訪問したかどうかを確認することができれば、その州への参照があることを意味します。だから、地図は一切必要ありません。

/* Marking a state as visited */ 
Set<State> visited = new HashSet<>(); 
visited.put(currentState); 

/* Checking if visited/retrieving */ 
if (visited.contains(currentState)) { 
    // already visited 
} else { 
    // do something with 'currentState' 
}