c++ - unordered_map 的用户定义哈希函数

Question

我正在尝试在 STL unordered_map 上创建一个模板化包装类。我将散列函数类作为模板参数传递给包装器类，并提供了字符串特化。下面的代码编译并工作，但如果包含注释部分，则编译错误:

"/usr/include/c++/6/bits/unordered_map.h:143:28: error: no matching function for call to ‘HashFunction

::HashFunction()’ const hasher& __hf = hasher(),".

但是，我必须拥有散列函数类的构造函数。我尝试了各种方法，但无法使其工作。请提供您的想法/意见。

#include <iostream>
#include <unordered_map>
using namespace std;

template< class Key >
class HashFunction
{
  public:
    //HashFunction( const Key & inKey );
    size_t operator()(const Key &inKey) const;
  private:
    unsigned mHashCode;
};

//template<>
//HashFunction< string >::HashFunction( const string & inKey )
//{
    //mHashCode=std::hash<string>{}(inKey);
//}

template <> 
size_t HashFunction< string >::operator()(const string &inKey) const 
{
  return std::hash<string>{}(inKey);
  //return mHashCode;
}

template< class Key, class Val, class Hash = HashFunction< Key > >
class unordered_map_wrapper
{
  public:
   unordered_map_wrapper();
  private:
    unordered_map<Key, Val, Hash> * mTable;
};

template< class Key, class Val, class Hash >
unordered_map_wrapper< Key, Val, Hash >::unordered_map_wrapper()
{
    mTable=new unordered_map<Key, Val, Hash>(10);
}

int main() {
    unordered_map_wrapper<string, unsigned> h;
    return 0;
}

Answer 1

这不是 Hash 模板参数在 std::unordered_map 中的工作方式!该映射创建一个 Hash 实例(使用默认构造函数，因此您需要提供它!)，用于进一步需要的所有哈希计算。所以你的类必须看起来像这样:

template<class Key>
class HashFunction
{
public:
    // HashFunction(); <- can just leave it out...
    size_t operator()(const Key& inKey) const;
};

template<>
size_t HashFunction<std::string>::operator()(const std::string& inKey) const
{
    // calculate hash value in operator!!!
    return std::hash<std::string>()(inKey);
}

不过，为了避免一直构造 std::hash，我宁愿专门化整个模板类:

template<class Key>
class HashFunction; // leave entirely unimplemented
                    // (if it has no general meaning, at least...)

template<>
class HashFunction<std::string>
{
public:
    size_t operator()(const std::string& inKey) const
    {
        return mHash(inKey);
    }
private:
    std::hash<std::string> mHash;
};

不过，重新实现已经存在的东西没有多大意义。我可以假设您在这里使用 std::string 只是作为您自己的类的占位符吗？

顺便说一下:一个简单的 typedef 会比你的包装类更容易完成这项工作:

template <typename Key, typename Value>
using my_unordered_map = std::unordered_map<Key, Value, HashFunction<Key>>;

也许您也对替代品感兴趣？首先假设您有两个类(而不是 std::string):

class C1
{ };
class C2
{ };

最优雅的解决方案(至少在我看来)是简单地将 std::hash 专门化为您的类(虽然通常情况下，向 std 命名空间添加某些内容是非法的，模板专门化是异常(exception)......):

namespace std
{
template<>
class hash<C1>
{
public:
    size_t operator()(C const& c) const
    {
        return 0; // your implementation here...
    }
};
// same for C2
}

// no typedef necessary, just use std::unordered_map directly:
std::unordered_map<C1, unsigned> m1;
std::unordered_map<C2, unsigned> m2;

您可以提供自己的 HashFunction 类，提供重载:

class HashFunction
{
public:
    size_t operator()(C1 const& c) const
    {
        return 0;
    }
    size_t operator()(C2 const& c) const
    {
        return 0;
    }
};

同样，typedef 让您的生活更轻松:

template <typename Key, typename Value>
using my_unordered_map = std::unordered_map<Key, Value, HashFunction>;

std::unordered_map<C1, unsigned, HashFunction> m1;
my_unordered_map<C1, unsigned> m1_;

std::unordered_map<C2, unsigned, HashFunction> m2;
my_unordered_map<C2, unsigned> m2_;

最后，如果您绝对需要使用一些参数初始化您的 HashFunction 以正确配置它，您可以这样做，但您必须提供一个预配置的实例然后到你的 HashMap !

template<typename T>
class HashFunction
{
public:
    HashFunction(double value);
    size_t operator()(T const& c) const;
private:
    double data;
};

template<typename T>
HashFunction<T>::HashFunction(double value)
        : data(value)
{ }

template<>
size_t HashFunction<C1>::operator()(C1 const& c) const
{
    return static_cast<size_t>(data);
};
template<>
size_t HashFunction<C2>::operator()(C2 const& c) const
{
    return static_cast<size_t>(data);
};

template <typename Key, typename Value>
using my_unordered_map = std::unordered_map<Key, Value, HashFunction<Key>>;

my_unordered_map<C1, unsigned> m1(12, HashFunction<C1>(10.12));
my_unordered_map<C2, unsigned> m2(10, HashFunction<C2>(12.10));

好吧，现在，至少，你的包装类可以再次派上用场了:

template <typename Key, typename Value, typename Hash = HashFunction<Key>>
class unordered_map_wrapper
{
public:
    unordered_map_wrapper()
        : mMap(16, Hash())
    { }
    unordered_map_wrapper(double parameter)
        : mMap(16, Hash(parameter))
    { }
private:
    std::unordered_map<Key, Value, Hash> mMap;
};

unordered_map_wrapper<C1, unsigned> m1(10.12);
unordered_map_wrapper<C2, unsigned> m2(12.10);
// possible due to provided default ctor:
unordered_map_wrapper<std::string, unsigned, std::hash<std::string>> m3;