Как создать дайджест SHA1 для дерева объектов?

Question

Допустим, у меня есть дерево объектов, каждый из которых имеет строковое представление. Я хочу создать дайджест SHA1 для всего дерева.

Самый простой способ - это рекурсивно пройтись по каждому узлу дерева. Для каждого узла я бы конкатенировал (в виде простых строк) дайджесты всех дочерних элементов SHA1, добавил строковое представление данного узла в эту объединенную строку и сделал для нее SHA1. Это будет дайджест SHA1 данного узла.

Вопрос в том, будет ли этот дайджест таким же "хорошим", как если бы я конкатенировал строковое представление дочерних узлов, а не дайджесты дочерних узлов?

Спасибо

Answer 1

Это было бы лучше, чем хэширование конкатенации детей. Рассмотрим следующее дерево:

• A
  • AA
  • AB

При объединении это становится "AAAB". Контраст со следующим деревом:

• A
  • AAA
  • B

По-другому, но хэш конкатенации будет таким же.

Answer 2

Предположим, что вы можете выбрать символ Unicode, который никогда не разрешен в метке узла.

Затем вы можете использовать классы потокового API (например, Java MessageDigest) для подачи всех меток в древовидном порядке, вставляя зарезервированный символ-разделитель между ними.

В конце у вас есть один сравнительно компактный дайджест, не оплачивая дополнительный уровень расчетов SHA.

EDIT

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

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