大整数整数的完美散列函数[1..2^64-1]

我需要构造一个完美的散列函数，它将一组整数[1..2^64-1]映射到自身（此函数实际上是一些复杂的排列）。大整数整数的完美散列函数[1..2^64-1]

为了解释这个问题，假设我们在数据库中有整数主键序列。我们需要以一种方式显示构建一个数字（我们向用户显示），其中数字与主键相对应，尽可能远离彼此。

所以，基本上我需要一个大集合整数的双射函数。例如。

1 - > X1
2 - > X3
3 - > X3
...
2^64 - 1 - > X2^64 - 1

任何建议或参考将不胜感激。

来源

2017-05-26 Aleksander Gurin

紧密数字之间的最小“距离”是可以接受的吗？ – diginoise

没有硬性限制。基本上我需要在更广泛的范围内传播序号。 –

模块乘以奇数是双射的，并保持在该范围内（0映射到自身，所以如果它不在输入范围内，它不在输出范围内） – harold

要在0到upperlimit（不包括）的空间中最大限度地分隔任意两个数字，我会将它们的距离设置为大约upperlimit的一半。

在蟒它看起来像这样（代码仅当upperlimit是即使工作，否则最后一个元素碰撞）：

def my_hash(n, upperlimit): 
    return n * upperlimit/2 % upperlimit + n/2 

def my_unhash(n, upperlimit): 
    return n % (upperlimit/2) * 2 + n/(upperlimit/2)

实施例的结果：

upperlimit = 16 
for i in range(upperlimit): 
    h = my_hash(i, upperlimit) 
    u = my_unhash(h, upperlimit) 
    print "%02d -> %02d -> %02d" % (i, h, u) 

00 -> 00 -> 00 
01 -> 08 -> 01 
02 -> 01 -> 02 
03 -> 09 -> 03 
04 -> 02 -> 04 
05 -> 10 -> 05 
06 -> 03 -> 06 
07 -> 11 -> 07 
08 -> 04 -> 08 
09 -> 12 -> 09 
10 -> 05 -> 10 
11 -> 13 -> 11 
12 -> 06 -> 12 
13 -> 14 -> 13 
14 -> 07 -> 14 
15 -> 15 -> 15

第二列显示散列值。如果需要，可以排除0，因为它映射到它自己。

来源

2017-05-26 13:15:49 fafl

不知道这个要求有多重要，但请注意，将空格分成2，可以让任何2个连续的数字相距很远，但通过跳过其他每个数字，它们都接近0 - > 0，2 - > 1 ，4 - > 2 ...同样适用于奇数。更好的策略（如果我们想要减少相距2的数字的接近度）是将可用空间划分为N个桶并在这些桶之间进行混洗。显然，使用N个存储桶意味着每个第N个数字都会接近...但是通过调整N（例如对于64位空间，使用N作为1024或更高的2的幂）将会产生传播。 – diginoise

好点，这里的要求不明确。我最大化了连续数字的距离。 – fafl

大整数整数的完美散列函数[1..2^64-1]

回答

相关问题