java - 如何拥有一个 "inconsistent with equals"的 TreeSet

Question

我阅读了很多关于 TreeSet、Comparable/Comparator Interfaces、equals、compareTo、compare 方法的文章，并且我知道 API 要求您必须使排序“与等于一致”，否则可能会发生奇怪的事情。

但就我而言，我认为这是一个相当普遍的情况，我确实需要一个“与等号不一致”的 TreeSet 排序。

假设我们正在进行某种启发式搜索，并且我们正在从根(初始)状态开始扩展(或生成)新状态。我们将新的(扩展/生成的)状态放入我们通常称为开放列表的 TreeSet 中。我们想使用 TreeSet 容器，因为我们不希望在我们的打开列表中有重复的状态。

生成/扩展的每个状态都由一个成本函数进行评估，并给出一个显示状态质量的启发式值。我们希望 TreeSet(开放列表)按此值排序。我们希望在 TreeSet 的顶部拥有最好的状态(具有最佳成本值)。

问题来了。为了适应按成本值排序，我们需要给 TreeSet 一个比较成本值的比较器。但是，两个不同的状态可以具有相同的成本/启发值。我想将这两种状态都放在我的开放列表中，因为它们不“平等”。但是比较器需要从比较方法中返回 0，因为它们具有相同的成本值。正因为如此，具有相同成本值的不同状态将不会被插入到列表中。

我想举一个简单的例子来让这个更容易理解。假设我们的状态是显示二进制数据的字符串，成本函数计算字符串中“1”的数量。

假设这些是生成的状态及其各自的成本值。

  No  State       Cost 
  1   01001001     3
  2   01101001     4
  3   10001001     3
  4   01001111     5

如您所见，所有这 4 个状态都是不同的。他们“不平等”。但是即使 state-1 和 state-3 不同，它们具有相同的成本值“3”。因此，当我们按成本对 TreeSet 进行排序时，state-3 将不会添加到 TreeSet 中，因为已经有一个具有相同成本值的元素。但是我们需要将该状态添加到列表中，因为它是完全有效的、不同的、新的状态。

我怎样才能克服这个问题？

谢谢。

Answer 1

您所需要的只是一个可以做两件事的比较器:

1. 首先比较成本。较低的成本将排在第一位。
2. 如果成本相等(并且只有这样)，它会使用任意决胜局对各州进行排名。 (例如，比较状态的 ID。)重要的是，虽然决胜局可以是任意的，但它应该是确定性的，仅取决于状态对象中的字段，这些字段将在集合中对象的整个生命周期中保持不变。

这是一种 lexicographic ordering并且它与 equals() 完全一致。 (因为当 equals() 返回 true 时比较器将返回 0。)

完全放在一边:根据您的具体用例，使用 PriorityQueue 可能会更好而不是 TreeSet。这样您就不必担心具有相同优先级的多个元素。