技术: C++11 hashtable 结构

基本的 hash table结构(桶+链表)在大学数据结构的课程就已经学过, 本文主要介绍如果要使用 unorder container要 hash函数。

hash table结构

其实这里谈散列表, 也只是为了用好新容器, 而已.

基本概念

散列表有多种, 这里只谈最常见的.

separate chaining : bucket & list (桶+ 链表; 不同系统采用的链表不同, gnu采用的单向链表)

rehashing: 如果元素的个数多余桶的数目, 一般就会重新扩充桶的数目—业界的通用做法, 没有太多依据.(注意, 重新分配是要花时间的, 成长要付出代价)

hash表存储算法: 一般最简单的算法是, 对桶的数据进行取模运算, 然后确定元素在hash表中存储的位置.

元素的hash值(hash code): 一般是经过算法运算的, 对元素的value经过一定的操作取得, 但这个算法过程不同于hash存储算法, 这里希望不同元素最好有不同的hash值, 这样碰撞或者重复的概率就比较小. 常见的hash算法, 如md5, sha1.

在使用unordered容器时指定hash<>函数模板对象作为模板参数, 例如: unordered_set<ClaName, HashCodeFunctor> set, 基本类型的, string的, 你可以不指定, 但是你自己自定义类型的一定要传入一个特化模板functor.

通常所说的 hash方法, 一般混合了 hash表存储算法, 以及hash code计算方法

hash code计算方法

可以简单检测一下基本的hash code方法:(标准库已经实现好了)

std::cout << hash<char>()(`c`) << std::endl;
std::cout << hash<char*>()("wiki") << std::endl;

//当然直接创建函数对象也可以
//auto
hash<char*> hashFunctor;
hashFunctor("wiki");

其简单的源码可能是:

template<class Key>
struct hash { //空的, 没有实现}; //泛化版本

//然后就有很多特化版本(函数对象了)
struct hash<char>
{
   size_t operator()(char x) const {return x; //直接返回ASCII编码}
}

所以指定自定义对象时, 也要自己特化(比如string类的特化, 就是放在string类自己的文件中, basic_string中)

template<>
struct hash<string> : public _hash_base<size_t, string>
{
	size_t operator()(const string& __s) const noexcept
	{
		return std::_Hash_impl::hash(__s.data(), __s.length()); //然后这里其实是调用_Hash_bytes()
	}
}

注意这种泛化方式.

实际上可以从include/c++/bits/functional_hash.h中找到相关基本类型的 hash code 计算方法, 特化类型的 functor, 对所有基本类型都做了特化.

底层的_Hash_bytes貌似由编译器代码实现了, 或者已经是二进制代码了, 所以找不到源码

这些 hash code 计算方法, 用法按照functor的用法即可.

通常版本的 hash code 计算方法怎么提供?

一共有三种方法:

• 提供一个函数
• 提供一个仿函数
• 借助标准库的hash函数模板特化一下自己的模板functor

写成函数?

size_t classname_hash_code_func(cosnt classname& c)
{
	//返回一个计算好的size_t值
}

这么做, 你使用 unodrder map 就要注意泛型参数了:(初始化容器需要制定相关的泛型参数)

unordered_set<className, size_t(*)(const classname&)> cc(桶的个数, classname_hash_code_func);

上面的形式, 即写成函数, 要求在调用的时候, 指定好桶的个数. (使用者要非常熟悉容器, unordered相关容器)

函数对象?

方便使用, 最好是为具体的类对象指定好, hash code函数对象

class ClassNameHashFunctor
{
public:
   std::size_t operator()(const ClaName& c) const{//...具体方法}
}

此时用的时候, 就非常简单了:

unordered_set<ClassName, ClassNameHashFunctor> set;

仿函数模板模板
最最常见的, 直接用特化的模板仿函数, 即, 借助标准库的hash仿函数, 例如:

namespace std 
{ //注意放入std名字空间

	template<>  //不需要模板参数了, 因为这里是特化
	struct ClassNameHashFunctor<ClassName>
	{
		std::size_t operator()(const ClaName& c) const noexcept{//...具体实现方法方法}
	}
};

调用的时候, 最简单(因为已经放入std了):

unordered_set<ClassName> set;

具体的实现

hash code的具体的实现方法?

• 可以用变参模板, 比如 initializer_list 或者 variadic template 去拆分然后借助基本类型的hash方法
• 让研究数学的人, 提供一种专门的hash方法, 减少冲突&碰撞次数; (本质上减少rehash几率)

算法实现的好坏, 不是以乱, 离散为考核, 而是以减少碰撞次数为目的.

但一些误区是, 分别计算hash然后相加; 这种方式太傻了(达不到目的), 不能减少存储冲突, 倒不如把所有计算参数传递给具体的hash函数, 然后计算.

通用实现

完整的例子, 比如说你要为Customer类写一个 hash code 计算的functor, 如下:

class CustomerHash
{
public:
	std::size_t operator()(const Customer& c) const noexcept
	{
		//这里用到hash_val函数模板, 可变参数模板, 所以这里没有指定具体类型<>
		//使用可变参数模板时, 不必为了专门的去特化而指定<>里的内容, 也没法指定
		return hash_val(c.firstmember, second.member); 
	}
};

//具体看你怎么用可变参数模板实现了
template<typename...Types>
inline size_t hash_val(const Types& ...args)
{
	size_t seed=0;i
	hash_val(seed, args...);
	return seed;
}

//然后按理调用下面的, 即逐个把args参数表中的第一个参数拆出来.
template<typename T, typename...Types>
inline void hash_val(size_t& seed, cosnt T& val, const Types& ...args)
{
	//处理一下seed, 结合value
	hash_combine(seed, value); //单独用要指定T, 不过现在在变参模板中, 则不必要.
	//递归调用下一个args, 再从args中拆
	hash_val(seed, args...);
}


//结合seed和第一个参数的函数模板如下
template<typename T>
inline void hash_combine(size_t &seed, const T&val)
{
	//下面这个应该是数学家想出来的算法(这是黄金比例算法)
	// 标准库的hash算法里面也提供了奇怪数字的种子
	seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

//hash_val递归的终止条件, 即args...只剩最后一个T& value了
template<typename T>
inline void hash_val(size_t &seed, const T&val)
{
	hash_combine(seed, val);
}

上面的variadic template就是一个通用的 hash code 方法, 即hash_val.

---

总结:
根据你调用 unordered container 的方式不同而不同, 一般都是使用自定义仿函数的方式;
但是实现上, 可以借鉴上面的通用实现.