如何专门化std :: hash< T>用户定义类型？ [英] How to specialize std::hash<T> for user defined types?

问题描述

问题

什么是std :: hash的一个很好的特化，用于std :: unordered_map的第三个模板参数， std :: unordered_set对于所有成员数据类型已经具有很好的std :: hash特殊化的用户定义类型？

对于这个问题，我定义good实现和理解简单，相当高效，并且不可能产生哈希表冲突。好的定义不包括任何有关安全性的声明。

Google的功能状态

目前，两个StackOverflow问题是Google搜索std hash specialization的第一个命中。

第一个，如何专门化std :: hash :: operator（）

第二个是如何专门化std ::哈希类型从其他库，基本上解决了同样的问题。

这留下了当前的问题。鉴于C ++标准库的实现在标准库中为原始类型和类型定义了哈希函数，什么是专门用于用户定义类型的std :: hash的简单有效的方法？有没有很好的方法来组合标准库实现提供的散列函数？

（编辑感谢dyp。） StackOverflow上的另一个问题解决了如何组合散列函数的对。

其他Google搜索结果没有更多帮助。

这文章似乎从知识中说出来，意味着许多事情，但对细节却很清楚。它与Dobbs博士在第一个例子中的简短说明相矛盾，说使用XOR来组合散列函数使得结果散列函数很弱。

因为XOR应用对任何两个相等的值导致0，我可以看到为什么XOR本身是弱的。

元问题
$ b

一个解释为什么这个问题无效，一般不能回答的很好的理由的回答也会受到欢迎。

解决方案

一个简单的方法是使用 boost :: hash 库和将其扩展为您的类型。它有一个很好的扩展函数 hash_combine （ std :: hash 缺少），允许轻松组合结构的单个数据成员的散列。

换句话说：

1. 重载


2. 为您自己的类型专门化 std :: hash 使用 boost :: hash_value 。

和促进世界， std :: hash<> 和 boost :: hash<> 。

---

更好的方法是在 N3980类型不知道＃。此基础结构使 hash_combine 不必要。

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:

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.

这篇关于如何专门化std :: hash< T>用户定义类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！