c++ - 特殊キー用の2つの整数を使用した優れたハッシュ関数

Question

map<double, double>タイプのキーを決定しようとしています。しかし、問題は、私が望むキーが2つの数字のペアによって生成されることです。（0、1）、（2、3）、（4、2）（0、2）などのペアに対してそのようなキーを生成できる優れた関数はありますか？

Answer 1

N'ary数値システムを選択します。ここで、Nはペアの数の可能な最大値です。

このような：

hash(a, b) = a + b * N

それから

a = hash(a, b) % N
b = hash(a, b) / N

これにより、すべてのペア（a、b）に固有のハッシュ（a、b）が存在することが保証されます。10進数の数値にも同じことが起こります。0（00、01、02、...と表記します）から99までのすべての数値があなたのペアであると想像してください。次に、hash（a、b）= a * 10 + bであり、その逆の場合、最初の桁を取得するには、数値を10で除算する必要があります。2番目は10を法として取得します。

おそらくa/bの最大値よりも小さいNを選択できないのはなぜですか？答えは、衝突を避けるためです。
任意の数を選択し、それがたまたま最大数よりも小さい場合、同じハッシュ関数が異なる数のペアによって提供される可能性が高くなります。たとえば、ペアにN = 10を選択した場合：（10、10）と（0、11）、両方のハッシュは110に等しくなりますが、この状況では適切ではありません。

Answer 2

理想的には、KeyValuePair<int, int>キーとしてを持っている必要があります。それ以上のコードを書くことは役に立たないと思います。何らかの理由でそれができない場合は、ペアをハッシュして単一のキーを与えることは、達成しようとしていることによって異なります。ハッシュがのようなハッシュ構造を対象としている場合はDictionary、衝突率とハッシュの速度のバランスをとる必要があります。衝突のない完全なハッシュを作成するには、より時間がかかります。同様に、最速のハッシュアルゴリズムでは、比較的多くの衝突が発生します。ここで重要なのは、完璧なバランスを見つけることです。また、効果的なハッシュの大きさや、ハッシュされた出力を元に戻して元の入力に戻すことができるかどうかも考慮する必要があります。。通常、衝突の可能性を最小限に抑えるよりも、ペアリング/ハッシュ/マッピングを高速化することを優先する必要があります（優れたハッシュアルゴリズムでは、衝突の可能性が低くなります）。完璧なハッシュを作成するには、このスレッドで多数のオプションを確認できます。