【C++】哈希表的封装——同时实现unordered_map和unordered_set

在学习红黑树之后，我们使用一颗红黑树同时封装map和set，加深了对红黑树和map，set的理解。现在学习了哈希表这一高效的数据结构，与之对应的也有一套unordered系列的map和set，所以现在也对哈希表进行封装，同时实现unordered_map，和unordered_set。由于之前已经实现过红黑树的封装，大逻辑是差不多的，所以推荐先了解红黑树的封装后再观看本文效果更佳。——红黑树封装map和set。当然了，对哈希表有一定了解也是必不可少的。——哈希表的实现

经历过红黑树封装的洗礼，对本次哈希表的封装已近不足为惧，只不过会有更多的细节需要注意；所以本篇采用总分的方式对哈希表的封装进行讲解。

框架

整体框架

使用同一张哈希表封装u_map和u_set，底层调用哈希表时就需要控制两者的参数相同，于是就有以下对参数的控制。

容器模板参数控制：
u_map和u_set是KV，K模型，且底层是哈希表，所以需要传递一个哈希函数(使用缺省值)，这样一来，使用时u_map和u_set的传参就和map和set一致。

哈希表模板参数控制：
u_map是KV模型，其数据存储在键值对pair中，u_set为K模型,数据类型为K。也正是由于两者储存数据的方式不一样，就需要向下提供一个仿函数获取K；于是，哈希表的模板参数就来到了四个。

unordered_map

	template<class K, class V,class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K,V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename HashBucket<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
		typedef typename HashBucket<K, pair<const K, V>, MapKeyOfT, Hash>::Const_Iterator const_iterator;

	private:
		HashBucket<K, pair<const K, V>, MapKeyOfT, Hash> _hb;
	};

unordered_set

	template<class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		//库里的方案
		typedef typename HashBucket<K, K, SetKeyOfT, Hash>::Const_Iterator iterator;
		typedef typename HashBucket<K, K, SetKeyOfT, Hash>::Const_Iterator const_iterator;
	private:
		HashBucket<K, K, SetKeyOfT, Hash> _hb;
	};

• 为防止和库里的产生冲突，记得封在自己的命名空间里。

迭代器框架

既然u_map和u-set的底层是哈希表，那么毫无疑问他们的迭代器也是由哈希表的迭代器封装而来。但是迭代器又分普通和const版，哈希表的迭代器也采用同一份迭代器代码同时实现普通，const迭代器，这就又需要对迭代器的模板参数进行控制，具体请看——list迭代器的实现，再加上哈希表的参数，此时的模板参数就会很多。

对着上图看会比较好理解

template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
	
	typedef HashBucket<K, T, KeyOfT, Hash> HB;

	Node* _node;
    const HB* _phb;
};

哈希表的完善

u_map和u_set的底层是哈希表，所以需要完善哈希表的默认成员函数。

拷贝构造

采用现代写法，先开好空间(是size不是capacity)，再调用哈希表的插入函数。

	HashBucket(const HashBucket& hb)
		:_bucket()
		,_num(0)
	{
		_bucket.resize(hb._bucket.size());
		auto it = hb.Begin();
		while (it != hb.End())
		{
			Insert(*it);
			it++;
		}
	}

赋值重载

采用现代写法：利用形参的传值传参时会调用拷贝构造函数构造一个临时对象，之后与该临时对象交换表_bucket和记录个数的_num。

	HashBucket& operator=(HashBucket hb)
	{
		_bucket.swap(hb._bucket);
		swap(_num, hb._num);
		return *this;
	}

析构函数

哈希表的底层是vector，理论上是不需要自己实现析构函数的，但是别忘了vector中挂着的一串串单链表可不归vector管，所以需要自己实现析构函数；总之还是那句话，只要自己实现了构造函数，就需要实现对应的析构函数释放资源。

需要释放的是每个桶里面的单链表，所以只需要遍历哈希表，将存在的单链表节点释放。

	~HashBucket()
	{
		for (int i = 0; i < _num; i++)
		{
			if (_bucket[i])
			{
				Node* cur = _bucket[i];
				while (cur)
				{
					Node* Next = cur->_next;
					delete cur;
					cur = Next;
				}
			}
			_bucket[i] = nullptr;
		}
	}

迭代器的增加

注意：哈希表的迭代器为前向迭代器只支持++，不支持 - -。

完善好默认成员函数后，接着实现哈希表的迭代器；对于哈希表迭代器的结构，先回顾一下哈希表的结构：
![哈希表
从学习迭代器以来，迭代器成员一般只有一个节点即可，有了这个节点就能去访问容器，但是现在哈希表的元素都在桶里面，需要节点去遍历，但是访问完当前桶如何访问下一个桶呢？这就需要再新增一个成员，该成员可访问哈希表，所以该成员为哈希表指针。

template<class K, class T,class Ref,class Ptr, class KeyOfT, class Hash>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
	
	typedef HashBucket<K, T, KeyOfT, Hash> HB;

	Node* _node;
    const HB* _phb;
};

• 注意哈希表指针成员需要加const修饰，因为当访问的是const对象，普通的哈希表指针就调不动了。

构造函数

用传进来的节点和哈希表初始化迭代器。

	HashIterator(Node* node, const HB* phb)
		:_node(node)
		, _phb(phb)
	{}

迭代器常规操作

对于下面的常规操作，在list迭代器的实现一文中已详细讲解。

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

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

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

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

遍历

由于哈希表的迭代器为前向迭代器，所以只需要实现前后置++即可

前置++

对于前置++，首先要确认当前桶还有没有元素，有则访问下一个；否则，需要访问下一个有效的桶：访问下一个桶，需要使用哈希函数先计算出当前在哪个桶，接着通过循环借助哈希表指针访问下一个桶，直到访问到有元素的桶。

• 需要注意的是循环结束是因为找到有效的桶break出来的还是因为访问完哈希表而跳出循环的，可以借助判断hashi == _phb->_bucket.size()，如果是访问完哈希表而退出循环的还需将节点设为空。

	Self& operator++()
	{
		//桶里有元素，先访问
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else//访问下一个桶
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(kot(_node->_data)) % _phb->_bucket.size();//算出现在的位置
			hashi++;//访问下一个桶
			//找下一个存在的桶
			while (hashi < _phb->_bucket.size())//size是表的大小，不是个数
			{
				if (_phb->_bucket[hashi])
				{
					_node = _phb->_bucket[hashi];
					break;
				}
				hashi++;
			}

			if (hashi == _phb->_bucket.size())
			{
				_node = nullptr;
			}
		}
		return *this;
	}

后置++

后置++，即返回++之前的值，直接使用ret构造一个++之前的值，最后返回ret即可；不过此时就不能引用返回了。

//后置
	Self operator++(int)
	{
		Self ret(*this);//返回++之前的值
		
		//桶里有元素，先访问
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else//访问下一个桶
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(kot(_node->_data)) % _phb->_bucket.size();//算出现在的位置
			hashi++;//访问下一个桶
			//找下一个存在的桶
			while (hashi < _phb->_bucket.size())//size是表的大小，不是个数
			{
				if (_phb->_bucket[hashi])
				{
					_node = _phb->_bucket[hashi];
					break;
				}
				hashi++;
			}

			if (hashi == _phb->_bucket.size())
			{
				_node = nullptr;
			}
		}
		return ret;
	}

哈希表的封装

完善哈希表之后，就可以正式进入封装了，所谓封装，就是套壳

哈希表模板参数的控制

最主要的就是u_set是K，u_map是KV模型，哈希表中的T就是对应上层传来的数据类型，u_set为K，u_map为pair。于是乎底层的哈希表就能直到T就是数据类型，便能进行存储。

仿函数解决取K问题

取K问题就是因为u_map存储的是pair，其K值存储在pair中，所以需要在上层向哈希表传递一个可以获取K值的仿函数，对于u_set来说是多此一举，但是为u_map配套实现一下也无妨。

对Key的非法操作

解决上面两个问题之后，整个项目基本就能跑了；但是还有一些小毛病，如：无论是u_set还是u_map，其K值是不能被修改的，但是我们现在实现的u_set还是u_map并没有对此作限制，所以还需要完善一下。

对K值进行修改：

解决方案：

u_map

u_map的方法十分简单，直接对pair的K用const修饰

private:
		HashBucket<K, pair<const K,V>, MapKeyOfT, Hash> _hb;

u_set同样可以这样解决问题；不过库里并没有采用这种方法，而是使用了另一种方法

u_set

将u_set的迭代器统一使用哈希表的const迭代器实现

public:
		//库里的方案
		typedef typename HashBucket<K, K, SetKeyOfT, Hash>::Const_Iterator iterator;
		typedef typename HashBucket<K, K, SetKeyOfT, Hash>::Const_Iterator const_iterator;

这样又会导致类型转化的问题

对此，需要在迭代器类中增加一个参数为普通迭代器的构造函数。至于为何，请参考红黑树的封装——同时实现map和set一文，在解决set的这个问题时也遇到了这个问题，该文中详细讲解了原因。

	//指明为普通迭代器类型，解决普通迭代器转const的问题
	//不能使用T,Ptr,Ref，必须原原本本写出具体类型
	typedef HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
	HashIterator(const Iterator& it)
		:_node(it._node)
		,_phb(it._phb)
	{}

insert的调整

哈希表在现实insert时，其返回值简单的用了bool，而在u_set，u_map中insert的返回值则是一对pair。

pair<iterator,bool> insert ( const value_type& val );

于是对insert进行调整：整体逻辑没变，只是返回值变为pair<Iterator, bool>，bool用于判断是否插入成功，Iterator用来指向元素，若插入成功，Iterator则指向新插入的节点，插入失败则说明容器中已有该元素，此时Iterator指向已存在的元素。

• 注意：迭代器有两个成员，一个是节点node，一个是指向哈希表的指针；所以需要使用节点和哈希表构造迭代器。

	pair<Iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		Hash hs;

		Iterator ret = Find(kot(data));
		//去重
		if(ret!=End())
		{
			return make_pair(ret, false);//注意迭代器有两个成员
		}

		//检查是否需要扩容
		if (_num == _bucket.size())//负载因子为1；
		{
			//扩容，需要重新映射。
			vector<Node*> newbucket;
			//newbucket.resize(_bucket.size() * 2);//二倍增长
			newbucket.resize(GetNextPrime(_bucket.size()));//素数数组
			for (size_t i = 0; i < _bucket.size(); i++)
			{
				if (_bucket[i])//非空说明有数据
				{
					Node* cur = _bucket[i];
					Node* next = nullptr;
					
					size_t newhashi;
					while (cur)
					{
						next = cur->_next;//先记录旧表的下一个节点
						newhashi = hs(kot(cur->_data)) % newbucket.size();//计算在新表的位置
						cur->_next = newbucket[newhashi];//串联新表的下一节点
						newbucket[newhashi] = cur;//头插
						cur = next;//遍历旧表
					}
				}
			}
			_bucket.swap(newbucket);//交换新旧两表
		}
		//插入过程
		size_t hashi = hs(kot(data)) % _bucket.size();
		Node* newnode = new Node(data);
		//头插
		newnode->_next = _bucket[hashi];
		_bucket[hashi] = newnode;
		++_num;
		return make_pair(Iterator(newnode,this), true);//注意迭代器有两个成员
	}

unordered_map的[]运算符重载

对于operator[]，只有KV模型的map系列才有，set系列没有该重载。[]重载会返回K值对应的V，且该返回是引用返回。
因此operator[]的使用方式有两种；

1. 插入：当容器中没有的输入的K值，则会插入该K值。
2. 修改：当容器中存在输入的K值，则会返回对应的V的引用。

所以operator[]的实现是借助了insert的

		V& operator[](const K& key)
		{
			pair<iterator, bool> it = _hb.Insert(make_pair(key, V()));
			return it.first->second;//具体请看->重载
		}

• 关于返回V&为何是返回it.first->second：it 为接受的是insert返回的pair对，其first为指向元素的迭代器，->调用了迭代器的operator->，此时返回的是存储KV的pair，此时的second为V

以上就是哈希表封装需要注意的问题，全部代码等gitee整理好就发