algorithm - 将一个小数字散列为一个随机的 64 位整数

Question

我正在寻找一个哈希函数，它对一个小整数(比如在 0...1000 范围内)进行运算并输出一个 64 位整数。

结果集应该看起来像 64 位整数的随机分布:结果之间没有线性相关的均匀分布。

我希望有一个只需要几个 CPU 周期即可执行的函数。 (代码将使用 C++)。

我考虑过将输入乘以一个大质数并取模 2**64(类似于线性同余生成器)，但输出之间存在明显的依赖关系(在较低位)。

谷歌搜索没有显示任何内容，但我可能使用了错误的搜索词。

有这样的功能吗？

---

一些背景信息:

我想避免在算法中使用带有伪随机数的大型持久表，并即时计算看似随机的数字。

安全不是问题。

Answer 1

我测试了 MurmurHash3 的 64 位终结器(@aix 和 this SO post 建议)。如果输入为零，则返回零，因此我首先将输入参数增加 1:

typedef unsigned long long uint64;

inline uint64 fasthash(uint64 i)
{
  i += 1ULL;
  i ^= i >> 33ULL;
  i *= 0xff51afd7ed558ccdULL;
  i ^= i >> 33ULL;
  i *= 0xc4ceb9fe1a85ec53ULL;
  i ^= i >> 33ULL;
  return i;
}

这里的输入参数 i 是一个小整数，例如 {0, 1, ..., 1000} 的一个元素。输出看起来是随机的:

i       fasthash(i) decimal:    fasthash(i) hex:
0       12994781566227106604    0xB456BCFC34C2CB2C
1       4233148493373801447     0x3ABF2A20650683E7
2       815575690806614222      0x0B5181C509F8D8CE
3       5156626420896634997     0x47900468A8F01875
...     ...                     ...

系列的后续元素之间没有线性相关:

两个轴的范围都是0..2^64-1