How to properly hash a pair of pointers?

Question

I have a std::unordered_map with keys of type std::pair<T*, T*> (i.e., a pair of pointers).

The code base has the following hash functor defined:

struct pair_hash {
  template<typename T>
  std::size_t operator()(std::pair<T, T> const &p) {
    return (std::hash<T>()(p.first) + 0x9e3779b9) ^ (std::hash<T>()(p.second) + 0x9e3779b9);
  }
};

And is used as:

std::unordered_map<std::pair<T*, T*>, U, pair_hash> myDictionary;

where U is an arbitrary object.

Now the hash functor displayed above must have certain issues because in VC++ it gives me an out of bounds crash in std::unordered_map::find.

Q:

Could it be that my hash functor is problematic or this behaviour is attributed to VC++ itself?
Is there a "proper/more proper" way to hash a pair of pointers?

Why not use [`std::hash`](http://en.cppreference.com/w/cpp/utility/hash)? — NathanOliver, Sep 07 '16 at 12:45
@NathanOliver: There is no `std::hash` for `std::pair`, which is the problem. `std::hash` for pointer exists and he uses it to implement the hash function for pair. — michalsrb, Sep 07 '16 at 12:51
@michalsrb Doh. I forgot you have to make your own for `std::pair`. — NathanOliver, Sep 07 '16 at 12:53
Down-voter care to comment on your down-vote. And how this question is off-topic? — 101010, Sep 07 '16 at 14:41

michalsrb · Answer 1 · 2016-09-07T12:49:12.300

2

return (std::hash<T>()(p.first) + 0x9e3779b9) ^ (std::hash<T>()(p.first) + 0x9e3779b9);
//                                                                ^^^^^
//                                                              p.second!
//                                                                         ^^^^^^^^^^
// Choose different magic constant to prevent collisions between (p1, p2) and (p2, p1)

Your function was returning zero for every pair of pointers. Therefore you were getting lots of collisions in the unordered_map.

edited Sep 07 '16 at 12:49

answered Sep 07 '16 at 12:43

michalsrb

4,703
1
18
35

1

Nice to know, but is there a better hashing for a pair of pointers? Plus I corrected the `p.second` part. – 101010 Sep 07 '16 at 13:15
@101010, how is your combiner bad? What test have you performed to know it doesn't fit your needs? – StoryTeller - Unslander Monica Sep 07 '16 at 13:22
1

@StoryTeller I didn't run any. VC++ crashes at `std::unordered_map::find` because of this hasher. Perhaps you could en-light me and suggest some. – 101010 Sep 07 '16 at 13:26
@101010, even after the fix? – StoryTeller - Unslander Monica Sep 07 '16 at 13:27
@StoryTeller No there's no fix, that was accidentally written by me in the question. The original code is the one with the correction. – 101010 Sep 07 '16 at 13:27

score 2 · Answer 2 · answered Sep 07 '16 at 13:12

2

If you can use Boost, there's a very useful hash_combine function that you could use.

answered Sep 07 '16 at 13:12

Bartek Banachewicz

38,596
7
91
135

1

And even if you can't, it's simple enough to roll out your own by boosts example – StoryTeller - Unslander Monica Sep 07 '16 at 13:16

How to properly hash a pair of pointers?

Q:

2 Answers2