【 C++ 】闭散列哈希表的模拟实现

哈希节点状态

我们都很清楚数组里的每一个值无非三种状态：

如果某下标没有值，则代表空EMPTY。
如果有值在代表存在EXIST。
如果此位置的值被删掉了，则表示为DELETE。

而这三种状态我们可以借助enum枚举来帮助我们表示数组里每个位置的状态。这里我们专门封装一个类来记录每个位置的状态，以此汇报给后续的哈希表。

enum State
{
	EMPTY,
	EXIST,
	DELETE
};

//哈希节点
template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	State _state = EMPTY;//记录每个位置的状态，默认给空
};

//哈希表
template<class K, class V, class HashFunc = DefaultHash<K>>//添加仿函数便于把其他类型的数据转换为整型数据
class HashTable
{
	typedef HashData<K, V> Data;
public:
	//相关功能的实现……
private:
	vector<Data> _tables;
	size_t _n = 0;//记录存放的有效数据的个数
};

实现好了哈希节点的类，就能够很好的帮助我们后续的查找，示例：

在这里插入图片描述

查找50：

50%10=0，下标0的值不是50，继续++下标往后查找，直至下标3的下标为止。

查找60：

60%10=0，下标0不是，往后++下标继续查找，找到下标4发现状态为EMPTY空，此时停止查询，因为往后就不可能出现了

删除10，再查找50：

50%10=0，下标0的值不是，++下标到下标1，发现状态为DELETE删除，继续++下标直至下标3的值为50，找到了。

哈希表的扩容

散列表的载荷因子定义为：α = 填入表中的元素个数 / 散列表的长度。
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以α越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α越小，表明填入表中的元素越少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是载荷因子α的函数，只是不同处理冲突的方法有不同的函数。
对于开放定址法（闭散列），载荷因子是特别重要因素，应严格限制在0.7 ~ 0.8以下。超过0.8，查表时的CPU缓存不命中（cache missing）按照质数曲线上升。因此，一些采用开放定址法的hash库，如Java的系统库限制了载荷因子为0.75，超过此值将resize散列表。

综上，我们在后续的插入操作中，必然要考虑到扩容的情况，我们直接把负载因子控制在0.7，超过了就扩容。具体操作见下文哈希表的插入操作。

构建仿函数把所有数据类型转换为整型并特化

在我们后续的插入操作中，插入的数据类型如果是整数，那么可以直接建立映射关系，可若是字符串，就没那么容易了，因此，我们需要套一层仿函数，来帮助我们把字符串类型转换成整型的数据再建立映射关系。主要分为以下三类需要写仿函数的情况：

key为整型，为默认仿函数的情况。
此时的数据类型为整型，直接强转size_t随后返回。
key为字符串，单独写个字符串转整型的仿函数。
针对于字符串转整型，我们推出下面两种方法，不过都是会存在问题的：
- 只用首字母的ascii码来映射，此法不合理，因为"abc"和"axy"本是俩不用字符串，经过转换，会引发冲突。
- 字符串内所有字符ASCII码值之和，此法也会产生冲突，因为"abcd"和"bcad"在此情况就会冲突。

为了避免冲突，几位大佬推出多种算法思想，下面我取其中一种算法思想来讲解：

BKDR哈希算法：
hash = hash * 131 + ch;   // 也可以乘以31、131、1313、13131、131313..

为了能够让我们的哈希表能够自动识别传入数据的类型，不用手动声明，这里我们可以借助特化来解决，仿函数+特化总代码如下：

//利用仿函数将数据类型转换为整型
template<class K>
struct DefaultHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//模板的特化
template<>
struct DefaultHash<string>
{
	size_t operator()(const string& key)
	{
		//BKDR哈希算法
		size_t hash = 0;
		for (auto ch : key)
		{
			hash = hash * 131 + ch;//把所有字符的ascii码值累计加起来
		}
		return hash;
	}
};

哈希表的插入

哈希表的插入主要是三大步骤：

去除冗余
扩容操作
插入操作

下面分开来演示。

1、去除冗余：

复用Find查找函数，去帮助我们查找插入的值是否存在。
若存在，直接返回false 。
不存在，再进行后续的插入操作。

2、扩容操作：

如果哈希表一开始就为空，则要扩容。
如果填入表中的元素个数*10 再 / 表的大小>=7，就扩容（*10是为了避免出现size_t的类型相除不会有小数的情况）。
扩容以后要重新建立映射关系。
创建一个新的哈希对象，扩容到先前旧表扩容的大小。
遍历旧表，把旧表每个存在的元素插入到新表，此步骤让新表自动完成映射关系，无序手动构建。
利用swap函数把新表交换到旧表那，此时的旧表就是已经扩好容且建立号映射关系的哈希表。

3、插入操作：

借助仿函数把插入的数据类型转为整型并定义变量保存插入键值对的key。
用此变量%=哈希表的size()，不能是capacity()，因为[ ]运算符会判断下标是否小于size，且对于哈希表，应该尽量控制size和capacity一样大。
遍历进行线性探测 / 二次探测，如果这个位置的状态为EXIST存在，说明还要往后遍历查找。
遍历结束，说明此位置的状态为空EMPTY或删除DELETE，可以放值。
把插入的值放进该位置，更新状态为EXIST，有效数据个数++。

//插入
bool Insert(const pair<K, V>& kv)
{
	//1、去除冗余
	if (Find(kv.first))
	{
		//说明此值已经有了，直接返回false
		return false;
	}
	//2、扩容
		//负载因子超过0.7，就扩容
	if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
	{
		size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		//扩容以后，需要重新建立映射关系
		HashTable<K, V, HashFunc> newHT;
		newHT._tables.resize(newSize);
		//遍历旧表，把旧表每个存在的元素插入newHT
		for (auto& e : _tables)
		{
			if (e._state == EXIST)
			{
				newHT.Insert(e._kv);
			}
		}
		newHT._tables.swap(_tables);//建立映射关系后交换
	}
	//3、插入
	HashFunc hf;
	size_t starti = hf(kv.first);//取出键值对的key，并且避免了负数的情况，借用仿函数确保是整型数据
	starti %= _tables.size();
	size_t hashi = starti;
	size_t i = 1;
	//线性探测/二次探测
	while (_tables[hashi]._state == EXIST)
	{
		hashi = starti + i;//二次探测改为 +i^2
		++i;
		hashi %= _tables.size();//防止hashi超出数组
	}
	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	_n++;
	return true;
}

哈希表的查找

查找的核心逻辑就是找到key相同，就返回此对象的地址，找到空就返回nullptr，具体细分规则如下：

先去判断表的大小是否为0，为0直接返回nullptr。
按照线性探测 / 二次探测的方式去遍历，遍历的条件是此位置的状态不为空EMPTY。
如果遍历到某哈希表中的对象的值等于要查找的值（前提是此位置的状态不为DELETE删除），返回此对象的地址。
当遍历结束后，说明此位置的状态为空EMPTY，哈希表没有我们要查找的值，返回nullptr。

//查找
Data* Find(const K& key)
{
	//判断表的size是否为0
	if (_tables.size() == 0)
	{
		return nullptr;
	}
	HashFunc hf;
	size_t starti = hf(key);//通过仿函数把其它类型数据转为整型数据
	starti %= _tables.size();
	size_t hashi = starti;
	size_t i = 1;
	//线性探测/二次探测
	while (_tables[hashi]._state != EMPTY)//不为空就继续
	{
		if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];//找到了就返回此对象的地址
		}
		hashi = starti + i;//二次探测改为 +i^2
		++i;
		hashi %= _tables.size();//防止hashi超出数组
	}
	return nullptr;
}

哈希表的删除

删除的逻辑很简单，遵循下面的规则：

复用Find函数去帮我们查找删除的位置是否存在。
若存在，把此位置的状态置为DELETE即可，此时表中的有效数据个数_n需要减减，最后返回true。
若不存在，直接返回false。

//删除
bool Erase(const K& key)
{
	//复用Find函数去帮助我们查找删除的值是否存在
	Data* ret = Find(key);
	if (ret)
	{
		//若存在，直接把此位置的状态置为DELETE即可
		ret->_state = DELETE;
		return true;
	}
	else
	{
		return false;
	}
}

完整代码

#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;

//利用仿函数将数据类型转换为整型
template<class K>
struct DefaultHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
//模板的特化
template<>
struct DefaultHash<string>
{
	size_t operator()(const string& key)
	{
		//BKDR哈希算法
		size_t hash = 0;
		for (auto ch : key)
		{
			hash = hash * 131 + ch;//把所有字符的ascii码值累计加起来
		}
		return hash;
	}
};

//闭散列哈希表的模拟实现
namespace CloseHash
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE
	};
	//哈希节点状态的类
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;//记录每个位置的状态，默认给空
	};


	//哈希表的类
	template<class K, class V, class HashFunc = DefaultHash<K>>//添加仿函数便于把其他类型的数据转换为整型数据
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		//插入
		bool Insert(const pair<K, V>& kv)
		{
			//1、去除冗余
			if (Find(kv.first))
			{
				//说明此值已经有了，直接返回false
				return false;
			}
			//2、扩容
				//负载因子超过0.7，就扩容
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				//扩容以后，需要重新建立映射关系
				HashTable<K, V, HashFunc> newHT;
				newHT._tables.resize(newSize);
				//遍历旧表，把旧表每个存在的元素插入newHT
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}
				newHT._tables.swap(_tables);//建立映射关系后交换
			}
			//3、插入
			HashFunc hf;
			size_t starti = hf(kv.first);//取出键值对的key，并且避免了负数的情况，借用仿函数确保是整型数据
			starti %= _tables.size();
			size_t hashi = starti;
			size_t i = 1;
			//线性探测/二次探测
			while (_tables[hashi]._state == EXIST)
			{
				hashi = starti + i;//二次探测改为 +i^2
				++i;
				hashi %= _tables.size();//防止hashi超出数组
			}
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
			_n++;
			return true;
		}
		//查找
		Data* Find(const K& key)
		{
			//判断表的size是否为0
			if (_tables.size() == 0)
			{
				return nullptr;
			}
			HashFunc hf;
			size_t starti = hf(key);//通过仿函数把其它类型数据转为整型数据
			starti %= _tables.size();
			size_t hashi = starti;
			size_t i = 1;
			//线性探测/二次探测
			while (_tables[hashi]._state != EMPTY)//不为空就继续
			{
				if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];//找到了就返回此对象的地址
				}
				hashi = starti + i;//二次探测改为 +i^2
				++i;
				hashi %= _tables.size();//防止hashi超出数组
			}
			return nullptr;
		}
		//删除
		bool Erase(const K& key)
		{
			//复用Find函数去帮助我们查找删除的值是否存在
			Data* ret = Find(key);
			if (ret)
			{
				//若存在，直接把此位置的状态置为DELETE即可
				ret->_state = DELETE;
				return true;
			}
			else
			{
				return false;
			}
		}
	private:
		vector<Data> _tables;
		size_t _n = 0;//记录存放的有效数据的个数
	};
}