0

要素のセットをインクリメンタルにハッシュする良い方法は何ですか? これは、要素を任意の順序で追加および削除できるようにするために発生する必要があり、それでも等しいセットは同じハッシュを持ちます。その目的は、セットのコレクションからセットまたはそのわずかな変更をすばやく見つけることができるようにすることです。

結合演算子へのベクトル空間アプローチについて

これが機能しないものです。b ビット整数の整数は、GF(2) 上のベクトル空間 V と考えることができます。ここで、加算は XOR 演算子 (たとえば、10 + 11 = 01) であり、0 または 1 による乗算はコンポーネントです。 -wise 論理積 (例: 1 * 10 = 10、0 * 10 = 00)。要素を b ビット整数 E = {e_1, ..., e_b} にランダムに (ただし固定で) マッピングし、要素のハッシュを合計してセットのハッシュを計算できます。その際、E がベクトル空間 V の基底を形成することを確認する必要があります。それ以外の場合、ハッシュは b ビット整数のすべての値を使用できません。

この手法の問題は、E-basis の使用サブセットが、たとえば、任意の基底ベクトル e_i のゼロ以外の最初のコンポーネントを持たない場合、結果のハッシュが奇数にならないことです。使用中の基底ベクトルのサブセットに応じて、同様の問題が発生します。要約すると、セットのハッシュを見つけるために XOR を使用しないでください。通常の合計 + を使用することは、おそらくそれ以上ではありません。

4

1 に答える 1

1

1 つの解決策は、赤黒木を拡張して、各ノードがそのノードをルートとするサブツリーの結合ハッシュを含むようにすることです (常に、現在のノード ハッシュと右子ハッシュを組み合わせた左子ハッシュ)。これにより、一定時間内にすべての要素のハッシュ (ルート ノードのハッシュ) を見つけることができますが、それ以外の場合は赤黒ツリーのプロパティには影響しません。ノード内の階層情報を自動的に更新できる一般的な赤黒ツリーの実装を作成することができます。更新ルールはデータ構造のユーザーによって指定されます。赤黒木は再調整時に回転する可能性があるため、これはハッシュ結合関数が連想的でなければならないことを意味します。論文「Hashing with SL2」Tillich と Zémor によって、連想ハッシュ結合関数 (行列乗算) を持つハッシュ関数を見つけることができます。ただし、これが許容できるパフォーマンスであるかどうかはわかりません。

于 2013-05-14T11:27:27.007 に答える