The Question
What is a good specialization of std::hash for use in the third template parameter of std::unordered_map or std::unordered_set for a user defined type for which all member data types already have a good specialization of std::hash?
For this question, I define "good" as simple to implement and understand, reasonably efficient, and unlikely to produce hash table collisions. The definition of good does not include any statements about security.
The State of What is Google'able
At the moment, two StackOverflow questions are the first hits for a Google search of "std hash specialization".
The first, How to specialize std::hash::operator() for user-defined type in unordered containers?, addresses whether it is legal to open the std namespace and add template specializations.
The second, How to specialize std::hash for type from other library, essentially addresses that same question.
This leaves the current question. Given that implementations of the C++ Standard Library defined hash functions for primitive types and types in the Standard Library, what is a simple and effective way of specializing std::hash for user defined types? Is there a good way to combine hash functions provided by a Standard Library implementation?
(Edit thanks to dyp.) Another question on StackOverflow addresses how to combine a pair of hash functions.
The other Google results are of no more help.
This Dr. Dobbs article states that XOR of two satisfactory hashes will produce a new satisfactory hash.
This articles seems to speak from knowledge and implies many things but is light on details. It contradicts the Dr. Dobbs article in a brief remark in the first example, saying that using XOR to combine hash functions makes for a weak resulting hash function.
Because XOR applied to any two equal values results in 0, I can see why XOR by itself is weak.
The Meta Question
A well reasoned answer explaining why this question is invalid and cannot be answered generally would also be welcome.
One easy way is to use boost::hash
library and extend it for your type. It has a nice extension function hash_combine
(std::hash
lacks that) that allows easy composition of hashes of individual data members of your structures.
In other words:
boost::hash_value
for your own type.std::hash
for your own type and implement it using boost::hash_value
.This way you get the best of std and boost worlds, both std::hash<>
and boost::hash<>
work for your type.
A better way is to use the proposed new hashing infrastructure in N3980 Types Don't Know #. This infrastructure makes hash_combine
unnecessary.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With