C++【哈希表的完善及封装】-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++【哈希表的完善及封装】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

✨个人主页： 北海
🎉所属专栏： C++修行之路
🎃操作环境： Visual Studio 2019 版本 16.11.17

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

🌇前言

关于哈希表的两种实现方法：闭散列、开散列已经在上一篇文章中学习过了，闭散列存在 踩踏 问题，十分影响效率，因此在实践中往往会选择更加优秀的开散列，哈希表（开散列）又叫做哈希桶，作为被选中的结构，我们需要对其进行改造，完善哈希桶，使其最终能封装出 unordered_set 与 unordered_map

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

🏙️正文

1、哈希表的完善

1.1、拷贝与赋值

单链表 是我们自己写的，其中涉及到了 动态内存管理，这就意味着除了要自己释放内存外，还需要给出 深拷贝 版的 拷贝构造 与 赋值重载 函数

//默认构造
HashTable()
	:_table()
	,_n(0)
{}

//拷贝构造
HashTable(const HashTable& ht)
	:_table()
	,_n(0)
{
	//开辟空间
	_table.resize(ht._table.size());

	//遍历插入节点
	for (auto node : ht._table)
	{
		//遍历桶中的元素
		Node* cur = node;
		while (cur)
		{
			Insert(cur->_kv);
			cur = cur->_next;
		}
	}
}

//赋值重载（现代写法）
HashTable& operator=(HashTable ht)
{
	//直接交换 _table 与 _n
	_table.swap(ht._table);
	_n = ht._n;

	return *this;
}

注意：提供了拷贝构造之后，就得提供默认构造函数

1.2、优化：哈希函数

在实际使用中，往往需要以 字符串 作为存储依据（键值），比如姓名与 快递信息 、商品名称 与价格、中文单词 与 英文释义

总之，字符串是一种非常常见的数据类型

而在我们实现的哈希表中，只考虑整型的存储情况，即直接用 key % capacity 计算哈希值，如果把整型换成 字符串 是会出问题的

比如在下面这个场景中，程序无法编译

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

为了解决这个问题，我们可以将 获取 key 值 单独封装为一个 仿函数，再利用 模板特化，使其既能支持整型也能支持 字符串

//获取 key 值的仿函数
template<class K>
struct GetKey
{
	size_t operator()(const K& key)
	{
		//此时为整型，直接返回即可
		return key;
	}
};

//模板的特化
template<>
struct GetKey<string>
{
	size_t operator()(const string& key)
	{
		//根据字符串，计算出数值并返回
		size_t val = 0;
		for (auto e : key)
			val += static_cast<size_t>(e);

		return val;
	}
};

添加了这个仿函数之后，就需要对 哈希表 中所有需要获取 key 的地方进行修改

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

此时 哈希表 中的键值可以正常存储 字符串

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习
三个字符串计算出的值分别为：1407、1956、1344

这是在 字符串长度不一且字符相差过大 的情况下计算出来的，假若 字符串过短或者字符串较为接近，可能会计算出相同的值，这会导致 哈希冲突

因此，单纯的累加每个字符的 ASCII 码值显得不够专业

有人专门对 字符串 进行研究，搞出了各种各样重复率较低的 字符串哈希算法

字符串哈希算法

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

在众多 字符串哈希算法 中，BKDRHash 一骑绝尘，各方面都非常优秀，因此这里我们选择 BKDRHash 算法作为 计算字符串值 的函数

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

BKDRHash 的核心就是 在原来值的基础上 * 131，再加上字符的 ASCII 码值

//模板的特化
template<>
struct GetKey<string>
{
	size_t operator()(const string& key)
	{
		//根据字符串，计算出数值并返回
		size_t val = 0;

		//BKDRHash
		for (auto e : key)
			val = val + 131 + static_cast<size_t>(e);

		return val;
	}
};

修改之后，三个字符串计算出的值分别为：3634、5100、3702

显然此时的值更为分散，符合我们的需求

关于 static_cast<>

这是 C++ 中提供的类型转换函数，static_cast<> 相当于 C语言中的隐式类型转换，这样写的话更加规范，让别人一眼就能看出这里发生了隐式类型转换

1.3、优化：素数大小

使用除留余数法时，哈希表的大小最好是素数，这样能够减少哈希冲突产生的次数

SGI 版 STL 中，哈希表 在扩容时就使用了这一技巧

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

简单来说，就是当我们扩容后，按照 下一个素数值大小 进行扩容

这些素数都是近似 2 倍的大小关系，在确保不会频繁扩容的同时，尽可能减少哈希冲突

所以需要这样一个函数

//获取素数
size_t GetNextPrime(size_t prime)
{
	//返回当前位置的下一个素数值，作为扩容后的空间大小
	// SGI版
	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
	};

	for (int i = 0; i < __stl_num_primes; i++)
		if (__stl_prime_list[i] > prime)
			return __stl_prime_list[i];
	
	return __stl_prime_list[__stl_num_primes - 1];	//返回最后一个值
}

同样的，需要对扩容的地方进行改造

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

在改造之后，哈希表 的初始大小变为 53

1.4、新增：迭代器类

哈希表 中理应提供一个 迭代器 对其中的值进行判断，因为桶是一个 单链表，只能向前走，不能回头，因此我们的 迭代器 要设计为 单向迭代器（只支持 ++）

关于多模板参数 template<class K, class V, class Ref, class Ptr> 的设计原理这里不再阐述，感兴趣的可以看看这篇文章：《C++ STL学习之【list的模拟实现】》

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

//迭代器类
template<class K, class V, class Ref, class Ptr>
struct HashTableIterator
{
	typedef HashNode<K, V> Node;	//迭代器中元素
	typedef HashTableIterator<K, V, Ref, Ptr> Self;	//迭代器自己

	HashTableIterator(Node* node)
		:_node(node)
	{}

	//基本功能
	//获取值
	Ref operator*()
	{
		return _node->_kv;
	}

	//获取指针
	Ptr operator->()
	{
		return &(operator*());
	}

	//判断逻辑
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
	bool operator!=(const Self& it)
	{
		return !(*this == it);
	}

	//++ 的实现

	Node* _node;	//迭代器
};

关于 迭代器类 比较麻烦的就是 operator++()

先来说说移动逻辑：

如果当前所在桶中还有数据，简单，直接移动至 _next 即可
如果没有数据（为空），就比较麻烦了，需要移动至当前哈希表中，下一个有数据的桶

显然，需要用到 哈希表，并且是 同一个哈希表
解决办法：构造迭代器时，传递当前哈希表的地址，构造一个指针指向哈希表

如何在 哈希表 中进行移动？
解决办法：首要问题是知道当前位于哈希表中的哪个位置。这个可以通过自己的 值 % 哈希表的大小 求出，清楚位置后，就向后移动，直到移动至一个不为空的位置，返回即可

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

因为要获取使用 哈希表，所以需要对 迭代器类 做出一些调整

//对哈希表的前置声明
template<class K, class V>
class HashTable;
	
//迭代器类
template<class K, class V, class Ref, class Ptr>
struct HashTableIterator
{
	typedef HashNode<K, V> Node;	//迭代器中元素
	typedef HashTableIterator<K, V, Ref, Ptr> Self;	//迭代器自己
	typedef HashTable<K, V> HT;	//哈希表·新增

	//改造构造函数
	HashTableIterator(Node* node, const HT* ht)	
		:_node(node)
		, _pht(ht)
	{}
	
	//基本功能
	//……

	Node* _node;	//迭代器
	const HT* _pht;	//指向哈希表的指针·新增
};

现在能通过 _pht 访问同一个哈希表

细节：

需要对哈希表进行前置声明才能正常使用
指向哈希表的指针为 const 指针，否则 const 哈希表对象调不动迭代器

现在对 operator++() 进行实现

//++ 的实现
Self operator++()
{
	//计算当前所处的位置
	size_t HashI = GetKey<K>()(_node->_kv.first) % _pht->_table.size();

	//如果下一个位置不为空，则直接向下走即可
	if (_node->_next)
		_node = _node->_next;
	else
	{
		//比较麻烦，实现桶之间的移动
		while (++HashI < _pht->_table.size())
		{
			//判断当前是否为空桶
			if (_pht->_table[HashI] != nullptr)
			{
				_node = _pht->_table[HashI];
				break;
			}
		}

		//看看是不是走到最后了
		if (HashI == _pht->_table.size())
			_node = nullptr;
	}

	return *this;	//返回的是迭代器对象
}

在这个函数中，访问了 哈希表类 中的私有成员 _table，这是不行的，为了让其能成功访问，我们可以把 迭代器类 设为 哈希表类 的 友元类

同时，在 哈希表类 中增加 迭代器操作 的相关函数

template<class K, class V, class Ref, class Ptr>
friend struct HashTableIterator;	//友元声明

//迭代器相关
typedef HashTableIterator<K, V, pair<K, V>&, pair<K, V>*> iterator;
typedef HashTableIterator<K, V, const pair<K, V>&, const pair<K, V>*> const_iterator;

iterator begin()
{
	//起始位置是第一个有数据的桶
	Node* _node = nullptr;
	for (auto e : _table)
	{
		if (e != nullptr)
		{
			_node = e;
			break;
		}
	}

	return iterator(_node, this);	//构造迭代器对象
}

iterator end()
{
	//最后一个位置为空
	return iterator(nullptr, this);
}

const_iterator begin() const
{
	Node* _node = nullptr;
	for (auto e : _table)
	{
		if (e != nullptr)
		{
			_node = e;
			break;
		}
	}

	return const_iterator(_node, this);	//构造迭代器对象
}

const_iterator end() const
{
	return const_iterator(nullptr, this);
}

现在可以测试 迭代器

直接用 范围 for，分别测试 普通迭代器 与 const 迭代器

void func(const HashTable<string, int> hash)
{
	//这里面的是 const 对象
	cout << "const 对象" << endl;
	for (auto e : hash)
		cout << e.first << " " << e.second << endl;

	cout << endl << "====================================" << endl << endl;
}

void TestOpenHash2()
{
	vector<pair<string, int>> goods{ make_pair("iPhone 14 Pro Max", 9399),
							make_pair("SAMSUNG Galaxy S23 Ultra", 6509),
							make_pair("HUAWEI Mate 50 Pro", 5999) };
	HashTable<string, int> hash;
	for (auto& e : goods)
		hash.Insert(e);


	func(hash);

	cout << "普通对象" << endl;
	for (auto e : hash)
		cout << e.first << " " << e.second << endl;
}

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

范围 for 没问题，迭代器也就没问题了

注意：

const 迭代器是为 const 对象提供的，所以可以选择重载 begin() 与 end()，也可以选择重新编写 cbegin() 和 cend()，二者除了函数名外，其他都是一样的
单向迭代器是不能向后走的，所以哈希表中没有反向迭代器

2、封装实现 unordered_set 和 unordered_map

如同使用一棵红黑树同时封装 set/map

同样可以使用一张哈希表同时封装 unordered_set/unordered_map

就连封装时遇到的问题都差不多

2.1、解决 k/v 参数冲突问题

unordered_set 需要 k 的模型，而 unordered_map 需要 k/v 的模型

为了满足不同的需求，需要对 哈希表 的模板进行调整，让其既能适应 unordered_set，也能适应 unordered_map

至于如何调整，可以看看 红黑树 封装时的图示（类似的原理）

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

//节点类
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;	//指向下一个节点
};

//对哈希表的前置声明
template<class K, class T>
class HashTable;

//迭代器类
template<class K, class T, class Ref, class Ptr>
struct HashTableIterator
{
	typedef HashNode<T> Node;	//迭代器中元素
	typedef HashTableIterator<K, T, Ref, Ptr> Self;	//迭代器自己
	typedef HashTable<K, T> HT;	//哈希表
	
	Node* _node;	//迭代器
	const HT* _pht;	//指向哈希表的指针
};

//哈希表
template<class K, class T>
class HashTable
{
	typedef HashNode<T> Node;

	template<class K, class T, class Ref, class Ptr>
	friend struct HashTableIterator;	//友元声明
public:

	//迭代器相关
	typedef HashTableIterator<K, T, T&, T*> iterator;
	typedef HashTableIterator<K, T, const T&, const T*> const_iterator;

private:
	//哈希桶中不需要平衡因子，节点存储满后，进行扩容就行了
	vector<Node*> _table;
	size_t _n = 0;	//有效数据量
};

还有很多细节都是需要改动的，但把接口简单修改后，unordered_set 和 unordered_map 都可以传递各自需要的参数了

unordered_set

#pragma once
#include "HashTable.hpp"

using namespace OpenHash;

namespace US
{
	template<class K>
	class unordered_set
	{
		typedef K data;
		typedef HashTable<K, data> HT;
	private:
		HT _t;	//这是一张哈希表
	};
}

unordered_map

#pragma once
#include "HashTable.hpp"

using namespace OpenHash;

namespace UM
{
	template<class K, class V>
	class unordered_map
	{
		typedef pair<const K, V> data;
		typedef HashTable<K, data> HT;
	private:
		HT _t;	//这也是一张哈希表
	};
}

注意：unordered_map 中 pair 的第一个参数 K 需要使用 const 修饰，拒绝被修改

2.2、解决 key 的获取问题

现在面临一个尴尬的问题：两个参数不同的类型，如何同时使用一种获取 key 的方法？

答案是：传递仿函数，根据自己的需求，创建仿函数，然后传给哈希表，让哈希表在计算 key 时使用即可，当然哈希表中涉及获取 key 的地方都要改

HashTable.hpp

//对哈希表的前置声明
template<class K, class T, class KeyOfT>
class HashTable;

//迭代器类
template<class K, class T, class Ref, class Ptr, class KeyOfT>
struct HashTableIterator
{
	typedef HashNode<T> Node;	//迭代器中元素
	typedef HashTableIterator<K, T, Ref, Ptr, KeyOfT> Self;	//迭代器自己
	typedef HashTable<K, T, KeyOfT> HT;	//哈希表
	
	//……

	//++ 的实现
	Self operator++()
	{
		//计算当前所处的位置
		size_t HashI = GetKey<K>()(KeyOfT()(_node->_data)) % _pht->_table.size();
		
		//……
	}
	
	//……
};

//哈希表
template<class K, class T, class KeyOfT>
class HashTable
{
	typedef HashNode<T> Node;

	template<class K, class T, class Ref, class Ptr, class KeyOfT>
	friend struct HashTableIterator;	//友元声明
public:

	//……

	//迭代器相关
	typedef HashTableIterator<K, T, T&, T*, KeyOfT> iterator;
	typedef HashTableIterator<K, T, const T&, const T*, KeyOfT> const_iterator;
	
	//……

	//查找
	iterator Find(const K& key)
	{
		//……
		
		while (cur)
		{
			if (KeyOfT()(cur->_data) == key)
				//……
		}

		//……
	}

	//插入
	bool Insert(const T& data)
	{
		if (Find(KeyOfT()(data)) != end())
			return false;	//冗余

		//判断扩容
		if (_n == _table.size())
		{
			//传统写法
			size_t newSize = GetNextPrime(_table.size());
			vector<Node*> newTable(newSize);	//新的表

			for (auto& cur : _table)
			{
				while (cur)
				{
					size_t HashI = GetKey<K>()(KeyOfT()(cur->_data)) % newSize;	//计算新的哈希值
					
					//……
				}
			}
		}

		//插入
		size_t HashI = GetKey<K>()(KeyOfT()data) % _table.size();	//计算哈希值
		
		//……
	}

	bool Erase(const K& key)
	{
		//这里直接查找，因为需要保存上一个节点信息（单链表的删除）

		size_t HashI = GetKey<K>()(key) % _table.size();
		Node* prev = nullptr;
		Node* cur = _table[HashI];

		//单链表的删除
		while (cur)
		{
			if (KeyOfT()(cur->_data) == key)
			{
				//……
			}
			
			//……
		}

	}
};

注意：新增了迭代器之后，Find 的返回值变成了 iterator

对于 哈希表 类来说，主要改动其实就两个：模板参数的改变、获取哈希表对象 key 值

如此一来，unordered_set 与 unordered_map 只需要提供符合自己特色的 key 获取仿函数即可，增加部分基础功能（具体函数的功能实现位于 HashTable.hpp 中）

unordered_set

#pragma once
#include "HashTable.hpp"

using namespace OpenHash;

namespace US
{
	template<class K>
	class unordered_set
	{
		struct KOfKey
		{
			K operator()(const K& key) const
			{
				return key;
			}
		};

		typedef K data;
		typedef HashTable<K, data, KOfKey> HT;
	public:
		//默认构造
		unordered_set()
			:_t()
		{}

		//迭代器区间构造
		template<class InputIterator>
		unordered_set(InputIterator first, InputIterator last)
			: _t()
		{
			//遍历迭代器，插入即可
			while (first != last)
			{
				insert(*first);
				++first;
			}
		}

		//迭代器
		typedef typename HT::iterator iterator;
		typedef typename HT::const_iterator const_iterator;

		iterator begin() { return _t.begin(); };
		iterator end() { return _t.end(); };

		const_iterator begin() const { return _t.begin(); };
		const_iterator end() const { return _t.end(); };

		//判空、求大小
		bool empty() const { return _t.Empty(); };
		size_t size() const { return _t.Size(); };

		//插入、删除元素
		bool insert(const data& val) { return _t.Insert(val); };
		bool erase(const K& key) { return _t.Erase(key); };

		//交换、查找、清理
		void swap(unordered_set& us) { _t.Swap(us._t); };
		iterator find(const K& key) { return _t.Find(key); };
		void clear() { _t.Clear(); };

	private: 
		HT _t;	//这是一张哈希表
	};
}

unordered_map

#pragma once
#include "HashTable.hpp"

using namespace OpenHash;

namespace UM
{
	template<class K, class V>
	class unordered_map
	{
		struct KVOfKey
		{
			K operator()(const pair<K, V>& kv) const
			{
				return kv.first;
			}
		};

		typedef pair<K, V> data;
		typedef HashTable<K, data, KVOfKey> HT;
	public:
		//默认构造
		unordered_map()
			:_t()
		{}

		//迭代器区间构造
		template<class InputIterator>
		unordered_map(InputIterator first, InputIterator last)
			: _t()
		{
			//遍历迭代器，插入即可
			while (first != last)
			{
				insert(*first);
				++first;
			}
		}

		//迭代器
		typedef typename HT::iterator iterator;
		typedef typename HT::const_iterator const_iterator;

		iterator begin() { return _t.begin(); };
		iterator end() { return _t.end(); };

		const_iterator begin() const { return _t.begin(); };
		const_iterator end() const { return _t.end(); };

		//判空、求大小
		bool empty() const { return _t.Empty(); };
		size_t size() const { return _t.Size(); };

		//插入、删除元素
		bool insert(const data& val) { return _t.Insert(val); };
		bool erase(const K& key) { return _t.Erase(key); };

		//交换、查找、清理
		void swap(unordered_map& um) { _t.Swap(um._t); };
		iterator find(const K& key) { return _t.Find(key); };
		void clear() { _t.Clear(); };
	private:
		HT _t;	//这也是一张哈希表
	};
}

进行功能测试：

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

可以正常使用，现在来进行优化

2.3、解决 unordered_set 迭代器非法操作

unordered_set 中只有键值，而键值是不能被随意修改的（通过迭代器的方式）

void TestUS2()
{
	vector<int> arr = { 7,3,6,9,3,1,6,2 };
	unordered_set<int> s1(arr.begin(), arr.end());

	auto it = s1.begin();
	*it = 668;

	for (auto e : s1)
		cout << e << " ";
	cout << endl;
}

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

结果为 668，这很正常，因为已经把迭代器中的键值改了，这就导致迭代器在移动时，是根据更改后的键值计算哈希值 = 668 % 53 = 32，而我们这组数中，32 位置及其后面都没有值，所以也就只打印了一个 668

当然，这不是重点，重点在于 我们把 unordered_set 中的键值修改了！

库中的解决方法：不管你 unordered_set 申请的是什么迭代器，我都给你 const 迭代器

//迭代器
typedef typename HT::const_iterator iterator;
typedef typename HT::const_iterator const_iterator;

再次测试（此时需要把赋值语句屏蔽，否则影响后面的结果）

为什么要屏蔽赋值语句？

因为接下来要展示的是一个编译时错误

而给常量赋值这个错误优先级更高，在编译前就报错了，也就是说，不能让赋值语句报的错影响我们的操作

虽然最终都是报了不能随便赋值 的错误，但如果我们不借此根治问题，后续没有出现赋值语句时，一样会报错

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

此时出现了一个非常经典的 类型转换 错误

为什么？
这是因为 unordered_set 中普通对象版的 begin() 或 end() 使用的是哈希表中 const 迭代器，但哈希表中的迭代器相关函数返回的是普通迭代器啊，也就是说，存在一个普通迭代器转为 const 迭代器的问题，两者差别很大，编译器无法自行转换

库中的解决方案：
在迭代器类中提供一个十分巧妙的函数，它对于普通迭代器对象来说，当传入的是普通迭代器时，相当于拷贝构造；当传入的是 const 迭代器时，相当于一个特殊的迭代器构造，即把普通迭代器对象构造为 const 迭代器；当然，这个函数对于 const 迭代器对象没有影响，毕竟这玩意不能被修改

//迭代器类
template<class K, class T, class Ref, class Ptr, class KeyOfT>
struct HashTableIterator
{
	//……
	
	typedef HashTableIterator<K, T, T&, T*, KeyOfT> iterator;	//普通版的迭代器·关键

	//一个特殊的构造，既能充当拷贝构造，也能充当特殊构造
	HashTableIterator(const iterator& it)
		:_node(it._node)
		, _pht(it._pht)
	{}

	//……
};

加上之后，代码能正常编过，当然不能给常量赋值的错误也能正常显现

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

这是一个非常牛X的解决方案

2.4、调整函数返回值

unordered_set 和 unordered_map 中的 insert() 返回值比较特殊，它不仅要返回 迭代器，也要表示本次插入操作 是否成功

改造起来也是十分的简单

HashTable.hpp

//插入
pair<iterator, bool> Insert(const T& data)
{
	auto ret = Find(KeyOfT()(data));
	if (ret != end())
		return make_pair(ret, false);	//冗余

	//判断扩容
	if (_n == _table.size())
	{
		//传统写法
		size_t newSize = GetNextPrime(_table.size());
		vector<Node*> newTable(newSize);	//新的表

		for (auto& cur : _table)
		{
			while (cur)
			{
				size_t HashI = GetKey<K>()(KeyOfT()(cur->_data)) % newSize;	//计算新的哈希值
				Node* next = cur->_next;

				//单链表头插至新表
				cur->_next = newTable[HashI];
				newTable[HashI] = cur;


				cur = next;
			}
		}

		_table.swap(newTable);
	}

	//插入
	size_t HashI = GetKey<K>()(KeyOfT()(data)) % _table.size();	//计算哈希值

	//单链表头插
	Node* cur = _table[HashI];	//原来的头节点
	_table[HashI] = new Node(data);	//创建新的头
	_table[HashI]->_next = cur;	//连接
	_n++;

	return make_pair（iterator(_table[HashI], this), true);
}

进行简单测试

unordered_set

void TestUS3()
{
	unordered_set<int> s1;
	auto ret = s1.insert(1);
	cout << "<" << *ret.first << ">" << " | " << ret.second << endl;

	ret = s1.insert(1);
	cout << "<" << *ret.first << ">" << " | " << ret.second << endl;
}

unordered_map

void TestUS3()
{
	unordered_set<int> s1;
	auto ret = s1.insert(1);
	cout << "<" << *ret.first << ">" << " | " << ret.second << endl;

	ret = s1.insert(1);
	cout << "<" << *ret.first << ">" << " | " << ret.second << endl;
}

测试结果：

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

显然，第二次插入时均失败（因为冗余了）

2.5、unordered_map 新增 operator[ ]

作为同时用于键值和实值的容器，unordered_map 需要一个能快速访问实值的函数，即 operator[]()

这个函数功能十分强大，具备：插入、修改、插入+修改、查找 等诸多功能，是 unordered_map 中的真香函数

实现逻辑：

判断 key 存不存在，如果存在，返回 value
如果不存在，就插入，并返回新的 value

可以分为几个判断写，也可以直接使用 insert()，毕竟这玩意的返回值也是 重量级 的

//unordered_map 中独有的功能
V& operator[](const K& key)
{
	auto ret = insert(make_pair(key, V()));	//获取 <迭代器, bool> 的键值对
	auto it = ret.first;	//获取迭代器
	return it->second;	//返回实值
}

简单测试一下

void TestUM3()
{
	vector<pair<string, int>> goods{ make_pair("iPhone 14 Pro Max", 9399),
					make_pair("SAMSUNG Galaxy S23 Ultra", 6509),
					make_pair("HUAWEI Mate 50 Pro", 5999) };

	unordered_map<string, int> m1;
	for (auto& e : goods)
		m1[e.first] = e.second;

	for (auto& e : m1)
		cout << e.first << " " << e.second << endl;
}

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习
没有问题，至此，使用一张哈希表同时封装出 unordered_set 和 unordered_map 就算是完成了

3、性能测试

将自己封装的 unordered_set 与库中的 unordered_set 进行性能对比（Release 模式下）

void TestPerformance()
{
	US::unordered_set<int> myUSet;
	std::unordered_set<int> stdUSet;

	srand((size_t)time(NULL));

	int mySetTime = 0;
	int stdSetTime = 0;

	clock_t begin, end;

	int sum = 0;
	int n = 5000000;
	for (int i = 0; i < n; i++)
	{
		int val = rand() % n + i;

		begin = end = 0;
		begin = clock();
		auto ret1 = myUSet.insert(val);
		end = clock();
		mySetTime += (end - begin);

		begin = end = 0;
		begin = clock();
		auto ret2 = stdUSet.insert(val);
		end = clock();
		stdSetTime += (end - begin);

		if (ret1.second && ret2.second)
			sum++;	//成功插入的数据量
	}

	cout << "成功插入 " << sum << " 个数据" << endl;
	cout << "myUSet 耗时: " << mySetTime << " ms" << endl;
	cout << "stdUSet 耗时: " << stdSetTime << " ms" << endl;
}

插入约 300w 个数据

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

在经过 Release 模式的优化后，我们自己封装实现的 unordered_set 异常生猛，遥遥领先

4、源码

源码在下面的仓库里

注：HashTable.hpp 是封装 unordered_set 和 unordered_map 后的成品；HashTable-副本.hpp 是纯净版的哈希表

《哈希表的完善及封装》

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

🌆总结

以上就是本次关于 C++【哈希表的完善及封装】的全部内容了，在本文中，我们首先将 哈希表 进行了完善，解决了一些深拷贝问题，新增了迭代器；当 哈希表 完善后，我们用一张 哈希表同时封装实现了 unordered_set 和 unordered_map，其中涉及大量泛型编程思想，值得仔细推敲

C++【哈希表的完善及封装】,C++修行之路,c++,散列表,开发语言,stl,学习

文章来源地址https://www.toymoban.com/news/detail-558846.html
相关文章推荐
C++ 进阶知识
C++【哈希表的模拟实现】
C++【初识哈希】
C++【一棵红黑树封装 set 和 map】
C++【红黑树】
C++【AVL树】
C++【set 和 map 学习及使用】
C++【二叉搜索树】
C++【多态】
C++【继承】