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

Question

我读过许多关于TreeSets、可比/比较器接口、等号、compareTo、比较方法的文章，我知道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时，状态-3将不会添加到TreeSet中，因为已经有一个具有相同成本值的元素。但是我们需要将这个状态添加到列表中，因为它是完全有效的、不同的、新的状态。

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

谢谢。

Answer 1

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

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

这是一种词典排序，它与equals()完全一致。(因为比较器将返回0当且仅当equals()返回true。)

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

Answer 2

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

obj1.equals(obj2)应该是与comparator.compare(obj1, obj2) == 0相同的布尔值；

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