Hash function for a pair of long long?

Question

I need to map a pair of long long to a double, but I'm not sure what hash function to use. Each pair may consist of any two numbers, although in practice they will usually be numbers between 0 and about 100 (but again, that's not guaranteed).

Here is the tr1::unordered_map documentation. I started like this:

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 general, I'm never sure what hash function to use. What's a good general-purpose hash function?

Answer 1

The natural way to hash a pair is to combine the hashes of its components in some way. The most simple way is just with 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

Note that this hashes pairs like (1,1) or (2,2) all to zero, so you might want to use some more complex way to combine the hashes of the parts, depending on your data. Boost does something like this:

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