在STL中，HashTable 是一个重要的底层数据结构，本题需要设计一个 HashTable，并实现以下功能：

1、基础功能

• 构造函数：初始化 HashTable 实例
• 析构函数：清理资源，确保无内存泄露

2、核心功能

• 在 HashTable 中添加键值对
• 删除 HashTable 中的键值对
• 查询 HashTable 中的键值对
• 获取 HashTable 中键值对的数量
• 获取 HashTable 中的所有键值对

3、高级功能

• 实现键值对数量达到一定的阈值后，自动扩容的功能

输入描述

题目的包含多行输入，第一行为正整数 N, 代表后续有 N 行命令序列。

接下来 N 行，每行包含一个命令，命令格式为 [operation] [parameters] ，具体命令如下：

insert 命令：

• 格式：insert [key] [value]
• 功能：在 HashTable 中添加键值对，如果键已经存在，则不进行任何操作

erase 命令：

• 格式：erase [key]
• 功能：删除 HashTable 中的键值对，如果键不存在，则不进行任何操作

find 命令：

• 格式：find [key]
• 功能：查询 HashTable 中的键值对

size 命令：

• 格式：size
• 功能：输出 HashTable 中键值对的数量

print 命令：

• 格式：print
• 功能：输出 HashTable 中所有键值对

clear 命令：

• 格式：clear
• 功能：清空哈希表

输出描述

输出为每行命令执行后的结果，具体输出格式如下：

insert 命令: 无输出

erase 命令: 无输出

find 命令: 输出一个整数，独占一行，代表 key 对应的 value 值，如果 HashTable 中不存在对应的 key，则输出 not exsit

size 命令: 输出一个整数，独站一行，表示 HashTable 中键值对的数量

print 命令: 打印哈希表中所有键值对，格式为 [key1] [value1] [key2] [value2]…每个数字后都有一个空格，打印结果独占一行，如果 HashTable 中不存在键值对，则打印 empty

clear 命令: 无输出

#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <list>
#include <utility>
#include <vector>
#include <sstream>
#include <string>
using namespace std;

template<typename Key,typename Value,typename Hash=hash<Key>>
class HashTable {

	class HashNode {
	public:
		Key key;
		Value value;
		explicit HashNode(const Key& key) :key(key), value()
		{}
		HashNode(const Key& key, const Value& value) :key(key), value(value)
		{}
		bool operator==(const HashNode& other) const
		{
			return key == other.key;
		}
		bool operator!=(const HashNode& other) const 
		{
			return key != other.key;
		}
		bool operator<(const HashNode& other) const
		{
			return key < other.key;
		}
		bool operator>(const HashNode& other) const
		{
			return key > other.key;
		}
		//直接比较键
		bool operator==(const Key& key_) const
		{
			return key == key_;
		}
		void print() const
		{
			cout << key << " " << value << " ";
		}
	};
private:
	using Bucket = list<HashNode>;//槽Bucket,本质上就是HashNode类型的链表
	vector<Bucket> buckets;//类型的嵌套，哈希表实质上就是buckets,它的每一项其实都是一个链表
	Hash hashFunction;
	size_t tableSize;//槽的数量，就是逻辑上的容量
	size_t numElements;//元素的数量

	float maxLoadFactor = 0.75;

	//由键计算哈希值
	size_t hash(const Key& key) const
	{
		return hashFunction(key) % tableSize;
	}

	//超过负载因子定义的容量阈值，需要增加槽的数量并重新设置哈希值（键对应的索引）
	void rehash(size_t newSize)
	{
		vector<Bucket> newBuckets(newSize);
		//对哈希表中的每个桶，对桶内的每个结点，重新改变这些结点内键所对应的哈希值
		for (Bucket& bucket : buckets)
		{
			for (HashNode& hashnode : bucket)
			{
				size_t newIndex = hashFunction(hashnode.key) % newSize;
				newBuckets[newIndex].push_back(hashnode);
			}
		}
		buckets = move(newBuckets);
		tableSize = newSize;
	}

public:
	//初始化哈希表
	//buckets数组大小其实就是tableSize
	HashTable(size_t size = 10, const Hash& hashFunc = Hash())
		:buckets(size),hashFunction(hashFunc), tableSize(size), numElements(0)
	{}
	//插入键到哈希表中
	//思路：找到该键对应的索引，由索引找到对应的桶（一个链表），若表中没有这个键值对，就插入进去。
	//在插入之前有扩容条件判断
	void insert(const Key& key, const Value& value)
	{
		//扩容条件先记住：元素数等于最大负载因子*桶数
		if ((numElements + 1) > maxLoadFactor * tableSize)
		{
			if (tableSize == 0) tableSize = 1;
			rehash(2 * tableSize);
		}
		size_t index = hash(key);
		Bucket& bucket = buckets[index];//并没有设置一个新的变量，而是设置一个别名
		if (std::find(bucket.begin(), bucket.end(), key) == bucket.end())
		{
			bucket.push_back(HashNode(key, value));//这样写也是可以的
			numElements++;
		}
	}

	void insertKey(const Key& key)
	{
		insert(key, Value{});
	}

	void erase(const Key& key)
	{
		size_t index = hash(key);
		auto& bucket = buckets[index];//获取对应的桶
		auto it = std::find(bucket.begin(), bucket.end(), key);
		if (it != bucket.end())
		{
			bucket.erase(it);//这其实是链表的删除操作
			numElements--;
		}
	}
	//查找哈希表中是否存在某个键
	Value *find(const Key& key)
	{
		size_t index = hash(key);
		auto& bucket = buckets[index];
		auto it = std::find(bucket.begin(), bucket.end(), key);
		if (it != bucket.end())
			return &it->value;
		else
			return NULL;
	}

	//获取哈希表中元素的数量
	size_t size() const
	{
		return numElements;
	}

	void print() const
	{
		for (size_t i = 0; i < buckets.size(); i++)
			for (const HashNode& element : buckets[i])
				element.print();
		cout << endl;
	}

	void clear()
	{
		this->buckets.clear();
		this->numElements = 0;
		this->tableSize = 0;
	}
};
	int main() {
		// 创建一个哈希表实例
		HashTable<int, int> hashTable;

		int N;
		std::cin >> N;
		getchar();

		std::string line;
		for (int i = 0; i < N; i++) {
			std::getline(std::cin, line);
			std::istringstream iss(line);
			std::string command;
			iss >> command;

			int key;
			int value;

			if (command == "insert") {
				iss >> key >> value;
				hashTable.insert(key, value);
			}

			if (command == "erase") {
				if (hashTable.size() == 0) {
					continue;
				}
				iss >> key;
				hashTable.erase(key);
			}

			if (command == "find") {
				if (hashTable.size() == 0) {
					std::cout << "not exist" << std::endl;
					continue;
				}
				iss >> key;
				int* res = hashTable.find(key);
				if (res != nullptr) {
					std::cout << *res << std::endl;
				}
				else {
					std::cout << "not exist" << std::endl;
				}
			}

			if (command == "print") {
				if (hashTable.size() == 0) {
					std::cout << "empty" << std::endl;
				}
				else {
					hashTable.print();
				}
			}

			if (command == "size") {
				std::cout << hashTable.size() << std::endl;
			}

			if (command == "clear") {
				hashTable.clear();
			}
		}
		return 0;
	}