performance - 寻求有效的关联位集散列

Question

假设您有一个有序的位集序列b1, b2, b3, ..., bN。

是否有有效的按位运算符散列计算可用于生成也是关联的散列？

换句话说，什么是推荐的散列函数hash(bX, bY)，例如：

hash(hash(b1, b2), b3) == hash(b1, hash(b2, b3))

按位排他或XOR提供可接受的低冲突率？

编辑：请注意，这里有一个相关的问题。

Answer 1

XOR 是关联的，但也是可交换的。它超出了您的需要，但我想不出一个实用的纯关联变体。我想到了矩阵乘法，但我不确定如何将它与二进制哈希一起使用。

加法也是关联的，因此您可以进行组合哈希：保留两个不同的哈希，一个与加法相结合，一个与 XOR 相结合。碰撞必须同时影响两者才能成为有效的碰撞。更有可能。

一个缺点是hash(a, b) == hash(b, a)（这是交换性）。不知道如何删除该属性。