長いロングハッシュ関数のためのハッシュ関数？

Question

long longのペアをdoubleにマッピングする必要がありますが、どのハッシュ関数を使用するかはわかりません。実際には通常0と約100の間の数値です（ただし、保証はできません）が、各ペアは任意の2つの数値で構成されます。

Hereは、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; 

一般に、私はどのハッシュ関数を使うべきか分かりません。良い汎用ハッシュ関数とは何ですか？

Answer 1

本当にハッシュベースの地図が必要ですか？バイナリツリーに基づく一般的なマップは、複雑さがあなたが解決している問題のために働くことを保証する限り、正常に動作します。

Answer 2

提案：この投稿を見てください："I don't understand std::tr1::unordered_map"。

また、Equality Predicates and Hash PredicatesのBoostドキュメントも良い場所です（このexampleも同様です）。

Answer 3

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

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

Answer 4

ペアをハッシュする自然な方法は、コンポーネントのハッシュを何らかの方法で結合することです。最も簡単な方法は、単にXORである：あなたが結合するいくつかのより複雑な方法を使用する場合がありますので、これは、ゼロに（1,1）または（2,2）のすべてのようなペアをハッシュすることを

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 

注意あなたのデータに応じて、部品のハッシュを作成します。彼らは非常に高速かつ効率的http://www.partow.net/programming/hashfunctions/index.html：

size_t seed = ah(p.first); 
return bh(p.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);