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

Question

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

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

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

Благодаря

Answer 1

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

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

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

EDIT

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

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

Answer 2

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

• • А.А.
  • AB

Когда сцеплены, это становится "AAAB". Контраст со следующим деревом:

• • AAA
  • B

разные, но хэш конкатенации будет то же самое.