部分订购的比较器
问题内容:
如何实现java.util.Comparator
根据部分顺序关系对元素进行排序?
例如,给定的部分顺序关系 一个 ≺ Ç , b ≺ Ç ; a 和 b 的顺序不确定。
由于Comparator
需要总排序,因此实现对那些未定义但一致的部分排序的元素进行排序。
以下工作有效吗?
interface Item {
boolean before(Item other);
}
class ItemPartialOrderComperator implements Comparator<Item> {
@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
) -
如何正确实施? (如果上面的实现不起作用)
(哈希码可能会发生冲突,为简单起见,冲突示例会忽略冲突;请参见Damien B对在Java中对 any
类的所有实例施加总排序的答案,以了解对哈希码的故障保护排序)
问题答案:
问题是,当您拥有无法比拟的元素时,您需要退回到比比较哈希码更聪明的地方。例如,给定部分顺序{a <b,c
<d},哈希码可以满足h(d)<h(b)<h(c)<h(a),这意味着a <b < c <d < a( 粗体
表示用哈希码打断领带),这将导致a出现问题TreeMap
。
通常,除了事先对密钥进行拓扑排序之外,您可能不需要做任何事情,因此欢迎您提供部分感兴趣的部分的详细信息。