【C++进阶篇】哈希表的模拟实现（赋源码）

前言

哈希表的核心思想就是映射，通过将key值以某种算法映射成不大于哈希表长度的哈希值，从而实现存储数据。上篇提到解决哈希冲突有 闭散列 和 开散列，本文将用这两种理论思想实现哈希表。
代码位置：哈希模拟的实现源码

一. 开放地址法实现哈希表

1.1 闭散列结构定义

该闭散列哈希表使用vector数组，其中数组里面包含一个结构体，该结构存储pair类型数据及当前位置的状态，是否为空，不为空，或者有数据然后被删除了的三个状态，伪代码如下：

//节点可能的三种状态
enum State
{
	EXIST,
	EMPTY,
	DELETE
};

//哈希表中存储的数据
template<class K, class V>
struct HashData
{
	pair<K, V> _kv;//存放数据类型
	State _state = EMPTY;//当前位置的状态，默认为空，即表示此位置没有数据
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;//表中实际存储的数据个数
};

• 仿函数作用：

因为里面是数组，通过key值映射成哈希值后，哈希值不能超过哈希表的长度，需要取模，所以同时也要传入仿函数，将任意类型数据不能取模转换成整数，本来就可以进行取模运算的，就无需借助额外的仿函数，所以就可以给一个默认的仿函数，该仿函数给本来是整数去使用的。

//默认的仿函数
template<class K>
class HashFunc
{
public:
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

1.2 构造函数

给vector数组开一定的空间，为了防止2的幂次方的数，底层给了一定合理的素数，下面给代码即可。

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

HashTable()
{
	_tables.resize(__stl_next_prime(1));
}

1.3 插入（线性探测）

插入之前判断该key值是否在存在，存在直接返回即可。对插入的key值映射成哈希值，然后进行探测，探测规则：当前位置为空，继续向后探测，跳出循环后，将该位置插入数据并将该位置的状态设置为存在，_n++(表示存储的数据个数+1)，这里有一个问题：扩容？？？

• 问题：如何扩容

1.3.1 传统写法

创建一个数组（数组已经扩容后），将旧表中的vector数组中的数据重新进行映射成新开的数组（这里的一个优势在于：原来在旧表中冲突的数据可能在新表中就不冲突了），也需进行探测，过程基本与插入过程一致，将旧数据完成探测之后，在新表与旧表进行交换。伪代码如下：

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

	//扩容
	if ((double)_n / (double)_tables.size() >= 0.7)
	{
		// 获取素数表里面比当前表大的下一个素数
		size_t newSize = __stl_next_prime(_tables.size() + 1);
		vector<HashData<K, V>> newTables(newSize);
		//遍历旧表，将数据都映射到新表
		for (size_t i = 0; i < _tables.size(); i++)
		{
			if (_tables[i]._state == EXIST)
			{
				size_t hash0 = _tables[i].kv.first % newSize;
				size_t i = 1;
				size_t hashi = hash0;
				while (newTables[hashi]._state == EXIST)
				{
					//冲突探测
					hashi = (hash0 + i) % newSize;
					i++;
				}

				newTables[hashi]._kv = kv;
				newTables[hashi]._state = EXIST;
				//_n++;需不需要写？？？思考一下
			}
		}
			_tables.swap(newTables);

		
	}

	Hash hs;
	size_t hash0 = hs(kv.first) % _tables.size();
	size_t i = 1;
	size_t hashi = hash0;
	while (_tables[hashi]._state == EXIST)
	{
		//冲突探测
		hashi = (hash0 + i) % _tables.size();
		i++;
	}

	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	_n++;

	return true;
}

• 细节1：

重新寻找哈希值，需要对新的哈希表的长度进行取余，不要依然对旧表中的哈希表长度进行取余，否则会导致新表中新增加的长度没有被使用，冲突概率未减少。

• 细节2：

_n++需不需要写？？？不需要，因为是将旧表中的数据重新映射至新表，数据并没有增加。

注意：可以看出上述代码有点冗余，特别是插入过程与重新建立映射关系的代码很相似。
下面这种写法很巧妙，且代码量少。

1.3.2 现代写法

思想：建立一个新表，然后给新表中的哈希表开一定足够的空间，然后将旧表中的数据直接插入新表中即可，插入的过程同时也完成探测过程。很优雅的写法，建议采用它。

• 伪代码：

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

	//扩容
	if ((double)_n / (double)_tables.size() >= 0.7)
	{
		size_t newSize = __stl_next_prime(_tables.size() + 1);
		HashTable<K, V, Hash> newHT;
		newHT._tables.resize(newSize);

		//遍历旧表，将数据都映射到新表
		for (size_t i = 0; i < _tables.size(); i++)
		{
			if (_tables[i]._state == EXIST)
			{
				newHT.Insert(_tables[i]._kv);//此行为已经将旧数据映射到了新表中，同时进行线性探测和冲突探测，可能原来在旧表中的数据冲突，在新表中它就不冲突了
			}
		}

		_tables.swap(newHT._tables);//将新表与旧表进行交换
	}

	Hash hs;
	size_t hash0 = hs(kv.first) % _tables.size();
	size_t i = 1;
	size_t hashi = hash0;
	while (_tables[hashi]._state == EXIST)
	{
		//冲突探测
		hashi = (hash0 + i) % _tables.size();
		i++;
	}

	_tables[hashi]._kv = kv;
	_tables[hashi]._state = EXIST;
	_n++;

	return true;
}

该实现是一个功能完整的线性探测哈希表，适合学习用途。

1.4 查找

查找过程很简单，首先对要查找的key值转化成映射后的哈希值，对应位置状态为！EXIST，进行查询当前位置状态不为空，且不为删除直接返回该指针即可，否则继续往后探测，当探测为空，说明不存在，直接返回nullptr即可。

• 伪代码：

HashData<K, V>* Find(const K& key)
{
	Hash hs;
	size_t hash0 = hs(key) % _tables.size();
	size_t hashi = hash0;
	size_t i = 1;
	while (_tables[hashi]._state != EMPTY)
	{
		if (_tables[hashi]._state == EXIST
			&& _tables[hashi]._kv.first == key)
		{
			return &_tables[hashi];
		}

		hashi = (hash0 + i) % _tables.size();
		++i;
	}

	return nullptr;
}

1.5 删除

直接调用接口Find即可，接收返回值，判断返回值是否为空，为空直接返回false；不为空将该位置的状态设置为删除即可，然后返回true即可。

• 伪代码：

bool Erase(const K& key)
{
	HashData<K, V>* ret = Find(key);
	if (ret == nullptr)
	{
		return false;
	}
	else
	{
		--_n;
		ret->_state = DELETE;
		return true;
	}
}

标记删除操作时间复杂度为 O(1)，无数据迁移开销。
声明：上述做法了解一下即可，下面这个才是王炸，需重点关注及掌握。

二. 链地址法实现哈希表（哈希桶）

2.1 开散列结构定义

该开散列哈希表使用vector数组，其中数组里面包含一个哈希表节点，该节点存储pair类型数据及下一个哈希表数据的指针。伪代码如下：

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;
    vector<Node*> _tables;    // 哈希槽数组（存储链表头指针）
    size_t _n = 0;            // 当前元素总数
};

该代码提供了链地址法哈希表的核心骨架。

2.2 构造函数

构造函数与上述闭散列一致。

inline unsigned long __stl_next_prime(unsigned long n)
{
	// Note: assumes long is at least 32 bits.
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

HashTable()
{
	_tables.resize(__stl_next_prime(1), nullptr);
}

2.3 插入

创建一个数组，扩容时，将旧表中的节点挪动至新表中，需重新建立映射关系，也需要进行探测，过程与插入过程一致，将旧数据完成探测之后，在新表与旧表进行交换。伪代码如下：
**插入数据时有个问题，**进行尾插还是头插，两者都可以，但头插很简单，尾插相对较复杂，需要找尾，当前桶挪动完毕，需要将当前桶只为nullptr，本文以头插为示例。

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

	if (_n == _tables.size())
	{
		size_t newSize = __stl_next_prime(_tables.size() + 1);
		vector<Node*> newtables(newSize, nullptr);
		//遍历旧表，将旧表的节点挪动到新表
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;

				size_t hashi = cur->_kv.first % newSize;
				cur->_next = newtables[hashi];
				newtables[hashi] = cur;
			}

			_tables[i] = nullptr;
		}

		_tables.swap(newtables);
	}

	size_t hashi = kv.first % _tables.size();
	Node* newnode = new Node(kv);

	//头插，尾插也行，找尾麻烦,需要找尾
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;
	++_n;
	return true;
}

2.4 查找

查找过程很简单，将要查找的key值转换成哈希值，然后对该桶进行遍历，判断桶中的数据key值是否与要查找的key值是否相等，相等返回该节点指针即可，找到空还未找到，返回nullptr即可。

• 伪代码如下：

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

	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}

		cur = cur->_next;
	}

	return nullptr;
}

2.5 删除

删除需要前驱指针（默认为空）将删除后的节点连接起来，删除过程相对来说较复杂，也需要要删除的key值转换成哈希值，然后遍历该桶，判断桶中节点的数据key值与要查找的key值是否相等，相等进行删除，返回true即可，里面有细节 -> :

• 细节一：

当删除头结点时，头结点没有前驱指针，会对空指针进1行解引用，所以需要分情况讨论。

1. 前驱指针不为空，和为空两种状态。
2. 不相等继续往后找，当前桶找完还未找到，返回false即可。

• 伪代码：

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

					delete cur;
					_n--;
					return true;
				}

				//不相等继续往后找
				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

代码正确处理了链表节点的删除，维护了计数器_n，但未处理重复键（若允许存在）。

三. 最后

本文详述了哈希表的两种实现方式：开放地址法（闭散列）与链地址法（开散列）。开放地址法通过线性探测解决冲突，采用标记删除优化性能，扩容时重建哈希表；链地址法以链表处理冲突，头插法简化操作，扩容时重新映射所有节点。两者均使用素数表优化哈希分布，核心操作包括插入、查找、删除，适用于不同场景，是高效键值存储的关键技术。