哈希表及其封装

哈希概念

在了解哈希表的之前我们先来熟悉一下unordered_map和unordered_set，这两个容器底层用的就是哈希结构。他们跟之前的map和set功能类似。

不同点在于：

unordered_map和unordered_set查找的效率要比map和set高
unordered系列的容器遍历无序，map和set遍历有序（底层实现）

在map和set中我们底层是有红黑树构成的，所以查找一个元素平均时间复杂度为 $o(Log_2N)$ ，而unordered_map和unordered_set中我们可以通过Key键，直接访问对应的元素，这里可以看做为一层映射关系，我们的 $Key - > Va l$ ，同时Key和Val的类型可以不相同。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结果中：

插入元素

根据插入数据的关键码，用此函数算对应的位置插入

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做存储的位置，依次比较，如果关键码相同就返回

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

例如数据： ${ 1，7，6，4，5，9 }$

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？

哈希冲突

对于两个不同的 $K 1$ 和 $K 2$ ，虽然这两个键不一样，但是HashFunc(K1)和HashFunc(K2)可能相同，那么此时由于位置已经被其中一个占了，另一个插入进来的时候必然会发生没有位置的情况，即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞

如何解决哈希冲突呢？

引起哈希冲突的原因可能是：哈希函数设计的不够合理。

哈希函数设计原则：

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

常用哈希函数

1. 直接定址法（常用）

就如上图一样我们每个为每一个元素都开放一个空间，让其Key都有位置映射。其实本质上就是一个哈希数组。举个栗子：

加入这里有一个数组 $n u m s [10]$ ，其中 $0 <= n u m s [i] <= 10$ ，此时要求我们求出 $[0, 10]$ 中每一个数字出现的次数，那么此时我们就可以开辟一个大小11的数组，来遍历数组 $n u m s$ ，记录每一个数字出现的次数，这中哈希函数最好实在 $连续范围内的数字$ 使用，不然会太浪费空间。

2.除留余数法（常用）

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

解决哈希冲突

解决哈希冲突有两种常用的方法：开散列和闭散列

闭散列（开放定址法）

当发生冲突的时候，我们会把Key对应的值存储到下一个空的位置，那么如何寻找下一个空的位置呢？

线性探测
二次探测

线性探测

在这里插入图片描述

线性探测的查找规则： $依次往后找，也就是说如果我们一直冲突的话，最后我们查找的次数是递增的： 1, 2, 3, 4, 5.. n$

二次探测的查找规则： $每次往后找平方次数的位置，例如：1^2,2^2,3^3...n^n，观察是否被占了，如果没有就插入$

这只是插入，当我们删除的时候，由于我们可能已经产生了冲突，所以当我们此时位置的值不对应的时候还需要继续往下寻找。

这里还需要看一下删除操作，如下图，当我们把11删除之后，11这个位置如何处理呢，直接置为空吗？，正常情况下我们当我们继续往后寻找的时候，如果当前位置被删除了我们还是需要继续查找的，所以我们可以给每一个位置增加一个状态，当这个位置为空的时候我们也就不需要往后查找了，但是如果是存在或者删除我们还需要继续往下查找。

在这里插入图片描述

代码实现：

那么根据上述我们可以定义出上述结构，关于这个负载因子，负载因子 = 元素个数 / 数组大小，负载因子决定了我们是否需要扩容，对于开放定址法负载因子到0.7~0.8就需要进行扩容了，因为负载因子越大，代表插入元素越多，那么冲突的可能性也就越大。

namespace open_address
{
	enum State
	{
		EXITS,
		DELETE,
		EMPTY
	};
	template<class T>
	struct HashData
	{
		T _data;
		State _state = EMPTY;
	};

	template<class T>
	class HashTables
	{
		typedef HashData<T> Node;
	private:
		vector<Node> _tables;
		size_t _n;
	public:
		HashTables()
		{
			_tables.resize(10);
		}

		Node* Find(const T& key)
		{
			size_t hashi = key % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._data == key)
					return &_tables[hashi];
				hashi = (hashi + 1) % _tables.size();
			}
			return nullptr;
		}
		
        //线性探测版
		bool Insert(const T& key)
		{
			//扩容
			//if ((_n * 10) / _tables.size() == 7)
			//{
			//	vector> newtables;
			//	newtables.resize(_tables.size()*2);
//            内容冗余
			//	for (size_t i = 0; i < _tables.size(); i++)
			//	{
			//		if (_tables[i]._state == EXITS)
			//		{
			//			size_t n = (_tables[i]._data) % newtables.size();
			//			//如果当前位置被占了，就继续往下去寻找
			//			while (newtables[n]._state != EMPTY)
			//			{
			//				n = (n + 1) % newtables.size();
			//			}
			//			newtables[n]._data = _tables[i]._data;
			//			newtables[n]._state = EXITS;

			//		}
			//	}
			//	_tables.swap(newtables);
			//}
			if (Find(key))
				return false;
            //新的写法
			if ((_n * 10) / _tables.size() == 7)
			{
				//在类中，成员函数可以访问类任意对象的私有成员
				HashTables<T> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._state == EXITS)
					{
						newHT.Insert(_tables[i]._data);
					}
				}
				_tables.swap(newHT._tables);
			}
			size_t hashi = key % _tables.size();
			//如果当前位置被占了，就继续往下去寻找
			while (_tables[hashi]._state != EMPTY) 
			{
				hashi = (hashi + 1) % _tables.size();
			}
			_tables[hashi]._data = key;
			_tables[hashi]._state = EXITS;
			_n++;
			return true;
		}

		bool Erase(const T& key)
		{
			if (Find(key) == nullptr)
			{
				cout << "No element" << endl;
				return false;
			}
			size_t hashi = key % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._data == key)
				{
					_tables[hashi]._state = DELETE;
					break;
				}
				hashi = (hashi + 1) % _tables.size();
			}
			return true;
		}
	};
}

开散列（拉链法）

拉链法数组里面存的是一个又一个的指针，每个指针都表示一个桶，例如数据： ${ 1，7，6，4，5，9 ,11 }$ ，假设我们数组长度为10，根据我们的哈希函数求出对应的位置。那么

hashkey(1) = 1%10 = 1
hashkey(11) = 11 % 10 = 1

此时这两种情况都放在下标为1的这个桶里，就不需要向闭散列一样再去后面去空位了。

代码实现：

namespace BucketNode
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next = nullptr;

		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};

	template<class T>
	class HashTables
	{
		typedef HashNode<T> Node;
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	public:
		HashTables()
		{
			_tables.resize(10);
		}

		Node* Find(const T& key)
		{
			size_t hashi = key % _tables.size();
			Node* cur = _tables[hashi];;
			while (cur)
			{
				if (cur->_data == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}

		bool Insert(const T& key)
		{
			if (Find(key))
				return false;

			if (_n / _tables.size() == 1)
			{
				vector<Node*> newtables(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						//把旧的数据插入到扩容后的表中
						size_t newidx = cur->_data % newtables.size();
						cur->_next = newtables[newidx];
						newtables[newidx] = cur;
						//继续遍历旧表的下一个元素
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}

			//直接进行头插到对应位置
			size_t hashi = key % _tables.size();
			Node* newNode = new Node(key);
			newNode->_next = _tables[hashi];
			_tables[hashi] = newNode;
			_n++;
			return true;
		}

		bool Erase(const T& key)
		{
			if (Find(key) == nullptr)
			{
				cout << "No element" << endl;
				return false;
			}

			size_t hashi = key % _tables.size();
			Node* cur = _tables[hashi];;
			Node* pre = nullptr;
			while (cur)
			{
				if (cur->_data == key)
				{
					if (pre == nullptr)
					{
						_tables[hashi] = cur->_next;
					}
					else
					{
						pre->_next = cur->_next;
					}
					delete cur;
					return true;
				}
				pre = cur;
				cur = cur->_next;
			}
			return false;
		}
	};
}

总结

这里有一个小问题：如果我们想要存储一个 $s t r in g$ 类型的数据，该如何去找对应的位置呢？

在这里插入图片描述

可以看到库里面的模版参数上还有一个hash，这时干什么的呢？

哈希表本质其实是把一个元素转化为整数，然后去哈希表找对应的关系存起来，对于正数我们直接转就可以了，但是如果是负数、 $s t r in g$ 类型呢？所以这就需要一个hash来帮我们把不同类型转化为整数。

代码实现：

template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t ret = 0;
			for (auto& e : s)
			{
				ret += (e * 31);
			}
			return ret;
		}
	};

在这里插入图片描述

然后只需要在每次查找位置的时候套上一层即可。

哈希表封装

Ok，了解完底层之后我们自己模拟实现一下unordered_map和unordered_set。这里底层我们都用开散列（拉链法）来实现。

所以我们还需要确定我们插入的是 $Key - > v a l$ 还是 $Key$ 。所以我们需要写一个KeyOfT方法，这个方法主要是在插入过程中返回键值，因为我们使用键来确定插入的位置的。

在这里插入图片描述

此时我们的Inset变为如下：

bool Insert(const T& data)
		{
			KeyOfT kot; //区分是键值对还是键值
			hash hs; //转为整数
			if (Find(kot(data)))
				return false;

			if (_n / _tables.size() == 1)
			{
				vector<Node*> newtables(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						//把旧的数据插入到扩容后的表中
						size_t newidx = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[newidx];
						newtables[newidx] = cur;
						//继续遍历旧表的下一个元素
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}

			//直接进行头插到对应位置
			size_t hashi = hs(kot(data)) % _tables.size();
			Node* newNode = new Node(data);
			newNode->_next = _tables[hashi];
			_tables[hashi] = newNode;
			_n++;
			return true;
		}

迭代器

operator++()

这里要分两种情况：

在这里插入图片描述

如图，_node是此时我们遍历到的位置，当我们++的时候我们需要观察他的_next是否有数据，如果有直接返回下一个节点的迭代器即可。如果没有需要的话需要继续向下去找，那么此时我们就需要知道后面这个表中到底有啥，所以我们实现迭代器的时候需要把这个表传过来，但是直接传这个表本身吗？不，那样空间效率太高了，所以我们可以穿一个表的指针过来，这样我们就可以访问表中的数据了，同时还需要让迭代器类变为表的友元类，因为我们需要去访问 _tables这个私有成员。

然后其他的则是一些必要的operator*和operator->，这里不做详细解释了。最后由于我们不管迭代器定义在哪里，编译器默认只会向上去查找，这里我们把迭代器定义在哈希表上方，然后再迭代器上方写一个哈希表的声明。

代码实现：

template<class K, class T, class KeyOfT, class hash>
	class HashTables;

	template<class K, class T, class KeyOfT, class hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K,T,KeyOfT,hash> Self;
		typedef HashTables<K, T, KeyOfT, hash> pht;
		pht* _pht;
		Node* _node;

		HTIterator(Node* node,pht* ht)
			:_node(node)
			,_pht(ht)
		{}

		Self& operator++()
		{
			hash hs;
			KeyOfT kot;
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				//由于需要访问_pht的私有成员，所以迭代器设置为哈希表的友元类
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				hashi++;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						break;
					}
					hashi++;
				}
				if (hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[hashi];
				}
			}
			return *this;
		}

		T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& x) const
		{
			return _node != x._node;
		}

	};

//部分代码，把迭代器设置为哈希表的友元类
template<class K,class T, class KeyOfT,class hash>
	class HashTables
	{
	public:
		template<class K, class T, class KeyOfT, class hash>
		friend struct HTIterator;

const迭代器

什么时候需要使用const迭代器呢？如下图：在这里插入图片描述

当我们需要打印哈希表里的数据的时候我们并不能修改它，所以这个时候就需要使用const迭代器了。

如下图，我们只需要让operator*和operator->这两个的返回值不能修改那么const迭代器就改好了。

注意事项：在实际模拟实现当中，由于我们传入的是const对象，那么此时的this指针的类型就变为了，const object* const了，所以之前迭代器里面的成员函数我们都需要让this加上const，不然编译不通过。

代码实现：

template<class K, class T, class KeyOfT, class hash, class Ref, class Ptr>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K,T,KeyOfT,hash, Ref, Ptr> Self;
		typedef HashTables<K, T, KeyOfT, hash> pht;
		const pht* _pht;   // ---> 增加const修饰
		Node* _node;

		HTIterator(Node* node,const pht* ht)
			:_node(node)
			,_pht(ht)
		{}

		Self& operator++() 
		{
			hash hs;
			KeyOfT kot;
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				//由于需要访问_pht的私有成员，所以迭代器设置为哈希表的友元类
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				hashi++;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						break;
					}
					hashi++;
				}
				if (hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[hashi];
				}
			}
			return *this;
		}

		Ref operator*() const // ---> 增加const修饰
		{
			return _node->_data;
		}

		Ptr operator->() const  // ---> 增加const修饰
		{
			return &_node->_data;
		}

		bool operator!=(const Self& x) const   // ---> 增加const修饰
		{
			return _node != x._node;
		}

	};


//哈希表表中的实现：
	ConstIterator Begin() const
		{
			if (_n == 0)
				return End();
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
					return ConstIterator(_tables[i], this);
			}
			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

operator[]（unordered_map）

operator[]返回的是 $Key - > Va l$ 中的 $Va l$ 引用，当我们哈希表中没有当前数据的时候他会插入，如果存在的话会改变 $Va l$ 。

代码实现：

		V& operator[](const K& key)
		{
			auto it = _ht.Insert(make_pair(key, K())); // pair
			return (it.first)->second;  // iterator->second。调用operator->()。
		}

总代码

unordered_set

#pragma once
#include "BucketNode.h"

namespace Unordered_set
{

	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t ret = 0;
			for (auto& e : s)
			{
				ret += (e * 31);
			}
			return ret;
		}
	};


	template<class K, class Hash = HashFunc<K>>
	class Unordered_set
	{
		struct KeyofValSet
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef BucketNode::HashTables<K,const K, KeyofValSet, Hash> HashTables;
		typedef typename BucketNode::HashTables<K, const K, KeyofValSet, Hash>::Iterator iterator;
		typedef typename BucketNode::HashTables<K, const K, KeyofValSet, Hash>::ConstIterator const_iterator;
	private:
		HashTables _ht;
	public:

		iterator begin()
		{
			return _ht.Begin();
		}
		iterator end()
		{
			return _ht.End();
		}

		const_iterator begin() const
		{
			return _ht.Begin();
		}

		const_iterator end() const
		{
			return _ht.End();
		}

		pair<iterator,bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}

		iterator erase(const K& key)
		{
			return _ht.Erase(key);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}


	};
	
}

unordered_map

#pragma once
#include "BucketNode.h"

namespace Unordered_map
{

	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	template<>
	struct HashFunc<string>
	{
		size_t operator()(const string& s)
		{
			size_t ret = 0;
			for (auto& e : s)
			{
				ret += (e * 31);
			}
			return ret;
		}
	};
	
	template<class K,class V,class Hash = HashFunc<K>>
	class Unordered_map
	{
		struct KeyofValMap
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef BucketNode::HashTables<K, pair<const K, V>, KeyofValMap, Hash> HashTables;
		typedef typename BucketNode::HashTables<K, pair<const K, V>, KeyofValMap, Hash>::Iterator iterator;
		typedef typename BucketNode::HashTables<K, pair<const K, V>, KeyofValMap, Hash>::ConstIterator const_iterator;
	private:
		HashTables _ht;
	public:

		V& operator[](const K& key)
		{
			auto it = _ht.Insert(make_pair(key, K()));
			return (it.first)->second;
		}

		iterator begin()
		{
			return _ht.Begin();
		}

		iterator end()
		{
			return _ht.End();
		}

		const_iterator begin() const
		{
			return _ht.Begin();
		}

		const_iterator end() const
		{
			return _ht.End();
		}

		pair<iterator,bool> insert(const pair<K,V>& kv)
		{
			return _ht.Insert(kv);
		}

		iterator erase(const K& key)
		{
			return _ht.Erase(key);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
	};
}

哈希表底层（拉链法）

#pragma once
#include 
using namespace std;
#include 

namespace BucketNode
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next = nullptr;

		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};

	template<class K, class T, class KeyOfT, class hash>
	class HashTables;

	template<class K, class T, class KeyOfT, class hash, class Ref, class Ptr>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K,T,KeyOfT,hash, Ref, Ptr> Self;
		typedef HashTables<K, T, KeyOfT, hash> pht;
		const pht* _pht;
		Node* _node;

		HTIterator(Node* node,const pht* ht)
			:_node(node)
			,_pht(ht)
		{}

		Self& operator++() 
		{
			hash hs;
			KeyOfT kot;
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				//由于需要访问_pht的私有成员，所以迭代器设置为哈希表的友元类
				size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
				hashi++;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])
					{
						break;
					}
					hashi++;
				}
				if (hashi == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[hashi];
				}
			}
			return *this;
		}

		Ref operator*() const
		{
			return _node->_data;
		}

		Ptr operator->() const
		{
			return &_node->_data;
		}

		bool operator!=(const Self& x) const
		{
			return _node != x._node;
		}

		bool operator==(const Self& x) const
		{
			return _node == x._node;
		}

	};

	template<class K,class T, class KeyOfT,class hash>
	class HashTables
	{
	public:
		template<class K, class T, class KeyOfT, class hash,class Ref,class Ptr>
		friend struct HTIterator;
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, KeyOfT, hash, T&, T*> Iterator;
		typedef HTIterator<K, T, KeyOfT, hash,const T&,const T*> ConstIterator;
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	public:
		Iterator Begin()
		{
			if (_n == 0)
				return End();
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
					return Iterator(_tables[i],this);
			}
			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr,this);
		}

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
					return ConstIterator(_tables[i], this);
			}
			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		HashTables()
		{
			_tables.resize(10);
		}

		Iterator Find(const K& key)
		{
			hash hs;
			KeyOfT kot;
			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];;
			while (cur)
			{
				if (kot(cur->_data) == key)
					return Iterator(cur,this);
				cur = cur->_next;
			}
			return End();
		}

		pair<Iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			hash hs;
			if (Find(kot(data)) != End())
				return {Iterator(nullptr,this),false};

			if (_n / _tables.size() == 1)
			{
				vector<Node*> newtables(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						//把旧的数据插入到扩容后的表中
						size_t newidx = hs(kot(cur->_data)) % newtables.size();
						cur->_next = newtables[newidx];
						newtables[newidx] = cur;
						//继续遍历旧表的下一个元素
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}

			//直接进行头插到对应位置
			size_t hashi = hs(kot(data)) % _tables.size();
			Node* newNode = new Node(data);
			newNode->_next = _tables[hashi];
			_tables[hashi] = newNode;
			_n++;
			return {Iterator(_tables[hashi],this),true};
		}

		Iterator Erase(const K& key)
		{
			KeyOfT kot;
			hash hs;
			if (_n == 0)
			{
				cout << "No element" << endl;
				return Iterator(nullptr,this);
			}

			size_t hashi = hs(key) % _tables.size();
			Node* cur = _tables[hashi];;
			Node* pre = nullptr;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (pre == nullptr)
					{
						_tables[hashi] = cur->_next;
						delete cur;
						return Iterator(_tables[hashi], this);
					}
					else
					{
						pre->_next = cur->_next;
						delete cur;
						return Iterator(pre->_next, this);
					}
				}
				pre = cur;
				cur = cur->_next;
			}
			return Iterator(nullptr, this);
		}
	};
}

相关阅读:
Linux 特殊指令（有部分指令可能是安卓的）
WMCTF2022 WEB
【Vue】Element开发笔记
【Java】Collection接口&迭代器
计算机网络原理谢希仁（第8版）第三章习题答案
详解 Sqllogictest
CentOS7安装Hadoop集群完整步骤（超级详细，亲测完美）
免费的 ChatGPT 浏览器插件工具推荐 | 亲测有效
【Scan Kit】集成扫码服务时Android Studio总是报错OOM如何解决？
Java多线程_定时器和单例模式

原文地址：https://blog.csdn.net/anjibgdexuexi/article/details/141287744

哈希表及其封装

文章目录

哈希概念

哈希冲突

常用哈希函数

1. 直接定址法（常用）

2.除留余数法（常用）

解决哈希冲突

闭散列（开放定址法）

线性探测

代码实现：

开散列（拉链法）

代码实现：

总结

哈希表封装

迭代器

operator++()

const迭代器

operator[]（unordered_map）

总代码

unordered_set

unordered_map

哈希表底层（拉链法）