8

When using the boost library, the fuction boost::hash_combine works like this:

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

http://www.boost.org/doc/libs/1_46_1/doc/html/hash/reference.html#boost.hash_combine

What is the advantage of this approach vs simply XOR-ing?

With XOR-ing, one can even use the hash function to use unordered containers as keys, while this one is order dependent.

Dale Myers
  • 2,703
  • 3
  • 26
  • 48
k_l
  • 189
  • 1
  • 3
  • 10
    Having {1,2} hash differently than {2,1} is often considered a good thing... – Marc Glisse Apr 26 '15 at 21:37
  • 1
    Please see http://stackoverflow.com/questions/8513911/how-to-create-a-good-hash-combine-with-64-bit-output-inspired-by-boosthash-co; this territory is beaten to death – sehe Apr 26 '15 at 22:41

1 Answers1

4

There are many ordered containers such as lists. If you would use XOR then you would basically say that [0, 1] is the same as [1, 0]. That's obviously not the case. It's much easier to override the method for unordered containers than to impose one that will create a lot of collisions for ordered ones. XOR has a lot of other nasty properties. For instance, if you have duplicate elements then they will cancel each other out.

In the end the idea for a hash is to be reasonably sure that you don't get the same value for multiple elements. XOR doesn't fit that property by itself.

Maarten Bodewes
  • 90,524
  • 13
  • 150
  • 263