射配對功能

Question

我正在尋找一個配對函數f：ZXZ - > Z，具有以下特點：

• 它並不需要是可逆的。我只需要它注射（不同的對映射到不同的整數），我從不需要計算回來。
• 據環Z定義（帶符號的整數）
• 它是高效計算

此刻，我使用的F（X，Y）= X +（MAX（X）-min（ X）+1）* Y

它的工作原理，我只是想知道是否有可能是更有效地使用結果空間，考慮到另一個功能：

• x，y是符號整數最多64位
• F（X，y）是一個整數，至多64個比特
• LEN（F（X，Y））< = 64位是易於計算

我知道這意味着我不能映射所有x，y組合都不會溢出。 我很高興能夠確定轉換是否適合64位。 因此，理想的映射函數將盡可能高效地使用可用的64位。

任何提示？

Answer 1

爲了編碼兩個64位整數成一個獨特的單個數字，有輸入可能2^64 * (2^64 -1)組合，因此受到明顯Pigeonhole Principle，我們需要大小至少2^64 * (2^64 -1)的輸出，這是等於2^128 - 2^64，或者換句話說，您需要128位容量來保存所有可能的輸出。

---

我知道它不能爲所有值存在。但這取決於值，而不是數據類型。例如。 f（4,5）仍然可以完成，即使當4和5存儲爲64位整數時也是如此。根據所使用的函數來檢查溢出是很容易的（在這種情況下，我不會使用映射）。

你知道的。也就是說，正如你所說的，你可以限制你的64位輸入的最大值。然後輸出可以是64位有符號或無符號整數。

輸出簽字，在C＃中實現：

public static long GetHashCode(long a, long b) 
{ 
    if (a < int.MinValue || a > int.MaxValue || b < int.MinValue || b > int.MaxValue) 
     throw new ArgumentOutOfRangeException(); 

    var A = (ulong)(a >= 0 ? 2 * a : -2 * a - 1); 
    var B = (ulong)(b >= 0 ? 2 * b : -2 * b - 1); 
    var C = (long)((A >= B ? A * A + A + B : A + B * B)/2); 
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1; 
} 

輸出爲未簽名，在C＃中實現：

public static ulong GetHashCode(long a, long b) 
{ 
    if (a < int.MinValue || a > int.MaxValue || b < int.MinValue || b > int.MaxValue) 
     throw new ArgumentOutOfRangeException(); 

    var A = (ulong)(a >= 0 ? 2 * a : -2 * a - 1); 
    var B = (ulong)(b >= 0 ? 2 * b : -2 * b - 1); 
    return A >= B ? A * A + A + B : A + B * B; 
} 

無符號的實施將是稍快，因爲的更少的計算。唯一配對的下限和上限是int.MaxValue（-2147483648）和int.MaxValue（2147483647）。原始功能是taken from here。鏈接中提到的「優雅配對」功能是最節省空間的可能，因爲它映射到可用空間中的每個點。有關類似方法的更多信息，請參閱Mapping two integers to one, in a unique and deterministic way

Answer 2

CRC polynomials計算速度快，擴散性好。我相信你會得到你最喜歡的語言的圖書館。以128位對兩個整數進行Concat並計算CRC。

請記住，無法映射64位中的128位而沒有發生衝突。