C++ hash(STL hash)及其函数模板用法详解

如果在容器中保存对象及其关联的键，并且不用键来决定 键/对象 对的顺序，那就必须对键值釆用其他方式来确定元素在内存中的位置。如果使用像 string 这样的对象作为键，就会遇到一些问题，可能的变量的数目是巨大的。具有 10 个字符的字母字符串可能的个数是 26¹⁰。这个索引范围没有多大用处。我们需要一种机制来将它变为可接受的范围；而且理想情况下，这个机制可以为每个键生成唯一的值。这也是哈希需要做的事情之一。

哈希是用给定范围的基本类型的数据项，或者用像 string 这样的对象，生成整数值的过程。哈希产生的值叫作哈希值或哈希码，它们通常被用在容器中，用来确定表中对象的位置。像前面所说的那样，理想情况下，每个对象应该产生唯一的哈希值，但这一般是不可能的。当不同键值的个数大于可能的哈希值个数时，显然就会出现上面所说的这种情况，我们早晚会得到重复的哈希值。重复的哈希值也叫作碰撞。

哈希不仅可以在容器中保存对象，它也被应用到很多其他地方，例如密码和加密数据的安全系统中，密码识别有时也包含哈希。在系统中保存明文密码是有很大风险的。保存密码的哈希值要比保存明文密码更安全，更能防范黑客。得到哈希值的黑客需要将哈希值转换为对他们有用的原始密码，而这是一个不可能完成的任务。因此STL提供的对不同类型数据哈希的能力不仅可以用在关联容器上，也可以被用在更加广阔的场景中。

虽然理解容器的哈希机制没在必要，但是这能让我们对它们能做些什么有一个基本的了解。哈希算法有很多，但却没有可以通用的。为某个场景确定合适的哈希算法并不总是简单。通常都需要对数据分割后再计算。这可能是最简单的处理键的算法了，不管什么类型的键，都会作为数值处理。所以哈希值可能是表达式k%m产生的。

显然，这种方法最多允许有 m 个不同的哈希值，值的范围为 0 到 m-1。可以很容易地看到哪里会产生重复的哈希值。值为 k+m、k+2*m 的键会有重复的哈希值，m 值的选择对于减少重复哈希值的出现至关重要，而且可以保证值是均匀分布的。如果 m 是 2 的幂，也就是 2ⁿ，哈希值的最小位为 k 的 n 位。这显然不是一个好的结果，因为 k 的大多数位都没有影响到哈希值；理想情况下，键的所有数位应该都可以影响哈希结果。m 通常是一个质数，因为它可以使哈希值更加均匀地分布在这个范围内。

另一种更好的计算哈希值的方式是选择一个常量 a，将它和 k 相乘，用 a*k 除以整数 m 来计算它的余数，然后从 (a*k)%m 的结果中选择一个长度值作为哈希值。显然 a 和 m 的选择是非常重要的。对于 32 位的计算机来说，m 通常选为 2³²。乘数 a 是和 m 相近的质数，这就意味着 a 和 m 除了 1 之外没有其他的公共因子。此外，a 的二进制表示中头部和尾部不能为 0，否则会和其他头部有 0 或尾部有 0 的键值产生碰撞。基于这些原因，这个算法也被叫作乘法哈希。

也有几个专门哈希字符串的算法。其中一个将字符串看作一定个数的单词，使用像乘法算法这样的方法来计算第一个单词的哈希值，然后加上下一个单词，再计算它的哈希值，重复这个过程，直到计算出所有单词最后的哈希值。

生成哈希值的函数

functional 头文件中定义了无序关联容器使用的特例化 hash<K> 模板。hash<K> 模板定义了可以从 K 类型的对象生成哈希值的函数对象的类型。hash<K> 实例的成员函数  operator()() 接受 K 类型的单个参数，然后返回 size_t 类型的哈希值。对于基本类型和指针类型，也定义了特例化的 hash<K> 模板。

hash<K> 模板专用的算法取决于实现，但是如果它们遵循 C++14 标准的话，需要满足一些具体的要求。这些要求如下：

• 不能拋出异常
• 对于相等的键必须产生相等的哈希值
• 对于不相等的键产生碰撞的可能性必须最小接近 size_t 最大值的倒数

注意，相等键生成相等的哈希值只适用于单次执行。这也就意味着，在不同的场合允许给定的键可以生成不同的哈希值。这就使我们可以在哈希算法中使用随机数，当对密码进行哈希时，这是我们所希望使用的。注意，C++14 为了保持一致性并没有排除给定类型的键的哈希值等同于键的可能。在无序关联容器中，用哈希函数哈希整数值可能就是这种情况。

下面是一个用 hash<K> 生成整数的哈希值的示例：

std::hash<int> hash_int;// Function object to hash int
std::vector<int> {-5, -2, 2, 5, 10};
std::transform(std::begin(n), std::end(n),std::ostream_iterator<size_t> (std:: cout," "),hash_int);

这里使用 transform() 算法来哈希 vector 中的元素。transform() 参数中的前两个迭代器指定了被操作元素的范围，第三个参数是一个指定输出地址的迭代器，这里是一个 ostream 迭代器，最后一个参数是应用到范围元素上的函数对象 hash<int>。某次测试的输出结果为：

554121069 2388331168 3958272823 3132668352 1833987007

在你的 C++ 编译器和库中，可能会产生不同的哈希值，所有的哈希值都是这样。下面是一个哈希浮点数值的示例：

std::hash<double> hash_double;
std::vector<double> x {3.14,-2.71828, 99.0, 1.61803399,6.62606957E-34};
std::transform(std::begin(x), std::end(x),std::ostream_iterator<size_t>(std::cout," "),hash_double);

某次测试的输出结果为：

4023697370 332724328 2014146765 3488612130 3968187275

指针也很容易哈希：

std::hash<Box*> hash_box; // Box class as in Chapter 2
Box box{1, 2, 3};
std:: cout << "Hash value = " << hash_box (&box)<<std::endl;    // Hash value = 2916986638

可以用相同的函数对象来哈希智能指针：

std::hash<Box*> hash_box; // Box class as in Chapter 2
auto upbox = std::make_unique<Box>(1A 2, 3);
std::cout << "Hash value = " << hash_box(upbox.get())<<std::endl; // Hash value = 1143026886

这里调用 unique_ptr<Box> 对象的成员函数 get() 来获取保存自由存储区地址的原生指针，然后将它传给哈希函数。这里使用的 hash<K> 模板也是 unique_ptr<T> 和 shared_ptr<T> 对象的特例化模板。例如，可以对 unique_ptr<Box> 对象而不是对它所包含的原生指针进行哈希：

std::hash<std::unique_ptr<Box>>hash_box; // Box class as in Chapter 2
auto upbox = std::make_unique<Box>(1, 2, 3);
std::cout << "Hash value = "<< hash_box (upbox)<< std::endl; // Hash value = 4291053140

原生指针和 unique_ptr 的哈希值是相同的。不要被这个误导，考虑到当一个类型的键没有具体的哈希函数时，这种对指针哈希的能力是很有用的。可以对地址进行哈希，而不是对对象自己。这和指针指向的对象无关。

如果想在无序容器中以指向键的指针为键，而不是以键为键，保存一些对象，思考一下会发生什么。指向键的指针的哈希值和原始键的哈希值有很大的不同，因为它们的地址不同，因而无法用它来检索对象。需要一种可以为使用的任何类型的键生成哈希值的方式。如果键的类型是我们所定义的，我们有一个选择，可以用 STL 提供的哈希函数来为我们定义的类的数据成员生成哈希值。

string 头文件中定义了一些特例化的 hash<K> 模板，它们会生成一些函数对象，这些函数对象生成表示字符串的对象的哈希值。有 4 个特例化的模板，它们分别对应于字符串类型：string、wstring、u16string 和 u32string。

wstring 类型的字符串包含的是 wchar_t 类型的字符；u16string 类型包含的是 charl6_t 类型的字符，它是用 UTF-16 编码的 Unicode 字符；u32string 类型包含的是 char32_t 类型的字符，它是用 UTF-32 编码的 Unicode 字符。

当然，字符类型 char、wchar_t、charl6_t 和 char32_t 都是C++14 中的基本类型。下面是一个对字符串对象进行哈希的示例:

std::hash<std::string> hash_str;
std::string food {"corned beef"};
std::cout << "corned beef hash is " <<hash_str (food) <<std::endl;

这里生成了一个函数对象，它用和前面章节中示例相同的方式来哈希 string 对象。本次测试的输出结果如下：

corned beef hash is 3803755380

这里对 C 风格字符串的哈希没有具体的规定。使用 const char* 类型的 hash<T> 模板会为指针进行特例化。如果想将 C 风格的字符串当作字符序列来哈希生成哈希值，可以先用它生成一个 string 对象，然后使用函数对象 hash<string>。

代码段生成的哈希值都是非常大的数，这看起来对于确定对象在无序容器中的位置没有什么帮助。有几种方式可以用哈希值确定对象在容器中的位置。一个常见的用法是用哈希值的比特序列作为对象在表或树中的索引。