c++ 实现哈希桶

2023-07-27
四川
本文字数：4634 字
阅读完需：约 15 分钟

闭散列的回顾

在前面的学习中我们知道了闭散列的运算规则，当两个数据计算得到的位置发生冲突时，它会自动的往后寻找没有发生冲突的位置，比如说当前数据的内容如下：

当插入的数据为 33 时计算的位置为 3，可是位置 3 已经被占领了并且 4 也被占领了，但是位置 5 没有被占领所以插入数据 33 就会占领位置 5，那么这里的图片就如下：

这就是闭散列的插入原则，并且每个节点都有一个变量用来表示状态，这样在查找就不会出现漏查的情况，但是这样的实现会存在一个问题，扩容是根据有效数据的个数和 vector 容量来确定的，但是查找的时候是根据当前元素的状态是否为空来判断后面还有没有要查找的数据，如果为空的话则说明当前元素的后面没有我们要查找的元素，如果为存在或者被删除的话就说明当前元素的后面还有我们要查找的数据，如果我们不停的插入数据并且删除数据的话就会导致容器中的每个元素的状态都变成了被删除这样在查找一个不存的数据时，就会陷入死循环的状态那么这就是我们之前模拟实现的一个缺点，那么这里我们就来看看第二个解决数据不集中的方法：拉链法或者叫哈希桶法。

拉链法/哈希桶的原理

这个方法就是每个位置上都是一个链表，如果有多个位置发生冲突了，那么就挂在这个位置的链表上，这样就不会导致占领别人的位置，当我们要查找的时候就是先找到插入数据的位置，然后再通过这个位置的链表来按照顺序来进行查找，比如说下面的图片

当我们想要插入一个数据 13 时就会先计算 13 对应在哈希表上的位置，根据之前的计算原则这里得到的位置就是 3，所以图片就变成了下面这样：

如果再插入数据 23 的话这里计算的位置依然是 3，但是此时 3 上已经有元素了，所以这时就会使用链表的头插将数据 23 插入到 13 的前面，那么这里的图片就是下面这样：

如果再插入数据 33 的话计算的位置依然是 3，所以就会把 33 放到 3 号位置对应的链表的头部，那么这里的图片就变成下面这样：

那么这就是哈希桶的插入规则，找到对应位置的链表将数据插入到头部即可，如果要查找的话也是相同的原理先找到数据对应的链表然后循环遍历这个链表找到出现的数据即可，删除也是相同的道理，先找到数据对应的下标然后根据下标找到对应的链表，最后遍历链表找到要删除的数据进行链表的删除即可，那么这就是哈希桶的实现思路接下来我们就来看看这种方法的准备工作。

准备工作

哈希的底层是一个 vector 的数组，数组中的每个节点都有一个 pair 类型的数据，其次还有一个指针指向当前链表节点的下一个节点，所以每个节点中有个一个 pair 类型的数据和一个指向节点的指针，所以这里得创建一个类来描述每个节点，并且类中有一个构造函数来初始化节点，这里的构造函数就需要一个 pair 类型的参数，在构造函数里面就将指针初始化为 nullptr 将 pair 类型的参数赋值为传递过来的参数，有因为这里的节点可能要存储各种各样的数据，所以这里得创建个模板来接收各种各样的参数，并且模板的参数得是两个，那么这里的代码就如下：

template<class K,class V>struct HashNode{	HashNode(const pair<K,V>& kv)		:_kv(kv)		,_next(nullptr)	{}	pair<K, V> _kv;	HashNode* _next;};

复制代码

根据前面的学习我们知道要想计算数据对应在哈希表上的位置就得添加对应的仿函数，那么这里的代码就如下

template<class K>struct HashFunc{	size_t operator()(const K& key)	{		return (size_t)key;	}};template<>struct HashFunc<string>{	size_t operator()(const string& s)	{		size_t res = 0;		for (auto& ch : s)		{			res *= 131;			res += ch;		}		return res;	}};

复制代码

最后就是哈希 bucket 类的准备工作，首先这个类有一个模板，模板中有三个参数，前两个表示存储数据的类型，最后一个表示的是仿函数，因为哈希的地城是 vector 数组，所以这里得添加一个 vector 容器用来存储数据和一个整型变量用来记录容器中有效字符的个数即可，并且 vector 中的每个元素都是节点类型，那么该类的构造函数就将 vector 容器的 resize 到 10 个元素即可，那么这里的代码就如下：

template<class K, class V, class Hash = HashFunc<K>>class BucketTable{	typedef HashNode<K, V> Node;public:typedef HashNode<K, V> Node;	BucketTable()		:_n(0)	{		_tables.resize(10);	}private:	vector<Node*> _tables;	size_t _n;};

复制代码

看到这里我们的准备工作就完成了接下来就要实现哈希的每个函数。

find 函数

find 函数就是先根据传递过来参数找到这个参数可能出现的位置，找到了位置就意味着找了一个链表的头节点，所以这个时候就可以通过循环遍历的方式来一一对比链表中是否含有想要查找的数据，如果存在的话就返回这个节点所在的地址，如果不存在的话就返回一个空指针，所以该函数的第一步就创建一个仿函数对象，并计算数据出现的位置：

Node* Find(const K& key){	Hash hf;	size_t pos = hf(key) % _tables.size();	Node* cur=_tables[pos]}

复制代码

cur 指向的是链表的第一个元素，所以接下来就可以使用 while 循环一个一个的遍历每个元素，每次循环都会改变 cur 的指向让其指向下一个元素，知道 cur 本身变为空就停止查找，在循环体的内部如果出现了跟查找变量一样的值就直接返回这个节点的地址，如果循环结束了也没有找到想要的值的话就返回一个空指针，那么这里的代码就如下：

Node* Find(const K& key){	Hash hf;	size_t pos = hf(key) % _tables.size();	Node* cur = _tables[pos];	while (cur)	{		if (cur->_kv.first == key)		{			return cur;		}		else		{			cur = cur->_next;		}	}	return nullptr;}

复制代码

插入函数

将数据插入的链表的时候得先判断一下要插入的元素当前是否已经存在，所以这里可以使用 find 函数来进行查找，根据 find 函数的返回值来判断是否存在，那么这里的代码就如下：

bool insert(const pair<K, V>& kv){	if (Find(kv.first))	{		return false;	}}

复制代码

如果当前的元素不存在的话就开始插入数据，这种实现方法也得根据传递过来的元素找到应该插入的位置，所以该函数的第一步就是创建一个仿函数对象然后根据传递过来的参数计算得出应该插入的位置，找到插入位置之后就使用头插来插入对应的数据，这里的头插就是先让 newnode 的_next 指向当前位置的链表，然后修改 vector 中当前位置的指向使其指向 newnode，那么这里的代码就如下：

bool insert(const pair<K, V>& kv){	if (Find(kv.first))	{		return false;	}	Hash hf;	size_t pos = hf(kv.first) % _tables.size();	Node* newnode = new HashNode<K,V>(kv);	newnode->_next = _tables[pos];	_tables[pos] = newnode;	++_n;	return true;}

复制代码

这里依然得添加负载因子，官方库中可以通过一些函数来得到当前容器的负载因子和最大的负载因子，如果负载因子等于 1 了我们就扩容，将其容量变为之前的两倍，但是扩容不能直接把链表对应的移动到新的容器上去因为这里的映射关系已经改变了比如说当前容器的容量为 10 则数据 18 对应的位置就是 8 上面的链表，如果容器发生了扩容使得容量变成了 20 的话 18 就对应的不再是 8 而是 18 上面的链表，所以我们这里解决的方法就是创建一个新的哈希表，然后遍历容器中的每个位置，如果当前位置不为空就往这个位置里面进行遍历对每个元素都进行插入操作，如果当前位置为空的话就跳转到下一个元素，那么这里的代码就如下：

bool insert(const pair<K, V>& kv){	if (!Find(kv.first))	{		return false;	}	if (_n / _tables.size() == 1)//平衡因子为1就更新	{		vector<Node*> newBH;		newBH._tables.resize(_n * 2);		for (auto& cur : _tables)		{			while (cur)			{				newBH.insert(cur->_kv);				cur = cur->_next;			}		}		_tables.swap(newBH._tables);	}	Hash hf;	size_t pos = hf(kv.first) % _tables.size();	Node* newnode = new HashNode<K,V>(kv);	newnode->_next = _tables[pos];	_tables[pos] = newnode;	++_n;	return true;}

复制代码

erase 函数

erase 函数也是分为三步来完成，首先找到节点对应的链表，然后再找链表中是否存在该元素，如果不存在的话就返回 false，如果存在的话就对该链表的该节点进行删除，因为这里删除的时候得保证链表之间的上下链接，所以这里创建一个指向指向被删除节点的前一个节点，以此来保证删除前后的链接，这里大家要注意的一点就是当删除的节点是头节点时，得改变 vector 容器中的指针的指向，那么这里的代码就如下：

bool erase(const K& key){	HashFunc<K> HF;	size_t pos = HF(key) % _tables.size();	Node* cur = _tables[pos];	Node* prev = cur;	while (cur)	{		if (cur->_kv.first == key)		{			if (cur == _tables[pos])			{				_tables[pos] = cur->_next;			}			else			{				prev->_next = cur->_next;			}			delete cur;			_n--;			return true;		}		else		{			prev = cur;			cur = cur->_next;		}	}	return false;}

复制代码

代码测试

可以通过下面的代码来进行相应的测试看看我们上面写的代码是否是正确的：

void TestHT1(){	BucketTable<int, int> ht;	int a[] = { 18, 8, 7, 27, 57, 3, 38, 18 };	for (auto e : a)	{		ht.insert(make_pair(e, e));	}	ht.insert(make_pair(17, 17));	ht.insert(make_pair(5, 5));	if (ht.Find(7)) { cout << "存在" << endl; }	else { cout << "不存在" << endl; }	ht.erase(7);	if (ht.Find(7)) { cout << "存在" << endl; }	else { cout << "不存在" << endl; }}int main(){	TestHT1();	return 0;}

复制代码

代码的运行结果如下：

我们可以再用下面的代码来进行一下测试：

void TestHT2(){	string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };	//HashTable<string, int, HashFuncString> countHT; 	BucketTable<string, int> countHT;	for (auto& e : arr)	{		HashNode<string, int>* ret = countHT.Find(e);		if (ret)		{			ret->_kv.second++;		}		else		{			countHT.insert(make_pair(e, 1));		}	}}

复制代码

这段代码的运行结果如下：

有了这个游戏之后就可以对 insert 函数进行改进，但是这里先不要急还有一个地方需要我们改进的就是插入数据的时候，上面扩容在插入数据的时候是创建一个哈希桶然后再调用哈希桶来插入原来哈希桶的每个数据，如果这么做的话，在新的哈希桶里面又会不断地创建地节点，并且在函数结束地时候又会删除节点，如果节点的个数非常多的话这就会导致效率低下，所以我们这里就有一个改进思路就是能不能用已有的节点来插入到新创建的哈希表呢？答案是可以的，我们依然是创建一个新的哈希表然后改变其内部的大小，然后遍历之前的老哈希表找到里面的元素并计算他在新表上的位置，然后修改其节点内部指针的指向，那么这里的代码如下：

if (_n / _tables.size() == 1)//平衡因子为1就更新{	/*vector<Node*> newBH;;	newBH.resize(_n * 2);	for (auto& cur : _tables)	{		while (cur)		{			newBH.insert(cur->_kv);			cur = cur->_next;		}	}	_tables.swap(newBH._tables);*/	vector<Node*> newBH;	newBH._tables.resize(__stl_next_prime(_tables.size()));	for (int i = 0; i < _tables.size(); i++)	{		Node* cur = _tables[i];		while (cur)		{			Node* next = cur->_next;			size_t pos = Hash()(cur->_kv.first);			cur->_next = newBH[pos];			newBH[pos] = cur;			cur = next;		}		_tables[i] = nullptr;	}}