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

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，你不能计算一个唯一的数字列表，并且这与您使用的哈希码算法无关。 None 他们将解决这部分问题。所以我真的请你重新考虑你在做什么。

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

Integer hash function colliding after few iterations

c#

algorithm

hash

hashcode