【C++】哈希表

以前，在顺序结构中，查找一个元素时，需要遍历每一个数据并判断比较，这样的最大时间复杂度为 $O(N)$ ；而在一个平衡树中，查找的一个元素的时候，最大的查找次数就是高度次，时间复杂度是 $O(\log N)$ ，我们常说的二分查找的效率也是 $O(\log N)$ 。它们的搜索的效率都取决于搜索过程中元素的比较次数。

我们理想的搜索方法应该是：不经过任何比较，一次直接从表中得到要搜索的元素，实现的时间复杂度为 $O(1)$ 。所以如果我们实现一种能够让元素的值与其存储位置存在映射关系的结构，这就可以使我们很快的查找到该元素了。而这种方式就是哈希（散列）方式。

哈希

哈希（hash）又称为散列。它是一种可以通过某种函数能够让元素的值与其存储位置存在映射关系的结构，其底层的存储结构是一个类似数组的结构。转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

因此，在向该结构中，插入元素的时候，我们就可以根据待插入元素的关键码（也就是实现的结构），通过哈希函数来映射出对应的位置进行插入。

而映射的实现是通过哈希函数实现的。

二、哈希函数

通过哈希函数可以将一个元素映射到对应的存储位置（也就是一个数组的下标所在位置）。这里我们介绍两种常用的方法就行了：直接定址法和除留余数法。

直接定址法的哈希函数是关键码的线性函数，即： $Hash(key)= A*key + B$ 。比如：对于下面的集合{10,30,50,70,80,90}，要放在一个有10个空间的数组中，则我们就可以选取 $Hash(key)= key/10$ 为哈希函数，则得到的哈希表如下所示：

这种方法的优点是：简单、均匀，但缺点也很明显，就是需要事先知道关键字的分布情况。

除留余数法，如果空间个数为m，则取一个不大于m，但最接近或者等于m的质数 p作为除数，按照哈希函数： $Hash(key) = key \% p$ ，其中 $p\leqslant m$ ，将关键码转换成哈希地址(数组下标)即可。比如下面这个集合{7，19，15，23， 11，44}，放在一个有10个空间的数组中，取p为10，则哈希函数就是： $Hash(key) = key \% 10$ ，则可以得到哈希表：

除留余数法算不需要先知道关键码的分布，是一种最简单，也最常用的方法了。

当然除了这两种方法，还有许多其他不常用的方法，如：平方取中法，折叠法，随机数法等等。

三、哈希冲突

对于两个数据元素的关键字 $k_i$ 和 $k_j$ (i != j)，有 $k_i\neq k_j$ ，但有： $Hash(k_i) == Hash(k_j)$ ，即：不同关键字通过相同哈希哈数计算出相同的哈希地址（下标），该种现象称为哈希冲突或哈希碰撞。比如：以 $Hash(key) = key \% 10$ 作为哈希函数为例，如果我们要将14和44,都放入到一个可以存放10个整数的空间，那么此时通过哈希函数得到的下标值是一样的，都是4。

那么，出现哈希冲突我们又该如何解决呢？请看下面的第五点。

四、负载因子

我们知道哈希表是用一个数组实现的，那么当我们想你哈希表中插入数据时，如果表中的数组大小不够的情况下，就需要将原本的数组扩容。但是，实际上，我们并不会等到哈希表中数组的所有空间都使用完了才扩容，而是到某一个规定的值时，才扩容。控制这个值的就是负载因子。

负载因子是哈希表中用来控制哈希表的这个数组扩容时机的变量，它的定义是： 负载因子（ $\alpha$ ）= 填入表中的数据个数 / 哈希表的长度 。

一般情况下：

负载因子越小：哈希表越 “空”，哈希冲突的概率越低，空间利用率越低（空间浪费严重）；
负载因子越大：哈希表越 “满”，哈希冲突的概率越高（冲突频繁，则查询 / 插入效率大幅下降），空间利用率越高。

所以，我们通常会将负载因子设置为到适中的位置，所以现在几乎所有编程语言的哈希表实现（比如 Java 的 HashMap、Python 的 dict）都会设置一个负载因子阈值（通常是 0.75），当实际负载因子超过这个阈值时，哈希表会触发 扩容（rehash） 操作。我们这里的哈希表也是一样。

五、解决哈希冲突的办法

解决哈希冲突两种常见的方法是：闭散列 和 开散列。

1. 闭散列（开放定址法）

闭散列：也叫开放定址法（open address）。通过开放定址法处理哈希冲突的散列表称为闭散列表。当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么就可以把 key 存放到冲突位置中的下一个空位置中去。找下一个空位置的常用方法有线性探测法和二次探测法。

（1）线性探测法

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止，如果做到当前哈希表的末尾仍没有找到空位置，则就绕回到表头开始找。比如：对于下面这个数据：

如果我们要插入33，通过哈希函数得到下标是3，但是3这个位置被23这个值占了，所以需要向后找，直到找到为空的位置，才能将它插入进去；如果我们要插入29，通过哈希函数得到的下标是9，但下标为9的位置也被占了，并且这个位置是哈希表的最后一个位置，则需要从哈希表的开头，即从下标为0的位置再开始找是空的位置，如下所示：

线性探测的优缺点：

线性探测优点：实现非常简单。
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得查找某关键码的位置需要许多次比较，导致搜索效率降低。

（2）二次探测法

线性探测的缺陷是容易产生数据“堆积”，这是因为它找空位置的方式就是挨着往后逐个去找。而二次探测则避免了这个问题。

二次探测是从最开始发生冲突的位置开始依次左右方式探测，找下一个空位置的方法为： $H_{i}= (H_0 + i^2 )\% m$ ，其中增量序为 $(i=1^2,2^2,3^2,...)$ ， $H_0$ 表示最开始发生冲突的位置， $H_i$ 表示第i次探测。比如：对于下面的数据：

插入33，则只需要进行两次探测就可以了，如下所示：

注意：有些变种算法会采用双向二次探测，即增量序为 $+1^2,-1^2,+2^2,-2^2,+3^2,-3^2,.......$ ，这样可以在发生冲突时，既向后跳也向前跳，进一步分散数据。

（3）代码实现

下面，我们就简单来实现一下通过线性探测法的哈希表：

首先我们哈希表是一个数组，所以我们可以通过vectro来实现，而它的每一个位置存储的是一个值（这里我们采用Key_Vlaue的类型存储），除此之外，由于还需要存储一个状态，来表示这个位置的实际情况，如果这个数据没有数据，那这个位置就是空，如果这个位置刚刚被删除，则就是处于删除状态，如果这个位置有数据，则就是存在状态。所以哈希表的基础框架就出来了：

#pragma once
#include<vector>
#include<utility>
using namespace std;
// 开放定址法
namespace open_address
{
	//定义状态
	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 HashTable
	{
	public:
        // 哈希表的操作
        // ......


	private:
		vector<HashData<K, V>> _table; // 表示这个哈希表
		size_t _n = 0; // 表示表中有效数据的个数
	};

}

然后我们在实现其他的函数操作（即插入，查找，删除的操作），那么我们的最终代码如下所示：

#pragma once
#include<vector>
#include<utility>
using namespace std;
// 开放定址法
namespace open_address
{
	//定义状态
	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 HashTable
	{
	public:
		// 构造
		HashTable()
		{
			_table.resize(10);
		}
		// 查找操作
		HashData<K, V>* Find(const K& key)
		{
			if (_n == 0) return nullptr;
			size_t hash_i = key % _table.size();
			// 线性探测来找值
			while (_table[hash_i]._state != EMPTY)
			{
				if (_table[hash_i]._state == EXIST    // 这个位置存在
					&& _table[hash_i]._kv.first == key)  // 是查找的值
				{
					return &_table[hash_i];
				}

				// 当前值不是，则向后找
				hash_i++;
				hash_i %= _table.size(); // 当hash_i加到表尾之后，则从头开始再找，直到为空才停止
			}
			return nullptr;
		}

		// 插入操作
		bool insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false; //如果该值存在，则插入失败
			}

			_CheckCapcity(); // 判断是否扩容

			// 线性探测--找位置
			size_t hash_i = kv.first % _table.size();
			while (_table[hash_i]._state == EXIST)
			{
				// 当前值存在，无法插入，则向后找
				hash_i++;
				hash_i %= _table.size();
			}
			// 开始插入
			_table[hash_i]._kv = kv;
			_table[hash_i]._state = EXIST;
			++_n; // 有效数据 +1
			return true;
		}
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			return false;
		}

	private:
		// 判断是否扩容
		void _CheckCapcity()
		{
			// 计算负载因子，判断是否扩容
			size_t a = _n * 10 / _table.size(); // 乘10防止数据丢失
			if (a >= 7) // 负载因子到0.7就扩容
			{
				// 2倍扩容
				size_t newSize = _table.size() * 2;
				// 先造一个新哈希表，再交换
				HashTable<K, V> newTable;
				newTable._table.resize(newSize);
				// 遍历旧表的数据插到新表
				for (int i = 0; i < _table.size(); i++)
				{
					// 在这一步不会进行扩容了，也就不会再次进入该扩容部分了，也就不会出现死循环
					newTable.insert(_table[i]._kv);
				}
				//交换和这两个表
				_table.swap(newTable._table);
			}
		}

	private:
		vector<HashData<K, V>> _table; // 表示这个哈希表
		size_t _n = 0; // 表示表中有效数据的个数
	};

}

2. 开散列（链地址法/开链法）

（1）基本原理

开散列法又叫链地址法(开链法)。使用这种方法构造的表也叫做开散列表。它的基本思想是：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各个链表的头结点存储在哈希表中。

例如：插入一个集合{11,21,31,23,15,5,18}，则得到的哈希表如下图所示：

（2）代码实现

框架实现

通过链地址法实现的哈希表的数组中的每一个元素都是一个单链表的头指针，所以我们节点定义和哈希表的框架实现如下所示：

namespace hash_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 HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		// 哈希表的操作
		// ......

	private:
		vector<Node*> _table; // 指针数组
		size_t _n = 0; // 表示表中有效数据(头指针)的个数
	};
}

哈希表的操作实现

构造和析构函数

构造函数初始化的时候可以实现先初始化10个空间，并将各个指针都置为空（nullptr）;

由于这里存储的数据都是一个一个节点，而申请的节点空间是不会自动释放的，所以我们还需要洗衣柜析构函数来处理这个申请的节点空间，防止内存泄漏。析构函数的实现就是先遍历哈希表，同时遍历各个单链表，逐个释放空间。其实现代码如下：

// 构造
HashTable()
{
	_table.resize(10, nullptr);
}
// 析构
~HashTable()
{
	// 遍历哈希表
	for (int i = 0; i < _table.size(); i++)
	{
		Node* cur = _table[i];
		// 遍历单链表
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_table[i] = nullptr;
	}
}

查找操作

由于哈希表中存的都是一个单链表的头结点，所以，我们查找时，就可以先通过哈希函数找到映射的位置，然后再遍历这个单链表进行查找。如果查找成功，则返回对应的节点指针。实现代码如下：

// 查找操作
Node* Find(const K& key)
{
	size_t hash_i = key % _table.size();
	Node* cur = _table[hash_i];
	while (cur)
	{
		if (cur->_kv->first == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}

插入操作

首先，判读插入的数据是否存在，如果已存在，则就插入就失败了。

然后再判断是否扩容：即判断负载因子是否大于1（这里的负载因子可以不用那么严格，控制在1，平均下来就是每个单链表都只有一个数据；另外std::unordered_map 的默认最大负载因子也是1，这样也可以保证封装时的一致）。考虑到这里的每一个数据都是一个申请的节点，那么扩容的方法就可以这样：遍历旧表，将各个节点都直接拿下来头插到新表中去，最后再将旧表置空，然后与新表交换。这样就扩容完成了。

最后插入新节点即可。实现代码如下所示：

    // 插入
	bool insert(const pair<K, V>& kv)
	{
		// 判断是否存在
		if (Find(kv.first)) return false;

		//判断是否扩容
		_CheckCapcity();

		// 插入新节点---头插
		size_t hash_i = kv.first % _table.size();
		Node* cur = new Node(kv);

		cur->_next = _table[hash_i];
		_table[hash_i] = cur;

		_n++;
		return true;
	}
private:
	// 判断是否扩容
	void _CheckCapcity()
	{
		// 计算负载因子
		size_t a = _n * 10 / _table.size(); 
		if (a == 10) // 负载因子到1就扩容
		{
			// 2倍扩容
			size_t newSize = _table.size() * 2;
			// 先造一个新哈希表，再交换
			vector<Node*> newTable;
			newTable.resize(newSize, nullptr);
			// 遍历旧表的数据，顺手迁到新表
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					//头插到新表
					size_t hash_i = cur->_kv.first % newSize;
					cur->_next = newTable[hash_i];
					newTable[hash_i] = cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
			//交换和这两个表
			_table.swap(newTable);
		}
	}

删除操作

删除一个值的节点，就是要先找到它的前一个节点，再进行删除操作；如果删除节点就是第一个节点，那么，我们就只需要修改哈希表上存储的头结点就可以了。实现代码如下所示：

// 删除
bool Erase(const K& key)
{
	size_t hash_i = key % _table.size();
	Node* cur = _table[hash_i];
	Node* prev = nullptr;
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			if (prev == nullptr)
			{
				_table[hash_i] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;

			}
			delete cur;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	return false;
}

（3）最终代码

关于开散列的总体实现如下所示：

#pragma once
#include<vector>
#include<utility>
using namespace std;
namespace hash_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 HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		// 构造
		HashTable()
		{
			_table.resize(10, nullptr);
		}
		// 析构
		~HashTable()
		{
			// 遍历哈希表
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				// 遍历单链表
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}

		// 查找操作
		Node* Find(const K& key)
		{
			size_t hash_i = key % _table.size();
			Node* cur = _table[hash_i];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		// 删除
		bool Erase(const K& key)
		{
			size_t hash_i = key % _table.size();
			Node* cur = _table[hash_i];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hash_i] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;

					}
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		// 插入
		bool insert(const pair<K, V>& kv)
		{
			// 判断是否存在
			if (Find(kv.first)) return false;

			//判断是否扩容
			_CheckCapcity();

			// 插入新节点---头插
			size_t hash_i = kv.first % _table.size();
			Node* cur = new Node(kv);

			cur->_next = _table[hash_i];
			_table[hash_i] = cur;

			_n++;
			return true;
		}



	private:
		// 判断是否扩容
		void _CheckCapcity()
		{
			// 计算负载因子
			size_t a = _n * 10 / _table.size(); 
			if (a == 10) // 负载因子到1就扩容
			{
				// 2倍扩容
				size_t newSize = _table.size() * 2;
				// 先造一个新哈希表，再交换
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);
				// 遍历旧表的数据，顺手迁到新表
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;
						//头插到新表
						size_t hash_i = cur->_kv.first % newSize;
						cur->_next = newTable[hash_i];
						newTable[hash_i] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				//交换和这两个表
				_table.swap(newTable);
			}
		}

	private:
		vector<Node*> _table; // 指针数组
		size_t _n = 0; // 表示表中有效数据(头指针)的个数
	};
}

3. 闭散列和开散列的比较

闭散列 (开放定址法)：当发生冲突时，按照某种探测策略（如线性探测、二次探测）在哈希表中寻找下一个空闲槽位，直到找到为止。

优点：

空间利用率高：不需要存储额外的指针，所有空间都用于存储数据。
缓存友好：数据在数组中是连续存储的，访问查询速度快。

缺点：

负载因子限制：负载因子，通常限制在较低水平，不能超过1，否则性能会极大的下降。
堆积问题：线性探测容易产生“堆积”，导致数据块越来越长；虽然二次探测能缓解此问题，但依然存在“堆积”问题。

开散列 (链地址法)：将哈希表的每个槽位（Bucket）定义为一个链表的头节点。所有哈希到同一位置的元素，都会被添加到该位置的链表中。

优点：

处理冲突简单：新节点只需要链接在对应单链表上即可。
适合高负载：即使负载因子超过1，依然可以工作，但性能会下降。是C++ std::unordered_map的首选方案。

缺点：

空间开销大：每个节点都需要链接指针，似乎增加了存储开销。

总的来说：虽然开散列需要设置链接指针，增加了存储开销。事实上：由于开散列必须保持大量的空闲空间以确保搜索效率（即负载因子<=0.75），而它的数据存储项所占空间又比指针大的多，所以使用闭散列反而比开散列节省存储空间。

六、解决存储string类型的问题

1. 解决方法

通过上面这两个代码，我们可以运行通过常规数字类型的存储，但是对于字符串呢？如下图所示：

说明我们还不能实现对字符串的访问。因为，我们在求映射的时候，都是直接使用pair中的first模上哈希表的大小的，因此当前的哈希表还不能实现对string的映射。要解决这个问题，我们可以使用一个仿函数，用来帮助我们取得string对应的映射值。怎么将字符串转成对应的整型呢？

这里采用了一种字符串哈希算法（一种将任意长度的字符串映射为固定长度数值的技术），它的原理就是选择一个质数作为种子（如131），通过递推公式 hash = hash * seed + current_char 计算出整个字符串的哈希值，这里的current_char 是指每一个字符的ASCLL码值。所以我们实现的仿函数代码如下所示：

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

//使用模板的特化，解决string类型的问题
template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

通过这个仿函数，我们就可以实现将string类型转成整型。这就需要我们在算映射关系的时候都使用这个 ()函数重载 。这里我们采用第三个模板参数来接收这个 ()函数重载 。实现代码如下所示：

template<class K, class V, class HashFunc = DefaultHashFunc<K> >
class HashTable
{
    // ......
}

2. 代码汇总

所以将所有取模时的key都修改一下，得到的最终代码如下所示：

对于闭散列：

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

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

//使用模板的特化，解决string类型的问题
template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

// 开放定址法
namespace open_address
{
	//定义状态
	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 = DefaultHashFunc<K>>
	class HashTable
	{
	public:
		// 构造
		HashTable()
		{
			_table.resize(10);
		}
		// 查找操作
		HashData<K, V>* Find(const K& key)
		{
			if (_n == 0) return nullptr;

			HashFunc hf;
			size_t hash_i = hf(key) % _table.size();
			// 线性探测来找值
			while (_table[hash_i]._state != EMPTY)
			{
				if (_table[hash_i]._state == EXIST    // 这个位置存在
					&& _table[hash_i]._kv.first == key)  // 是查找的值
				{
					return &_table[hash_i];
				}

				// 当前值不是，则向后找
				hash_i++;
				hash_i %= _table.size(); // 当hash_i加到表尾之后，则从头开始再找，直到为空才停止
			}
			return nullptr;
		}

		// 插入操作
		bool insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))
			{
				return false; //如果该值存在，则插入失败
			}

			_CheckCapcity(); // 判断是否扩容

			// 线性探测--找位置
			HashFunc hf;
			size_t hash_i =hf( kv.first) % _table.size();
			while (_table[hash_i]._state == EXIST)
			{
				// 当前值存在，无法插入，则向后找
				hash_i++;
				hash_i %= _table.size();
			}
			// 开始插入
			_table[hash_i]._kv = kv;
			_table[hash_i]._state = EXIST;
			++_n; // 有效数据 +1
			return true;
		}
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			return false;
		}

	private:
		// 判断是否扩容
		void _CheckCapcity()
		{
			// 计算负载因子，判断是否扩容
			size_t a = _n * 10 / _table.size(); // 乘10防止数据丢失
			if (a >= 7) // 负载因子到0.7就扩容
			{
				// 2倍扩容
				size_t newSize = _table.size() * 2;
				// 先造一个新哈希表，再交换
				HashTable<K, V> newTable;
				newTable._table.resize(newSize);
				// 遍历旧表的数据插到新表
				for (int i = 0; i < _table.size(); i++)
				{
					// 在这一步不会进行扩容了，也就不会再次进入该扩容部分了，也就不会出现死循环
					newTable.insert(_table[i]._kv);
				}
				//交换和这两个表
				_table.swap(newTable._table);
			}
		}

	private:
		vector<HashData<K, V>> _table; // 表示这个哈希表
		size_t _n = 0; // 表示表中有效数据的个数
	};
}

对于开散列：

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

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

//使用模板的特化，解决string类型的问题
template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto ch : str)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};

namespace hash_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 = DefaultHashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		// 构造
		HashTable()
		{
			_table.resize(10, nullptr);
		}
		// 析构
		~HashTable()
		{
			// 遍历哈希表
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				// 遍历单链表
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}

		// 查找操作
		Node* Find(const K& key)
		{
			HashFunc hf;
			size_t hash_i = hf(key) % _table.size();
			Node* cur = _table[hash_i];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
		// 删除
		bool Erase(const K& key)
		{
			HashFunc hf;
			size_t hash_i = hf(key) % _table.size();
			Node* cur = _table[hash_i];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr)
					{
						_table[hash_i] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;

					}
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		// 插入
		bool insert(const pair<K, V>& kv)
		{
			// 判断是否存在
			if (Find(kv.first)) return false;

			//判断是否扩容
			_CheckCapcity();

			// 插入新节点---头插
			HashFunc hf;
			size_t hash_i = hf(kv.first) % _table.size();
			Node* cur = new Node(kv);

			cur->_next = _table[hash_i];
			_table[hash_i] = cur;

			_n++;
			return true;
		}

	private:
		// 判断是否扩容
		void _CheckCapcity()
		{
			// 计算负载因子
			size_t a = _n * 10 / _table.size(); 
			if (a == 10) // 负载因子到1就扩容
			{
				// 2倍扩容
				size_t newSize = _table.size() * 2;
				// 先造一个新哈希表，再交换
				vector<Node*> newTable;
				newTable.resize(newSize, nullptr);
				// 遍历旧表的数据，顺手迁到新表
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;
						//头插到新表
						HashFunc hf;
						size_t hash_i = hf(cur->_kv.first) % newSize;
						cur->_next = newTable[hash_i];
						newTable[hash_i] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
				//交换和这两个表
				_table.swap(newTable);
			}
		}

	private:
		vector<Node*> _table; // 指针数组
		size_t _n = 0; // 表示表中有效数据(头指针)的个数
	};
}

感谢各位观看！希望能多多支持

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能