《C++进阶之STL》【哈希表】

/*------------------任务：定义哈希表函数的“结构体模板”------------------*/
template <class K>
struct HashFunc
{
	//1.重载()运算符 ---> 作用：将K类型转化为size_t类型，用于计算哈希值
	size_t operator()(const K& key)
	{
		return (size_t)key;  //注意：默认为直接转换，适用于int、long等整数类型
	} 
};



/*------------------任务：定义哈希函数的“模板特化”------------------*/
template <>
struct HashFunc<string>
{
	//1.实现：“()运算符的重载” ---> 作用：将string类型的变量转化为哈希值
	size_t operator()(const string& s)
	{
		//1.定义size_t类型变量记录string类型的变量计算的哈希值
		size_t hash = 0;

		//2.使用范围for循环遍历字符串并用BKDR算法计算其哈希值
		for (auto it : s)
		{
			//2.1：先将字符的ASCII值累加到哈希值中
			hash += it;
			//2.2：再让哈希值乘以质数131（BKDR哈希算法认为：131可有效减少冲突）
			hash *= 131;
		}

		//3.返回最终计算的哈希值
		return hash;
	}
};

/*------------任务：定义哈希表中节点的三种状态的“枚举”------------*/
enum State
{
	EXIST,  //存在状态
	EMPTY,  //空状态
	DELETE  //删除状态
};

/*------------任务：定义哈希表存储的数据结构的“结构体模板”------------*/
template <class K, class V>
struct HashData
{
	//1.存储键值对类型的数据
	//2.记录存储的节点的状态

	pair<K, V> _kv;
	State _state = EMPTY; //节点的状态默认为空
};



/*------------任务：使用“开放地址法 - 线性探测”实现哈希表------------*/
template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:
	/*------------------成员变量------------------*/

	//1.存储HashData类型数据的数组
	//2.记录哈希表中有效元素的变量 

	vector<HashData<K,V>> _tables;
	size_t _n;
    
public:
    //…………
    
};

/*------------------任务：实现“获取下一个 >=n 的质数的函数”---> “用于哈希表扩容”------------------*/
inline unsigned long _stl_next_prime(unsigned long n)
{
	//1.指定素数表的大小
	static const int __stl_num_primes = 28;

	//2.定义素数表覆盖常见哈希表大小
	static const unsigned long _stl_prime_list[__stl_num_primes] =   //注意：这里的素数表的类型是unsigned long 类型
	{
		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
	};

	//3.使用二分查找找到第一个 >=n 的素数
	//3.1：使用一个指针指向素数表中的“第一个素数”
	const unsigned long* first = _stl_prime_list;
	
	//3.1：使用一个指针指向素数表中的“最后一素数的下一位置”
	const unsigned long* last = _stl_prime_list + __stl_num_primes;

	//3.3：使用lower_bound()接口函数求出第一个 >=n 的素数
	const unsigned long* pos = lower_bound(first, last, n);
	
	//3.4：适合作为哈希表容量的质数
	return pos == last ? *(last - 1) : *pos;

	/*
	*  说明遍历完质数表，所有预定义的质数都比 n 小
	*  此时返回最大的质数 *(last - 1)，因为 last 是数组末尾的下一个位置，last - 1 指向最后一个有效质数 
	*/
}

/*------------------任务：定义“哈希表节点的结构体模板”------------------*/
template<class K, class V>
struct HashNode
{
	/*------------------成员变量------------------*/

	//1.存储的键值对
	//2.下一个节点的指针

	pair<K, V> _kv;
	HashNode<K, V>* _next;

	/*------------------成员函数------------------*/
	//1.实现：哈希桶节点的“构造函数”
	HashNode(const pair<K, V>& kv)
		:_kv(kv)
		, _next(nullptr)
	{
	}
};


/*------------------任务：定义“哈希表的类模板”------------------*/
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:
	/*------------------成员变量------------------*/

	//1.存储Node*类型数据的数组
	//2.记录哈希表中有效元素的变量 

	vector<HashNode<K, V>*> _tables;
	size_t _n;
    
public:
    
};

#pragma once

//包含需要使用的头文件
#include <iostream>
#include <vector>
using namespace std;

/*------------------任务：定义哈希表函数的“通用类模板”------------------*/
template <class K>
struct HashFunc
{
	//1.重载()运算符 ---> 作用：将K类型转化为size_t类型，用于计算哈希值
	size_t operator()(const K& key)
	{
		return (size_t)key;  //注意：默认为直接转换，适用于int、long等整数类型
	} 
};



/*------------------任务：定义哈希函数的“模板特化”------------------*/
template <>
struct HashFunc<string>
{
	//1.实现：“()运算符的重载” ---> 作用：将string类型的变量转化为哈希值
	size_t operator()(const string& s)
	{
		//1.定义size_t类型变量记录string类型的变量计算的哈希值
		size_t hash = 0;

		//2.使用范围for循环遍历字符串并用BKDR算法计算其哈希值
		for (auto it : s)
		{
			//2.1：先将字符的ASCII值累加到哈希值中
			hash += it;
			//2.2：再让哈希值乘以质数131（BKDR哈希算法认为：131可有效减少冲突）
			hash *= 131;
		}

		//3.返回最终计算的哈希值
		return hash;
	}
};


/*------------------任务：实现“获取下一个 >=n 的质数的函数”---> “用于哈希表扩容”------------------*/
inline unsigned long _stl_next_prime(unsigned long n)
{
	//1.指定素数表的大小
	static const int __stl_num_primes = 28;

	//2.定义素数表覆盖常见哈希表大小
	static const unsigned long _stl_prime_list[__stl_num_primes] =   //注意：这里的素数表的类型是unsigned long 类型
	{
		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
	};

	//3.使用二分查找找到第一个 >=n 的素数
	//3.1：使用一个指针指向素数表中的“第一个素数”
	const unsigned long* first = _stl_prime_list;
	
	//3.1：使用一个指针指向素数表中的“最后一素数的下一位置”
	const unsigned long* last = _stl_prime_list + __stl_num_primes;

	//3.3：使用lower_bound()接口函数求出第一个 >=n 的素数
	const unsigned long* pos = lower_bound(first, last, n);
	
	//3.4：适合作为哈希表容量的质数
	return pos == last ? *(last - 1) : *pos;

	/*
	*  说明遍历完质数表，所有预定义的质数都比 n 小
	*  此时返回最大的质数 *(last - 1)，因为 last 是数组末尾的下一个位置，last - 1 指向最后一个有效质数 
	*/
}

#pragma once

#include "HashTable.h"

namespace open_address
{
	/*------------任务：定义哈希表中节点的三种状态的“枚举”------------*/
	enum State
	{
		EXIST,  //存在状态
		EMPTY,  //空状态
		DELETE  //删除状态
	};

	/*------------任务：定义哈希表存储的数据结构的“结构体模板”------------*/
	template <class K, class V>
	struct HashData
	{
		//1.存储键值对类型的数据
		//2.记录存储的节点的状态

		pair<K, V> _kv;
		State _state = EMPTY; //节点的状态默认为空
	};



	/*------------任务：使用“开放地址法 - 线性探测”实现哈希表------------*/
	template <class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	private:
		/*------------------成员变量------------------*/

		//1.存储HashData类型数据的数组
		//2.记录哈希表中有效元素的变量 

		vector<HashData<K,V>> _tables;
		size_t _n;


		/*注意现在的结构的形式是：
		*    1.哈希表
		*		1.1：成员变量：容器vector
		*				1.1.1：键值对_kv
		*				1.1.2：枚举：_state
		*			               1.1.2.1：存在
		*						   1.1.2.2：空
		*						   1.1.2.2：删除
		*       1.2：成员变量：变量_n
		*/



		/*------------------成员变量------------------*/
	public:
		/*------------------成员变量（公有）------------------*/
		//1.实现：“哈希表的构造函数”
		HashTable()
			:_tables(_stl_next_prime(0))
			, _n(0)
		{
		}


		//2.实现：“查找操作” ----> 查找键对应的数据，找到返回指针，未找到返回nullptr
		HashData<K, V>* Find(const K& key)  //注意：传入“键”返回“哈希表存储元素的指针”
		{
			/*--------------第一步：计算初始哈希位置--------------*/

			//1.实例化哈希函数对象
			Hash hash;

			//2.计算哈希值 + 对其取模计算初始位置
			size_t hash_0 = hash(key) % _tables.size(); ///注意：这里相当于调用时vector的接口函数size()

			//3.定义变量记录当前的探测位置
			size_t hash_i = hash_0;

			//4.定义探测步长计数器
			size_t i = 1;


			/*--------------第二步：线性探测循环--------------*/

			while (_tables[hash_i]._state != EMPTY) //注意：遇到EMPTY标记时停止（EMPTY表示无数据，DELETE需继续）
			{
				//1.如果当前位置为EXIST且键匹配 ---> 找到了键为key的元素，返回该位置的指针 
				if (_tables[hash_i]._state == EXIST && _tables[hash_i]._kv.first == key)
				{
					return &_tables[hash_i];
				}


				//2.进行线性探测计算下一个位置
				hash_i = (hash_0 + i) % _tables.size();  //注意：取模防止越界

				//3.探测步长自增
				++i;
			}
			/*--------------第三步：--------------*/

			//“如果这个位置的状态为空 + 遇到EMPTY仍未找到” ---> 说明哈希表中并不存在键为key的元素
			return nullptr;
		}



		//3.实现：“删除操作” ---> 删除键对应的数据，成功返回true，未找到返回false
		bool Erase(const K& key)
		{
			//1.调用Find函数查找键key对应的目标的元素
			HashData<K, V>* ret = Find(key);  //注意：返回指向该元素的指针（存在）或nullptr（不存在）

			//2.判断是否找到的目标元素
			//情况1：找到了键为key的元素
			if (ret)
			{
				//1.将该元素的状态设置为DELETE（删除状态）
				ret->_state = DELETE;

				//2. 更新有效元素的数量
				--_n;

				//3.删除成功返回true即可
				return true;
			}

			//情况2：未找到键未key的元素
			else
			{
				return false;
			}

			/* 注意事项：删除键为key的元素为什么是：“将这个元素的状态设置为删除状态”呢？
			*
			*    核心逻辑：不直接清除数据，而是标记为DELETE状态
			*    原因：开放定址法中，直接删除会破坏哈希冲突形成的探测链
			*    例如：若删除中间元素，后续元素的查找可能提前终止
			*/
		}



		//4.实现：“插入操作”---> 插入键值对，成功返回true，键已存在返回false
		bool Insert(const pair<K, V>& kv)
		{
			/*----------------第一步：查重判断----------------*/
			//1.使用Find()函数先检查键kv.first是否已经存在
			if (Find(kv.first))
			{
				return false; // 当键kv.first已经存在时，插入失败
			}


			//1.进行扩容的判断：负载因子（_n/_tables.size()）≥0.7时扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				/*----------------第二步：扩容操作----------------*/

				//2.创建新哈希表，容量为大于当前size的最小质数（减少哈希冲突）
				HashTable<K, V, Hash> newHt;
				newHt._tables.resize(_stl_next_prime(_tables.size() + 1));

				/*  注意事项：
				*
				*      newHt：是一个哈希表
				*	   _tables：是哈希表中的一个成员变量，本质上是vector；哈希表的另一个成员变量是_n，本质上是size_t类型的变量
				*      resize： 是vecotr容器中用来进行扩容的接口函数
				*/

				//3.遍历旧表，将所有EXIST状态的元素重新插入新表
				for (auto& htData : _tables)
				{
					if (htData._state == EXIST)
					{
						newHt.Insert(htData._kv);  // 注意：需重新计算哈希值（因表长改变，取模结果不同）
					}
				}

				//4.交换新旧哈希表：旧表.swap(新表)
				_tables.swap(newHt._tables);   //注意：当前表指向新表，旧表由newht接管（离开作用域时自动释放）
			}


			/*----------------第三步：初始位置----------------*/

			//1.实例化哈希函数对象
			Hash hashFunc;

			//2.计算哈希值 + 对其取模计算初始位置
			size_t hash_0 = hashFunc(kv.first) % _tables.size(); ///注意：这里相当于调用时vector的接口函数size()

			//3.定义变量记录当前的探测位置
			size_t hash_i = hash_0;

			//4.定义探测步长计数器
			size_t i = 1;


			/*----------------第四步：线性探测----------------*/

			//1.使用while循环第一个非EXIST位置（EMPTY或DELETE均可，EXIST需要继续寻找）
			while (_tables[hash_i]._state == EXIST)
			{
				//2.进行线性探测计算下一个位置
				hash_i = (hash_0 + i) % _tables.size();  //注意：取模防止越界，环形探测

				//3.探测步长自增
				++i;
			}

			/* 注意事项：“查找”和“插入”使用while进行线性探测的“循环判断条件不同”
			*      查找操作：while (_tables[hash_i]._state != EMPTY) ---> 查找的位置EXIST或DELETE需要继续寻找“键为key的元素”
			*
			*      插入操作：while (_tables[hashi]._state == EXIST) ---> 查找的位置EXIST需要继续寻找“空位置”
			*/


			/*----------------第五步：插入数据----------------*/

			//1.将键值对插入该位置
			_tables[hash_i]._kv = kv;

			//2.将该位置的设置为EXIST
			_tables[hash_i]._state = EXIST;

			//3.更新哈希表中有效元素的数量
			++_n;

			//4.插入成功返回true即可
			return true;

		}

	};
}

#pragma once

#include "HashTable.h"

//任务8：使用“链地址法”实现哈希表
namespace hash_bucket
{
	/*------------------任务：定义“哈希表节点的结构体模板”------------------*/
	template<class K, class V>
	struct HashNode
	{
		/*------------------成员变量------------------*/

		//1.存储的键值对
		//2.下一个节点的指针

		pair<K, V> _kv;
		HashNode<K, V>* _next;

		/*------------------成员函数------------------*/
		//1.实现：哈希桶节点的“构造函数”
		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			, _next(nullptr)
		{
		}
	};


	/*------------------任务：定义“哈希表的类模板”------------------*/
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	private:
		/*------------------成员变量------------------*/

		//1.存储Node*类型数据的数组
		//2.记录哈希表中有效元素的变量 

		vector<HashNode<K, V>*> _tables;
		size_t _n;

		/*注意现在的结构的形式是：
		*    1.哈希表
		*      1.1：成员变量：容器vector
		*			   1.1.1：哈希表节点类型的指针：HashNode<K,V>*
		*					  1.1.1.1：键值对：_kv
		*					  1.1.1.2：下一个节点的指：_next
		*	   1.2：成员变量：变量_n
		*/

		/*------------------类型别名------------------*/

		//1.重命名哈希表节点的类型：HashNode<K,V> ---> Node
		typedef HashNode<K, V> Node;

	public:
		/*------------------成员函数------------------*/

		//1.实现：“哈希表的构造函数”
		HashTable()
			:_tables(_stl_next_prime(0)) //初始化为11个桶
			, _n(0)
		{
		}


		//2.实现：“哈希表的析构函数”
		~HashTable()
		{
			//1.遍历哈希表的每个桶（注：_tables 是存储桶头节点指针的容器）
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				//2.获取当前桶的头节点指针，从第一个桶开始清理
				Node* current = _tables[i];

				//3.遍历当前桶对应的链表，逐个释放节点内存
				while (current)
				{
					//3.1：提前保存当前节点的下一个节点指针 ---> 防止删除当前节点后丢失链表连接
					Node* next = current->_next;

					//3.2：释放当前节点的内存（避免内存泄漏）
					delete current;

					//3.3：移动到下一个节点，继续清理
					current = next;
				}

				//4.将当前桶的头节点指针置空，确保析构后桶不会指向无效内存
				_tables[i] = nullptr;
			}
		}

		//3.实现：“查找操作”---> 根据键查找对应的节点，找到返回节点指针，未找到返回 nullptr
		Node* Find(const K& key)
		{
			//1. 实例化哈希函数对象
			Hash hashFunc;
			/* 代码解释：
			*     1. 利用模板参数 Hash 生成哈希函数实例
			*     2. 若 K 是 int，使用默认的整数哈希；若 K 是 string，使用特化的字符串哈希
			*/

			//2. 计算键的哈希值并取模，得到对应的桶索引
			size_t hash_i = hashFunc(key) % _tables.size();
			/* 代码解释：
			*      1. hashFunc(key)：调用哈希函数，将键转换为 size_t 类型的哈希值
			*	   2. % _tables.size()：对哈希表的桶数量取模，确定节点应该落在哪个桶中
			*	   3.目的：将任意键映射到 [0, _tables.size()-1] 范围内的桶索引
			*/

			//3. 获取对应桶的头节点，开始遍历链表
			Node* current = _tables[hash_i]; //注意：_tables[hash_i] 是桶的头节点指针


			//4. 遍历当前桶对应的链表
			while (current) //注意：若 current 为 nullptr，说明桶为空，直接跳过循环
			{
				//4.1 检查当前节点的键是否匹配目标 key
				if (current->_kv.first == key)
				{
					return current;
				}
				
				//4.2 若不匹配，移动到链表的下一个节点
				else
				{
					current = current->_next;
				}
			}

			//5. 遍历完链表后仍未找到匹配的键，返回 nullptr
			return nullptr;
		}



		//4.实现：“删除操作”---> 根据键删除哈希表中的节点，成功返回 true，失败返回 false
		bool Erase(const K& key)
		{
			//1.计算键的哈希值，确定所在桶
			Hash hashFunc;
			size_t hash_i = hashFunc(key) % _tables.size();

			//2.定义一个指向桶的头节点的指针
			Node* curr = _tables[hash_i];
			//3.定义一个指向当前节点的前驱节点的指针
			Node* prev = nullptr;  //作用记录待删除节点的前驱节点

			//3.遍历当前桶的链表
			while (curr)
			{
				//4.找到目标节点
				if (curr->_kv.first == key)
				{
					//4.2：处理待删除节点
					if (prev == nullptr)
					{
						//情况1：待删除节点是桶的头节点
						_tables[hash_i] = curr->_next;
					}
					else
					{
						//情况2：待删除节点在链表中间或末尾
						prev->_next = curr->_next;
					}

					//4.3：释放节点内存
					delete curr;

					//4.4：有效元素数量减一
					--_n;

					//4.5：删除成功
					return true;
				}

				//5.未找到目标节点，继续遍历
				//5.1：当前节点的前驱节点指向当前节点
				prev = curr;
				//5.2：当前节点指向下一个节点的位置
				curr = curr->_next;
			}

			//6.遍历结束仍未找到目标节点，删除失败
			return false;
		}





		//5.实现：“插入操作”---> 插入键值对，成功返回true，键已存在返回false
		bool Insert(const pair<K, V>& kv)
		{
			/*----------------第一步：查重判断----------------*/
			//1.使用Find()函数判断键kv.first是否已经存在
			if (Find(kv.first))
			{
				return false; // 当键kv.first已经存在时，插入失败
			}

			/*----------------第二步：扩容操作----------------*/

			//1.进行扩容判断：负载因子（元素数/桶数）等于1时触发扩容
			if (_n == _tables.size()) //目的：避免哈希冲突过多导致链表过长，影响性能
			{
				/*
				//////////////////方法一：创建新哈希表对象并复用Insert函数//////////////////

				//2.创建新哈希表，容量为大于当前size的最小质数（减少哈希冲突）
				HashTable<K, V, Hash> newHt;
				newHt._tables.resize(_stl_next_prime(_tables.size() + 1));

				//3.使用for循环变量的旧表中的所有桶 ---> 将旧表中的所有节点重新插入到新表中
				for (size_t i = 0; i < _tables.size(); i++)
				{
					//4.定义一个指针指向当前桶存储的链表的头节点
					Node* current = _tables[i];

					//5.遍历链表 ---> 将遍历的到的每个节点节点进行插入
					while (current)
					{
						//5.1：将链表中的每个节点重新插入到新表中
						newht.Insert(cur->_kv);  // 复用Insert函数（会重新计算哈希值并查重）

						//5.2：指向当前节点的current指针向后移动一位
						cur = cur->_next;

					}
				}

				//6.交换新旧哈希表：旧表.swap(新表)
				_tables.swap(newHt._tables);   //注意：当前表指向新表，旧表由newht接管（离开作用域时自动释放）

				*/



				//////////////////方法二：直接操作数组进行节点迁移（优化版）//////////////////
				//2.创建新数组，容量为大于当前size的最小质数（减少哈希冲突）
				//vector<Node*> newVector(_stl_next_prime(_tables.size() + 1));
				vector<Node*> newVector(_tables.size() * 2);

				//3.使用for循环变量的旧表中的所有桶 ---> 将旧表中的所有节点重新插入到新表中
				for (size_t i = 0; i < _tables.size(); i++)
				{
					//4.定义一个指针指向当前节点的指针
					Node* current = _tables[i];

					//5.遍历链表 ---> 将遍历的到的每个节点节点进行插入
					while (current)
					{
						//6.定义一个指针指向当前节点的下一个节点的指针 ---> 暂存下一节点避免链表断裂
						Node* next = current->_next;

						//7.实例化哈希函数
						Hash hashFunc;  //创建哈希函数对象

						//8.重新计算“遍历到节点”在新表中的桶索引 ---> 因表长变化，哈希值需重新取模
						size_t hash_i = hashFunc(current->_kv.first) % newVector.size();


						//9.使用头插入法将当前节点插入新表对应桶的头部
						//第一步：新插入的节点的下一个节点 ---> 该节点的桶索引位置的链表头节点
						current->_next = newVector[hash_i];

						//第二步：将新插入的节点的指针赋值给其对应的桶
						newVector[hash_i] = current;

						//第三步：指向当前节点的current指针向后移动一位
						current = next;
					}

					//10.清空旧表的当前桶
					_tables[i] = nullptr;  //注意：当前桶在旧表中的哈希值是i，在新表中的哈希值是hash_i
				}
				//11.交换新旧哈希表：旧表.swap(新表)
				_tables.swap(newVector);   //注意：当前表指向新表，旧表由newht接管（离开作用域时自动释放）

			}

			/*----------------第三步：插入数据----------------*/

			//1.创建新节点
			Node* newNode = new Node(kv);

			//2.实例化哈希函数
			Hash hashFunc;

			//3.计算“新插入数据”的哈希值/桶索引
			size_t hash_i = hashFunc(kv.first) % _tables.size();

			//4.1：头插第一步：
			newNode->_next = _tables[hash_i];
			//4.2：头插第二步：
			_tables[hash_i] = newNode;

			//5.更新新表中有效元素的数量
			++_n;

			//6.插入成功返回true即可
			return true;
		}

	};
}

#include "HashTable.h" 
#include "open_address.h"
#include "hash_bucket.h"

#include <string>
#include <iostream>
using namespace std;

// 辅助函数：打印测试结果
void printTestResult(const string& testName, bool result)
{
    cout << (result ? "[PASS] " : "[FAIL] ") << testName << endl;
}



/*-----------------------测试：开放寻址法哈希表-----------------------*/
void test_open_address()
{
    cout << "\n===== 测试开放寻址法哈希表 =====" << endl;

    /*--------------------创建哈希表--------------------*/
    open_address::HashTable<int, string> ht;
    cout << "创建哈希表成功" << endl;


    /*--------------------插入测试--------------------*/
    cout << "\n--- 插入测试 ---" << endl;
    bool insert1 = ht.Insert({ 1, "A" });
    printTestResult("插入键1值A", insert1);

    bool insert2 = ht.Insert({ 1, "B" }); // 重复键
    printTestResult("插入重复键1值B（期望失败）", !insert2);

    bool insert3 = ht.Insert({ 2, "C" });
    printTestResult("插入键2值C", insert3);


    /*--------------------查找测试--------------------*/
    cout << "\n--- 查找测试 ---" << endl;
    auto node1 = ht.Find(1);
    printTestResult("查找键1", node1 != nullptr && node1->_kv.second == "A");

    auto node2 = ht.Find(2);
    printTestResult("查找键2", node2 != nullptr && node2->_kv.second == "C");

    auto node3 = ht.Find(3);
    printTestResult("查找不存在的键3", node3 == nullptr);


    /*--------------------删除测试--------------------*/
    cout << "\n--- 删除测试 ---" << endl;
    bool erase1 = ht.Erase(1);
    printTestResult("删除键1", erase1);

    bool erase2 = ht.Erase(1); // 重复删除
    printTestResult("重复删除键1（期望失败）", !erase2);

    bool erase3 = ht.Erase(3); // 删除不存在的键
    printTestResult("删除不存在的键3", !erase3);


    /*--------------------扩容测试--------------------*/
    cout << "\n--- 扩容测试 ---" << endl;
    cout << "开始插入大量数据以触发扩容..." << endl;
    for (int i = 3; i < 100; ++i)
    {
        ht.Insert({ i, to_string(i) });
    }
    cout << "插入完成，验证数据访问..." << endl;

    auto node99 = ht.Find(99);
    printTestResult("查找扩容后的键99", node99 != nullptr && node99->_kv.second == "99");

    cout << "开放寻址法哈希表测试完毕" << endl;
}



/*-----------------------测试：链地址法哈希表-----------------------*/
void test_hash_bucket()
{
    cout << "\n===== 测试链地址法哈希表 =====" << endl;


    /*--------------------创建哈希表--------------------*/
    hash_bucket::HashTable<string, int> ht;
    cout << "创建哈希表成功" << endl;


    /*--------------------插入测试--------------------*/
    cout << "\n--- 插入测试 ---" << endl;
    bool insert1 = ht.Insert({ "apple", 5 });
    printTestResult("插入键apple值5", insert1);

    bool insert2 = ht.Insert({ "apple", 10 }); // 重复键
    printTestResult("插入重复键apple值10（期望失败）", !insert2);

    bool insert3 = ht.Insert({ "banana", 8 });
    printTestResult("插入键banana值8", insert3);

    /*--------------------查找测试--------------------*/
    cout << "\n--- 查找测试 ---" << endl;
    auto node1 = ht.Find("apple");
    printTestResult("查找键apple", node1 != nullptr && node1->_kv.second == 5);

    auto node2 = ht.Find("banana");
    printTestResult("查找键banana", node2 != nullptr && node2->_kv.second == 8);

    auto node3 = ht.Find("orange");
    printTestResult("查找不存在的键orange", node3 == nullptr);

    /*--------------------删除测试--------------------*/
    cout << "\n--- 删除测试 ---" << endl;
    bool erase1 = ht.Erase("apple");
    printTestResult("删除键apple", erase1);

    bool erase2 = ht.Erase("apple"); // 重复删除
    printTestResult("重复删除键apple（期望失败）", !erase2);

    bool erase3 = ht.Erase("orange"); // 删除不存在的键
    printTestResult("删除不存在的键orange", !erase3);

    /*--------------------扩容测试--------------------*/
    cout << "\n--- 扩容测试 ---" << endl;
    cout << "开始插入大量数据以触发扩容..." << endl;
    for (int i = 0; i < 100; ++i)
    {
        string key = "key_" + to_string(i);
        ht.Insert({ key, i });
    }
    cout << "插入完成，验证数据访问..." << endl;

    auto node = ht.Find("key_99");
    printTestResult("查找扩容后的键key_99", node != nullptr && node->_kv.second == 99);

    cout << "链地址法哈希表测试完毕" << endl;
}


//自定义日期结构体 ---> 用于测试复杂类型的哈希
struct Date
{
    /*-------------------成员变量-------------------*/
    int _year;
    int _month;
    int _day;


    /*-------------------成员函数-------------------*/
    //1.实现：日期类的“构造函数”
    Date(int year = 1, int month = 1, int day = 1)
        :_year(year)
        , _month(month)
        , _day(day)
    {
    }

    //2.实现：“自定义相等比较”（哈希表需要判断键是否相等）
    bool operator==(const Date& d) const
    {
        return _year == d._year
            && _month == d._month
            && _day == d._day;
    }
};

//自定义日期的哈希函数（模仿BKDR算法）
struct DateHashFunc
{
    //1.实现：“运算符()的重载” ---> 作用：用于计算日期类对象的哈希值
    size_t operator()(const Date& d)
    {
        //1.定义size_t类型的变量记录日期类对象计算的哈希值
        size_t hash = 0;

        //2.分步哈希，减少冲突概率
        hash += d._year;
        hash *= 131;   // 乘以质数，增强离散性

        hash += d._month;
        hash *= 131;

        hash += d._day;
        hash *= 131;

        //3.返回最终计算的哈希值
        return hash;
    }
};


void test01()
{
    /*---------------测试：字符串作为键的哈希表---------------*/
    hash_bucket::HashTable<string, string> ht1;

    const char* a1[] = { "abcd", "sort", "insert" };
    for (auto& it : a1)
    {
        ht1.Insert({ it, it });  // 键值均为字符串
    }

    /*---------------测试：负数作为键的哈希表（需保证哈希函数处理负数）---------------*/
    hash_bucket::HashTable<int, int> ht2;

    const int a2[] = { -19,-30,5,36,13,20,21,12 };
    for (auto& it : a2)
    {
        ht2.Insert({ it, it });
    }


    /*---------------测试：日期结构体作为键（自定义“哈希函数”和“相等比较”）---------------*/
    hash_bucket::HashTable<Date, int, DateHashFunc> ht3;

    ht3.Insert({ { 2025, 6, 29 }, 1 });  // 插入日期键值对
    ht3.Insert({ { 2025, 6, 30 }, 1 });

}

int main()
{
    test_open_address();

    test_hash_bucket();

    test01();

    return 0;
}