我在寻找一个配对函数f：ZXZ - > Z，具有以下特点：

I'm looking for a pairing function f: ZxZ -> Z, with the following characteristics:

目前，我使用的是F（X，Y）= X +（最大（X）-min（X）+1）* Y

At the moment, I'm using f(x,y) = x + (max(x)-min(x)+1) * y

它的工作原理，我只是想知道是否有可能是因为使用了结果空间更有效，考虑另外一个功能：

It works, I'm just wondering whether there could be another function that uses the result space more efficiently, considering that:

我不知道这意味着我不能映射所有的x，y的组合没有结果溢出。 我很高兴足以与能够确定转换是否适合在64位与否。 出于这个原因，提供了理想的映射函数将作为有效地利用现有的64位尽可能

I do know that this means I cannot map all x,y combinations without the result to overflow. I'm happy enough with being able to establish whether the conversion would fit in 64bits or not. For this reason, the ideal mapping function would use the available 64bits as efficiently as possible.

任何提示？

推荐答案

要连接code两个64位的整数到一个独特的单号，有 2 ^ 64 *（2 ^ 64 - 1）输入组合的可能，因此受到明显鸽巢原理，我们需要的大小输出至少 2 ^ 64 *（2 ^ 64 -1），这等于 2 ^ 128 - 2 ^ 64 ，或者换句话说，你需要一个容量为128位，以容纳所有可能的输出。

To encode two 64 bit integers into a unique single number, there are 2^64 * (2^64 -1) combinations of inputs possible, so by the obvious Pigeonhole Principle, we need an output of size at least 2^64 * (2^64 -1), which is equal to 2^128 - 2^64, or in other words, you need a capacity of 128 bits to hold all the possible outputs.

我知道这不可能对于所有的值存在。但是，这依赖于值，而不是在数据类型。例如。 F（4,5），仍然可以完成的，即使在图4和5如64位整数存储。这很容易检查，根据所使用的功能，对于溢出（在这种情况下，我不会使用映射）。

I know it can't exist for all values. But that depends on the values, not on the data types. E.g. f(4,5) can still be done, even when 4 and 5 are stored as 64bit integers. It's easy to check, depending on the function used, for overflows (in that case I wouldn't use the mapping).

您知道。不过，正如你说的，你可以有最高值的上限为您的64位输入。则输出可以是64位有符号或无符号整数。

You know that. That said, as you say you could have a cap on maximum values for your 64 bit inputs. The output then can be 64 bit signed or unsigned integer.

输出签字，在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）。最初的功能是取自这里。在链接中提到的优雅配对函数是最节省空间的可能，因为它映射到可用空间的每一个点。欲了解更多关于类似的方法，请参阅Mapping两个整数之一，以独特的和确定的方式

The unsigned implementation will be slightly faster because of the fewer calculations. The lower and upper bound to uniquely pair is int.MaxValue (-2147483648) and int.MaxValue(2147483647). The original function is taken from here. The Elegant Pairing function mentioned in the link is the most space efficient possible since it maps to every single point in the available space. For more on similar methods, see Mapping two integers to one, in a unique and deterministic way