¿Función hash para un par de largo?

Question

Necesito asignar un par de long long a un double, pero no estoy seguro de qué función hash usar. Cada par puede consistir en dos números, aunque en la práctica generalmente serán números entre 0 y aproximadamente 100 (pero una vez más, eso no está garantizado).

Here es la documentación tr1::unordered_map. Empecé como esto:

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 general, nunca estoy seguro de qué función hash para su uso. ¿Cuál es una buena función hash de propósito general?

Answer 1

¿Realmente necesita un mapa basado en hash? El mapa general basado en un árbol binario funcionará bien siempre que la complejidad garantice que funciona para el problema que está resolviendo.

Answer 2

Una sugerencia: Tome un vistazo a este SO mensaje: "I don't understand std::tr1::unordered_map".

Además, la Documentación de Boost en Equality Predicates and Hash Predicates es un buen lugar también (así como también example).

Answer 3

boost::hash biblioteca funcional de la forma.

o escriba el suyo. versión más simple = pair.first * max_second_value + pair.second

Answer 4

La forma natural de unir un par es combinar los hash de sus componentes de alguna manera. La forma más sencilla es sólo 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 

Tenga en cuenta que este hash pares como (1,1) o (2,2) todos a cero, por lo que es posible que desee utilizar alguna forma más compleja de combinar la hash de las partes, según sus datos. Boost hace algo como esto:

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