如何在Java中正确实现树的equals()和hashCode()方法？

Question

我有一个树状结构，需要重写equals/hashCode方法，因为在单元测试中需要检查预期结果。

树类型结构的问题在于它们会递归地相互引用，尤其是父节点和子节点之间。

如果在equals/hashCode方法中使用了所有字段，就会出现循环引用的情况。问题在于如何正确地重写这些方法，以避免违反协议。

我将举个例子来说明我是如何实现的。

public class App {
    public static void main(String[] args) {
        Book book1 = new Book(1L, "The catcher in the rye");
        Book book2 = new Book(2L, "Rich Dad Poor Dad");

        BookTree bookTree1 = new BookTree(book1);
        BookTree bookTreeChild1 = new BookTree(book2);
        bookTree1.addChild(bookTreeChild1);

        BookTree bookTree2 = new BookTree(book1);
        BookTree bookTreeChild2 = new BookTree(book2);
        bookTree2.addChild(bookTreeChild2);

        if (!bookTree1.equals(bookTree2)) {
            throw new RuntimeException("Invalid override equals");
        }
    }
}

class Book {
    private Long id;
    private String name;

    public Book(Long id, String name) {
        this.id = id;
        this.name = name;
    }

    public Long getId() {
        return id;
    }

    public void setId(Long id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if (object == null || getClass() != object.getClass()) return false;
        Book book = (Book) object;
        return Objects.equals(id, book.id) &&
                Objects.equals(name, book.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

class Tree<T> {
    private List<Tree<T>> children = new ArrayList<>();
    private Tree<T> parent = null;
    private T data;

    public Tree(T data) {
        this.data = data;
    }

    public Tree(T data, Tree<T> parent) {
        this.data = data;
        parent.addChild(this);
    }

    public List<Tree<T>> getChildren() {
        return children;
    }

    public void addChild(Tree<T> child) {
        child.setParent(this);
        this.children.add(child);
    }

    public void addChild(T data) {
        Tree<T> newChild = new Tree<>(data);
        this.addChild(newChild);
    }

    public void removeChildren() {
        this.children = new ArrayList<>();
    }

    public void addChildren(List<Tree<T>> children) {
        for(Tree<T> t : children) {
            t.setParent(this);
        }
        this.children.addAll(children);
    }

    private void setParent(Tree<T> parent) {
        this.parent = parent;
    }

    public Tree<T> getParent() {
        return parent;
    }

    public T getData() {
        return this.data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    public boolean isLeaf() {
        return this.children.size() == 0;
    }

    public void removeParent() {
        this.parent = null;
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) return true;
        if (object == null || getClass() != object.getClass()) return false;
        Tree<?> tree = (Tree<?>) object;
        return Objects.equals(children, tree.children) &&
                Objects.equals(data, tree.data);
    }

    @Override
    public int hashCode() {
        return Objects.hash(children, data);
    }
}

class BookTree extends Tree<Book> {

    public BookTree(Book data) {
        super(data);
    }

    public BookTree(Book data, Tree<Book> parent) {
        super(data, parent);
    }
}

从我的实现中可以看出，我仅使用了两个字段：“data”和“children”。 因此，我的问题是我是否正确实现了equals/hashCode方法？ 如果不正确，请指出如何改正。

- FreeOnGoo

Answer 1

因此，我的问题是我是否正确实现了equals/hashCode方法？

首先，“什么是正确的？”...有人可能会想为什么树应该首先实现equals()和hashCode()方法。特别是hashCode()方法很棘手：该方法的重点（主要）是您可以将相应的对象存储在HashMap/HashSet中。但这引发了一个大大的警告信号：当hashCode()方法随时间返回不同的值时，这两个类都不喜欢它。而这正是您的代码将要做的事情：每次更改树（添加/删除节点）时，hashCode()方法都会给出不同的结果。

所以我们可以查看标准库的内容：在那里我们找到JTree...它没有实现这两种方法！另一方面，当我们看向AbstractSet（TreeSet的基类）时，我们发现这两种方法都被实现并包括成员。所以两种方式都是有效的。

回到问题：这真的取决于您想让这两种方法如何工作。当两个树具有完全相同的内容时，它们是否相等（意思是：子项的顺序是否重要）？

长话短说：假设您想确保所有数据相等，并且所有子项相等，并且按相同顺序排列，则您的实现似乎是正确的。

是的，只检查这两个属性的限制非常有意义：当您包含父链接时，您立即陷入无法打破的递归中。

最后提醒一下：您在问题中标记了JUnit。这意味着您考虑为生产代码编写测试。那么，这些测试应该回答您的问题。意思是：一种方法是您坐下来定义这两种方法的合同。然后，您创建多个测试用例，验证这些合同的所有方面。然后您的测试用例告诉您，您的生产代码是否符合您的合同。

我认为这是关键点：没有通用规则告诉我们如何实现Tree类的equals()和hashCode()。您必须查看您的要求以确定如何实现。然后，您从该知识中派生出测试，然后将其应用以验证给定的实现是否符合要求/合同。

- GhostCat

---

这个答案强调了Java的OO实现以及OO本身存在的一些根本性问题。“这两个类都不喜欢hashCode()随时间变化而返回不同的值”。在典型的OO设计中，无法避免随时间的变化...如果一个类不喜欢它...那就是一个大问题。我最近发现JTree不喜欢没有实现hashCode()和equals()，而且在DefaultMutableTreeNode中也没有实现。 “Mutable”意味着随时间的变化。JTree.getRowForPath没有hashCode()就无法工作。有这么多问题。 - Jason

上面提到的一些细节...JTree 使用 VariableHeightLayoutCache 来存储 TreePath 到 TreeStateNode 的映射。TreePath.hashCode 委托给树路径中的最后一个节点，即 TreeNode。许多实现使用 DefaultMutableTreeNode，它没有实现 hashCode（使用 Object.hashCode，它基于实例而不是对象属性的值或两个实例的逻辑相等性而变化）。因此，当查询它们的 JTree 时，具有相同逻辑值的两个 TreePath 将产生不同的结果。 - Jason

我知道这不是关于树本身的 hashCode 和 equals 的问题，但我认为这很相关，因为人们也不会预期在此处需要 hashCode。一般来说，最好重写 equals，因为这是一个基本操作，而默认实现是不够的。必须也重写 hashCode，以满足Java协议，即如果 equals 返回true，则 hashCode 值相等。所以我认为OP想要实现这些是可以的，但是，OP必须定义什么构成相等。 - Jason

Answer 2

我认为@GhostCat的回答中提出的“什么是正确的？”非常关键。我想重点关注这一部分。

可以认为OP中给出的示例是正确的。

我会把Tree类命名为TreeNode，我认为这是更合适的名称。那么问题就变成了，如果两个TreeNode具有相同的数据和相同的子节点但父节点不同，它们是否相等？这是OP的当前实现。这可以被认为是正确的。但是，如果要求一个TreeNode也拥有相同的父节点，则在比较两个树节点时，整个树必须相等。在这种情况下，比较两个树节点并没有真正意义，为什么不从根节点开始比较两棵树呢？我之所以说这个，是因为在树中比较两个节点并问问题“这两个子树是否相等，而不考虑父节点是否不同”是有价值的。因此，我认为OP的代码比要求父节点也相等更具灵活性。在这种情况下，parent属性用于方便导航而不是用于标识。您还可以想象一个TreeNode，其中没有parent属性，只有父节点知道其子节点。这将使数据完整性更易于维护（因为链接仅存储在父节点中），但导航更具挑战性）。

我倾向于将parent视为用于导航或仅从TreeNode（或Tree，如OP所称的类）中删除parent属性的方法。

- Jason