11

假设我需要TreeSet使用一些域逻辑排序的元素。按照这种逻辑,一些不相等的元素的顺序无关紧要,因此 compare 方法可以返回 0,但在这种情况下,我无法将它们放入TreeSet.

所以,问题:像这样的代码我会有什么缺点:

class Foo implements Comparable<Foo>{}
new TreeSet<Foo>(new Comparator<Foo>(){
    @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<Foo>(new Comparator<Foo>(){
    @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()我不需要稳定排序更好吗?

4

11 回答 11

9

虽然这可能有效,但远非最佳实践。

来自SortedSet 文档

请注意,如果有序集合要正确实现 Set 接口,则由有序集合维护的排序(无论是否提供显式比较器)必须与 equals 一致。(请参阅Comparable接口或Comparator接口以了解与等于一致的精确定义。)这是因为 Set 接口是根据等于操作定义的,但排序集使用其 compareTo(或比较)方法执行所有元素比较,因此从排序集的角度来看,此方法认为相等的两个元素是相等的。一个有序集合的行为是明确定义的,即使它的排序与equals不一致;它只是不遵守 Set 接口的一般约定。

对于实现的对象,Comparable方法和.equals()hashcode()compareTo()


恐怕 aSortedSet不是您想要的,番石榴也不MultiSet够用(因为它不会让您独立检索多个相等的项目)。我认为你需要的是一个SortedList. 我所知道的没有这样的野兽(可能在 commons-collections 中,但这些有点在遗留方面),所以我使用 Guava 的 ForwardingList 作为基类为您实现了一个。简而言之:这个 List 将几乎所有东西都委托给ArrayList它在内部使用的一个,但它Collections.binarySearch()在它的add()方法中使用它来找到正确的插入位置,并且它UnsupportedOperationException在所有可选方法上抛出一个在给定位置添加或设置值的ListListIterator接口。

构造函数与 的构造函数相同ArrayList,但对于它们中的每一个,还有一个带有自定义的第二个版本Comparator。如果你不使用自定义的 Comparator,你的列表元素需要实现Comparable,否则RuntimeException排序时会出现 s。

public class SortedArrayList<E> extends ForwardingList<E> implements
    RandomAccess{

    private final class ListIteratorImpl extends ForwardingListIterator<E>{
        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<E> delegate(){return inner.listIterator(start);};

    }

    private Comparator<? super E> comparator;

    private List<E> inner;

    public SortedArrayList(){this(null, null, null);}

    @SuppressWarnings("unchecked")
    private SortedArrayList(
        final List<E> 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<E>(values)
                      : new ArrayList<E>()
                   )
                : 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<E>(initialCapacity), null, null);
    }

    public SortedArrayList(final int initialCapacity,
        final Comparator<? super E> comparator){
        this(new ArrayList<E>(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<E> delegate(){ return inner; }

    @Override
    public List<E> subList(final int fromIndex, final int toIndex){
        return new SortedArrayList<E>(
            inner.subList(fromIndex, toIndex),
            null,
            comparator
        );
    }

    @Override
    public ListIterator<E> listIterator(){ return new ListIteratorImpl(0); }

    @Override
    public ListIterator<E> listIterator(final int index){
        return new ListIteratorImpl(index);
    }

    @Override
    public E set(int i, E e){ throw new UnsupportedOperationException(); }

}
于 2010-12-03T09:52:30.070 回答
2

hashcode()方法不保证任何less thanor greater thancompare()并且equals()应该产生相同的含义,但它不是必需的。

据我从您令人困惑的代码中可以理解(无意冒犯:)),您想将重复项添加到TreeSet. 出于这个原因,你想出了这个实现。这就是原因,你不能把它们放在文档中TreeSet,引用文档,

一个集合的行为是明确定义的,即使它的顺序与equals不一致;它只是不遵守 Set 接口的一般约定。

所以,你需要用你的equals()方法做一些事情,所以它永远不会返回真正的东西。最好的实现是,

public boolean equals(Object o) {
    return false;
}

顺便说一句,如果我的理解是正确的,为什么不List改用它并对其进行排序。

于 2010-12-03T09:51:40.490 回答
2

当心:即使是两个 Foos f1,你也可以f2得到!这意味着您将无法使用您的方法获得稳定的排序。f1 != f2f1.hashCode() == f2.hashCode()compare

于 2010-12-03T09:58:32.083 回答
2

Java中没有规则说两个对象的哈希码必须不同,因为它们不相等(因此o1.hashCode() - o2.hashCode()可以0在您的情况下返回)。

的行为也equals() 应该与 的结果一致compareTo()。这不是必须的,但如果您不能保持这一点,则表明您的设计存在很大缺陷。

我强烈建议查看对象的其他字段并使用其中一些来扩展您的比较,以便您获得!= 0objects are 的值equals() == false

于 2010-12-03T09:59:34.537 回答
1

有两点可能相关,其中一种情况下的返回值显示为 -1,这取决于函数参数变量或相关使用国家/地区是否允许负值,以及您使用的方法是否为允许。有标准的数据排列方法,如选择器或选择排序,如果您的工作场所没有副本,通常可以从国家权威机构获得论文描述或代码。使用大于或小于之类的比较可以加快代码速度,并通过隐含的直通到后面的脚本或代码避免使用直接比较相等性。

于 2010-12-08T15:06:07.583 回答
1

是的,正如上面其他人所说,在这里使用 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;
}
于 2010-12-03T10:19:55.060 回答
1

这里有几个问题:

  • 哈希码通常不是唯一的,特别System.identityHashCode是在模糊的现代 JVM 上不会是唯一的。

  • 这不是稳定性的问题。我们正在对数组进行排序,但是创建了一个树结构。哈希码冲突将导致compare返回零,这TreeSet意味着一个对象获胜而另一个被丢弃 - 它不会降级为链接列表(线索名称中有“Set”)。

  • 从另一个哈希码中减去一个哈希码通常会出现整数溢出问题。这意味着比较不会是传递的(即它被破坏了)。幸运的是,在 Sun/Oracle 实现中,System.identityHashCode总是返回正值。这意味着广泛的测试可能不会发现这种特定类型的错误。

我不相信有一个很好的方法来实现这一点TreeSet

于 2010-12-03T12:29:43.753 回答
1

非常有趣的问题。据我了解,您的问题是重复元素。

我认为如果 o1.equals(o2) 它们的哈希码也可能相等。这取决于 Foo 类中 hashCode() 的实现。所以,我建议你改用 System.identityHashCode(x) 。

于 2010-12-03T09:52:14.923 回答
1

您有一个Foo可比较的类,但想在TreeSet<Foo>结构中使用不同的排序。那么你的想法就是正确的方法。使用该构造函数来“否决” Foo.

于 2010-12-03T09:54:55.217 回答
1
int res = o1.compareTo(o2);

if(res == 0 || !o1.equals(o2)){
    return o1.hashCode() - o2.hashCode();
}

可能会有问题,因为如果 2 个对象相等(即在您的 中res == 0),那么这 2 个对象返回相同的哈希码。哈希码对每个对象都不是唯一的。


编辑@Stas,System.identityHashCode(Object x);仍然不会帮助你。原因在 javadoc 上有描述:

为给定对象返回与默认方法返回的相同hashCode()的哈希码,无论给定对象的类是否覆盖hashCode()。空引用的哈希码为零。

于 2010-12-03T09:58:19.430 回答
1

如果您对任何两个给定元素没有特定的预期顺序,但仍想认为它们不相等,那么无论如何您都必须返回一些指定的顺序。

正如其他人发布的那样,hashCode()这不是一个好的候选者,因为hashCode()两个元素的值很容易相等。System.identityHashCode()可能是更好的选择,但仍然不完美,因为 evenidentityHashCode()也不保证唯一值

Guava arbitrary()Ordering实现了Comparatorusing System.identityHashCode()

于 2010-12-03T10:07:43.223 回答