Fonction de hachage pour une paire de long long?

Question

J'ai besoin de mapper une paire de long long à double, mais je ne suis pas sûr de la fonction de hachage à utiliser. Chaque paire peut être constituée de deux nombres quelconques, bien qu'en pratique ils seront généralement des nombres entre 0 et environ 100 (mais encore une fois, ce n'est pas garanti).

Here est la documentation tr1::unordered_map. J'ai commencé comme ceci:

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; 

En général, je ne suis jamais sûr de la fonction de hachage à utiliser. Qu'est-ce qu'une bonne fonction de hachage à usage général?

Answer 1

Avez-vous vraiment besoin d'une carte basée sur le hachage? La carte générale basée sur un arbre binaire fonctionnera correctement tant que la complexité garantit que le problème est résolu.

Answer 2

Une suggestion: Jetez un coup d'oeil à cet article: "I don't understand std::tr1::unordered_map".

En outre, la documentation Boost sur Equality Predicates and Hash Predicates est un bon endroit aussi (ainsi que ce example).

Answer 3

boost::hash forme de la bibliothèque fonctionnelle.

ou écrivez le vôtre. version la plus simple = pair.first * max_second_value + pair.second

Answer 4

La manière naturelle de hacher une paire consiste à combiner les hachages de ses composants d'une manière ou d'une autre. La façon la plus simple est juste avec 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 

Notez que ce hash paires comme (1,1) ou (2,2) tout à zéro, vous voudrez peut-être utiliser une façon plus complexe de combiner la les hachages des pièces, en fonction de vos données. Boost fait quelque chose comme ceci:

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