c# - 整数哈希函数在几次迭代后发生冲突

Question

我正在使用计算对象列表散列的代码，算法取自以下问题:Quick and Simple Hash Code Combinations .基于种子和因子的第二个答案值是 1009 和 9176。它适用于计算随机整数列表的哈希值，但我发现当列表相似时它根本不起作用。

如果我们创建一个包含 20 个随机整数的列表并使用以下方法计算散列:

int[] hashCodes = {
    -1641555406,
    1406166370,
    431811193,
    -719284004,
    -463280747,
    138136561,
    -1634028130,
    -792182888,
    1325264708,
    2143865166,
    25622596,
    -977152280,
    1955313253,
    -1440973864,
    1627089736,
    1733757615,
    -576076691,
    -145918914,
    1015082677,
    -954685337,
    -1307289157
};
int hashCode = 1009;
foreach (var c in hashCodes)
    hashCode = hashCode * 9176 + c;

而不是只改变第一个数字:

hashCodes[0] = -145574454;
hashCode = 1009;
foreach (var c in hashCodes)
    hashCode = hashCode * 9176 + c;

我们最终会得到相同的哈希码。任何随机整数列表的结果都是相同的——如果只有第一个数字不同，我们最终会在 8-10 次迭代中得到相同的哈希码。

我相信这是由于整数溢出和截断最高位，但我不确定。我尝试根据第一个答案(分别为 17 和 31)使用种子和因子，并且效果很好。这是为什么？

应该如何计算这样的散列(整数列表的散列)？

编辑:根据评论，这不是加密安全的散列，它不是这样使用的，它只是一种将唯一整数键分配给整数列表的方法。

Answer 1

原因是你的乘法部分将位移到左边，如果你有足够的循环迭代，从列表中的第一个数字获得的位最终将被完全丢弃，不再对最终结果产生影响。

数字 9176 可以用二进制写成 10001111011000，实际上最低的 1 位将指示在第一个条目完全脱离列表之前需要运行多少轮。

最后一个 1 位位于位置 3(或从右数第 4 个位置)，这意味着您在每次迭代时都将这些位从第一个数字 4 个位置向左移动。当您完成 8 次此操作时，您已将该数字完全移出 32 位缓冲区(int 是 32 位)。

更好的方法(但请参阅下面我的评论)是至少确保没有位完全丢失，因此计算哈希码的另一种但仍然相当简单的方法可能是这样的:

hashCode = ((hashCode << 27) | (hashCode >> 5)) ^ c;

这基本上是将当前哈希码向左旋转 27 位，从右侧向后旋转掉掉的 5 位，然后与 c 进行异或运算。也将其烘焙到数字中。

但是，您应该使用更标准化的方法来计算这些哈希值。我上面建议的更改肯定会有其自身的问题，它们只是不那么明显。

和 真的 ，因为 pigeon hole principle ，您无法计算 唯一 number 用于数字列表，这与您使用的哈希码算法无关。他们都不会解决这部分问题。所以我真的希望你首先重新考虑你在做什么。