Funzione hash per un paio di long long?

Question

Ho bisogno di mappare una coppia di long long a double, ma non sono sicuro di quale funzione hash usare. Ogni coppia può essere composta da due numeri qualsiasi, anche se in pratica saranno numeri compresi tra 0 e circa 100 (ma, di nuovo, non è garantito).

Here è la documentazione di tr1::unordered_map. Ho iniziato così:

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; 

In generale, non sono mai sicuro di quale funzione hash utilizzare. Qual è una buona funzione di hash generale?

Answer 1

Hai davvero bisogno di una mappa basata sull'hash? La mappa generale basata su un albero binario funzionerà benissimo fintanto che la complessità garantisce che funzioni per il problema che stai risolvendo.

Answer 2

Un suggerimento: dai un'occhiata a questo post SO: "I don't understand std::tr1::unordered_map".

Inoltre, la Boost Documentation su Equality Predicates and Hash Predicates è un buon posto (oltre a questo example).

Answer 3

boost::hash modulo libreria funzionale.

o scrivi il tuo. versione più semplice = pair.first * max_second_value + pair.second

Answer 4

Il modo naturale per eseguire l'hash di una coppia è combinare gli hash dei suoi componenti in qualche modo. Il modo più semplice è solo con 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 

Si noti che questo hash coppie come (1,1) o (2,2) tutto a zero, quindi si potrebbe desiderare di utilizzare un modo più complesso per combinare il hash delle parti, a seconda dei dati. Boost fa qualcosa di simile:

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