java - 使用相同的对象作为 HashMap 中的键和值

Question

我已经尽可能多次地重新措辞此搜索，但我什么也没得到，所以要么以前没有问过这个问题，要么我不知道如何问。

我正在开发一个个人项目，该项目归结为试图找到从起始状态到结束状态的最短路径。

状态太多(超过 2^64)，因此我无法生成整个图。然而，每个状态都包含足够的信息来确定与其相邻的所有状态。从一个状态到另一个状态有(无限)多条路径，我只对最短的路径感兴趣。这要求我知道我以前是否到达过某个状态，以及我第一次是如何到达那里的。

我的状态对象包含所有状态信息，以及引导我到达那里的路径的深度，以及我从该路径中的上一个状态到达那里所采取的移动。如果我按照不同的路径到达相同的状态，状态信息将相同，但深度和先前的移动字段将不同。

我想要一个数据结构，它可以告诉我之前是否访问过该状态，如果访问过，则从中检索深度和先前的状态信息。

到目前为止，我想出的最佳解决方案是使用将状态映射到状态的 HashMap，并使用相同的状态对象作为键和值，如下所示:myHashMap。 put(myState, myState)

我已经实现了 hashCode() 和 equals() ，这样，如果两个状态的状态信息相同(即我们以前来过这个房间)，则无论我如何到达那里(即，我们之前来过这个房间)，它们都将被视为“相等”。我用哪扇门进入房间)。

这看起来相当愚蠢，但我想不出另一种方法(快速存储/访问)来存储有关我是否去过某个州以及如何到达那里的信息。

我的计划有意义吗，或者有更好的方法吗？

Answer 1

您说“我想要一个数据结构，它可以告诉我以前是否访问过该状态，如果访问过，则从中检索深度和先前的状态信息。”

集合(HashSet 可能比您所描述的 TreeSet 更好)将完成第一部分。现在，我看到您正在尝试使用 map 来完成后半部分的操作，即检索信息。但是，如果您已经能够检查您是否访问过某个州，则意味着您拥有对该州的引用。所以，您根本不需要 map 。

/*  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'
}