将一个小数字散列到随机查看的64位整数

Question

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

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

我希望一个只需要几个CPU周期才能执行的函数.(代码将使用C++).

我考虑将输入乘以一个大素数并取模2**64(类似于线性全等生成器),但输出之间存在明显的依赖关系(在低位中).

谷歌搜索没有显示任何内容,但我可能使用错误的搜索字词.

这样的功能存在吗？

---

一些背景信息:

我想避免在算法中使用带有伪随机数的大型持久表,并在运行中计算随机数字.

安全不是问题.

Answer 1

我测试了MurmurHash3的64位终结器(由@aix和这个SO帖子建议).如果输入为零,则给出零,因此我首先将输入参数增加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