散列少数到随机寻找64位整数

本文介绍了散列少数到随机寻找64位整数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我要寻找一个哈希函数，它运行在一个小的整数（取值范围为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和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