要素のセットをインクリメンタルにハッシュする良い方法は何ですか? これは、要素を任意の順序で追加および削除できるようにするために発生する必要があり、それでも等しいセットは同じハッシュを持ちます。その目的は、セットのコレクションからセットまたはそのわずかな変更をすばやく見つけることができるようにすることです。
結合演算子へのベクトル空間アプローチについて
これが機能しないものです。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 を使用しないでください。通常の合計 + を使用することは、おそらくそれ以上ではありません。