寻求高效的关联位散列

Question

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

是否有一个有效的按位运算符哈希计算可用于生成也是关联的哈希？

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

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

会按位异或XOR提供可接受的低碰撞率是多少？

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

Answer 1

XOR是关联性的，但也是可交换的。它比你需要的要多，但我没有想到一个纯粹结合的实用变体。矩阵乘法浮现在脑海中，但我不确定如何在二进制哈希中使用它。

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

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