以与订单无关的方式散列一组整数

Question

我想散列一组整数,使得整数的顺序对计算的散列值没有影响.即H([32224,12232,564423]) == H([564423,32224,12232]).

唯一集的数量将在几百万的范围内.速度非常重要,但我需要通过选择的方法知道碰撞的上限.

维基百科有一个很好的关于散列向量的部分,但我不明白它背后的数学是在代码中自信地实现它们.如果有人能解释一些代码涉及的数学,我将不胜感激.理想情况下,我希望最终的哈希值为32位.如果它有用 - 我将用Java实现它.

更新:由于性能原因(在许多此类集上运行),我特别希望避免对集合中的整数进行排序.

Answer 1

一种简单的方法是将各个整数的哈希值合并或加在一起.xor和add是可交换的,因此这满足了顺序独立性.

从而:

int hc = 0;
for(int i = 0; i < n; i++) {
   hc += a[i];
}
return hc;

要么

int hc = 0;
for(int i = 0; i < n; i++) {
   hc ^= a[i];
}
return hc;

因为int的哈希码无论如何都是它的值.

事实上,这是究竟是什么HashSet<Integer>.hashCode(使用添加)就行了.如果您的整数已经装箱,或者您可以装箱,那么这就是一个内置的解决方案.

Answer 2

您可以将所有整数放入Java HashSet中并使用其hashCode。

另一方面，java.util.Set 在文档中指定了以下内容：

返回该集合的哈希码值。集合的哈希码定义为集合中元素的哈希码之和，其中空元素的哈希码定义为零。这确保了 s1.equals(s2) 意味着对于任何两个集合 s1 和 s2 来说 s1.hashCode()==s2.hashCode()，正如 Object.hashCode() 的一般契约所要求的。

然后 Integer.hashCode() 是

该对象的哈希码值，等于该 Integer 对象表示的原始 int 值。

i1, i2, ... i_n因此， Java 标准库中整数集的 hashCode是i1 + i2 + ... + i_n。

如果数字相当小，您还可以将每个元素乘以某个适当大小的素数。Knuth 使用了 2654435761，这对于 java int 来说太大了，但是您可以取它的 2 补码，-1640531527。因此取 C = -1640531527，然后你的代码是C*i1 + C*i2 + ... C*i_n.

private static final int C = -1640531527;

public static int calculateHash(int[] set) {
    int code = 0;
    for (int e: set) {
        code += C * e;
    }

    return code;
}

然而，这种想法有一个明显的缺陷。要充分利用 hashCode，您需要能够证明 2 个集合确实相等，因此在任何情况下，最简单的证明方法就是对元素进行排序。当然，如果集合的数量大大少于数百万，那么冲突也不会那么多。