关联非交换哈希函数

Question

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

• 是关联的
• 不是可交换的
• 易于在32位整数上实现：int32 hash(int32, int32)

如果我是正确的，则该功能可以实现以下目标

• 根据子字符串的散列计算连接字符串的散列
• 并发计算哈希
• 计算在二叉树上实现的列表的哈希-包括顺序，但不包括树的平衡方式

到目前为止，我发现的最好的结果是4x4的位矩阵相乘，但是实现起来很麻烦并且将空间减少到16位。

我非常感谢您的帮助。

Answer 1

这是我想出的（用Java编写）。基本思想是将32bit-int拆分为2个数字。较旧的位总和包括乘法效果。较年轻的位跟踪该乘法效果。有用。它具有良好的分布-也可以针对（0，1），（1，0）等常见参数。

public class AssociativelyMergedIntegers {
  /** biggest unsigned 16-bit prime */
  private static final int PRIME = 65521;

  /** associative, not commutative hash function */
  public static int merged(int first, int second) {
    int firstFactor = remainderOf(first & 0x0000FFFF);
    int secondFactor = remainderOf(second & 0x0000FFFF);
    int firstSum = remainderOf(first >>> 16 & 0x0000FFFF);
    int secondSum = remainderOf(second >>> 16 & 0x0000FFFF);
    int resultSum = remainderOf(firstSum + (long) firstFactor * secondSum);
    int resultFactor = remainderOf((long) firstFactor * secondFactor);
    return resultSum << 16 ^ resultFactor;
  }

  private static int remainderOf(long number) {
    int rest = (int) (number % PRIME);
    return rest == 0
        ? PRIME - 2
        : rest;
  }
}

Answer 2

我目前正在尝试使用Quarternion哈希函数，也许这可能是一个很好的起点https://github.com/spareilleux/quaternionhash