关联非交换散列函数
关联非交换散列函数
提问于 2011-03-30 19:19:04
是否有具有下列属性的散列函数？
- 是结合的
- 不是交换的
- 在32位整数上易于实现：
int32 hash(int32, int32)
如果我是正确的，这样的功能可以实现以下目标
- 从子串的散列中计算级联字符串的散列
- 并发计算散列
- 计算在二叉树上实现的列表的散列，包括顺序，但不包括树是如何平衡的。
到目前为止，我发现的最佳方法是4x4位矩阵的乘法，但这很难实现，并将空间缩小到16位。
我很感谢你的帮助。
回答 2
Stack Overflow用户
发布于 2022-04-11 05:48:01
Stack Overflow用户
发布于 2022-07-05 16:14:40
矩阵乘法是结合的和非交换的.
您可以尝试将您的散列表示为矩阵，但如果它们具有行列式(这很可能！)，则会导致信息丢失。
因此，您应该生成一个三角矩阵，其对角线为1，以确保您有1的行列式(这可以保证组合不会丢失信息)。
此外，三角形矩阵的合成产生了一个新的三角形矩阵，使得读取的组成与生成的组成相同。
注:要使用这种方法，散列的长度必须是三角形数字！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5491130
复制相关文章
相似问题
腾讯云开发者
