1

次のプロパティを持つ特定のハッシュコードを探しています。私はそのようなハッシュコードを知りませんし、そのようなことをすることが可能かどうかもわかりません。ただそれをそこに出して、人々が言うことを見たかったのです。

私は2つのデータベース（大まかに使用される用語-SQLやそのようなものは考えないでください）、1つはマスター、もう1つはバックアップを持っています。2つのデータベースの同期を維持し、データベースが同期していないことを検出する必要があります。そこにあるすべてのデータを検証するのではなく、検証可能なハッシュコードを保持することが望ましいでしょう。ただし、2つのデータベースが必ずしもすべての変更を共有するわけではありません。マスターからバックアップへの変更はバッチ処理されるため、マスターからバックアップへの特定の変更が折りたたまれる可能性があります。

つまり、データベースの現在の状態に要素A-> X、B-> Y、およびC->Zがあるとします。ここで、BはB-> Y1に変更され、その後B->Y2に変更されます。マスターからバックアップに送信される唯一の変更は、B->Y2です。中間のB->Y1はスキップされます。

ここで、各データベースのすべての要素をループしてそれらが一致することを確認するのではなく、両方の場所で要素の実行中のハッシュコードを保持し、それを比較することをお勧めします。ハッシュコードは次のようなものを計算する必要があります。

hm0の以前のハッシュコードを想定：
ハッシュコードhm1 = f（hm0、A-> X、B-> Y、C-> Z）

Bが変更された場合：
ハッシュコードhm2 = f（hm1、B-> Y1）
、次に
ハッシュコードhm3 = f（hm2、B-> Y2）

したがって、マスターはh3のハッシュコードを持ちます。これで、バックアップは変更B-> Y2を受け取らないため、実行中のハッシュコードを計算すると、次のようになります。

ハッシュコードhb1=f（hb0、A-> X、B-> Y、C-> Z）
ハッシュコードhb2 = f（hb1、B-> Y2）

データベースの現在の状態は同じであるため、hb2とhm3を一致させる必要があります。しかし、ほとんどの（すべてではないにしても）ハッシュコードはこのようには機能しません。

したがって、最初にハッシュからB-> Yの寄与を「削除」し、次にB-> Y1の寄与を「追加」してから、B-> Y1の寄与を削除して、ハッシュコードへのB->Y2の寄与。したがって、次のようなものが必要です。

2つの関数f、g：fは、新しい要素の寄与を追加することによって既存のハッシュコードを変更し、gは、要素の寄与を削除することによって既存のハッシュコードを変更します。

マスターの場合：
hm1 = f（hm0、A-> X、B-> Y、C-> Z）

BがB->Y1に変更されたとき：
hm2 = g（hm1、B-> Y）
hm3 = f（hm2、B-> Y1）

BがB->Y2に変更された場合：
hm4 = g（hm3、B-> Y1）
hm5 = f（hm4、B-> Y2）

hm5は、データベースの現在の状態の新しいハッシュコードです（A-> X、B-> Y2、C-> Z）

バックアップ時：
hb1 = f（hb0、A-> X、B-> Y、C-> Z）

BがB->Y2に変更されたとき：
hb2 = g（hb1、B-> Y）
hb3 = f（hb2、B-> Y2）

これで、両方のデータベースの現在の状態が同じであるため、hm5とhb3が一致するはずです。

だから：そのようなアルゴリズムfとgはありますか？質問を明確にしたいと思います。ありがとうございます。

4

2 に答える 2

1

コードを足したり引いたりするだけです。h（x）が任意のハッシュ関数である場合：

hm2 = hm1 + h(B->Y)
hm3 = hm2 + h(B->Y1)
hm4 = hm3 - h(B->Y1) 
hm5 = hm4 + h(B->Y2)

hb2 = hb1 + h(B->Y)
hb3 = hb1 + h(B->Y2)

hm5とhb3は同じです。

必ずしも加算または減算する必要はないことに注意してください。任意の可逆演算が機能します（理論的には乗算/除算も機能しますが、0付近で何が起こるかについて、オーバーフローの問題やあいまいさが増える可能性があります）。

于 2009-04-05T18:51:29.217 に答える
0

うーん。あなたが求めていることを正確に実行するハッシュ関数についてはよくわかりません。しかし、Gitがリビジョンを保存する方法と同様の構造が、必要なことを実行する可能性があるようです（Monotoneがリビジョンを保存する方法に触発されました）。

Gitは、リポジトリ内の各ファイルのSHA-1合計を計算します。これらはblob識別子として使用されます。次に、ファイル名をBLOB ID（およびサブディレクトリの場合は他のサブツリー）にマップするツリーがあります。ツリーの識別子は、そのSHA-1の合計です。（使用法とは関係ありませんが、ツリーは、作成者、日付、1つ以上の親リビジョンなどのリビジョンによって参照されます）。

これは、ブロブを更新するときに、ブロブごとにSHA-1の合計を再計算する必要がないことを意味します。変化するブロブに対してSHA-1を再計算し、ツリーに対してSHA-1を再計算するだけです。

あなたはあなたのデータで同じことをすることができます。各オブジェクトのハッシュを計算し、すべてのkey-> hash（value）マッピングを1つのファイルに入れて、そのハッシュを計算します。key-> hash（value）を含むファイルが大きすぎて毎回再ハッシュしたくない場合は、ファイルをセクションに分割し、key-> hash（section）を作成できます。各セクションにはkey-があります。 > hash（value）。ほとんどの場合、通常は1レベルの分岐で十分ですが、本当に必要な場合は、これらからツリー構造を構築できます。

于 2009-04-05T18:59:53.673 に答える