如何实现java.util.Comparator根据部分顺序关系对元素进行排序?
java.util.Comparator
例如,给定的部分顺序关系 一个 ≺ Ç , b ≺ Ç ; a 和 b 的顺序不确定。
由于Comparator需要总排序,因此实现对那些未定义但一致的部分排序的元素进行排序。
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)
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。
通常,除了事先对密钥进行拓扑排序之外,您可能不需要做任何事情,因此欢迎您提供部分感兴趣的部分的详细信息。