在之前的課程中吴叶，我們知道以Hash Table為底層的容器過程（如unordered_map）毯盈，在使用過程中，必須要有一個hash function來為每一個元素生成一個hash code作為元素在哈希表中的key，也就是元素在哈希表中的具體位置蜕依。對于一些build-in類型（比如字符串），標(biāo)準(zhǔn)庫自帶hash function琉雳，但是對于自定義類型來說样眠，這個函數(shù)該如何定義？我們能否找到一個通用的方法翠肘，實現(xiàn)hash code的計算呢檐束？
自定義類型，都是由基本類型組成束倍，我們可以將它其中的各個基本數(shù)據(jù)類型分開計算出被丧，然后將其相加（當(dāng)然這是比較天真的方法）盟戏。先看看這種方法的實現(xiàn)代碼：
[cpp]view plaincopyprint?
classCustomerHash
{
public:
std::size_toperator()(constCustomer&?c)const{
returnstd::hash()(c.fname)
+?std::hash()(c.Iname)
+?std::hash
}
}
class CustomerHash
{
public:
std::size_t operator()(const Customer& c) const{
return std::hash()(c.fname)
+ std::hash()(c.Iname)
+ std::hash
}
}
這個方法可以實現(xiàn)出計算Hash code，但是因為這個方法只是簡單的相加hash code晚碾，因此hash code的重復(fù)概率比較高進(jìn)而會導(dǎo)致籃子中的元素過多抓半，影響查詢的效率。
在了解其他方法之前格嘁，先介紹一下hash function的三種定義型式：
型式1：
[cpp]view plaincopyprint?
#include
classCustomer{
//........
};
classCustomerHash
{
public:
std::size_toperator()(constCustomer&?c)const{
return/*........*/;
}
};
unordered_set?customers;
#include
class Customer{
//........
};
class CustomerHash
{
public:
std::size_t operator()(const Customer& c) const{
return /*........*/;
}
};
unordered_set customers;
型式2：
[cpp]view plaincopyprint?
size_tcustomer_hash_func(constCustomer&?c)
{
return/*......*/;
}
unorder_set?customers(20笛求，?customer_hash_func);
size_t customer_hash_func(const Customer& c)
{
return /*......*/;
}
unorder_set customers(20， customer_hash_func);
型式3：
通過偏特化來實現(xiàn)
[cpp]view plaincopyprint?
classMyString
{
private:
char*?_data;
size_t_len;
};
namespacestd;
{
template<>
structhash
{
size_toperatoe()(constMyString&?s)constnoexcept{
returnhash()(string(s.get()));
}
}
}
class MyString
{
private:
char* _data;
size_t _len;
};
namespace std;
{
template<>
struct hash
{
size_t operatoe()(const MyString& s) const noexcept{
return hash()(string(s.get()));
}
}
}
通過以上三種型式可以指定我們需要的hash function糕簿，但是能否能有一個萬用的hash function來實現(xiàn)自定義類型的hash code的計算探入？
在C++ TR1版本及以后，STL為我們提供了一個萬用的hash function懂诗，它是如何實現(xiàn)的呢蜂嗽？
具體調(diào)用代碼如下：
[cpp]view plaincopyprint?
classCustomerHash
{
public:
std::size_toperator()(constCunstomer&?c)const{
returnhash_val(c.fname,?c,Iname,?c.no);
}
}
class CustomerHash
{
public:
std::size_t operator()(const Cunstomer& c) const {
return hash_val(c.fname, c,Iname, c.no);
}
}
接下來看看它的實現(xiàn)代碼，具體如下：
[cpp]view plaincopyprint?
//auxiliary?generic?funtions
template
inlinesize_thash_val(constTypes&...?args){
size_tseed?=?0;
hash_val(seed,?args...);
returnseed;
}
template
inlinevoidhash_val(size_t&?seed,constT&?val,constType&...?args){
hash_combine(seed,?val);
hash_val(seed,?args...);
}
#include
template
inlinevoidhash_combine(size_t&?seed,constT&?val){
seed?=?std::hash(val)?+?0x9e3779b9
+?(seed?<<?6)?+?(seed?>>?2);
}
//auxiliary?generic?funtions
template
inlinevoidhash_val(size_t&?seed,constT&?val){
hash_combine(seed,?val);
}
//auxiliary generic funtions
template
inline size_t hash_val(const Types&... args){
size_t seed = 0;
hash_val(seed, args...);
return seed;
}
template
inline void hash_val(size_t& seed, const T& val, const Type&... args){
hash_combine(seed, val);
hash_val(seed, args...);
}
#include
template
inline void hash_combine(size_t& seed, const T& val){
seed = std::hash(val) + 0x9e3779b9
+ (seed << 6) + (seed >> 2);
}
//auxiliary generic funtions
template
inline void hash_val(size_t& seed, const T& val){
hash_combine(seed, val);
}
這種方法和之前提到的簡單相加的方法相比殃恒，更加的巧妙植旧，它使用了C++11中的variadic templates，可以傳入多個模板离唐，傳入函數(shù)中的每個參數(shù)都有一個模板病附，對不同類型的參數(shù)會有不同的解決方案，也就是會傳入不同的函數(shù)亥鬓。
由上圖可知完沪，在①中加入了seed（最終被視為hash code），從而使得模板變成1+n的形式嵌戈，通過遞歸調(diào)用②中的hash_val函數(shù)覆积，不斷調(diào)用④中的hash_combine函數(shù)來改變seed，同時減少接收的參數(shù)熟呛，最終遞歸結(jié)束時變成1+1的形式宽档，調(diào)用③中的hash_val函數(shù)，也會調(diào)用④中的hash_combine函數(shù)庵朝，最終確認(rèn)seed值雌贱，也就是算出最后的hash code。
其中④中的hash_combine函數(shù)中的0x9e3779b9屬于黃金比例中的一部分：
tuple是元之組合偿短，數(shù)之組合的意思，它是C++2.0之后引進(jìn)的一種存放各種不同類型元素的集合馋没。
tuple的使用方法如下：
tuple實現(xiàn)的原理昔逗，以Gnu4.8為例：
它是通過繼承的方法來不斷地剔除第一個參數(shù)，最終來實現(xiàn)對每一個元素的操作篷朵。
type traits（類型萃取機）能有效地分辨類是否具有某種類型勾怒，通過調(diào)用它我們可以實現(xiàn)對不同的類型指定不同的操作婆排。
在Gnu2.9中的實現(xiàn)代碼如下：
[cpp]view plaincopyprint?
struct__true_type{};
struct__false_type{};
//泛化
template
struct__type_traits{
typedef__true_type?this_dummy_member_must_be_first;
typedef__false_type?has_trivial_default_constructor;
typedef__false_type?has_trivial_copy_constructor;
typedef__false_type?has_trivial_assignment_operator;
typedef__false_type?has_trivial_destructor;
typedef__false_type?is_POD_type;//POD?=?Plain?Old?Data，代表舊式的class?也就是struct
}笔链；
//int的特化
template<>
struct__type_traits{
typedef__true_type?has_trivial_default_constructor;
typedef__true_type?has_trivial_copy_constructor;
typedef__true_type?has_trivial_assignment_operator;
typedef__true_type?has_trivial_destructor;
typedef__true_type?is_POD_type;
}
//double的特化
template<>
struct__type_traits{
typedef__true_type?has_trivial_default_constructor;
typedef__true_type?has_trivial_copy_constructor;
typedef__true_type?has_trivial_assignment_operator;
typedef__true_type?has_trivial_destructor;
typedef__true_type?is_POD_type;
}
struct __true_type{};
struct __false_type{};
//泛化
template
struct __type_traits{
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;? //POD = Plain Old Data段只，代表舊式的class 也就是struct
}；
//int的特化
template<>
struct __type_traits{
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
}
//double的特化
template<>
struct __type_traits{
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
}
上面的type traits是依靠模板的泛化和特化的版本來實現(xiàn)鉴扫。
從C++11開始赞枕，type traits的特性變得更為強大和復(fù)雜。
萬變不離其宗坪创，通過模板的泛化和特化炕婶，我們可以實現(xiàn)各種操作。
（1）is_void
（2）is_integral
（3）is_class莱预，is_union柠掂，is_enum，is_pod
（4）is_move_assignable
Gnu2.9：
Gnu4.9：
