我需要构造一个完美的散列函数,将一组整数 [1..2^64 - 1] 映射到自身(这个函数实际上是一些复杂的排列)。
为了解释这个问题,假设我们在数据库中有整数主键序列。我们需要显示构造一个数字(我们向用户显示),以使关闭的数字对应于彼此尽可能远的主键。
所以,基本上我需要一个大型整数集的双射函数。例如
- 1 -> X1
- 2 -> X3
- 3 -> X3
- ...
- 2^64 - 1 -> X2^64 - 1
任何建议或参考将不胜感激。
我需要构造一个完美的散列函数,将一组整数 [1..2^64 - 1] 映射到自身(这个函数实际上是一些复杂的排列)。
为了解释这个问题,假设我们在数据库中有整数主键序列。我们需要显示构造一个数字(我们向用户显示),以使关闭的数字对应于彼此尽可能远的主键。
所以,基本上我需要一个大型整数集的双射函数。例如
任何建议或参考将不胜感激。
要在从 0 到(不包括)的空间中最大程度地隔开任何两个数字,upperlimit
我会将它们的距离设置为大约upperlimit
.
在 python 中它看起来像这样(代码只有在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,因为它映射到自身。