首页 > 编程笔记

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

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

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

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

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

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

另一种更好的计算哈希值的方式是选择一个常量 a,将它和 k 相乘,用 a*k 除以整数 m 来计算它的余数,然后从 (a*k)%m 的结果中选择一个长度值作为哈希值。显然 a 和 m 的选择是非常重要的。对于 32 位的计算机来说,m 通常选为 232。乘数 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 标准的话,需要满足一些具体的要求。这些要求如下:

注意,相等键生成相等的哈希值只适用于单次执行。这也就意味着,在不同的场合允许给定的键可以生成不同的哈希值。这就使我们可以在哈希算法中使用随机数,当对密码进行哈希时,这是我们所希望使用的。注意,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>。

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

推荐阅读