19

のペアを にマップする必要がありますがlong long、double使用するハッシュ関数がわかりません。各ペアは、任意の 2 つの数字で構成されますが、実際には、通常はその前後の数字になります0(100ただし、これは保証されません)。

これがtr1::unordered_mapドキュメントです。私はこのように始めました：

typedef long long Int;
typedef std::pair<Int, Int> IntPair;

struct IntPairHash {
  size_t operator(const IntPair& p) const {
    return ...; // how to hash the pair?
  }
};

struct IntPairEqual {
  bool operator(const IntPair& a, const IntPair& b) const {
    return a.first == b.first 
      && a.second == b.second;
  }
};

tr1::unordered_map<IntPair, double, IntPairHash, IntPairEqual> myMap;

一般に、どのハッシュ関数を使用すればよいかわかりません。優れた汎用ハッシュ関数とは?

4

4 に答える 4

11

ペアをハッシュする自然な方法は、そのコンポーネントのハッシュを何らかの方法で組み合わせる方法です。最も簡単な方法は、xorを使用することです。

namespace std {
namespace tr1 {

template<typename a, typename b>
struct hash< std::pair<a, b> > {
private:
   const hash<a> ah;
   const hash<b> bh;
public:
   hash() : ah(), bh() {}
   size_t operator()(const std::pair<a, b> &p) const {
      return ah(p.first) ^ bh(p.second);
   }
};

}} // namespaces

これは（1,1）や（2,2）のようなハッシュペアをすべてゼロにすることに注意してください。データによっては、より複雑な方法を使用してパーツのハッシュを組み合わせることができます。Boostは次のようなことをします：

size_t seed = ah(p.first);
return bh(p.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
于 2009-04-10T17:00:57.480 に答える
10

boost::hashフォーム機能ライブラリ。

またはあなた自身を書いてください。最も単純なバージョン=pair.first* max_second_value + pair.second

于 2009-04-10T15:58:52.153 に答える
2

提案：このSO投稿を見てください：「わかりませんstd::tr1::unordered_map」。

また、EqualityPredicateとHashPredicatesに関するBoostDocumentationも（この例と同様に）良い場所です。

于 2009-04-10T15:58:32.683 に答える
1

ハッシュベースのマップが本当に必要ですか? 二分木に基づく一般的なマップは、複雑さが解決しようとしている問題に対して機能することが保証されている限り、問題なく機能します。

于 2009-04-10T15:51:36.380 に答える