7

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);
}

(1, 2) と (2, 1) (数字が反転) のような 2 つのペアがあっても機能するようです。これらは同じハッシュ値を生成しますが、値は引き続きハッシュ マップに正常に挿入されます。何かご意見は？

4

5 に答える 5

2

hash_combineこれは、boost の現在のバージョンのドキュメントに基づいた実装です: ( 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;
}

この関数の背後にあるロジックを実際に保証することはできませんが、ここで言及されているほとんどのオプションよりも確実に見えます。

于 2013-05-10T00:22:38.267 に答える
1

stdext::hash_value が最初と 2 番目のそれぞれのハッシュ値の適切な分布を提供すると仮定すると、ミラー イメージのペア (たとえば (1,2) と ( 2,1))。あなたのデータセットがそれらの多くを期待するようなものである場合は、ハッシュ関数を微調整してそれらを強制的に異なるものにすることを検討してください. たとえば、最初のハッシュ値を反転します。

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

これについて言及したのは、あなたがミラー イメージのペアについて懸念を表明したからです。その点で入力がランダムに近い場合、^ は問題ないはずです。目標は衝突を最小限に抑えることであり、衝突を完全に回避することではないことに注意してください。

于 2013-05-09T22:10:07.263 に答える
0

楽しみのために、単純で問題のケースに直接対処する別のアプローチを次に示します。具体的には次のとおりです。

  • firstとの両方secondが同じ場合、それらの共通のハッシュ値を返します
  • それ以外の場合は、値を XOR しますが、次のようになります。
    • h(a, b) が h(b, a) と衝突するのを防ぐために、a < b を使用して h(a)^h(b) と h(a)^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 のアドバイスに従い、boost::hash_combine を使用することをお勧めします。分岐が少ないと速度が向上する可能性があります。

于 2013-05-10T02:00:08.390 に答える
0

他の人が指摘しているように、ハッシュ関数はハッシュテーブルの効率のみに影響し、正確さには影響しません。鏡像のペアが頻繁にある場合にのみ、関数は悪くなります。一部のアプリケーションではこれが問題になる可能性があるため、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);
}
于 2013-05-09T23:35:32.310 に答える