如何拥有“与等于不一致”的 TreeSet

Question

我已经阅读了大量关于 TreeSets、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 个状态都是不同的。他们“不相等”。但是即使状态 1 和状态 3 不同，它们也具有相同的成本值“3”。因此，当我们按成本对 TreeSet 进行排序时，状态 3 将不会添加到 TreeSet 中，因为已经存在具有相同成本值的元素。但是我们需要将该状态添加到列表中，因为它是完全有效的、不同的、新的状态。

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

谢谢。

Answer 1

您需要的只是一个比较器，它可以做两件事：

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

这是一种字典顺序，与equals(). （因为比较器将返回 0 iffequals()返回 true。）

完全搁置：根据您的特定用例，使用 a 可能PriorityQueue比使用TreeSet. 那么您就不必担心具有相同优先级的多个元素。