boost::hash_combine vs simple XOR'ing

2020-07-08 07:19发布

问题:

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.

回答1:

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.



标签: c++ boost hash