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

目录

1、框架

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

3、哈希桶的插入

4、哈希桶的查找

5、哈希桶的删除

6、源码链接

1、框架

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

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

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

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

//利用仿函数将数据类型转换为整型
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;
	}
};

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<K, V>& 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<K, V> 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<Node*> 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、源码链接

开散列哈希桶的模拟实现