uint32_t値のペアの可換ハッシュ関数

の値の一意の識別子を作成する高速で単純なハッシュ関数が必要です。つまり、(2,7)と(7,2)のハッシュ値は同じです。uint32_t値のペアの可換ハッシュ関数

2013-07-20 plasmacel

'pair.first'と' pair.second'に 'std :: hash'の結果を追加するだけでいいですか？ –

2つの数字のうちの小さい方（または大きい方）をビットシフトし、もう一方を追加することによってuint64を作成します。次に、64bit intをハッシュするだけです。（あるいは、ハッシュ関数を使ってペアをコピーし、順序を保証するために要素をスワップし、そのペアに実際のハッシュを適用してください） –

@DavidRodríguez-dribeas：ええと、私は解決策を思いついた。私はすでにそれのためのビットシフトのものを持っていたが、比較は魔法であることを私は思い出した。 – plasmacel

、解決策は次のとおりです。

これらのメソッドは、完全ハッシュ関数である 無店舗バージョン

uint64_t hash(uint32_t x, uint32_t y) 
{ 
    const uint64_t a = static_cast<uint64_t>(x); 
    const uint64_t b = static_cast<uint64_t>(y); 

    const uint64_t h0 = (b << 32) | a; 
    const uint64_t h1 = (a << 32) | b; 

    return (x < y) ? h0 : h1; // conditional move (CMOV) instruction 
}

に改善することができる

uint64_t hash(uint32_t x, uint32_t y) 
{ 
    const uint64_t a = static_cast<uint64_t>(x); 
    const uint64_t b = static_cast<uint64_t>(y); 

    if (x < y) return (b << 32) | a; 
    else return (a << 32) | b; 
}

- 彼らはゼロ衝突を保証します。しかし、それらは、2^32 - 1を超える値をハッシュできないという欠点があります。

出典

2013-07-20 19:29:43 plasmacel

私はシフトの考え方が好きです、それは自然であり、一意性を証明する必要はありません。 2^32以上の値を扱う場合は、文字列をユニークな識別子として返すことができます。ハッシュの2つの部分を分離する特別なシンボルを予約します（表現ベースを10以上に変更することも良い考えです） – pkacprzak

"表現ベースを10以上に変更することも良いアイデアです。 " - どういう意味ですか？ – plasmacel

数値を文字列として表す場合は、{0,1、...、9}より大きいアルファベットを使用できます。 16進数のシステムまたはそれより大きい。ベースが大きいほど表現は短くなります。 – pkacprzak

constexpr uint32_t hash_max = ...;  

constexpr uint32_t commutative_hash(uint32_t i, uint32_t j) { 
    return (i*j + (i*i)*(j*j) + (i*i*i)*(j*j*j)) % hash_max; 
};

余分なかっこは、この式を最適化する方が簡単です。

はCPUのパイプラインを破る（と遅いです）あなたは高速機能を作りたい場合は任意の条件付き命令（またはstd::max/std::min）を使用しないでください。自分の質問に答えるために

出典

2013-07-20 18:57:04

ありがとうございますが、これは乗算が非常に遅いため非常に遅いです。私の答えを見てください。 – plasmacel

私は自分の機能がより速いと確信しています。私の機能をベンチマークしましたか？なぜ私はそれが速いの答えの説明を追加しました。 –

正しい説明のために@LeonidVolnitsky +1。条件文によっては、分岐予測が混乱することがあります。 – NumberFour

uint32_t値のペアの可換ハッシュ関数

答えて

関連する問題