整数の大きなセットのための完全なハッシュ関数[1..2^64 - 1]

Question

整数[1..2^64 - 1]のセットをそれ自身にマップする完全なハッシュ関数を構築する必要があります実際にはいくつかの複雑な順列です）。

この問題を説明するために、データベースに整数主キーのシーケンスがあるとします。できるだけ遠くにある主キーに近い数字が対応するように、数字（ユーザーに表示する）を作成する必要があります。

したがって、基本的には、大規模な整数セットのための全単射関数が必要です。例えば。 1 - -

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

何か提案や参考に感謝します。

Answer 1

0からupperlimit（除外）までのスペースに最大2つの数字を配置するには、その距離を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 

は、2番目の列は、ハッシュを示し値。必要に応じて0を除外することができます。なぜなら、それ自体にマップするからです。