如何编写 C++ 无序容器的哈希函数

当使用自定义类型作为 unordered_map/unordered_set 的 key 时，哈希函数应该如何实现？

在2005年TR1发布之前，C++社区的标准库中没有哈希表。一个理想的状态是，原始的标准库中应该有哈希映射和哈希集合的容器。

到 2005 年，已经有足够多的非标准实现允许TR1 扩展四个新的模板类：

• unordered_map
• unordered_multimap
• unordered_set
• unordered_multiset

通常使用容器的方式：

//
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include 
#include 
#include 

using namespace std;

typedef string Name;

int main(int argc, char* argv[])
{
    unordered_map ids;
    ids["Mark Nelson"] = 40561;
    ids["Andrew Binstock"] = 40562;
    for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
        cout << ii->first << " : " << ii->second << endl;
    return 0;
}

这个程序可以很好地运行，key 是 string 类型，是基本类型。但是我们在实际使用过程中，可能会使用自定义类型作为key，为简单起见，假设想将名字和姓氏分开，并使用 pair 保存姓名：

//
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include 
#include 
#include 

using namespace std;

typedef pair Name;

int main(int argc, char* argv[])
{
    unordered_map ids;
    ids[Name("Mark", "Nelson")] = 40561;
    ids[Name("Andrew","Binstock")] = 40562;
    for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
        cout << ii->first.first 
        << " "
        << ii->first.second 
        << " : "
        << ii->second
        << endl;
        return 0;
}

这个微小的改动，在Visual C++ 中会产生 7 个错误，g++ 中产生 5 个，并且没有任何错误指向问题发生的原因。

问题到底是什么呢？实际上非常简单：unordered_map 不知道如何为给定的 std::pair 键类型创建哈希值。但是用户看到的错误如下：

c:program filesmicrosoft visual studio 10.0vcincludexfunctional(768):
 error C2440: 'type cast' :
 cannot convert from 'const Name' to 'size_t'

或者 g++ 中更加糟糕的错误：

/tmp/cc0B9FPH.o: In function `std::__detail::_Hash_code_base, 
std::allocator >, std::basic_string, std::allocator > >, 
std::pair, std::allocator >, 
std::basic_string, std::allocator > > const, int>, 
std::_Select1st, std::allocator >, 
std::basic_string, std::allocator > > const, int> >, 
std::equal_to, std::allocator >, 
std::basic_string, std::allocator > > >, 
std::hash, std::allocator >, 
std::basic_string, std::allocator > > >, 
std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code(
std::pair, std::allocator >, 
std::basic_string, std::allocator > > const&) const'

Java 程序员并不会遇到类似的问题，因为Java语言在基类 Object 中定义了一个默认的哈希函数。任何 Java 对象都可以用作 Java 的 HashMap 泛型类中的键。虽然在很多情况下，基类中的定义可能并不是最好的，但它至少可以运行。

template,
    class Pred = std::equal_to,
    class Alloc = std::allocator > >
    class unordered_map;

unordered_map 的定义如上，其中第三个参数是函数对象类型，用于将一个 key 转换为 哈希值。它默认被设置为 std::hash。在 unordered_map 内部会调用该类型对象的 operator() 函数。

还需要注意的是，unordered_map 的几个构造函数也采用默认参数，该参数是此函数对象类型的实例。

所以有两个地方我们可以提供一些关于如何对 unordered_map 中使用的键进行哈希处理的信息，但通常不填写这些项目。经常不这样做的原因是 C++ 标准库已经为常用类型定义了 std::hash 的实例。所以可以编写一个包含这样一行的程序：

int main(int argc, char* argv[])
{
    cout << std::hash()("Mark Nelson") << endl;
    return 0;
}

运行得到：

134514544

当然，问题在于标准库没有实现 hash> 的版本 - 或任何其他无限种类的用户定义类。

但是，由于 Name 类由两个 string 对象组成，并且标准库知道如何对 string 对象进行哈希处理，因此我可以自己创建一个非常好的哈希函数，如下所示：

size_t name_hash( const Name & name )
{
    return hash()(name.first) ^ hash()(name.second);
}

一般经验而言，如果我有两个独立变量的哈希值，使用 XOR 将它们结合起来，我可以预期得到的哈希值可能与输入哈希值一样好。

构建好了哈希函数，实际使用 unordered_map：

unordered_map> ids(100, name_hash );

这样写比较重复冗余，C++ 中提供了 decltype 关键字，可以把哈希函数的类型作为一个模板参数传给它：

//
// This program uses a simple user-defined function
// to provide a hash function for use in unordered_map
// 
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include 
#include 
#include 
#include 

using namespace std;

typedef pair Name;

size_t name_hash( const Name & name )
{
    return hash()(name.first) ^ hash()(name.second);
}

int main(int argc, char* argv[])
{
	unordered_map ids(100, name_hash );
	ids[Name("Mark", "Nelson")] = 40561;
	ids[Name("Andrew","Binstock")] = 40562;
	for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
		cout << ii->first.first 
                     << " "
                     << ii->first.second 
                     << " : "
                     << ii->second
                     << endl;
	return 0;
}

//
// This program uses a simple user-defined function
// to provide a hash function for use in unordered_map.
// The function is passed in as a lambda expression to
// the unordered_map constructor.
// 
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include 
#include 
#include 
#include 

using namespace std;

typedef pair Name;

int main(int argc, char* argv[])
{
    unordered_map> 
    ids(100, []( const Name & name )
             {
                 return hash()(name.first) ^ hash()(name.second);
             } );
    ids[Name("Mark", "Nelson")] = 40561;
    ids[Name("Andrew","Binstock")] = 40562;
    for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
        cout << ii->first.first 
             << " "
             << ii->first.second 
             << " : "
             << ii->second
             << endl;
    return 0;
}

其实生成的代码和方法1中的是相同的，只是使用了Lambda语法而已。

struct hash_name {
    size_t operator()(const Name &name ) const
    {
        return hash()(name.first) ^ hash()(name.second);
    }
};

使用这个函数对象定义 unordered_map 时，代码会简单一些：

unordered_map ids;

可以看到，仍然要包含第三个模板类参数，但不必在构造函数中传入对函数对象的引用。这是因为 unordered_map 跟踪类定义，当需要实际获取哈希时，它可以简单地即时构造对象并传入数据。执行此操作的示例（假设）类可能具有如下代码：

template 
class HashMap {
...
void insert( HashKey &key, HashVal &val )
{
    size_t index = HashObject()( key );
...

完整的示例程序：

//
// This program uses a function object to define
// a hash function for use in unordered_map.
// 
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include 
#include 
#include 
#include 

using namespace std;

typedef pair Name;

struct hash_name {
   size_t operator()(const Name &name ) const
   {
       return hash()(name.first) ^ hash()(name.second);
   }
};

int main(int argc, char* argv[])
{
   unordered_map ids;
   ids[Name("Mark", "Nelson")] = 40561;
   ids[Name("Andrew","Binstock")] = 40562;
   for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
       cout << ii->first.first 
            << " "
            << ii->first.second 
            << " : "
            << ii->second
            << endl;
   return 0;
}

当你将 unordered_map 和 所有的默认参数一起使用时，它尝试使用 std::hash 类型的函数对象来创建您的哈希键。如前面所讨论的那样，自定义类型之所以不能正常运行的原因是没有为你的特定类创建哈希对象的特化。在许多情况下，这是因为您的特定类还没有被创建出来。

按理说，如果你正在实现一个被其他人使用的类，可能为这个类创建哈希类的实例是非常好的。当您这样做并在定义您的类的头文件中包含定义时，其他人将能够将您的类用作任何无序容器的键，而无需任何额外操作。

为您的类定义 std::hash 的特化实际上与上面的方法 3 没有什么不同，唯一的区别是必须为你的类使用 hash 这个名称，并且您必须将其定义为该模板类的特化，最后，您必须将所有操作提升到 std 命名空间中。

//
// This program uses a specialization of
// std::hash to provide the function
// object needed by unordered_map.
// 
// Compile this example with Visual Studio 2010
// or g++ 4.5 using -std=c++0x
//
#include 
#include 
#include 
#include 

using namespace std;

typedef pair Name;

namespace std {
    template <>
        class hash{
        public :
            size_t operator()(const Name &name ) const
            {
                return hash()(name.first) ^ hash()(name.second);
            }
    };
};

int main(int argc, char* argv[])
{
    unordered_map ids;
    ids[Name("Mark", "Nelson")] = 40561;
    ids[Name("Andrew","Binstock")] = 40562;
    for ( auto ii = ids.begin() ; ii != ids.end() ; ii++ )
        cout << ii->first.first 
             << " "
             << ii->first.second 
             << " : "
             << ii->second
             << endl;
	return 0;
}

除了需要哈希函数，无序容器也需要能够测试两个键是否相等。执行此操作的规范方法是使用在全局命名空间中定义的 operator==() 版本。这通常是在创建新类时应该要构造的函数，但如果忽略它，将遇到本文前面看到的同样大量难以理解的编译器错误

在本文中处理无需它，因为标准库已经为 std::pair 定义了这个运算符。当然，在使用 std::pair 时，您还必须确保有 T1 和 T2 的相等运算符。

总结来说，如果要将自定义类型作为 unordered_map 的键值，需要如下两个步骤：

• 定义哈希函数的函数对象；
• 定义等比函数的函数对象或者在自定义类里重载 operator==()

1、Hash Functions for C++ Unordered Containers

2、【侯捷】C++STL标准库与泛型编程（第四讲）

3、C++ STL：unordered_map 自定义键值类型