2

全准序(也称为全预序)是一种较弱的排序关系,允许两个不同的元素被认为是“相同大小”。例如,所有字符串的集合是按长度准排序的,因为两个不同的字符串可以具有相同的长度。

现在假设我们有一个字符串列表,我们想按长度排序(最短的优先)。如果两个字符串的长度相同,我们不关心哪个先出现。乍一看,这样写似乎有道理

Collections.sort(list, (s, t) -> s.length() - t.length());

不幸的是,这是非法的。Comparator 接口的 Javadoc 明确要求比较必须实现总排序。这是违反的,因为 "a".length() - "b".length() 等于 0,但 "a".equals("b") 是假的。

那么,我们应该如何干净地做到这一点呢?干净地说,我的意思是不引入虚假比较,例如通过哈希码或自然排序。

4

2 回答 2

1

您使用长度的解决方案确实提供了总排序

您所指的是"a".length() - "b".length() == 0,但"a".equals("b") == false不是总排序。它与与 equals 保持一致有关。在这一点上,Comparable 接口的文档说:

当且仅当 c.compare(e1, e2)==0 对于每个 e1 具有与 e1.equals(e2) 相同的布尔值时,比较器 c 对一组元素 S 施加的排序被称为与 equals 一致和 S 中的 e2。

这并不意味着您必须提供与 equals 一致的比较器。

于 2015-10-13T21:48:23.377 回答
1

您误解了文档。当他们说

一个比较函数,它对某些对象集合进行总排序。

这是一个定义,而不是要求。对于给定的Comparator, c, if c.compare(o1, o2) == 0, 那么对于 , 定义的顺序而言c,o1o2是相等的。

文档继续讨论 a Comparator“与 equals 一致”意味着什么,这基本上意味着 中固有的平等意义,Comparator如上所述,与允许对象的equals()方法中固有的平等意义相同。该讨论基于某些Comparators 将不具有该特征的可能性,而您提出的一个则没有。使用这样的 aComparator来订购 aSortedSet或 aSortedMap可能会产生违反这些接口契约的行为,但是使用这样的 aComparator并没有错Collections.sort()

于 2015-10-13T21:51:17.703 回答