c++ - 为 boost HashMap 定义自定义哈希函数

Question

我是 C++ 的新手，我需要将一些用 C 编写的代码转换为 C++。问题是我发现 C++ 语法很难即时理解。我希望使用无序的 boost HashMap ，并且我希望定义我自己的哈希函数。我查看了如何执行此操作，然后遇到了这段代码:

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;
}

有人可以帮助我进行转换吗？特别是，种子和 union 收割机负责什么？

Answer 1

第一个 (ihash) 是通用哈希，以函数对象的形式实现。这有几个优点:

• 它是通用的，这意味着您可以将它与不同容量/负载因子的哈希表一起使用，而无需了解/关心内部组织

• 因为它是一个可调用对象，并且默认可构造，您实际上可以“只”实例化无序映射:

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

  然后它将使用 ihash 的默认构造实例作为哈希函数(对于 iequal_to，就此而言也是如此)。

第二个看起来像是硬连线到哈希表实现中的哈希函数。显然，这个哈希表实现假定所有键都必须是 unsigned char*，并且它派生了一个桶索引作为哈希实现的一部分。备注:

• 您不能轻松地将其用于默认可构建的 map :

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

  因为这会导致散列函数的 nullptr 实例。所以你最终会一直将 &hash 传递给构造函数重载。推理你的代码会更难，因为传递错误的函数指针并非不可能，只要原型(prototype)匹配

• 此函数假定键不能包含嵌入的 NUL 字符(这不是 std::string

的限制)
• 这个函数不是常量正确的(意味着你不能让它为 map 或 unordered_map 工作，除非你添加了常量，例如 size_t (*) (unsigned char const*)).

除了这些观察之外，这两个函数基本上做相同的工作，其中 ihash 根据全局 C++ 语言环境 (see docs) 进行大小写 fold 。

我不确定您卡在哪里，因为您的示例看起来应该相对完整？因此，这里有一个独立的小示例，以防它帮助您摆脱困境:

#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