【 C++ 】开散列哈希桶的模拟实现

目录

1、框架

2、构建仿函数把数据类型转为整型并特化

3、哈希桶的插入

4、哈希桶的查找

5、哈希桶的删除

6、源码链接

---

1、框架

根据我们先前对开散列哈希桶的了解，得知其根本就是一个指针数组，数组里每一个位置都是一个链表指针，因此我们要单独封装一个链表结构的类，以此来告知我们哈希表类的每个位置为链表指针结构。

namespace Bucket
{
    //结点类
	template
	struct HashNode
	{
		pair _kv;
		HashNode* _next;
		//构造函数
		HashNode(const pair& kv)
			:_kv(kv)
			, _next(nullptr)
		{}
	};
    //哈希表的类
	template>
	class HashTable
	{
		typedef HashNode Node;
	public:
		//相关功能的实现……
	private:
		//指针数组
		vector _tables;
		size_t _n = 0;//记录有效数据的个数
	};
}

---

2、构建仿函数把数据类型转为整型并特化

此步 *** 作的方法和闭散列哈希表所实现的步骤一致，目的都是为了能够让后续 *** 作中传入的所有数据类型转换为整型数据，以此方便后续建立映射关系，直接看代码：

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

---

3、哈希桶的插入

哈希桶的插入主要分为这几大步骤

1. 去除冗余
2. 扩容 *** 作
3. 头插 *** 作

下面开始具体展开说明：

1、去除冗余：

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

2、扩容 *** 作：

针对哈希桶的扩容，我们有两种方法进行扩容，法一和哈希表扩容的方法一致

法一：

1. 当负载因子==1时扩容
2. 扩容后重新建立映射关系
3. 创建一个新的哈希桶对象，扩容到newSize的大小
4. 遍历旧表，把旧表每个存在的元素插入到新表，此步骤让新表自动完成映射关系，无序手动构建
5. 利用swap函数把新表交换到旧表那，此时的旧表就是已经扩好容且建立号映射关系的哈希表

此扩容的方法会存在一个问题：释放旧表会出错！！！

• 当我们把旧表的元素映射插入到新表的时候，最后都要释放旧表，按照先前哈希表的释放，我们无需做任何处理，但是现在定义的结构是vector，是自定义类型，会自动调用析构函数进行释放，vector存储的数据是Node*，Node*是内置类型，不会自动释放，最后会出现表我们释放了，但是链表结构的数据还没释放，因此，我们还需借助手写析构函数来帮助我们释放。

//析构函数
~HashTable()
{
	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_tables[i] = nullptr;//释放后置空
	}
}

此扩容的方法可以进行优化，见法二。

法二：

• 这里我们没必要再创建新的节点，相反把扩容前的节点拿过来重新映射到新表中，大体逻辑和前面差不太多，只是这里不需要再创建新节点。直接利用原链表里的节点。

3、头插 *** 作：

1. 借助仿函数找到映射的位置（头插的位置）
2. 进行头插的 *** 作
3. 更新有效数据个数

//插入
bool Insert(const pair& kv)
{
	//1、去除冗余
	if (Find(kv.first))
	{
		return false;
	}
	//构建仿函数，把数据类型转为整型，便于后续建立映射关系
	HashFunc hf;
	//2、负载因子 == 1就扩容
	if (_tables.size() == _n)
	{
		/*法一
		size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		HashTable newHT;//
		newHT._tables.resize(newSize, nullptr);
		//遍历旧表，把旧表的数据重新映射到新表
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)//如果cur不为空，就插入
			{
				newHT.Insert(cur->_kv);
				cur = cur->_next;
			}
		}
		newHT._tables.swap(_tables);*/

		//法二：
		size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
		vector newTable;
		newTable.resize(newSize, nullptr);
		for (size_t i = 0; i < _tables.size(); i++)//遍历旧表
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = hf(cur->_kv.first) % newSize;//确认映射到新表的位置
				//头插
				cur->_next = newTable[hashi];
				newTable[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
		newTable.swap(_tables);
	}
	//3、头插
	//找到对应的映射位置
	size_t hashi = hf(kv.first);
	hashi %= _tables.size();
	//头插到对应的桶即可
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

---

4、哈希桶的查找

遵循下列规则：

1. 先去判断表的大小是否为0，为0直接返回nullptr
2. 利用仿函数去找到映射的位置
3. 在此位置往后的一串链表中进行遍历查找，找到了，返回节点指针
4. 遍历结束，说明没找到，返回nullptr

//查找
Node* Find(const K& key)
{
	//防止后续除0错误
	if (_tables.size() == 0)
	{
		return nullptr;
	}
	//构建仿函数，把数据类型转为整型，便于后续建立映射关系
	HashFunc hf;
	//找到对应的映射下标位置
	size_t hashi = hf(key);
	//size_t hashi = HashFunc()(key);//匿名对象
	hashi %= _tables.size();
	Node* cur = _tables[hashi];
	//在此位置的链表中进行遍历查找
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			//找到了
			return cur;
		}
		cur = cur->_next;
	}
	//遍历结束，没有找到，返回nullptr
	return nullptr;
}

---

5、哈希桶的删除

哈希桶的删除遵循这两大思路：

1. 找到删除的值对应哈希桶的下标映射位置
2. 按照单链表删除节点的方法对该值进行删除

//删除
bool Erase(const K& key)
{
	//防止后续除0错误
	if (_tables.size() == 0)
	{
		return false;
	}
	//构建仿函数，把数据类型转为整型，便于后续建立映射关系
	HashFunc hf;
	//找到key所对应的哈希桶的位置
	size_t hashi = hf(key);
	hashi %= _tables.size();
	Node* cur = _tables[hashi];
	Node* prev = nullptr;
	//删除
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			if (prev == nullptr)//头删
			{
				_tables[hashi] = cur->_next;
			}
			else//非头删
			{
				prev->_next = cur->_next;
			}
			delete cur;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	return false;
}

法二：替换法删除

• 上述的删除是实打实的删除，建立prev作为cur的前指针，以此利用prev和cur->next来建立关系从而删除cur节点，但是我们可以不用借助prev指针，就利用先前二叉搜索树的替换法删除的思想来解决。图示：

1. 当我要删除88时，把节点88的下一个节点的值78替换掉88，随后删除节点78，再建立链表的关系即可。 
2. 当删除的是尾节点98时，直接和头节点进行交换，删除头节点，并建立链表关系。

这里就不代码演示了，因为整体的成本看还是法一更方便理解些。

---

6、源码链接

开散列哈希桶的模拟实现