比较器和等号()
假设我需要使用某些域逻辑排序的元素的TreeSet
。 通过这个逻辑,一些元素的顺序并不重要,因此比较方法可以返回0,但在这种情况下我不能将它们放在TreeSet
。
所以,问:我将从这样的代码中得到什么缺点:
class Foo implements Comparable{} new TreeSet(new Comparator(){ @Override public int compare(Foo o1, Foo o2) { int res = o1.compareTo(o2); if(res == 0 || !o1.equals(o2)){ return o1.hashCode() - o2.hashCode(); } return res; } });
更新 :
好。 如果它应该始终是方法equals()
, hashcode()
和compareTo()
之间的一致性,如@SPFloyd – seanizer和其他人说。 如果我将删除Comparable
接口并在Comparator
移动此逻辑(我可以在没有破坏封装的情况下完成它)会更好甚至更好吗? 所以它将是:
class Foo{} new TreeSet(new Comparator(){ @Override public int compare(Foo o1, Foo o2) { //some logic start if(strictliBigger(o1, o2)){ return 1;} if(strictliBigger(o2, o1)){ return -1;} //some logic end if(res == 0 || !o1.equals(o2)){ return o1.hashCode() - o2.hashCode(); } return res; } });
更新2 :
如果我不需要稳定排序, System.identityHashCode(x)
会比hashCode()
好吗?
虽然这可能有效,但它远非最佳实践。
来自SortedSet文档 :
请注意, 如果有序集合要正确实现Set接口,则由有序集合维护的排序(无论是否提供显式比较器) 必须与equals一致 。 (有关与equals一致的精确定义,请参阅Comparable接口或Comparator接口。)这是因为Set接口是根据equals操作定义的,但是有序集使用compareTo(或compare)方法执行所有元素比较因此,从排序集的角度来看,这种方法被认为相等的两个元素是相等的。 即使排序与equals不一致,排序集的行为也是明确定义的; 它只是不遵守Set接口的一般合同。
对于实现Comparable
对象, equals()
, hashcode()
和compareTo()
方法之间应始终保持一致。
我担心SortedSet
不是你想要的,Guava MultiSet
也不够(因为它不会让你独立检索多个相同的项目)。 我认为你需要的是一个SortedList
。 我知道没有这样的野兽(可能在公共集合中,但是那些在传统方面有点),所以我使用Guava的ForwardingList作为基类为你实现了一个。 简而言之:此List几乎将所有内容委托给它在内部使用的ArrayList
,但它在其add()
方法中使用Collections.binarySearch()
来查找正确的插入位置,并在List
和ListIterator
接口的所有可选方法上抛出UnsupportedOperationException
在给定位置添加或设置值。
构造函数与ArrayList
的构造函数相同,但是对于每个构造函数,还有一个带有自定义Comparator
的第二个版本。 如果不使用自定义Comparator,则列表元素需要实现Comparable
或RuntimeException
将在排序期间发生。
public class SortedArrayList extends ForwardingList implements RandomAccess{ private final class ListIteratorImpl extends ForwardingListIterator { private final int start; public ListIteratorImpl(final int start){ this.start = start; } @Override public void set(E element){throw new UnsupportedOperationException();} @Override public void add(E element){throw new UnsupportedOperationException();} @Override protected ListIterator delegate(){return inner.listIterator(start);}; } private Comparator super E> comparator; private List inner; public SortedArrayList(){this(null, null, null);} @SuppressWarnings("unchecked") private SortedArrayList( final List existing, final Collection extends E> values, final Comparator super E> comparator ){ this.comparator = (Comparator super E>) (comparator == null ? Ordering.natural() : comparator ); inner = ( existing == null ? (values == null ? new ArrayList (values) : new ArrayList () ) : existing; } public SortedArrayList(final Collection extends E> c){ this(null, c, null); } public SortedArrayList(final Collection extends E> c, final Comparator super E> comparator){ this(null, c, comparator); } public SortedArrayList(final Comparator super E> comparator){ this(null, null, comparator); } public SortedArrayList(final int initialCapacity){ this(new ArrayList (initialCapacity), null, null); } public SortedArrayList(final int initialCapacity, final Comparator super E> comparator){ this(new ArrayList (initialCapacity), null, comparator); } @Override public boolean add(final E e){ inner.add( Math.abs( Collections.binarySearch(inner, e, comparator) ) + 1, e ); return true; } @Override public void add(int i, E e){throw new UnsupportedOperationException();} @Override public boolean addAll(final Collection extends E> collection){ return standardAddAll(collection); } @Override public boolean addAll(int i, Collection extends E> es){ throw new UnsupportedOperationException(); } @Override protected List delegate(){ return inner; } @Override public List subList(final int fromIndex, final int toIndex){ return new SortedArrayList ( inner.subList(fromIndex, toIndex), null, comparator ); } @Override public ListIterator listIterator(){ return new ListIteratorImpl(0); } @Override public ListIterator listIterator(final int index){ return new ListIteratorImpl(index); } @Override public E set(int i, E e){ throw new UnsupportedOperationException(); } }
注意:即使是两个Foos f1
, f2
和f1 != f2
你也可以得到f1.hashCode() == f2.hashCode()
! 这意味着您不会使用compare
方法获得稳定的排序。
Java中没有规则说两个对象的哈希码必须是不同的,因为它们不相等(所以o1.hashCode() - o2.hashCode()
在你的情况下可以返回0
)。
此外, equals()
的行为应与compareTo()
的结果一致。 这不是必须的,但如果你不能保持这一点,它表明你的设计有一个很大的缺陷。
我强烈建议查看对象的其他字段,并使用其中一些来扩展比较,以便得到一个值!= 0
对象是equals() == false
。
hashcode()
方法不保证任何less than
或greater than
。 compare()
和equals()
应该产生相同的含义,但它不是必需的。
据我所知,你可以从令人困惑的代码中理解(没有违法的:)),你想要在TreeSet
添加重复项。 出于这个原因,你想出了这个实现。 这就是原因,你不能把它们放在TreeSet
,引用文档,
集合的行为即使其排序与equals不一致也是明确定义的; 它只是不遵守Set接口的一般合同。
所以,你需要用yor equals()
方法做一些事情,所以它永远不会返回真正的东西。 最好的实施方式是,
public boolean equals(Object o) { return false; }
顺便说一句,如果我理解正确,为什么不使用List
而是对它进行排序。
非常有趣的问题。 据我所知,你的问题是重复的元素。
我认为如果o1.equals(o2)他们的哈希码也可能相等。 它取决于你的Foo类中hashCode()的实现。 所以,我建议你改用System.identityHashCode(x)。
你有一个可比的Foo
类,但想在TreeSet
结构中使用不同的排序。 然后你的想法是正确的方法。 使用该构造函数“否决” Foo
的自然排序。
如果您对任何两个给定元素没有特定的预期排序,但仍希望将它们视为不相等,那么您必须返回一些指定的排序。
正如其他人发布的那样, hashCode()
不是一个好的候选者,因为两个元素的hashCode()
值很容易相等。 System.identityHashCode()
可能是更好的选择,但仍然不完美,因为即使identityHashCode()
也不保证唯一值
Guava的random arbitrary()
Ordering使用System.identityHashCode()
实现了一个Comparator
。
是的,正如其他人所说,hashCode()在这里使用并不安全。 但是如果你不关心o1.compareTo(o2)== 0等于对象的排序,你可以这样做:
public int compare(Foo o1, Foo o2) { int res = o1.compareTo(o2); if (res == 0 && !o1.equals(o2)) { return -1; } return res; }
int res = o1.compareTo(o2); if(res == 0 || !o1.equals(o2)){ return o1.hashCode() - o2.hashCode(); }
可能有问题,因为如果2个对象相等(即在你的res == 0
),那么这两个对象返回相同的哈希码。 哈希码对于每个对象都不是唯一的。
编辑 @Stas, System.identityHashCode(Object x);
仍然不会帮助你。 原因在javadoc上描述:
返回与默认方法
hashCode()
返回的给定对象相同的哈希码,无论给定对象的类是否覆盖hashCode()
。 空引用的哈希码为零。
这里有几个问题:
-
散列码通常不是唯一的,特别是
System.identityHashCode
在模糊的现代JVM上不是唯一的。 -
这不是稳定性的问题。 我们正在对数组进行排序,但是创建了一个树结构。 哈希码冲突将导致
compare
返回零,对于TreeSet
意味着一个对象获胜而另一个被丢弃 – 它不会降级到链接列表(线索在名称中具有“设置”)。 -
通常存在整数溢出问题,从一个哈希代码中减去一个哈希代码。 这意味着比较不会传递(即它被破坏)。 幸运的是,在Sun / Oracle实现中,
System.identityHashCode
始终返回正值。 这意味着广泛的测试可能不会发现这种特殊的错误。
我不相信有一种使用TreeSet
实现这一目标的好方法。
两点可能是相关的,这些是一种情况下的返回显示为-1,这取决于函数参数变量或相关使用国家是否允许负值,以及您使用的方法是否为允许的。 有标准数据安排方法,如选择器或选择排序,如果副本不在您的工作场所,通常可以从国家机构获得纸质描述或代码。 使用大于或小于的比较可以加快代码速度并避免使用对后续脚本或代码的隐含穿透来直接比较相等性。