部分有序的比较器
如何实现根据部分顺序关系对其元素进行排序的java.util.Comparator ？
例如，给定偏序关系a≺c，b≺c; a和b的顺序是不确定的。
由于Comparator需要总排序，因此实现命令部分排序未定义但是一致的元素。
以下工作会怎样？
interface Item { boolean before(Item other); } class ItemPartialOrderComperator implements Comparator { @Override public int compare(Item o1, Item o2) { if(o1.equals(o2)) { // Comparator returns 0 if and only if o1 and o2 are equal; return 0; } if(o1.before(o2)) { return -1; } if(o2.before(o1)) { return +1; } return o1.hashCode() - o2.hashCode(); // Arbitrary order on hashcode } }
- 这个比较器的订购是否具有传递性？
（我担心不是） -
Comparators是否需要传递？
（在TreeMap） - 如何正确实现？
（如果上面的实现不起作用）
（Hashcodes可能会发生碰撞，为简单起见，碰撞示例忽略了碰撞;请参阅Damien B的回答 ， 对Java中* any *类的所有实例强加一个总排序，以便对哈希码进行故障安全排序。）
问题是，当你拥有无法比较的元素时，你需要回到比比较哈希码更聪明的东西。 例如，给定部分顺序{a TreeMap出现问题。
一般情况下，除了事先对键进行拓扑排序之外，您可能无需做任何事情，因此欢迎您关注部分顺序的一些细节。
它似乎更像是一个答案，而不是一个评论所以我会发布它
文件说：
从比较合同中可以看出，商是S上的等价关系，强加的排序是S上的总顺序。
所以不，比较器需要总排序。 如果您通过部分订购实施此操作，则违反了接口合同。
即使它可能在某些情况下有效， 也不应试图以违反接口合同的方式解决您的问题。
请参阅此问题，了解适合部分排序的数据结构。
每当我尝试使用哈希码进行此类事情时，我都会后悔。 如果您的订购是确定性的，那么您会更高兴 – 如果没有别的话可用于调试。 以下将通过为任何以前未遇到的Item创建新索引并使用这些索引进行比较（如果所有其他方法都失败）来实现此目的。
请注意，订购仍然不保证是可传递的。
class ItemPartialOrderComperator implements Comparator- { @Override public int compare(Item o1, Item o2) { if(o1.equals(o2)) { return 0; } if(o1.before(o2)) { return -1; } if(o2.before(o1)) { return +1; } return getIndex(o1) - getIndex(o2); } private int getIndex(Item i) { Integer result = indexMap.get(i); if (result == null) { indexMap.put(i, result = indexMap.size()); } return result; } private Map
indexMap = new HashMap(); }
在jdk7中，您的对象将抛出运行时exception：
区域：API：实用程序概要：arrays和集合的更新排序行为可能会抛出IllegalArgumentException说明：已替换
java.util.Arrays.sort和（间接）java.util.Collections.sort使用的排序算法。
如果新排序实现检测到违反Comparable合同的Comparable，则可能抛出IllegalArgumentException 。 以前的实现默默地忽略了这种情况。 如果需要先前的行为，则可以使用新的系统属性java.util.Arrays.useLegacyMergeSort来恢复先前的mergesort行为。不相容的性质：行为
RFE： 6804124
如果a < b和b < c暗示a < c ，那么您已使用hashCodes进行了总排序。 拿a < d, d < c 。 偏序表示b和d不一定是有序的。 通过引入hashCodes，您可以提供排序。
示例：is-a-descendant-of（human，human）。
Adam (hash 42) < Moses (hash 17), Adam < Joe (hash 9)
暗示
Adam < Joe < Moses
一个反面的例子是相同的关系，但是当时间旅行允许成为你自己的后代时。
当一个项既不是“之前”也不是“之后”另一项时，不是返回哈希码的比较，而是返回0 。 结果将是重合项的“总排序”和“任意”排序。