为boost哈希映射定义自定义哈希函数

Question

我对C++非常陌生，我需要将用C编写的一些代码转换为C++。问题是，我发现C++语法在运行中很难理解。我希望使用无序的boost哈希映射，我希望定义我自己的哈希函数。我抬起头怎么做，我整个这一段代码跑：

struct ihash 
    : std::unary_function<std::string, std::size_t> 
{ 
    std::size_t operator()(std::string const& x) const 
    { 
     std::size_t seed = 0; 
     std::locale locale; 

     for(std::string::const_iterator it = x.begin(); 
      it != x.end(); ++it) 
     { 
      boost::hash_combine(seed, std::toupper(*it, locale)); 
     } 

     return seed; 
    } 
}; 

Which you can then use in a case insensitive dictionary: 

boost::unordered_map<std::string, int, ihash, iequal_to> idictionary; 

我有以下的散列函数：

unsigned long hash (unsigned char *str) 
{ 
    unsigned long hash = 5381; 
    int c; 

    while(c = *str++) 
    hash = ((hash << 5) + hash) + c; /* hash + 33 + c */ 
    hash %= outer_relation->hash_table.bucket_count(); 

    return hash; 
} 

有人能帮我转换。特别是种子和结合体负责什么？

Answer 1

如果你想使用自己的哈希为什么不实施ihash这样的事情？

struct ihash : std::unary_function<std::string, std::size_t> { 
    std::size_t operator()(std::string const& value) const { 
    std::size_t hash = 5381; 
    const char* str = value.c_str(); 
    int c; 
    while(c = *str++) 
    hash = ((hash << 5) + hash) + c; /* hash + 33 + c */ 
    hash %= outer_relation->hash_table.bucket_count(); 
    return hash; 
    } 
} 

Answer 2

第一个（ihash）是通用散列，以函数对象的形式实现。这有几个优点：

• 这是通用的，这意味着，你可以用不同容量/负载因子的哈希表使用它不知道/关心内部组织

• ，因为它是一个可调用的对象，这是缺省构造的，你其实可以“公正”实例化无序地图：

  boost::unordered_map<std::string, int, ihash, iequal_to> idictionary; 
  

  然后将使用ihash默认构造的实例作为散列函数（同为iequal_to，对于这个问题）。

第二个看起来像硬件连接到哈希表实现的哈希函数。显然，这个哈希表实现假设所有的密钥必须是unsigned char*，并且它将派生一个桶索引作为哈希实现的一部分。注：

• 不能舒适地使用此为默认constructible地图：

  boost::unordered_map<std::string, int, unsigned long(*)(unsigned char*), iequal_to> idictionary; 
  

  ，因为这将导致nullptr实例哈希函数。所以你最终会将&hash传递给一个构造函数。这将是很难推理你的代码，因为它不是不可能通过错误的函数指针，只要原型匹配

• 此函数假定键不能包含嵌入的NULL字符（东西是不是限制了std::string

• 此功能不是const的，正确的是（这意味着你不能使它成为map或unordered_map工作，除非你添加的常量，如size_t (*)(unsigned char const*)）。

除了这些意见，这两个功能基本上做同样的工作，其中ihash根据全球C++语言环境（see docs）确实进行了大小写折叠。

我不完全确定你卡在哪里，因为你的示例看起来应该比较完整？所以，在这里不用一点自我包含的样本的情况下，它可以帮助你摆脱这种困境：

#include <boost/unordered_map.hpp> 
#include <boost/algorithm/string/predicate.hpp> 
#include <iostream> 

namespace hash_examples 
{ 
    struct iequal_to 
     : std::binary_function<std::string, std::string, bool> 
    { 
     iequal_to() {} 
     explicit iequal_to(std::locale const& l) : locale_(l) {} 

     template <typename String1, typename String2> 
     bool operator()(String1 const& x1, String2 const& x2) const 
     { 
      return boost::algorithm::iequals(x1, x2, locale_); 
     } 
    private: 
     std::locale locale_; 
    }; 

    struct ihash 
     : std::unary_function<std::string, std::size_t> 
    { 
     ihash() {} 
     explicit ihash(std::locale const& l) : locale_(l) {} 

     template <typename String> 
     std::size_t operator()(String const& x) const 
     { 
      std::size_t seed = 0; 

      for(typename String::const_iterator it = x.begin(); 
       it != x.end(); ++it) 
      { 
       boost::hash_combine(seed, std::toupper(*it, locale_)); 
      } 

      return seed; 
     } 
    private: 
     std::locale locale_; 
    }; 
} 

int main() 
{ 
    using namespace hash_examples; 
    boost::unordered_map<std::string, int, ihash, iequal_to> map; 
    map.emplace("one", 1); 
    map.emplace("two", 2); 
    map.emplace("three", 3); 

    std::cout << map.at("TWO"); 
} 

注意，hash_examples都是直接从http://www.boost.org/doc/libs/1_55_0/libs/unordered/examples/case_insensitive.hpp

看到它Live On Coliru