Fast hash for std::set<int> of two values?

Question

I am using a std::set<int> for the key of a std map (std::unordered_map<std::Set<int>,float>). I need a hash for this set.

The set will always be only two integers, whose values could be up to 2 million.

Any ideas on a good and fast hash for such a key as performance is critical?

Answer 1

I'd ditch the set idea (it is a waste of both memory and time to store two integers in a std::set) and go with the pair. Then define

template <class A>
struct unordered_pair_hash
{
  std::size_t operator()(const std::pair<A, A>& p) const { 
    using std::min;
    using std::max;
    return std::hash(min(p.first, p.second))+
        17*std::hash(max(p.first, p.second));
  }
};

template <class A>
struct unordered_pair_eq
{
  bool operator()(const std::pair<A, A>& p1, const std::pair<A, A>& p2) const {
    using std::min;
    using std::max;
    return min(p1.first, p1.second)==min(p2.first, p2.second) &&
           max(p1.first, p1.second)==max(p2.first, p2.second);
  }
};

and then declare the map with a custom hash and equality.

std::unordered_map<std::pair<int, int>, float, unordered_pair_hash<int>, unordered_pair_eq<int> > ...

Answer 2

You could use boost::hash_combine() : http://www.boost.org/doc/libs/1_44_0/doc/html/hash/combine.html

Answer 3

You didn't exactly state what the purpose of your lookup is, but maybe you should (or shouldn't):

• simply use a struct { int a, b; } as a key - you control the insertion of the members (make sure a <= b)

• use a Sparse Matrix implementation

Regards

rbo