Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to specialize std::hash<T> for user defined types?

Tags:

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.

like image 530
Praxeolitic Avatar asked Jun 23 '14 08:06

Praxeolitic


1 Answers

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:

  1. Overload boost::hash_value for your own type.
  2. Specialize 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.

like image 74
Maxim Egorushkin Avatar answered Oct 01 '22 23:10

Maxim Egorushkin