問題タブ [hashtree]

hash trees のウィキペディアの記事を見ていますが、それらの図に少し混乱しています。

リーフ ノードには、明らかに基になるデータのハッシュが含まれています。

ハッシュ ツリーのリーフ ノードは、非リーフ ノードとは異なりますか? 非リーフ ノードには、データのハッシュまたはハッシュのハッシュが含まれていますか?

この図を考えると：

これらHash 1のハッシュはどれですか?

1. Hash 1-0+Hash 1-1
2. Data block 002+Data block 003

それとも、ハッシュ ツリーはアプリケーション (rsync、P2P ネットワーク、Git など) によって根本的に異なりますか?

ユーザーをナビゲートするための動的ディレクトリを作成するロジックに取り組んでいます。

ユースケースでは、最大 50 個のノードが必要であり、最後の次数ノードには 50 個の葉が必要です (最後のエントリを除く)。

このケースは、50 x 50、50 x 50 x 50 などで適切に機能します。

ツリーが最小の深さを持ち、葉でも均等にバランスが取れているように、n = 50のようなn配列ツリーを作成するための標準的なデータ構造とロジックを提案できますか。

例のために。

6310 のリストがある場合、ノード 1 (2500) ノード 2 (2500) & ノード 3 (1310) があるため、レベル 1 には 3 つのノードしかなく、レベル 2 にはノードが 50 に等しいという不均衡が生じるため、配布は失敗します。

ここで、level1 も最初の 50 範囲を持ち、その後 level2 の分布を持つようにする必要があります。最後のノードは不均一に保つことができます。

AWS Glacierサービスについて知り、RESTAPIを介してファイルをアップロードするための小さなPythonアプリケーションを作成したいと思いました。必要なヘッダーを調べて、に遭遇しましx-amz-sha256-tree-hashた。ファイル全体のSHA-256ハッシュと、各1MBチャンクのすべてのハッシュの親のハッシュを計算する必要があります。これにより、次のツリーが作成されます。

（ここから撮影した画像）

私はすでに1MBのチャンクを読み取る関数と、そのハッシュをオンザフライで計算するクラスを作成しましたが、その後、完全に苦労しました。

私のアプリケーションでは、chunkデータを取得してメソッドでハッシュを計算し、__init__親と子（通常のツリーのように）を保持するというクラスを作成しました。ユーザーがファイルを開くと、これらのチャンクインスタンスはそれぞれのハッシュで適切に生成されます（この例では、7つのチャンクインスタンスになります）。

今、私は互いに関連している2つの大きな問題を抱えています。

1. このツリーを逆に構築するにはどうすればよいですか？基本的に、最下層の2つのチャンクインスタンスごとに新しいチャンクを作成し、それらの2つのハッシュに基づいてハッシュを計算する必要があります。しかし、私はその親をどこに保管しますか？親の子供たちと逆ツリーウォーキングをしますか？
2. それは奇数の子供たちとどのように機能しますか？各親レイヤーを通過するアルゴリズムがある場合、最後の（0.5 MB）チャンクを見逃します。

私はSOでこのトピックをチェックしましたが、その方法は、常に与えられているわけではない偶数の子カウントでのみ機能します。

この問題を解決する方法/アルゴリズム/アプローチを見つけるのを手伝ってもらえますか？

前もって感謝します！

ポール

「Cassandra」と「Dynamo」の両方で、マークル ツリー (別名ハッシュ ツリー) がデータ同期に使用されます。

他のハッシュ関数と同様に、異なるデータが同じハッシュ値を持つ可能性があります。

[y!=x] であるが [hash(x) = hash(y)] である x と y が存在する

NOSQL の「ビッグデータ」が大きくなるにつれて、そのようなデータに遭遇する確率は高くなります。

これは、データ セットが大きくなるにつれて、Merkle ツリー内の異なるノードが同じ親ハッシュを生成することはほぼ確実であることを意味します。

このような場合、クラスター内の 2 つの異なるマシンがマークル ツリーをトラバースすると、データが一貫しているという誤検出が発生します。ツリーのその枝にそれ以上データが書き込まれなければ、マシンは永遠に同期されないままになります。

これはどのように処理されますか？

unordered_map次のように、のキーとしてカスタム クラスを使用しようとしています。

ただし、g++ では次のエラーが表示されます。

私は、クラスをハッシュする方法をC++に伝える必要があると思いますが、Nodeそれを行う方法がよくわかりません。このタスクを達成するにはどうすればよいですか?

XML データの大きなチャンクを読み取る必要がある SAX パーサーを実行しているときに、この例外を受け取りました。データはハッシュツリーに格納されます。約 15 分間実行した後、この例外が見つかりました。どういう意味ですか？

私はツリーモデル（を使用closure_tree）であるモデルタグを持っており、gemのおかげで次のようなことができます：

その子を熱心にロードします。これで、子も使用するインスタンス メソッドができました。したがって、前述のクエリでタグを取得し、タグとその子を反復処理してこのインスタンス メソッドを呼び出すと、bulletgem は N+1 クエリを実行していると不平を言い、include(children). これは、子の子をロードしていないために発生するため、インスタンス メソッドを呼び出すときに、第 1 レベルのタグの各サブタグの子に対して個別のクエリを作成します。

次のようにすることでこれを解決できます。

この場合、ActiveRecord はタグ、その子、およびその子の子を積極的に読み込みます。ただし、これは 3 世代しかない場合に機能します。つまり、タグが祖父母であり、親 (ルート タグの子) と孫 (ルート タグの子の子) です。たとえば、私が4世代を持っている場合、私がしなければならないよりも:

したがってdepth、ルート タグの最も遠い孫の を特定できる場合、条件付きでクエリを作成する方法はありますか? 深さが 2 の場合は を使用includes(:children)し、深さが 3 の場合は を使用includes(children: :children)します。