Как правильно реализовать equals (), hashCode () для дерева в Java?

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);
    }
}

Как вы можете видеть из моей реализации,Я использую только два поля: «данные» и «дети».Соответственно, мой вопрос заключается в том, правильно ли я реализовал методы equals / hashCode?Если не так, то, пожалуйста, покажите как.

Answer 1

Соответственно, мой вопрос, правильно ли я реализовал методы equals / hashCode?

Прежде всего: "что правильно?" ... можно задаться вопросом, почему дерево должно реализовывать equals() и hashCode() в первую очередь. Особенно сложен hashCode(): смысл этого метода (главным образом) в том, что вы можете сохранить соответствующий объект в HashMap / HashSet. Но это поднимает большой красный флаг: оба этих класса не любят, когда hashCode() возвращает разные значения с течением времени. И это именно то, что будет делать ваш код: каждый раз, когда вы меняете свое дерево (добавляя / удаляя узел), hashCode() будет давать другой результат.

Итак, мы могли бы взглянуть на то, что делают стандартные библиотеки: и там мы находим JTree ..., который не реализует оба метода! С другой стороны, когда мы смотрим в сторону AbstractSet (который является базовым классом для TreeSet), мы обнаруживаем, что оба метода реализованы и включают члены. Так что оба пути кажутся верными.

Возвращаясь к вопросу: это действительно зависит от того, как вы хотите , чтобы эти два метода работали. Одинаково ли два дерева, если они имеют одинаковое содержание (имеется в виду: имеет ли значение порядок детей)?

Короче говоря: если вы хотите убедиться, что все данные равны и что все дочерние элементы равны и в том же порядке, то ваша реализация кажется правильной.

И да, это ограничение для проверки только этих двух атрибутов имеет большой смысл: когда вы включаете родительскую ссылку, вы сразу получаете рекурсию, которая не может быть нарушена.

Наконец: вы пометили этот вопрос JUnit. Это подразумевает, что вы подумаете о написании тестов для своего производственного кода. Тогда эти тесты должны ответить на ваш вопрос. Значение: одним из подходов будет то, что вы садитесь и определяете контракт для этих двух методов. И затем вы создаете несколько тестовых случаев, которые проверяют все аспекты этих контрактов. И тогда ваши контрольные примеры сообщают вам, соответствует ли ваш производственный код вашему контракту.

Я думаю, что это ключевой момент: нет универсального правила, которое говорит нам, если / как реализовать equals() и hashCode() для класса Tree. Вы должны изучить ваши требования, если / как это сделать. Затем вы выводите тесты из этих знаний, которые затем применяете для проверки соответствия данной реализации требованиям / контракту.