プリミティブ型の対のための良いハッシュ関数

Question

私は2つのプリミティブ型のstd :: pairに対して良いハッシュ関数を見つけようとしています。これは私がそれが今実現してい方法です。

template<typename T, typename U> 
std::size_t operator()(const std::pair<T,U> &rhs) const 
{ 
    return stdext::hash_value<T>(rhs.first)^stdext::hash_value<U>(rhs.second); 
} 

私のような2組を持っている場合でも動作するように表示されます（1、2）及び（2、1）（数字は反転し）。それらは同じハッシュ値を生成しますが、値は依然としてハッシュマップに正常に挿入されます。何かご意見は？

Answer 1

stdext :: hash_valueは1番目と2番目のそれぞれに対してハッシュ値の分布が良いと仮定すると、鏡像ペアの発生率が不均衡に高くなることを期待しないと、 2）および（2,1））。あなたのデータセットがの場合はに多くのデータセットがあると思われるので、ハッシュ関数を微調整してそれらを強制的に異なるものにすることを検討してください。たとえば、最初のハッシュ値を反転する：

return ~stdext::hash_value<T>(rhs.first)^stdext::hash_value<T>(rhs.second); 

私はミラーイメージのペアについて懸念を表明しているため、これを説明します。あなたの入力がその点でランダムに近いなら、^はうまくいくはずです。衝突の発生を最小限に抑え、完全に回避しないことを忘れないでください。

Answer 2

一般に、ハッシュコンテナは常にこのケース（ハッシュコリジョン）を処理する必要があります。連鎖とプロービングのように使用できる2つの方法がありますが、いずれもパフォーマンスを損なう可能性があります。

代わりに、firstとsecondが同じハッシュを生成しないように、boost::hash_combineを使用してハッシュを組み合わせることをお勧めします。

Answer 3

他にも述べたように、ハッシュ関数は、正確性ではなくハッシュテーブルの効率にのみ影響します。あなたの機能は鏡像対が頻繁である場合にのみ悪くなります。アプリケーションによってはこれが問題であるかもしれないので、1つのハッシュ値の上半分のワードと下半分のワードを交換し、次にxorを交換するのが合理的です。他の多くのスキームも可能ですが、これは非常に高速で簡単です。

template<typename T, typename U> 
std::size_t operator()(const std::pair<T,U> &rhs) const 
{ 
    const int h = sizeof(size_t) * 8/2; 
    size_t a = stdext::hash_value<T>(rhs.first); 
    return ((a << h) | (a >> h))^stdext::hash_value<U>(rhs.second); 
} 

Answer 4

ここで、ブーストの現在のバージョンからのドキュメントに基づいてhash_combineの実装です： （http://www.boost.org/doc/libs/1_53_0/doc/html/hash/reference.html#boost.hash_combine）

template<typename T> void hash_combine(size_t & seed, T const& v) { 
    seed ^= stdext::hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
} 

あなたはこのようにそれを使用したい：

template<typename T, typename U> 
std::size_t operator()(const std::pair<T,U> &rhs) const { 
    size_t retval = stdext::hash_value<T>(rhs.first); 
    hash_combine(retval, rhs.second); 
    return retval; 
} 

私はこの関数の背後にあるロジックを実際に保証することはできませんが、ここで述べたほとんどのオプションよりも強固に見えます。

Answer 5

はちょうどそれの楽しみのために、ここでは簡単ですし、直接問題のあるケースに対処する別のアプローチは、具体的には、です：

• firstとsecondの両方が同じであれば、それはそれ以外の場合は、それらの共通のハッシュ値
• を返します。 h（a、b）がh（b、a）と衝突するのを防ぐために、
  • の値をXORするが、h（a、b）の間で選択するには<bを使用する。^h（〜b）

実装：

1 template<typename T, typename U> 
2 std::size_t operator()(const std::pair<T,U> &rhs) const 
3 { 
4  std::size_t a = stdext::hash_value<T>(rhs.first); 
5  return rhs.first == rhs.second ? a : 
6   a^(rhs.first < rhs.second ? stdext::hash_value<U>(rhs.second) 
7          : stdext::hash_value<U>(~rhs.second)); 
8 } 

冗談はさておき、私はマークBのアドバイスに従い、ブースト:: hash_combineを使用することをお勧めしたい - レス分岐が速度を向上する可能性があります。