19

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?

  • 21
    Have you considered using one or more of the following general purpose hash functions: http://www.partow.net/programming/hashfunctions/index.html they are extremely fast and efficient. –  Jan 23 '11 at 10:11

4 Answers4

10

boost::hash form functional library.

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

bayda
  • 13,365
  • 8
  • 39
  • 48
10

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);
sth
  • 222,467
  • 53
  • 283
  • 367
  • 1
    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)); – velkyel Jul 23 '14 at 10:46
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).

Community
  • 1
  • 1
dirkgently
  • 108,024
  • 16
  • 131
  • 187
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.

lothar
  • 19,853
  • 5
  • 45
  • 59
  • Hmm okay, in that case, what would the Compare function that compares two IntPairs look like (the `less` function for IntPairs)? –  Apr 10 '09 at 15:55
  • @Frank: simplest form: (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)) – David Rodríguez - dribeas Apr 10 '09 at 16:19
  • This one (a.first < b.first) && (a.second < b.second) would also work, right? –  Apr 10 '09 at 17:34
  • @Frank: They both define an ordering they are just different. I prefer '@dribeas' version it seems more logical (but slightly more expensive) – Martin York Apr 10 '09 at 20:18
  • Actually, I found that std::pair already defines the operator<, so I don't need to provide my own compare object. –  Apr 10 '09 at 20:23
  • 3
    @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". – Piotr Findeisen Jun 02 '09 at 17:12