大整數整數的完美散列函數[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]

回答

相關問題