私はペアリング関数fを探しています

Question

単射ペアリング機能：ZXZ - 次の特性を持つ、> Z：

• それは可逆的である必要はありません。私はそれが命を欲しければ（異なるペアが異なる整数にマップされる）必要があるだけで、ペアを計算する必要はありません。
• それは（符号付き整数）これは現時点で

効率的に計算可能である

Z上で定義され、Iは（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

明らかPigeonhole Principleによって、我々は2^128 - 2^64に等しい少なくとも2^64 * (2^64 -1)サイズの出力を必要とするので、ユニーク単一番号に2つの64ビット整数を符号化するために、可能な入力の2^64 * (2^64 -1)組み合わせが存在する、すなわちすべての可能な出力を保持するには128ビットの容量が必要です。

---

私はそれがすべての値のために存在することはできません知っています。しかし、それは値に依存し、データ型には依存しません。例えば。 4と5が64ビットの整数として格納されていても、f（4,5）を実行することはできます。オーバーフローのために、使用される関数に応じてチェックするのは簡単です（その場合はマッピングを使用しません）。

あなたはそれを知っています。つまり、64ビット入力の最大値を上限にすることができます。出力は64ビット符号または符号なし整数になります。

出力が署名され、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; 
} 

：

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＃で実装符号なしですより少ない計算。ユニークペアの下限と上限は、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ビットで整数を連結し、CRCを計算します。

は、あなたが衝突することなく、64ビットで128ビットをマッピングすることはできませんことを覚えておいてください。