[c++11]hash<T>哈希结构模板

2019-11-08 02:38:48

字体：大中小

来源：转载

供稿：网友

一、哈希结构模板hash简介

c++11新增的哈希结构模板定义于头文件 <functional>：

template<class _Kty>struct _Bitwise_hash : public unary_function<_Kty, size_t>{...};

哈希结构模板定义一个函数对象（重载了Operator()），实现了散列函数: 1.接受一个参数的类型Key 2.返回一个类型为size_t的值，表示该参数的哈希值 3.调用时不会抛出异常 4.若两个参数k1k2相等，则hash<Key>()(k1) == hash<Key>()(k2) 5.若两个不同的参数k1k2不相等，则hash<Key>()(k1) == hash<Key>()(k2)成立的概率应非常小，接近1.0/std::numeric_limits<size_t>::max()

无序关联容器unordered_set，unordered_multiset，unordered_map和unordered_multimap默认使用哈希结构模板来为键计算散列值。

二、成员

成员类型

`argument_type`	模板第一个类型参数
`result_type`	`size_t`

公有成员方法

默认构造函数	构造一个哈希函数对象
`size_t operator()(T &t)`	计算t的散列值

三、扩展和应用

在头文件里，实例化了内置类型的哈希结构模板：

template<> struct hash<bool>;template<> struct hash<char>;template<> struct hash<signed char>;template<> struct hash<unsigned char>;template<> struct hash<char16_t>;template<> struct hash<char32_t>;template<> struct hash<wchar_t>;template<> struct hash<short>;template<> struct hash<unsigned short>;template<> struct hash<int>;template<> struct hash<unsigned int>;template<> struct hash<long>;template<> struct hash<long long>;template<> struct hash<unsigned long>;template<> struct hash<unsigned long long>;template<> struct hash<float>;template<> struct hash<double>;template<> struct hash<long double>;template< class T > struct hash<T*>;

C++11实例化了字符串的哈希结构模板

std::hash<std::string>std::hash<std::u16string>std::hash<std::u32string>std::hash<std::wstring>

C++11，std::error_code的哈希支持

std::hash<std::error_code>

C++11实例化的其他哈希结构模板

std::hash<std::bitset>std::hash<std::unique_ptr>std::hash<std::shared_ptr>std::hash<std::type_index>std::hash<std::vector<bool>>std::hash<std::thread::id>

四、代码示例

IDE：vs2013

#include <iostream>#include <functional>//#include <string>#include <stdlib.h>using std::hash;//using std::string;using std::cout;//自定义类型class S {public: string first_name; string last_name;};//自己封装一个哈希函数对象的类型，内部使用了hash结构模板class MyHash {public: size_t operator()(const S &s) const { size_t h1 = hash<string>()(s.first_name); size_t h2 = hash<string>()(s.last_name); return h1 ^ (h2 << 1); }};//也可以用自定义类实例化一个hash结构模板template<>class hash < S > {public: size_t operator()(const S &s) const { size_t h1 = hash<string>()(s.first_name); size_t h2 = hash<string>()(s.last_name); return h1 ^ (h2 << 1); }};int main(){ cout << "计算string的散列值的示例：/n"; string str = "Meet the new boss..."; hash<string> hash_fn; size_t str_hash = hash_fn(str); cout << str_hash << '/n'; cout << "/n计算自定义类型S的散列值的示例：/n"; string s1 = "Hubert"; string s2 = "Farnsworth"; hash<string> h1; S obj_S; obj_S.first_name = s1; obj_S.last_name = s2; cout << "hash(s1) = /t" << h1(s1) << "/n" << "hash(s2) = /t" << hash<string>()(s2) << "/n" << "MyHash(obj_S) = " << MyHash()(obj_S) << "/n" << "hash(obj_S) = /t" << hash<S>()(obj_S) << "/n"; ::system("pause"); return 0;}

输出：运行结果输出