时间戳

首页 > 解决方案 > 如何在 Java 中正确实现 Tree 的 equals()、hashCode()？

java - 如何在 Java 中正确实现 Tree 的 equals()、hashCode()？

问题描述

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

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

如果所有字段都用在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？如果错了，请说明如何。

标签： javatreeequalshashcode

解决方案

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

首先：“什么是正确的？” ...人们可能想知道为什么一棵树应该equals()首先实现hashCode()。尤其hashCode()是棘手：该方法的重点是（主要）因此您可以将相应的对象存储在 HashMap/HashSet 中。但这引发了一个很大的危险信号：当随着时间的推移返回不同的值时，这两个类都不喜欢它。hashCode()这正是您的代码将要做的事情：每次更改树（添加/删除节点）时，hashCode()都会产生不同的结果。

所以我们可以看看标准库做了什么：在那里我们发现JTree ...它没有实现这两种方法！另一方面，当我们查看AbstractSet（它是 TreeSet 的基类）时，我们发现这两种方法都已实现并包含成员。所以这两种方式似乎都是有效的。

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

长话短说：假设您要确保所有数据都是平等的，并且所有孩子都是平等的，并且顺序相同，那么您的实现似乎是正确的。

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

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

我认为这是这里的关键点：没有通用规则告诉我们是否/如何实现equals()以及hashCode()用于 Tree 类。如果/如何做到这一点，您必须研究您的要求。然后您从该知识中派生测试，然后您应用这些测试以验证给定的实现是否满足要求/合同。

推荐阅读