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

Do you really need a hash based map? The general map based on a binary tree will work fine as long as the complexity guarantees it makes work for the problem you are solving.

Answer 2

A suggestion: Take a look at this SO post: "I don't understand std::tr1::unordered_map".

Also, the Boost Documentation on Equality Predicates and Hash Predicates is a good place too (as well as this example).

Answer 3

boost::hash form functional library.

or write your own. simplest version = pair.first * max_second_value + pair.second

Answer 4

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);