如何确保equals()和hashCode()同步？

Question

我们正在编写一个需要非常复杂逻辑计算equals()和hashCode()的类。其大致如下：

@Getters @Setters @FieldDefaults(level=AccessLevel.PRIVATE)
public class ExternalData {
  TypeEnum type;
  String data;
  List<ExternalData> children;
} 

我们不构建这些对象，它们是从外部复杂系统的XML反序列化而来。根据类型不同，可能会忽略数据，或者处理带有子节点的数据，或者处理没有子节点的数据，每种节点类型的数据比较取决于该节点类型。我们创建了equals()和hashCode()方法以反映所有这些规则，但最近遇到了一个问题，hashCode与equals不同步导致相等的对象被添加两次到HashSet中。我认为HashMap（以及Java中的HashSet）是这样实现的：https://en.wikipedia.org/wiki/Hash_table。实现首先基于hashCode将对象放入桶中，然后对于每个桶检查equals。在不幸的情况下，即两个相等的对象将进入不同的桶中，它们永远不会通过equals()进行比较。在这里，“不同步”意味着它们进入了不同的桶中。如何确保equals和hashCode不失同步？

编辑：此问题与Java中覆盖equals和hashCode时应考虑哪些问题？不同。那里他们询问通用指导方针，接受的答案不适用于我的情况。他们说“使equals和hashCode一致”，这里我正在询问如何确切地做到这一点。

- Artem

---

可能是属性测试吧。没有简单的规则，你必须进行测试。 - Paul Hicks

基本上是代码审查。在某些情况下，您可能可以进行静态分析，以检查equals和hashCode是否使用相同的字段，但是边角情况可能会压倒这样的系统。您还可以使用像Lombok这样的项目为您生成它们。 - yshavit

在可能的情况下，使用自动生成等工具来帮助您。例如，查看Immutables库-为您生成hashCode/equals。 - Oliver Charlesworth

@Robert，那个主意很糟糕。hashCode 的官方文档表明，不相等的对象可能具有相同的 hashCode。 - dorukayhan

是的，相等的对象必须具有相同的哈希码，但是不相等的对象也可能具有相同的哈希码，这就是dorukayhan所说的。考虑 Long 类。有2^64个可能的 Long 对象，但只有2^32个可能的哈希码。根据鸽笼原理，许多不相等的 Long 对象必须具有相同的哈希码。 - David Conrad

Answer 1

Guava testlib库有一个名为EqualsTester的类，可以用来编写关于equals()和hashCode()实现的测试。

添加测试既可以帮助您确保代码现在是正确的，也可以确保在将来修改代码时它仍然是正确的。

- Daniel Pryden

---

@T.J.Crowder，我昨天喜欢了你的答案，那个评论是什么？ :) - Artem

@T.J.Crowder 我认为这实际上是一个好主意，也可能是唯一可以保证它们完全相同的100％方法，而不依赖于人们编写更多测试并在添加功能时添加2个位置。我们的系统是离线的（在某种意义上），对内存限制没有硬性要求，但对一致性有要求。我们实际上计划让公共代码返回hashCode和布尔值对（如果提供了第二个参数）。所以我很乐意接受你最初的答案 :) - Artem

@Artem：我对答案不满意，正如Daniel指出的那样，但现在我已经更新了它，我很满意，并将其恢复了。 （我还删除了上面的评论，因为它们与Daniel在这里的回答实际上没有任何关系。） - T.J. Crowder

Answer 2

考虑的一个选项可能是代码生成。基本上，您编写了一个需要进行比较的事物列表，并拥有一个程序来生成等于方法和哈希码方法。由于两种方法都是从相同的比较列表生成的，它们不应该失去同步（当然，前提是个别元素没有）。

- plugwash

Answer 3

如果遍历算法足够复杂，你想要避免重复，可以将算法隔离成一个方法，使其既可以被equals使用，也可以被hashCode使用。

我看到两个选项，它们（通常情况下）在普适性和效率之间进行权衡。

广泛适用

第一种选择是编写一个相当通用的遍历方法，接受一个函数式接口，并在遍历的每个阶段回调该接口，因此你可以传递一个lambda表达式或实例进入其中，包含你想要在遍历时执行的实际逻辑；访问者模式。该接口需要有一种方式来表示“停止遍历”（例如，当equals知道答案是“不相等”时可以退出）。从概念上来说，它可能会像这样：

private boolean traverse(Visitor visitor) {
    while (/*still traversing*/) {
        if (!visitor.visitNode(thisNode)) {
            return false;
        }
        /*determine next node to visit and whether done*/
    }
    return true;
}

然后equals和hashCode使用它来实现相等性检查或哈希码构建，而无需知道遍历算法。

我选择让方法返回一个标志，表示遍历是否提前结束，但这只是一个设计细节。在您的情况下，您可能不返回任何内容，或者返回this以进行链接，具体取决于您的情况。

问题在于，使用它意味着分配一个实例（或使用lambda，但那么您可能仍然需要分配一些东西来更新lambda以跟踪其正在执行的操作），并进行大量的方法调用。也许在您的情况下这很好；也许它会严重影响性能，因为您的应用程序需要经常使用equals。 :-)

具体而高效

...因此，您可能希望编写一些特定于此情况的代码，编写一些已经内置了equals和hashCode逻辑的代码。它在被hashCode使用时返回哈希码，或者对于equals返回一个标志值(0 = 不相等, !0 = 相等)。虽然不再常用，但它避免了创建访问者实例以传递/lamda开销/调用开销。从概念上来说，这可能看起来像这样：

private int equalsHashCodeWorker(Object other, boolean forEquals) {
    int code = 0;

    if (forEquals && other == null) {
        // not equal
    } else {
        while (/*still traversing*/) {
            /*update `code` depending on the results for this node*/
        }
    }

    return code;    
}

再次强调，具体实现会根据你的情况以及样式指南等而有所不同。一些人会让other参数兼具两个目的(标志和“其他”对象)，通过让equals方法处理other == null的情况并只在有非null对象时才调用该工作线程。我更喜欢避免这种参数含义重复的情况，但你也可以经常看到这种做法。

测试

无论你选择哪种方式，如果你在一个有测试文化的公司中，自然而然地你会想为已经失败的复杂案例以及其他可能出现故障的案例构建测试。

hashCode的副笔记

不考虑上述情况，如果你期望hashCode被频繁调用，你可以考虑将结果缓存到实例字段中。如果你使用的对象是可变的（而且看起来确实如此），每当修改对象状态时就需要使存储的哈希码失效。这样，如果对象没有改变，在后续调用hashCode时就不必重新遍历。但是，如果你忘记在任一修改器方法中使哈希码失效......

- T.J. Crowder

---

对我来说这并不太有意义：equals()方法需要一个第二个对象进行比较，但是hashCode()方法不需要。因此，我没有看到任何简单的方法可以同时使用相同的代码路径。而且我绝对不建议在equals()或者特别是hashCode()中进行任何分配操作，因为那些方法将被从你无法控制的代码中调用，通常在热点路径上。例如，将一个不相关的对象添加到包含你的对象的HashMap中可能会导致你的对象的hashCode()被调用--如果这种情况每秒发生许多次，那么就会产生很大的垃圾回收压力。 - Daniel Pryden

@DanielPryden HashMap不会缓存哈希码吗？无论是否缓存，如果它被调整大小，它几乎肯定只会查看已经在表中的对象的哈希值，而这并不会在每次插入时发生。 - Random832

@DanielPryden：两点都非常好。我已经更新了答案。 - T.J. Crowder

Answer 4

如果 a.equals(b)，那么就意味着 a.hashcode() == b.hashcode()。

然而，要小心。 !a.equals(b) 不 意味着 a.hashcode() != b.hashcode()。

这仅仅是因为哈希冲突可能会根据您的算法和大量因素成为一个严重问题。通常情况下，如果两个对象相等，则它们的哈希码将始终相等。但是，您不能仅通过比较哈希码来确定两个对象是否相等，因为 a.hashode() == b.hashcode() 也 不 意味着 a.equals(b)。

- Will Sherwood