散列少数到随机寻找64位整数 [英] hashing a small number to a random looking 64 bit integer

问题描述

我要寻找一个哈希函数，它运行在一个小的整数（取值范围为0〜1000说吧），输出64位整型。

I am looking for a hash-function which operates on a small integer (say in the range 0...1000) and outputs a 64 bit int.

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

The result-set should look like a random distribution of 64 bit ints: a uniform distribution with no linear correlation between the results.

我所期待的一个功能，只需要几分钟的CPU周期来执行。 （在code将在C ++中）。

I was hoping for a function that only takes a few CPU-cycles to execute. (the code will be in C++).

我认为由大素数的输入相乘并取模2 ** 64（像一个线性同余发生器），但也有输出之间明显的依赖关系（在较低位）。

I considered multiplying the input by a big prime number and taking the modulo 2**64 (something like a linear congruent generator), but there are obvious dependencies between the outputs (in the lower bits).

谷歌搜索并没有表现出任何东西，但我可能使用错误的搜索条件。

Googling did not show up anything, but I am probably using wrong search terms.

有没有这样的功能存在？

Does such a function exist?

一些背景-信息：

我想避免的算法采用伪随机数大的持久表，并计算上飞随机找数。

I want to avoid using a big persistent table with pseudo random numbers in an algorithm, and calculate random-looking numbers on the fly.

安全不是一个问题。

推荐答案

我测试MurmurHash3的64位终结（由@aix和<建议的href="http://stackoverflow.com/questions/5085915/what-is-the-best-hash-function-for-uint64-t-keys-ranging-from-0-to-its-max-value">this SO帖子）。这使得零，如果输入的是零，所以我通过增加输入参数1第一：

I tested the 64-bit finalizer of MurmurHash3 (suggested by @aix and this SO post). This gives zero if the input is zero, so I increased the input parameter by 1 first:

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;
}

下面的输入参数我是一个小整数，例如 {0，1，...，1000} 。输出看起来是随机的：

Here the input argument i is a small integer, for example an element of {0, 1, ..., 1000}. The output looks random:

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

没有了一系列的后续元素之间的线性关系：

There is no linear correlation between subsequent elements of the series:

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

这篇关于散列少数到随机寻找64位整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！