unordered_map 哈希函数 C++
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7222143/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
unordered_map hash function c++
提问by Vladp
I need to define an unordered_map like this unordered_map<pair<int, int>, *Foo>, what is the syntax for defining and passing a hashand equalfunctions to this map?
我需要像这样定义一个 unordered_map unordered_map<pair<int, int>, *Foo>，定义和传递 ahash和equal函数到这个地图的语法是什么？
I've tried passing to it this object:
我试过把这个对象传递给它：
class pairHash{
public:
long operator()(const pair<int, int> &k) const{
return k.first * 100 + k.second;
}
};
and no luck:
没有运气：
unordered_map<pair<int, int>, int> map = unordered_map<pair<int, int>, int>(1,
*(new pairHash()));
I have no Idea what is the size_type_Busketsmeans so I gave it 1.
What is the right way to do it?
Thanks.
我不知道是什么size_type_Buskets手段所以我给了它1。正确的做法是什么？谢谢。
回答by Kerrek SB
This is an unfortunate omission in C++11; Boost has the answer in terms of hash_combine. Feel free to just paste it from them! Here's how I hash pairs:
这是 C++11 中的一个不幸的遗漏；Boost 在 方面给出了答案hash_combine。随意从他们那里粘贴它！这是我如何散列对：
template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
namespace std
{
template<typename S, typename T> struct hash<pair<S, T>>
{
inline size_t operator()(const pair<S, T> & v) const
{
size_t seed = 0;
::hash_combine(seed, v.first);
::hash_combine(seed, v.second);
return seed;
}
};
}
You can use hash_combineas the basis for many other things, like tuples and ranges, so you could hash an entire (ordered) container, for example, as long as each member is individually hashable.
您可以hash_combine用作许多其他事物的基础，例如元组和范围，因此您可以散列整个（有序）容器，例如，只要每个成员都可以单独散列。
Now you can just declare a new map:
现在你可以声明一个新地图：
std::unordered_map<std::pair<int, int>, my_mapped_type> mymap;
If you want to use your homebrew hasher (which hasn't got good statistical properties), you have to specify the template parameters explicitly:
如果你想使用你的自制散列器（它没有很好的统计属性），你必须明确指定模板参数：
std::unordered_map<std::pair<int,int>, int, pairHash> yourmap;
Note that there's no need to specify a copy of a hasher object, as the default is to default-construct one for you.
请注意，无需指定 hasher 对象的副本，因为默认设置是为您默认构造一个。
回答by Praetorian
The return type of the hash function should be size_t, not long(although this is not the cause of the error). The syntax you've shown for providing a custom hash function is incorrect.
散列函数的返回类型应该是size_t，不是long（虽然这不是错误的原因）。您显示的用于提供自定义哈希函数的语法不正确。
You'll also need to provide an equal predicate to make the above work properly.
您还需要提供一个相等的谓词才能使上述内容正常工作。
#include <unordered_map>
#include <utility>
using namespace std;
class pairHash{
public:
size_t operator()(const pair<int, int> &k) const{
return k.first * 100 + k.second;
}
};
struct pairEquals : binary_function<const pair<int,int>&, const pair<int,int>&, bool> {
result_type operator()( first_argument_type lhs, second_argument_type rhs ) const
{
return (lhs.first == rhs.first) && (lhs.second == rhs.second);
}
};
int main()
{
unordered_map<pair<int, int>, int, pairHash, pairEquals> myMap;
myMap[make_pair(10,20)] = 100;
myMap.insert( make_pair(make_pair(100,200), 1000) );
}
EDIT:
You don't need to define the equal predicate since operator==is defined for std::pairand it does exactly what I've done in pairEquals. You'll only need the pairEqualsdefinition if you expect the comparison to be done differently.
编辑：
您不需要定义相等的谓词，因为operator==是为std::pair它定义的，它完全符合我在pairEquals. pairEquals如果您希望以不同的方式进行比较，则只需要定义。
回答by Paul Baltescu
If you are fine with using Boost, a cleaner solution is to rely on Boost's implementation of the hash function for pairs (which in fact does exactly what kerrek-sb explains in his answer). Therefore all you have to do is:
如果您可以使用 Boost，更简洁的解决方案是依赖 Boost 对散列函数的实现（实际上这正是 kerrek-sb 在他的回答中所解释的）。因此，您所要做的就是：
#include <unordered_map>
#include <boost/functional/hash.hpp>
using namespace std;
using namespace boost;
unordered_map<pair<int, int>, int, hash<pair<int, int>>> table;
