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?

Boycott

Have you considered using one or more of the following general purpose hash functions: partow.net/programming/hashfunctions/index.html they are extremely fast and efficient. – Sectarian

Answer 1

boost::hash form functional library.

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

Rudy

Answer 2

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

Gherlein

Please read boost hash.hpp more carefully. Bost does something like this: seed = hash(first) + 0x9e3779b9 + (seed<<6) + (seed>>2); return seed ^ (hash(second) + 0x9e3779b9 + (seed<<6) + (seed>>2)); – Coax

Answer 3

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

Mediator

Answer 4

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.

Unwept

Hmm okay, in that case, what would the Compare function that compares two IntPairs look like (the less function for IntPairs)? – Boycott

@Frank: simplest form: (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)) – Psychopath

This one (a.first < b.first) && (a.second < b.second) would also work, right? – Boycott

@Frank: They both define an ordering they are just different. I prefer '@dribeas' version it seems more logical (but slightly more expensive) – Corettacorette

Actually, I found that std::pair already defines the operator<, so I don't need to provide my own compare object. – Boycott

@Framk, @Martin: (a.first < b.first) && (a.second < b.second) is not an ordering. Pairs (1,0) and (0,1) are different and incomparable in this "ordering". – Outrider