performance - 効率的な連想ビットセット ハッシュの検索

Answer 1

XOR は結合的ですが可換的でもあります。それはあなたが必要とする以上のものですが、私は実用的な純粋に連想的な変種を思いつきません. 行列の乗算が思い浮かびますが、それをバイナリ ハッシュで使用する方法がわかりません。

加算も連想的であるため、組み合わせたハッシュを実行できます。2 つの異なるハッシュを保持します。1 つは加算と組み合わせ、もう 1 つは XOR と組み合わせます。衝突は、効果的な衝突であるために両方に影響を与える必要があります。はるかに可能性があります。

欠点は、hash(a, b) == hash(b, a)(これは可換性です) ということです。そのプロパティを削除する方法がわかりません。