关联非交换哈希函数

Question

是否有具有以下属性的哈希函数？

• 是联想的
• 不是可交换的
• 可以在32位整数上轻松实现: int32 hash(int32, int32)

如果我是正确的,这样的功能可以实现以下目标

• 从子串的哈希中计算连接字符串的哈希值
• 同时计算哈希值
• 计算在二叉树上实现的列表的哈希 - 包括顺序,但不包括树的平衡方式

到目前为止我发现的最好的是4x4比特矩阵的乘法,但这很难实现并将空间减少到16比特.

我很感激任何帮助.

Answer 1

多项式滚动哈希可以帮助：

• H(A1,...,An) = (H(A1,...,An-1) * 基数 + An) Mod P

只要知道长度，就可以轻松连接两个结果或从结果中减去前缀/后缀。