C++:探索哈希表秘密之哈希桶实现哈希

发布于:2024-11-29 ⋅ 阅读:(26) ⋅ 点赞:(0)

在这里插入图片描述


前言

前面我们用开放定址法代码实现了哈希表:
C++:揭秘哈希:提升查找效率的终极技巧_1

对于开放定址法来说,包含以下两种探测插入节点位置方法:

  1. 线性探测
  2. 二次探测

在这里插入图片描述

但是开放定址法的缺点也很明显,开放定址法容易很多数据堆积在一起,大大减少了效率。

为了解决上述问题,引入了第二种方法实现哈希表
——链地址法(哈希桶法)


一、链地址法概念

开放定址法中,所有的元素都放到哈希表里。

链地址法中,所有的数据不再直接存储在哈希表中。哈希表中存储一个指针,没有数据映射到这个位置时,这个指针为空;有多个数据映射到这个位置时,我们把这些冲突的数据链接成一个链表,挂在哈希表这个位置下面。链地址法也叫做拉链法或者哈希桶。

下⾯演⽰ {19,30,5,36,13,20,21,12,24,96} 等这⼀组值映射到M=11的表中。

在这里插入图片描述


二、哈希表扩容

开放定址法的负载因子必须小于 1,而链地址法的负载因子则没有限制,可以大于 1。

负载因子越大,哈希冲突的概率越高,空间利用率越高;负载因子越小,哈希冲突的概率越低,空间利用率越低。

STL 中 unordered_xxx 的最大负载因子基本控制在 1,当负载因子大于 1 时会扩容。我们下面的实现也使用这种方式。

也就是说,我们期望基本每个节点下面都挂一个桶,有那么一两个数据,如下图:

在这里插入图片描述


三、哈希桶插入逻辑

首先,如果不需要扩容,我们需要将一个节点挂上去,因为每一个哈希桶类似于链表,而链表的头插效率是十分高的,因此我们采用头插。

在这里插入图片描述

// 如果不需要扩容
			size_t hashi = hf(kv.first) % _table.size();

			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;

			++_n;
			return true;

其次,如果需要扩容的话,需要遍历_table取每一个哈希桶的每一个结点重新插入到新表,但是这样的话还牵扯到了旧表资源的释放。

因此我们使用顺手牵羊,直接将旧表的节点迁过来头插,解决资源释放的问题。

在这里插入图片描述

// 遍历旧表,顺手牵羊,把节点牵下来挂到新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						// 头插到新表
						size_t newhashi = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[newhashi];
						newTable[newhashi] = cur;

						cur = next;
					}

					_table[i] = nullptr;
				}

				_table.swap(newTable);
			}

四、析构函数

因为我们vector中存储的是自定义类型,因此我们需要显示写析构函数。

遍历整个哈希表,删除每一个节点,最后将其置空。

~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				_table[i] = nullptr;
			}
		}

五、删除逻辑

删除就比较简单了,它分两种情况:

  1. 删除的值prev为空——直接删除它,把_table[i] = cur

在这里插入图片描述

  1. 删除的值prev不为空——涉及到前后的链接

在这里插入图片描述

bool Erase(const K& key)
		{
			HashFunc hf;

			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

六、查找

这里的查找比较简单,遍历整个_table就可以啦~
在这里插入图片描述


七、链地址法代码实现总结

#pragma once
#include<vector>

namespace hash_bucket
{
	template<class K>
	struct DefaultHashFunc
	{
		size_t operator() (const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct DefaultHashFunc<string>
	{
		size_t operator() (const string& str)
		{
			// BKDR
			size_t hash = 0;
			for (auto ch : str)
			{
				hash *= 131;
				hash += ch;
			}

			return hash;
		}
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		HashData<K, V>* _next;

		HashData(const pair<K, V>& kv)
			: _kv(kv)
			, _next(nullptr)
		{}
	};

	template<class K, class V, class HashFunc = DefaultHashFunc<K>>
	class HashTable
	{
		typedef HashData<K, V> Node;
	public:
		HashTable()
		{
			_table.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				_table[i] = nullptr;
			}
		}

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

			// 仿函数控制
			HashFunc hf;

			// 如果需要扩容
			if (_n == _table.size())
			{
				size_t newSize = _table.size() * 2;
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);

				// 遍历旧表,顺手牵羊,把节点牵下来挂到新表
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;

						// 头插到新表
						size_t newhashi = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[newhashi];
						newTable[newhashi] = cur;

						cur = next;
					}

					_table[i] = nullptr;
				}

				_table.swap(newTable);
			}

			// 如果不需要扩容
			size_t hashi = hf(kv.first) % _table.size();

			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;

			++_n;
			return true;
		}

		Node* Find(const K& key)
		{
			HashFunc hf;

			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		bool Erase(const K& key)
		{
			HashFunc hf;

			size_t hashi = hf(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;

			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}

			return false;
		}

		void Print()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				printf("[%d]->", i);
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << ":" << cur->_kv.second << "->";
					cur = cur->_next;
				}
				printf("NULL\n");
			}
			cout << endl;
			
		}

	private:
		vector<Node*> _table;     // 指针数组
		size_t _n = 0;            // 存储了多少个有效数据
	};
}

到这里就结束啦,创作不易,如果对您有帮助的话,麻烦给一个一键三连,谢谢各位大佬~

在这里插入图片描述