所有STL容器的泛型哈希函数 [英] Generic Hash function for all STL-containers
问题描述
我在我的实现中使用了一个 std :: unordered_map< key，value> 。我将使用任何STL容器作为关键。我想知道是否可以为正在使用的任何容器创建通用散列函数。
这个问题SO提供所有STL容器的通用打印功能。虽然你可以这样做，为什么不能像哈希函数那样定义一切？是的，也是一个很大的问题，它需要快速高效。
我正在考虑做一个简单的哈希函数，将键的值转换为 size_t 并执行一个简单的功能像此。
可以这样吗？
PS：请不要使用 boost 库。谢谢。
我们可以通过模仿Boost并组合哈希来获得答案。
$ b $警告：结合哈希算法，即从事物的许多哈希算出许多事物的哈希，通常不是一个好主意，因为生成的哈希函数在统计学上不是好感。应该从所有组成部分的整个原始数据构建许多事物的正确散列，而不是中间散列。但是目前还没有一个很好的标准方式。
无论如何：
首先，我们需要 hash_combine 函数。由于超出我的理解，它不包括在标准库中，但它是其他一切的核心：
template< class T>
inline void hash_combine（std :: size_t& seed，const T& v）
{
std :: hash< T>散列器;
seed ^ = hasher（v）+ 0x9e3779b9 +（seed<< 6）+（seed>> 2）;
}
使用这个，我们可以将散列的元素，对和元组（为读者练习）。
但是，我们也可以使用它来通过散列其元素来散列容器。这正是Boost的范围散列所做的，但是通过使用组合功能可以让自己变得简单。
完成写入范围的哈希，只是专注于 std :: hash ，你很好：
namespace std
{
template< typename T，class Comp，class Alloc>
struct hash< std :: set< T，Comp，Alloc>>
{
inline std :: size_t operator（）（const std :: set< T，Comp，Alloc>& s）const
{
return my_range_hash（s.begin （），s.end（））;
}
};
/ * ...同上其他容器* /
}
如果你想模仿漂亮的打印机，你甚至可以对所有的容器做一些更加极端的事情，并且专门为 std :: hash 而设计，但是我可能会更加小心使用它，并为容器创建一个显式的哈希对象：
template< typename C> struct ContainerHasher
{
typedef typename C :: value_type value_type;
inline size_t operator（）（const C& c）const
{
size_t seed = 0;
（typename C :: const_iterator it = c.begin（），end = c.end（）; it！= end; ++ it）
{
hash_combine< value_type>种子，*它）;
}
返回种子;
}
};
用法：
code> std :: unordered_map< std :: set< int>，std :: string，ContainerHasher< std :: set< int>>> X;
I'm using an std::unordered_map<key,value> in my implementation. i will be using any of the STL containers as the key. I was wondering if it is possible to create a generic hash function for any container being used.
This question in SO offers generic print function for all STL containers. While you can have that, why cant you have something like a Hash function that defines everything ? And yeah, a big concern is also that it needs to fast and efficient.
I was considering doing a simple hash function that converts the values of the key to a size_t and do a simple function like this.
Can this be done ?
PS : Please don't use boost libraries. Thanks.
We can get an answer by mimicking Boost and combining hashes.
Warning: Combining hashes, i.e. computing a hash of many things from many hashes of the things, is not a good idea generally, since the resulting hash function is not "good" in the statistical sense. A proper hash of many things should be build from the entire raw data of all the constituents, not from intermediate hashes. But there currently isn't a good standard way of doing this.
Anyway:
First off, we need the hash_combine function. For reasons beyond my understanding it's not been included in the standard library, but it's the centrepiece for everything else:
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);
}
Using this, we can hash everything that's made up from hashable elements, in particular pairs and tuples (exercise for the reader).
However, we can also use this to hash containers by hashing their elements. This is precisely what Boost's "range hash" does, but it's straight-forward to make that yourself by using the combine function.
Once you're done writing your range hasher, just specialize std::hash and you're good to go:
namespace std
{
template <typename T, class Comp, class Alloc>
struct hash<std::set<T, Comp, Alloc>>
{
inline std::size_t operator()(const std::set<T, Comp, Alloc> & s) const
{
return my_range_hash(s.begin(), s.end());
}
};
/* ... ditto for other containers */
}
If you want to mimic the pretty printer, you could even do something more extreme and specialize std::hash for all containers, but I'd probably be more careful with that and make an explicit hash object for containers:
template <typename C> struct ContainerHasher
{
typedef typename C::value_type value_type;
inline size_t operator()(const C & c) const
{
size_t seed = 0;
for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it)
{
hash_combine<value_type>(seed, *it);
}
return seed;
}
};
Usage:
std::unordered_map<std::set<int>, std::string, ContainerHasher<std::set<int>>> x;
这篇关于所有STL容器的泛型哈希函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
