在 Int32 或 UInt32 中散列位的好方法是什么？

Question

我有一个伪随机数生成器的实现，特别是 George Marsaglia 的 XOR-Shift RNG。我的实现在这里：

FastRandom.cs

事实证明，第一个随机样本与种子非常密切相关，如果您查看 Reinitialise(int seed) 方法，这一点非常明显。这不好。我提出的解决方案是将种子的各个部分混合如下：

_x = (uint)(  (seed * 2147483647) 
           ^ ((seed << 16 | seed >> 48) * 28111) 
           ^ ((seed << 32 | seed >> 32) * 69001)
           ^ ((seed << 48 | seed >> 16) * 45083));

因此，我通过将种子位与四个素数相乘并进行异或运算以形成 _x 来显着削弱任何相关性。我还在乘法之前旋转种子的位，以确保不同幅度的位在 32 位值的整个值范围内混合。

四向轮换似乎是什么都不做和每一次可能的轮换（32）之间的一个很好的平衡。质数是“悬而未决”——足够的大小和位结构可以将位混在一起并将它们“散布”在整个 32 位上，而不管起始种子如何。

我应该使用更大的素数吗？是否有解决这个问题的标准方法，也许有更正式的基础？我试图以最小的 CPU 开销来做到这一点。

谢谢

=== 更新 ===

我决定使用一些设置位更好地分布在所有 32 位上的素数。结果是我可以省略移位，因为乘法可以达到相同的效果（散列整个 32 位范围内的位），所以我只需将四个乘积相加即可得到最终种子......

_x = (uint)(  (seed * 1431655781) 
            + (seed * 1183186591) 
            + (seed * 622729787)
            + (seed * 338294347));

我可以用更少的素数/乘法逃脱。两个看起来太少了（我仍然可以在第一个样本中看到图案），三个看起来还可以，所以为了安全起见，我做了四个。

=== 更新 2 ===

仅供参考，以上简化为功能等效：

_x = seed * 3575866506U;

我最初没有发现这一点，当我发现时，我想知道在计算的不同阶段溢出是否会导致不同的结果。我相信答案是否定的——这两个计算总是给出相同的答案。

Answer 1

根据一些研究人员的说法，CrapWow、Crap8和Murmur3是当今最好的非加密哈希算法，它们既快速、简单又具有良好的统计性。

更多信息请参阅非加密哈希函数 Zoo。

编辑：截至 2021 年 5 月，floodberry.com 指向非加密哈希函数动物园的链接无效。内容仍然可以在archive.org上找到。