如何在 Java 中为 Tree 正确实现 equals(), hashCode()？

Question

我有一个树结构，我需要覆盖方法 equals/hashCode 因为我在单元测试中使用了预期结果的检查。

树型结构的问题在于它们递归地相互引用。特别是，parents 对应 children，反之亦然。

如果所有字段都用在方法中equals/hashCode，那么就会有一个循环。问题是如何正确覆盖 then 以不违反合同。

我将举例说明我是如何实现它的。

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 方法？如果错了，请说明方法。

Answer 1

Accordingly, my question is whether I implemented the methods equals/hashCode correctly?

首先："what is correct?" ...有人可能想知道为什么树应该首先实现 equals() 和 hashCode()。特别是 hashCode() 很棘手：该方法的要点（主要）是让您可以将相应的 object 存储在 HashMap/HashSet 中。但这引发了一个大危险信号：当 hashCode() returns 随着时间的推移出现不同的值时，这两个 class 都不喜欢它。这正是您的代码将要执行的操作：每次更改树（adding/removing 一个节点）时，hashCode() 都会给出不同的结果。

所以我们可以看看标准库做了什么：我们发现 JTree ... which doesn't implement both methods! On the other hand, when we look towards AbstractSet（这是 TreeSet 的基础 class），我们发现这两种方法都已实现并且包括成员。所以这两种方式似乎都是有效的。

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

长话短说：假设您要确保所有 data 都相等，并且所有 children 都是相等，并且顺序相同，那么您的实施似乎是正确的。

是的，限制只检查这两个属性很有意义：当您包含 parent link 时，您会立即得到进入无法破坏的递归。

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

我认为这是这里的关键点：没有通用规则告诉我们if/how 为树 class 实现 equals() 和 hashCode()。您必须查看您的要求 if/how 才能做到这一点。然后你从这些知识中得到测试，然后你应用它来验证给定的实现是否满足 requirements/contract.

Answer 2

我认为@GhostCat 的回答是他们问“什么是正确的？”至关重要。我想重点关注这部分。

OP中给出的样本可以认为是正确的。

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

我赞成将 parent 用于导航或简单地从 TreeNode 中删除 parent 属性的方法（或 Tree 作为OP 调用 class).

如何在 Java 中为 Tree 正确实现 equals(), hashCode()？

How to correctly implement equals(), hashCode() for Tree in Java?

java

tree

equals

hashcode