2

それぞれが文字列表現を持つオブジェクトのツリーがあるとしましょう。ツリー全体で SHA1 ダイジェストを作成したいと考えています。

最も簡単な方法は、ツリーの各ノードを再帰的に調べることです。ノードごとに、すべての子の SHA1 ダイジェストを (単純な文字列として) 連結し、指定されたノードの文字列表現をこの連結された文字列に追加し、それに SHA1 を実行します。これは、特定のノードの SHA1 ダイジェストになります。

問題は、子ノードのダイジェストではなく、子ノードの文字列表現を連結した場合と同じように、このダイジェストが「良い」ものになるかどうかです。

ありがとう

4

2 に答える 2

2

これは、子の連結をハッシュするよりも優れています。次のツリーを検討してください。

  • あ
    • AA
    • AB

連結すると「AAAB」になります。次のツリーと対比してください。

  • あ
    • AAA
    • B

異なりますが、連結のハッシュは同じになります。

于 2010-05-27T14:20:13.340 に答える
1

ノードのラベルで許可されていない Unicode 文字を選択できるとします。

次に、ストリーム API (Java MessageDigest など) クラスを使用して、予約済みの区切り文字を間に挿入して、すべてのラベルをツリー順にフィードできます。

最後に、余分なレベルの SHA 計算に料金を支払うことなく、1 つの比較的コンパクトなダイジェストが得られます。

編集

上記のスキームはまったく正しくありませんが、ツリーの構造をエンコードしない限り、元の質問でもありません。コードは、トラバーサル順序よりも強力な各ノードのある種の ID を構築し、それをノードのハッシュ入力に含める必要があります。これにより、形状が異なるが同じラベルを持つツリーが同じようにハッシュされなくなります。

答えの元のスキームは、ツリーの順序が重要であるが正確な構造が重要でない場合に機能します。

于 2010-05-27T14:36:52.100 に答える