> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：手撕哈希表的闭散列和开散列

> 毒鸡汤：谁不是一边受伤，一边学会坚强。

> 专栏选自：C嘎嘎进阶

> 望小伙伴们点赞收藏加关注哟

前言

谈到哈希表，大家都做过这样的题目，统计字符串的字母个数，像这样的题目可以创建一个数组，每个字母采用 a['ch']++ 计入数组中，这样的数组我们称之为哈希表，这种哈希表也是最简单的，如果说为了方便直接调用哈希表，那这个哈希表该如何模拟呢？这个问题也是今天我们所探讨的，手撕哈希表。

主体

学习手撕哈希表的闭散列和开散列咱们按照下面的图解：

哈希概念

知识回顾

在顺序结构以及平衡树中，由于元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较；比如顺序表中需要从表头开始依次往后比对寻找，查找时间复杂度为 O(N)，平衡树中需要从第一层开始逐层往下比对寻找，查找时间复杂度为 O(logN)；即搜索的效率取决于搜索过程中元素的比较次数。

分析探讨

如果构造一种存储结构，可以通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一对一的映射关系，那么在查找时通过该函数就可以很快找到该元素；当向该结构中：

• 插入元素时：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放；
• 搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

总结归纳

该方法即为 哈希 (散列) 方法，哈希方法中使用的转换函数称为哈希 (散列) 函数，构造出来的结构称为哈希表 (Hash Table) (或者称散列表)。

注意事项

我们上面提到的不管是顺序搜索、平衡树搜索还是哈希搜索，其 key 值都是唯一的，也就是说，搜索树中不允许出现相同 key 值的节点，哈希表中也不允许出现相同 key 值的元素，我们下文所进行的所有操作也都是在这前提之上进行的。

哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希冲突有两种常见的解决办法：

1. 闭散列 (开放定址法)：当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；
2. 开散列 (链地址法)：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 (哈希冲突) 归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中；也就是说，当发生哈希冲突时，把 key 直接链接在该位置的下面。

哈希函数

哈希函数有如下设计原则：

1. 哈希函数的定义域必须包括需要存储的全部关键码，而如果哈希表允许有m个地址时，其值域必须在0到m-1之间；
2. 哈希函数计算出来的地址要尽量能均匀分布在整个空间中；
3. 哈希函数应该比较简单。

 直接定址法

什么是直接定址法：

直接定址就是根据 key 值直接得到存储位置，最多再进行一个简单的常数之间的转换。

分析：

• 直接定址法的优点是简单，且不会引起哈希冲突 ，由于直接定址法的 key 值经过哈希函数转换后得到的值一定是唯一的，所以不存在哈希冲突。
• 直接定址法适用于数据范围集中的情况，这样 key 值映射到哈希表后，哈希表的空间利用率高，浪费的空间较少

图解：

 除留余数法

什么是除留余数法：

简单来说就是用 key 值除以哈希表的大小得到的余数作为哈希映射的地址，将 key 保存到该地址中

分析：

• 除留余数的优点是可以处理数据范围分散的数据
• 缺点是会引发哈希冲突

图解：

 方法总结

直接定制法–(常用)

• 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况使用场景：适合查找比较小且连续的情况

除留余数法–(常用)

• 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：**Hash(key) = key% p(p<=m),**将关键码转换成哈希地址

平方取中法–(了解)

• 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

折叠法–(了解)

• 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

随机数法–(了解)

• 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法

数学分析法–(了解)

• 设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

闭散列哈希

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；那如何寻找下一个空位置呢？有两种方法 – 线性探测法和二次探测法。

 线性探测法

什么是线性探测：

线性探测法是指从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

图解：

哈希表的基本框架

框架搭建步骤：

• 在哈希表中我们使用了 vector 来存储数据，并增加了一个变量 n 来记录表中有效数据的个数；同时，哈希表的每个下标位置存储的数据都是一个 KV 模型的键值对
• 当key映射的下标位置被占用时，key会向后寻找下一个空位置进行插入，但如果key走到数组尾都还没找到空位置，那么key就会从数组起始位置重新往后寻找
• 在哈希表的每个位置的数据中还增加了一个 state 变量来记录该位置的状态 (存在、删除、空) 

代码如下：

//标识每个存储位置的状态--空、存在与删除
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 {
	typedef HashData<K, V> Data;
private:
	vector<Data> _tables;
	size_t _n;  //记录表中有效数据的个数
};

哈希表的插入删除与查找

插入：

通过哈希函数得到余数即数组下标，如果该下标的状态为删除或为空则插入，如果为存在则向后寻找下一个状态为删除/空的位置进行插入。

查找：

通过哈希函数得到余数即数组下标，取出小标位置的key与目标key进行比较，相等就返回该位置的地址，不相等就继续往后查找，如果查找到状态为空的下标位置就返回 nullptr。

删除：

复用查找函数，查找到就通过查找函数的返回值将小标位置数据的状态置为 删除，找不到就返回 false。

代码实现：

#pragma once

#include <vector>
#include <utility>
using std::pair;
using std::vector;

//标识每个存储位置的状态--空、存在与删除
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 {
	typedef HashData<K, V> Data;

public:
	HashTable()
		: _n(0)
	{
		//将哈希表的大小默认给为10
		_tables.resize(10);
	}

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

		//除留余数法 && 线性探测法
		//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
		size_t hashi = kv.first % _tables.size();
		//不能放在EXIST的位置，DELETE和EMPTY都能放
		while (_tables[hashi]._state == EXIST) {
			++hashi;
			if (hashi == _tables.size()) hashi = 0;  //如果探测到末尾则从头开始重新探测
		}

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

		return true;
	}

		//将find的返回值定义为Data的地址，可以方便我们进行删除以及修改V
		Data* find(const K& key) {
			Hash hash;  //仿函数对象
			size_t hashi = hash(key) % _tables.size();
			//记录hashi的起始位置，避免哈希表中元素全为EXIST和DELETE时导致死循环
			size_t starti = hashi;
			//最多找到空
			while (_tables[hashi]._state != EMPTY) {
				//key相等并且state为EXIST才表示找到
				if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)
					return &_tables[hashi];
				++hashi;
				//如果找到尾还没找到，就从0重新找
				if (hashi == _tables.size()) hashi = 0;
				//如果找一圈还没找到，就跳出循环
				if (hashi == starti) break;
			}

			return nullptr;
		}

	bool erase(const K& key) {
		//找不到就不删，找到就把状态置为DELETE即可
		Data* ret = find(key);
		if (ret) {
			ret->_state = DELETE;
			return true;
		}

		return false;
	}

private:
	vector<Data> _tables;
	size_t _n;  //记录表中有效数据的个数
};

哈希表的扩容

哈希表的扩容和普通顺序表容器的扩容不同，它不是容器满了才扩容，而是会有一个负载因子，也叫载荷因子，当载荷因子超过一定大小时就立即扩容。

代码如下：

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

    //如果大于标定的载荷因子就扩容，这里我们将载荷因子标定为0.7
    //扩容现代写法--复用insert接口
    if ((1.0 * _n / _tables.size()) >= 0.7) {
        HashTable<K, V> newHT;
        newHT._tables.resize(_tables.size() * 2);

        for (auto& e : _tables)
            newHT.insert(e._kv);

        _tables.swap(newHT._tables);
    }

    //除留余数法 && 线性探测法
    //将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置，如果该位置被占用往后放
    size_t hashi = kv.first % _tables.size();
    //不能放在EXIST的位置，DELETE和EMPTY都能放
    while (_tables[hashi]._state == EXIST) {
        ++hashi;
        if (hashi == _tables.size()) hashi = 0;  //如果探测到末尾则从头开始重新探测
    }

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

    return true;
}

哈希表的仿函数

模板参数是一个仿函数，仿函数分为设计者提供的默认仿函数和用户提供的仿函数，系统默认的仿函数可以将一些常见的 key 的类型全部转化为整形，比如字符串、指针、整数；而用户提供的仿函数则可以根据用户自己的 key 类型将其转化为整形，比如 People 类 (身份证号)、Date 类 等等

代码如下：

template<>
struct HashFunc<string> {
	size_t operator()(const string& key) {
		size_t sum = 0;
		for (auto ch : key)
			sum += ch;

		return sum;
	}
};

细节分析：

有了仿函数，解决了传字符串的问题

闭散列整体代码实现

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;

// 哈希表的仿函数 ，通过上层容器提供的仿函数获取到元素的键值
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 类模板特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
			hash *= 131;
		}

		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 Hash = HashFunc<K>>
	class HashTable
	{
	public:

		// 默认开辟 10 个空间
		HashTable(size_t size = 10)
		{
			_tables.resize(size);
		}

		// 查找
		HashData<K, V>* Find(const K& key)
		{
			// 仿函数对象
			Hash hs;
			// 线性探测
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				// key相等并且state为EXIST（存在）才能表示找到
				if (key == _tables[hashi]._kv.first
					&& _tables[hashi]._state == EXIST)
				{
					return &_tables[hashi];
				}

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

			return nullptr;
		}

		// 插入
		bool Insert(const pair<K, V>& kv)
		{
			// 为空就返回
			if (Find(kv.first))
				return false;

			// 扩容
			if (_n * 10 / _tables.size() >= 7)
			{
				// 扩容
				HashTable<K, V, Hash> newHT(_tables.size() * 2);
				// 遍历旧表，插入到新表
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHT.Insert(e._kv);
					}
				}
				// 交换
				_tables.swap(newHT._tables);
			}

			// 仿函数对象
			Hash hs;
			// 线性探测，找需要插入的地方
			size_t hashi = hs(kv.first) % _tables.size();
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size();
			}

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

			return true;
		}

		// 删除
		bool Erase(const K& key)
		{
			// 查找
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				_n--; // 元素减一
				ret->_state = DELETE;// 状态改为删除
				return true;
			}
			else
			{
				return false;
			}
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 实际存储的数据个数
	};

	// 测试一
	void TestHT1()
	{
		int a[] = { 1,4,24,34,7,44,17,37 };
		
		// 创建哈希表
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e)); // 插入元素
		}

		for (auto e : a)
		{
			auto ret = ht.Find(e);
			if (ret)
			{
				cout << ret->_kv.first << ":E" << endl;
			}
			else
			{
				cout << ret->_kv.first << ":D" << endl;
			}
		}
		cout << endl;

		ht.Erase(34);
		ht.Erase(4);

		for (auto e : a)
		{
			auto ret = ht.Find(e);
			if (ret)
			{
				cout << ret->_kv.first << ":E" << endl;
			}
			else
			{
				cout << e << ":D" << endl;
			}
		}
		cout << endl;
	}

	// 测试二
	struct Date
	{
		int _year;
		int _month;
		int _day;
	};
	struct HashFuncDate
	{
		// 2024/6/3
		// 2024/3/6
		size_t operator()(const Date& d)
		{
			size_t hash = 0;
			hash += d._year;
			hash *= 131;

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

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

			return hash;
		}
	};
	void TestHT2()
	{
		HashTable<string, string> dict;
		dict.Insert(make_pair("sort", "排序"));
		dict.Insert(make_pair("string", "字符串"));
		HashTable<Date, string, HashFuncDate> DateHash;
	}

}

开散列哈希

什么是开散列哈希：

开散列法又叫 链地址法 (开链法)，首先对关键码集合用散列函数计算散列地址，即 key 映射的下标位置，具有相同地址的关键码 (哈希冲突) 归于同一子集合，每一个子集合称为一个桶 (哈希桶)，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中；也就是说，当发生哈希冲突时，把 key 作为一个节点直接链接到下标位置的哈希桶中。

图解：

 开散列的节点结构

由于开散列的不同冲突之间不会互相影响，所以开散列不再需要 state 变量来记录每个下表位置的状态；同时，因为开散列每个下标位置链接的都是一个哈希桶，所以 vector 中的每个元素都是一个节点的指针，指向单链表的第一个元素，所以 _tables 是一个指针数组；最后，为了是不同类型的 key 都能够计算出映射的下标位置，所以我们这里也需要传递仿函数。

代码如下：

//开散列
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>
	struct HashFunc {
		size_t operator()(const K& key) {
			return key;
		}
	};

	//类模板特化
	template<>
	struct HashFunc<string> {
		size_t operator()(const string& key) {
			//BKDR字符串哈希算法
			size_t sum = 0;
			for (auto ch : key)
				sum = sum * 131 + ch;

			return sum;
		}
	};

	//哈希表
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable {
		typedef HashNode<K, V> Node;
        	private:
		vector<Node*> _tables;  //指针数组
		size_t _n;  //表中有效数据的个数
	};
}

 开散列的插入删除与查找

开散列的插入

开散列插入的前部分和闭散列一样，根据 key 与哈希表大小得到映射的下标位置，与闭散列不同的是，由于哈希表中每个下标位置都是一个哈希桶，即一个单链表，那么对于发现哈希冲突的元素我们只需要将其链接到哈希桶中即可，这里显然是选择将冲突元素进行头插，因为尾插还需要找尾，会导致效率降低：

// 插入函数
bool Insert(const pair<K, V>& kv)
{
	// 查看元素是否存在
	if (Find(kv.first))
		return false;

	// 仿函数对象
	Hash hs;

	// 负载因子到1就扩容
	if (_n == _tables.size())
	{
		// 扩容
		vector<Node*> newTables(_tables.size() * 2, nullptr);
		for (size_t i = 0; i < _tables.size(); i++)
		{
			// 取出旧表中节点，重新计算挂到新表桶中
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;

				// 头插到新表
				size_t hashi = hs(cur->_kv.first) % newTables.size();
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;

				cur = next;
			}

			_tables[i] = nullptr;
		}

		_tables.swap(newTables);
	}
			
	// 调用仿函数的匿名对象来将key转换为整数
	size_t hashi = hs(kv.first) % _tables.size();
			
	// 头插
	Node* newnode = new Node(kv);
	newnode->_next = _tables[hashi];
	_tables[hashi] = newnode;

	++_n;
	return true;
}

开散列的查找

开散列的查找也很简单，根据余数找到下标，由于下标位置存储的是链表首元素地址，所以我们只需要取出首元素地址，然后顺序遍历单链表即可：

// 查找
Node* Find(const K& key)
{
	// 仿函数对象
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}

		cur = cur->_next;
	}

	return nullptr;
}

开散列的删除

和闭散列不同的是，开散列的删除不能直接通过查找函数的返回值来进行删除，因为单链表在删除节点时还需要改变父节点的指向，让其指向目标节点的下一个节点，所以我们需要通过遍历单链表来进行删除：

// 删除
bool Erase(const K& key)
{
	// 仿函数对象
	Hash hs;
	size_t hashi = hs(key) % _tables.size();
	Node* prev = nullptr;
	Node* cur = _tables[hashi];
	while (cur)
	{
		// 删除还要分是否为头节点
		if (cur->_kv.first == key)
		{
			// 删除
			if (prev)
			{
				prev->_next = cur->_next;
			}
			else
			{
				_tables[hashi] = cur->_next;
			}

			delete cur;

			--_n;
			return true;
		}

		// 下一个结点
		prev = cur;
		cur = cur->_next;
	}

	return false;
}

开散列整体代码实现

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;

// 哈希表的仿函数 ，通过上层容器提供的仿函数获取到元素的键值
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 类模板特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash += e;
			hash *= 131;
		}

		return hash;
	}
};

// 开散列哈希表
namespace hash_bucket
{
	// 哈希表的节点结构 -- 单链表
	template<class K, class V>
	struct HashNode
	{
		HashNode<K, V>* _next;
		pair<K, V> _kv;

		// 初始化列表
		HashNode(const pair<K, V>& kv)
			:_next(nullptr)
			, _kv(kv)
		{}
	};

	// 哈希表
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:

		// 构造函数
		HashTable()
		{
			_tables.resize(10, nullptr); // 开空间
			_n = 0;
		}

		// 析构函数
		~HashTable()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;

					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		// 插入函数
		bool Insert(const pair<K, V>& kv)
		{
			// 查看元素是否存在
			if (Find(kv.first))
				return false;

			// 仿函数对象
			Hash hs;

			// 负载因子到1就扩容
			if (_n == _tables.size())
			{
				// 扩容
				vector<Node*> newTables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					// 取出旧表中节点，重新计算挂到新表桶中
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;

						// 头插到新表
						size_t hashi = hs(cur->_kv.first) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}

			// 调用仿函数的匿名对象来将key转换为整数
			size_t hashi = hs(kv.first) % _tables.size();

			// 头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;
			return true;
		}

		// 查找
		Node* Find(const K& key)
		{
			// 仿函数对象
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}

				cur = cur->_next;
			}

			return nullptr;
		}

		// 删除
		bool Erase(const K& key)
		{
			// 仿函数对象
			Hash hs;
			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				// 删除还要分是否为头节点
				if (cur->_kv.first == key)
				{
					// 删除
					if (prev)
					{
						prev->_next = cur->_next;
					}
					else
					{
						_tables[hashi] = cur->_next;
					}

					delete cur;

					--_n;
					return true;
				}

				// 下一个结点
				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

		// 测试
		void Some()
		{
			size_t bucketSize = 0;
			size_t maxBucketLen = 0;
			size_t sum = 0;
			double averageBucketLen = 0;

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					++bucketSize;
				}

				size_t bucketLen = 0;
				while (cur)
				{
					++bucketLen;
					cur = cur->_next;
				}

				sum += bucketLen;

				if (bucketLen > maxBucketLen)
				{
					maxBucketLen = bucketLen;
				}
			}

			averageBucketLen = (double)sum / (double)bucketSize;

			printf("load factor:%lf\n", (double)_n / _tables.size());
			printf("all bucketSize:%d\n", _tables.size());
			printf("bucketSize:%d\n", bucketSize);
			printf("maxBucketLen:%d\n", maxBucketLen);
			printf("averageBucketLen:%lf\n\n", averageBucketLen);
		}

	private:
		vector<Node*> _tables; // 指针数组
		size_t _n; // 元素个数
	};

	// 测试一
	void TestHT1()
	{
		HashTable<int, int> ht;
		int a[] = { 1,4,24,34,7,44,17,37 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

		ht.Insert(make_pair(5, 5));
		ht.Insert(make_pair(15, 15));
		ht.Insert(make_pair(25, 25));

		ht.Erase(5);
		ht.Erase(15);
		ht.Erase(25);
		ht.Erase(35);

		for (auto e : a)
		{
			auto ret = ht.Find(e);
			if (ret)
			{
				cout << ret->_kv.first << ":E" << endl;
			}
			else
			{
				cout << ret->_kv.first << ":D" << endl;
			}
		}
		cout << endl;

		HashTable<string, string> dict;
		dict.Insert(make_pair("sort", "排序"));
		dict.Insert(make_pair("string", "字符串"));
	}

	// 测试二
	void TestHT2()
	{
		const size_t N = 30000;

		unordered_set<int> us;
		set<int> s;
		HashTable<int, int> ht;

		vector<int> v;
		v.reserve(N);
		srand(time(0));
		for (size_t i = 0; i < N; ++i)
		{
			//v.push_back(rand()); // N比较大时，重复值比较多
			v.push_back(rand() + i); // 重复值相对少
			//v.push_back(i); // 没有重复，有序
		}

		size_t begin1 = clock();
		for (auto e : v)
		{
			s.insert(e);
		}
		size_t end1 = clock();
		cout << "set insert:" << end1 - begin1 << endl;

		size_t begin2 = clock();
		for (auto e : v)
		{
			us.insert(e);
		}
		size_t end2 = clock();
		cout << "unordered_set insert:" << end2 - begin2 << endl;

		size_t begin10 = clock();
		for (auto e : v)
		{
			ht.Insert(make_pair(e, e));
		}
		size_t end10 = clock();
		cout << "HashTbale insert:" << end10 - begin10 << endl << endl;

		size_t begin3 = clock();
		for (auto e : v)
		{
			s.find(e);
		}
		size_t end3 = clock();
		cout << "set find:" << end3 - begin3 << endl;

		size_t begin4 = clock();
		for (auto e : v)
		{
			us.find(e);
		}
		size_t end4 = clock();
		cout << "unordered_set find:" << end4 - begin4 << endl;

		size_t begin11 = clock();
		for (auto e : v)
		{
			ht.Find(e);
		}
		size_t end11 = clock();
		cout << "HashTable find:" << end11 - begin11 << endl << endl;

		cout << "插入数据个数：" << us.size() << endl << endl;
		ht.Some();

		size_t begin5 = clock();
		for (auto e : v)
		{
			s.erase(e);
		}
		size_t end5 = clock();
		cout << "set erase:" << end5 - begin5 << endl;

		size_t begin6 = clock();
		for (auto e : v)
		{
			us.erase(e);
		}
		size_t end6 = clock();
		cout << "unordered_set erase:" << end6 - begin6 << endl;

		size_t begin12 = clock();
		for (auto e : v)
		{
			ht.Erase(e);
		}
		size_t end12 = clock();
		cout << "HashTable Erase:" << end12 - begin12 << endl << endl;
	}
}

结束语

       今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力，回见。