如何获得“与等号不一致”的树集

Question

我读过很多关于树集、可比/比较器接口、equals、compareTo、compare方法的帖子，我知道API说您必须使您的排序“与equals一致”，否则可能会发生奇怪的事情。

但在我的情况下，我认为这是一个相当普遍的情况，我真的需要一个“与等于不一致”的TreeSet排序。

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

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

现在问题来了。为了适应按成本值排序，我们需要为树集提供一个比较成本值的比较器。但是，两个不同的州可能具有相同的成本/启发值。我想把这两个州都列入我的公开名单，因为它们并不“平等”。但comparator需要从compare方法返回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

“与equals一致”的意思是，对于彼此相等的两个对象，比较器应返回0，或者：

<代码>obj1。等于（obj2）应与比较器的布尔值相同。比较（obj1、obj2）==0；

但是您可以自由地使用自己的比较器，它将低成本置于高成本之上，只要比较器在相等的状态下返回0。

Answer 2

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

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

这是一种词典排序，它与equals（）完全一致。（因为比较器将返回0 iffequals（）返回true。）

旁白：根据您的具体使用情况，使用优先级队列（PriorityQueue）可能比使用树集（TreeSet）更好。那么您就不必担心具有相同优先级的多个元素。