射配对功能

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位而没有发生冲突。