1. 概要

この記事では、ツリー構造のhash関数を作成する方法について説明します。

まず、問題と、2つのツリー構造が異なるかどうかを判断する方法を定義します。 次に、それを説明するための例を示します。 最後に、この問題を解決するためのアプローチを示し、特定の制約の下でハッシュ関数をカスタマイズするための追加のフォローアップアイデアを提供します。

2. 問題の定義

ノードとエッジのツリー構造があります。 与えられたツリー構造を表すハッシュコードを取得したいと思います。 これを使用して、任意の2つのツリー構造を一定時間で比較できます。

ツリーはノードとエッジの連結グラフであり、自己ループがなく、2つのエッジが同じノードのペアを接続していないことを思い出してください。

理解を深めるために例を見てみましょう。

次の3つのツリー構造が与えられます。

 

これらの木のハッシュ値を計算した後、赤、青、緑の木のハッシュをそれぞれ表す値、、が得られる可能性があります。

ご覧のとおり、赤と緑の木はまったく同じように見えるため、ハッシュ値は同じです。 一方、青いものは形が違うので違う。

3. ハッシュツリーアプローチ

このアプローチの主なアイデアは、子のハッシュ値に応じて各ノードのハッシュを構築することです。 ルートノードのハッシュを取得すると、ツリー全体のハッシュを表します。

DFS トラバーサルを使用して、指定されたツリーに飛び込みます。 リーフノードに到達した瞬間に、その単一ノードのハッシュをゼロとして返します。

次に、DFSトラバーサルに戻ると、子のハッシュ値のシーケンスに対して任意のハッシュアルゴリズムを使用して、現在のノードのハッシュを取得できます。 このアプローチでは、次の式を使用して、長さのシーケンスのハッシュを取得します。

   

ここで、およびは事前定義された定数値です。 これらの値を変更して、別のハッシュ値を取得できます。

最後に、ルートノードのハッシュを取得すると、ツリー全体のハッシュを表します。 その理由は、ツリー内の各ノードのハッシュを構築するために、そのサブツリー内のすべてのノードのハッシュ値を使用したためです。

3.1. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、をルートとするサブツリーのハッシュを返す関数を定義します。 この関数には、ハッシュするサブツリーのルートを表す1つのパラメーターがあります。

まず、をルートとする現在のサブツリーのハッシュを格納するを宣言します。 次に、現在のノードの子を反復処理し、各子のハッシュ値を取得します。

3番目に、次の式を使用して、子のハッシュを使用してサブツリーのハッシュ値を取得します。

   

最後に、はをルートとするツリー全体のハッシュを返します。

3.2. 複雑さ

このアルゴリズムの時間計算量はです。ここで、は指定されたツリー内のノードの数です。 この複雑さの理由は、DFSトラバーサルの複雑さと同じです。これは、指定されたツリーの各ノードと各エッジを1回だけ反復するためです。

4. ファローアップ

ツリー構造が与えられ、そのハッシュを取得したいとしますが、子の順序は重要ではありません。 例を見てみましょう：

 

ご覧のとおり、ノードの順序を入れ替えると、赤いツリーでは緑のツリーと同じになります。 したがって、赤と緑の木のハッシュは同じである必要があります。 一方、青いツリーの子の順序を変更して他の2つのツリーのいずれかに等しくすることができるような一連の操作がないため、青いツリーは他のツリーのいずれとも等しくありません。

このアプローチでは、前のアプローチと同じアイデアを使用しますが、子の順序以降、現在のノードのハッシュを取得する前に、各ノードの子のハッシュ値をsortします。関係ない。

前のアプローチで行ったようにDFSトラバーサルを使用して、現在のノードの子のハッシュ値を取得します。 ただし、子のハッシュのシーケンスにハッシュアルゴリズムを適用する前に、各子の初期位置を無視するようにそのシーケンスを並べ替えます。 次に、ソートされたシーケンスに任意のハッシュアルゴリズムを適用して、子の順序に関係なく、現在のノードのハッシュを取得します。

最後に、指定されたツリーのハッシュは、そのツリーのルートのハッシュになります。

4.1. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、をルートとするサブツリーのハッシュを返す前のアプローチと同じ関数を定義します。 この関数には、ハッシュするサブツリーのルートを表す1つのパラメーターがあります。

まず、現在のノードの子のハッシュ値を格納するという空のリストを宣言します。 次に、現在のノードの子を反復処理し、それぞれのハッシュ値を取得してリストに追加します。

3番目に、現在のノードの子の初期位置を無視するようにリストを並べ替えます。 次に、任意のハッシュアルゴリズムを使用して、子のハッシュのシーケンスのハッシュを取得します。 この式を使用して、子のハッシュに応じて現在のノードのハッシュを取得しました。

   

最後に、をルートとするツリー全体のハッシュを返します。

4.2. 複雑さ

このアルゴリズムの複雑さはです。ここで、は指定されたツリー内のノードの数です。 この複雑さの理由は、ツリーの各ノードと各エッジを1回だけ反復するためです。

ただし、子の最初の順序は重要ではないため、ノードごとに、子のハッシュを昇順で並べ替えます。 この操作の複雑さは。

各ノードは1つのノードの子であることに注意してください。 したがって、1回だけ並べ替えに使用されます。

5. 結論

この記事では、ツリー構造のハッシュ関数を作成する方法を紹介しました。

まず、問題を説明する例を示しました。 次に、それを解決するためのアプローチを検討しました。 次に、子の順序に関係なく、ツリー構造のハッシュを取得するための追加のフォローアップを行いました。

最後に、実装について説明し、各アルゴリズムの時間計算量について説明しました。