如果密钥以与equals不一致的方式实现Comparable,那么Java 8的HashMap是否会出错？这是一个错误吗？

Question

我知道,自Java 8以来,如果HashMap有足够的哈希冲突,并且密钥实现Comparable,它将使用平衡树而不是bin的链表.但是,从我所看到的,Comparable接口并不需要说compareTo()是"一致equals()"(虽然它强烈推荐).

我错过了什么？如果密钥碰巧具有合规但非推荐的实现,则新实现似乎允许HashMap违反Map接口的要求Comparable.

以下JUnit测试在OpenJDK 8u72上公开此行为:

import static org.junit.Assert.*;

import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

class Foo
        implements Comparable<Foo> // Comment this out to fix the test case
{
    private final int bar;
    private final int baz;

    Foo(int bar, int baz) {
        this.bar = bar;
        this.baz = baz;
    }

    public boolean equals(Object obj) {
        // Note that this ignores 'baz'
        return obj instanceof Foo && bar == ((Foo) obj).bar;
    }

    public int hashCode() {
        return 0;
    }

    public int compareTo(Foo o) {
        // Inconsistent with equals(), but seems to obey the requirements of
        // Comparable<Foo>
        return Integer.compare(baz, o.baz);
    }
}

public class FooTest {
    @Test
    public void test() {
        Set<Foo> set = new HashSet<>();
        for (int i = 0; i < 128; ++i) {
            set.add(new Foo(i, 0));
        }

        // This fails if Foo implements Comparable<Foo>
        assertTrue(set.contains(new Foo(64, 1)));
    }
}

Answer 1

首先,让我们回顾一下equals和compareTo暗示的一致性:

(Comparable)

一类的自然顺序C被说成是与equals一致当且仅当e1.compareTo(e2) == 0具有相同的布尔值的e1.equals(e2)每一个e1和e2阶级的C.

因此,自然排序与equals不一致的一种情况是e1.compareTo(e2)尽管e1.equals(e2)返回但可能返回零的排序false.一个例子是不区分大小写的排序与区分大小写的相等.另一个例子是BigDecimal具有自然顺序,其中new BigDecimal("1.0").compareTo(BigDecimal.ONE)返回零但new BigDecimal("1.0").equals(BigDecimal.ONE)返回false.

请注意,新HashMap实现处理这些情况.自然排序仅有助于找到候选者,但是如果equals方法返回,则候选者将仅被视为相等true.这意味着当你有很多具有相同哈希码的键并且根据它们的自然顺序而不是等于equals时,你最终会在这些键之间进行线性搜索,就像在旧的实现中一样.

相比之下,你的例子完全不同.compareTo尽管equals测试将返回,但您的实现可能会告诉两个对象不相等true.BigDecimal我知道,这绝不会与自然排序的任何其他实际例子一起发生,这些例子与equals不一致.

当前实现不支持您的情况,但正如您可能已经注意到的那样,如果对象也具有相同的哈希代码,则仍然只会中断.我怀疑这种情况是否具有实际意义.到目前为止我看到的所有例子都是在了解了新的HashMap实现后才构建的.

Answer 2

它不是IMO中的任何错误,因为代码的行为与实现者的预期相同 - 但这是一个不寻常的Comparable实现的已知结果.从Comparable文档:

强烈建议(尽管不要求)自然排序与之一致equals.这是因为没有显式比较器的有序集(和有序映射)在与自然顺序不一致的元素(或键)一起使用时表现得"奇怪" equals.特别地,这样的有序集(或有序映射)违反了集合(或映射)的一般契约,其根据该equals方法定义.

现在,虽然这不是正常意义上的排序集或地图,但与问题有明确的关系.

我同意这是一个可能的问题,而且是一个非常微妙的问题,特别是因为它很难在简单的情况下重现.我会更新你的文档,以便非常注意你的类Comparable以一种与之不一致的方式实现的事实equals,并特别将其称为潜在问题.