新手入门：用 C++ 实现开放定址法哈希表（附完整代码解析）

HalvmånEver

698人浏览 · 2025-10-20 17:18:09

HalvmånEver · 2025-10-20 17:18:09 发布

大家好！最近刚学完哈希表，捣鼓出了一个用开放定址法实现的版本，踩了不少坑也懂了很多细节。今天就从新手的角度，跟大家聊聊哈希表是什么、开放定址法怎么玩，再一步步拆解我写的代码，希望能帮到和我一样刚入门的小伙伴

对了，结尾附有详细代码，可以结合一起食用本博客(下一次更新哈希桶实现)

一、先搞懂：哈希表到底是个啥？

我们之前学过数组（查找慢，要遍历）、链表（插入慢，要找位置），那哈希表是干啥的？简单说就是 ——用空间换时间，实现 “近似 O (1) 查找”。

核心思路很简单：给每个 “键（K）” 算一个 “哈希值”，这个值对应数组的一个下标，把 “键值对（K-V）” 存在这个下标位置。比如键是 10，数组长度是 11，哈希值就是 10%11=10，就存在下标 10 的位置。下次找 10 的时候，直接算哈希值找下标 10，一秒定位，这就是哈希表快的原因！

二、冲突了怎么办？开放定址法来救场

理想很丰满，但现实会遇到 “哈希冲突”：两个不同的键，算出来的哈希值一样。比如数组长度 11，键 10 和键 21，10%11=10，21%11=10，都想存在下标 10，这就冲突了。

解决冲突有两种常见方法：哈希桶（挂链表）和开放定址法。今天我们聊的是开放定址法—— 冲突了就 “换个位置”，在数组里找下一个空的位置存，而不是挂链表。

举个例子：下标 10 冲突了，就看 11（模数组长度后是 0），再冲突看 1，直到找到空位置。这就是我们代码里用的 “线性探测”（最简单的开放定址法）。

三、代码拆解：从 0 到 1 实现开放定址法哈希表

先放完整代码（就是我写的那个版本），然后我们一点点拆，每个部分都讲清楚 “为什么这么写”“作用是什么”。

#pragma once
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

// 标记哈希表每个位置的状态
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 HashTable
{
private:
	vector<HashData<K, V>> _tables;  // 底层用vector存数据
	size_t _n;  // 有效数据个数（不是vector长度！）
public:
	// 找下一个素数（为什么用素数？后面讲）
	inline unsigned long __stl_next_prime(unsigned long n)
	{
		// 预定义的素数表（从STL里借鉴的，够用了）
		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
		};
		// 找第一个 >=n 的素数（用lower_bound，STL算法）
		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(__stl_next_prime(0))  // 初始长度设为第一个素数（53）
		, _n(0)  // 初始没有数据
	{}

	// 获取哈希表底层数组长度
	size_t GetSize()
	{
		return _tables.size();
	}

	// 插入键值对（核心函数）
	bool insert(const pair<K, V>& kv)
	{
		// 1. 先判断键是否已存在，存在就不插入
		if (Find(kv.first))
		{
			return false;
		}

		// 2. 检查负载因子，超过0.7就扩容（为什么是0.7？后面讲）
		if ((double)_n / _tables.size() >= 0.7)
		{
			HashTable<K, V> newht;  // 新建一个空的哈希表
			// 新表长度设为当前长度的下一个素数
			newht._tables.resize(__stl_next_prime(_tables.size() + 1));
			// 把旧表的有效数据（EXIST状态）重新插入新表
			for (auto& data : _tables)
			{
				if (data._state == EXIST)
				{
					newht.insert(data._kv);
				}
			}
			// 交换新旧表的数据（newht会自动销毁，不浪费空间）
			_tables.swap(newht._tables);
		}

		// 3. 计算哈希值（键 % 数组长度）
		size_t hash0 = kv.first % _tables.size();
		size_t hash1 = hash0;  // hash1用来找最终的位置

		// 4. 线性探测：冲突了就找下一个位置
		while (_tables[hash1]._state == EXIST)
		{
			hash1 = (++hash1) % _tables.size();  // 往后挪一位，模长度防止越界
		}

		// 5. 找到空位，存入数据
		_tables[hash1]._kv = kv;
		_tables[hash1]._state = EXIST;
		_n++;  // 有效数据个数+1

		return true;
	}

	// 查找键：找到返回数据地址，没找到返回nullptr
	HashData<K, V>* Find(const K& key)
	{
		// 计算初始哈希值
		size_t hash0 = key % _tables.size();
		size_t hash1 = hash0;

		// 线性探测：遇到EMPTY才停止（DELETE要继续找！）
		while (_tables[hash1]._state != EMPTY)
		{
			// 如果是EXIST且键匹配，返回地址
			if (_tables[hash1]._state == EXIST && _tables[hash1]._kv.first == key)
			{
				return &_tables[hash1];
			}
			// 继续往后找
			hash1 = (++hash1) % _tables.size();
		}

		// 遇到EMPTY，说明没找到
		return nullptr;
	}

	// 删除键：成功返回true，没找到返回false
	bool Erase(const K& key)
	{
		// 先找键的位置
		HashData<K, V>* ret = Find(key);
		if (ret == nullptr)
			return false;

		// 关键：不是设为EMPTY，而是设为DELETE
		ret->_state = DELETE;
		_n--;  // 有效数据个数-1
		return true;
	}
};

3.1 第一步：定义状态枚举（State）

为什么需要State？直接用 “是否为空” 判断不行吗？

一开始我也这么想，但删除元素的时候发现问题了：比如我删除了下标 5 的元素，如果把它设为EMPTY，下次查找下标 6 的元素时，遇到下标 5 的EMPTY就会停止，导致找不到 6 的元素（因为当初插入 6 是因为 5 冲突了，现在 5 设为 EMPTY，查找逻辑会误以为后面没有数据）。

所以需要三个状态：

EXIST：这个位置有有效数据；
EMPTY：这个位置从来没存过数据；
DELETE：这个位置的数据被删除了，查找时要继续往后找。

3.2 第二步：定义哈希数据结构（HashData）

每个位置要存两样东西：

pair<K, V> _kv：键值对（比如pair<int, string>存学号和姓名）；
State _state：这个位置的状态，初始是EMPTY（刚创建哈希表时，所有位置都是空的）。

3.3 第三步：素数表函数（__stl_next_prime）

这是我从 STL 源码里借鉴的一个函数，核心作用是 “找一个比 n 大的最小素数”。

为什么要用素数作为哈希表长度？

因为素数的因子只有 1 和它本身，用键对素数取模时，结果的分布会更均匀，冲突概率更低。

举个例子：如果数组长度是 10（非素数，因子有 2、5），键 10、20、30 取模都是 0，冲突严重；如果长度是 11（素数），10%11=10，20%11=9，30%11=8，分布均匀多了。

函数怎么工作？

预定义一个素数数组，包含从 53 到 4294967291 的素数（覆盖了大部分场景）；
用lower_bound在数组里找第一个大于等于 n 的素数（lower_bound是 STL 的二分查找算法，效率高）；
如果 n 比最大的素数还大，就返回最大的素数（防止越界）。

3.4 第四步：构造函数（HashTable ()）

初始化哈希表：

_tables(__stl_next_prime(0))：底层 vector 的初始长度是第一个素数（53），因为__stl_next_prime(0)找第一个 >=0 的素数是 53；
_n(0)：_n记录有效数据的个数，初始为 0（还没插入数据）。

3.5 第五步：插入函数（insert）—— 核心中的核心

插入要解决三个问题：“不能重复插入”“冲突了怎么办”“数组满了怎么办”。我们一步步看：

① 先判断键是否已存在

调用Find函数，如果找到相同的键，就返回false（不重复插入）。

② 检查负载因子，决定是否扩容

负载因子 = 有效数据个数（_n） / 哈希表长度（_tables.size ()）。

为什么设 0.7？这是经验值：负载因子越小，冲突概率越低，但浪费空间；负载因子越大，冲突概率越高，查找变慢。0.7 是平衡空间和时间的一个值，超过这个值就需要扩容。

③ 扩容逻辑

扩容不是简单地把数组拉长，而是：

新建一个哈希表（newht），长度是当前长度的下一个素数；
把旧表中所有EXIST状态的数据，重新插入新表（因为新表长度变了，键的哈希值也变了，不能直接复制）；
用swap交换新旧表的数据（newht是局部变量，交换后会自动销毁，不浪费内存）。

④ 线性探测解决冲突

计算初始哈希值hash0 = kv.first % _tables.size()；
如果hash0位置是EXIST（冲突了），就往后挪一位（hash1 = (++hash1) % _tables.size()），直到找到EMPTY或DELETE的位置；
把数据存入这个位置，状态设为EXIST，_n加 1。

3.6 第六步：查找函数（Find）

查找逻辑和插入的探测逻辑要一致（都是线性探测），否则会找不到数据。

计算初始哈希值hash0；
线性探测：遇到EMPTY就停止（说明后面没有目标数据）；遇到DELETE就继续找（因为这个位置的数据被删了，目标数据可能在后面）；
如果遇到EXIST且键匹配，就返回这个位置的地址（方便后续修改值）；没找到就返回nullptr。

3.7 第七步：删除函数（Erase）

删除的关键是 “不能设为EMPTY，要设为DELETE”。

先调用Find找到要删除的位置；
如果没找到，返回false；
如果找到，把状态设为DELETE（不是EMPTY！），_n减 1，返回true。

四、新手必看：测试代码

光懂代码还不够，跑起来才知道有没有用。写个main函数测试一下，插入、查找、删除都试一遍：

#include "HashTable.h"  // 包含我们写的哈希表头文件

int main()
{
	// 定义一个哈希表：键是int，值是string
	HashTable<int, string> ht;

	// 1. 插入数据
	ht.insert({ 1001, "张三" });
	ht.insert({ 1002, "李四" });
	ht.insert({ 1003, "王五" });
	cout << "插入后，哈希表长度：" << ht.GetSize() << endl;  // 初始长度53

	// 2. 查找数据
	auto find1 = ht.Find(1002);
	if (find1)
		cout << "找到1002：" << find1->_kv.second << endl;  // 输出“李四”
	else
		cout << "没找到1002" << endl;

	// 3. 删除数据
	bool erase1 = ht.Erase(1002);
	if (erase1)
		cout << "删除1002成功" << endl;
	else
		cout << "删除1002失败" << endl;

	// 4. 再次查找删除的数据
	auto find2 = ht.Find(1002);
	if (find2)
		cout << "找到1002：" << find2->_kv.second << endl;
	else
		cout << "没找到1002（删除成功）" << endl;

	return 0;
}

运行结果：

插入后，哈希表长度：53
找到1002：李四
删除1002成功
没找到1002（删除成功）

详细代码:

#pragma once
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

//开放定址法
//即在数组里面映射，有相同的取模值的话就寻找这个数组里面EMPTY的位置或者DELETE的位置映射
//edge
// 0 1 2 3 4 5
// n1 n2 n5 n3 n4

//哈希桶
//即在数组里面映射，有相同的取模值的话就用类似链表的东西挂在该数组对应位置的下面
//edge
// 0 1 2 3 4
// n1 n4 n7 n5
// n2 n6
// n3
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 HashTable
{
private:
   vector<HashData<K, V>> _tables;
   size_t _n; //记录数据个数
public:
   //直接打表弄素数，关键是这个真的是c++ gil标准实现写法
   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); //查找第一个 >=n 的数字
       return pos == last ? *(last - 1) : *pos;
   }

   HashTable()
       : _tables(__stl_next_prime(0)) //让他为素数，因为素数只能被他自己和1整除，可以更好的进行取模运算得到更多的不同风格值
       , _n(0)
   {}

   size_t GetSize()
   {
       return _tables.size();
   }

   bool insert(const pair<K, V>& kv)
   {
       if (Find(kv.first))
       {
           return false;
       }
       //负载因子计算 _n / _tables.size()
       if ((double)_n / _tables.size() >= 0.7) //负载因子已达上限，扩容
       {
           HashTable<K, V> newht;
           newht._tables.resize(__stl_next_prime(_tables.size() + 1)); //+1获取下一个素数，继续扩充为素数
           for (auto& data : _tables)
           {
               if (data._state == EXIST)
               {
                   newht.insert(data._kv);
               }
           }
           _tables.swap(newht._tables);
       }
       size_t hash0 = kv.first % _tables.size();
       size_t hash1 = hash0;
       //int i = 0; //控制1 2 3 4 5
       //int flag = 1; //控制+-
       while (_tables[hash1]._state == EXIST)
       {
           //线形探测(逻辑简单，往前加一，但是会造成数据堆积):
           hash1 = (++hash1) % _tables.size();
           //二次探测(逻辑复杂一点，+-1 * 1，+-2 * 2，+-3 * 3...):
           //要是简单点来，用线性探测足够
           //hash1 = (hash0 + (i * i * flag)) % _tables.size();
           //if (hash1 < 0) //处理负数情况
           //{
           //   hash1 += _tables.size();
           //}
           //if (flag == 1)
           //{
           //   flag = -1;
           //}
           //else
           //{
           //   i++;
           //   flag = 1;
           //}
           //如果使用二次探测，下面的Find函数也要修改哦，而且负载因子也要改为0.5，可以更标准
       }
       _tables[hash1]._kv = kv;
       _tables[hash1]._state = EXIST;
       _n++;
       return true;
   }

   HashData<K, V>* Find(const K& key)
   {
       size_t hash0 = key % _tables.size();
       size_t hash1 = hash0;
       while (_tables[hash1]._state != EMPTY)
       {
           if (_tables[hash1]._state == EXIST && _tables[hash1]._kv.first == key)
           {
               return &_tables[hash1]; //传地址回去，方便后续修改
           }
           hash1 = (++hash1) % _tables.size();
       }
       return nullptr;
   }

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