【C++/STL】：哈希表的改造 -- 封装unordered系列

点击跳转至文章： 【C++/STL】：哈希 – 线性探测&哈希桶

前言

与map/set的封装类似，unordered系列的底层本质上也是复用，通过对哈希表的改造，再分别套上一层 unordered_map 和 unordered_set 的 “壳子”，以达到 “一表二用” 的目的。

各个结构的改造不再详细说明，细节可参考文章：map和set的封装

unordered系列的底层哈希表是用哈希桶结构实现的。

一，哈希表的改造

1. 哈希表的基本框架

(1) K：关键码类型；

(2) V:：不同容器V的类型不同，如果unordered_map，V代表一个键值对，如果是unordered_set，V 为 K；

(3) KeyOfValue：因为V的类型不同，通过value取key的方式就不同，详细见unordered_map/set的实现；

(4) Hash：哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模。

template <class K, class T, class KeyOfT,class Hash = HashFunc<K>>
class HashBucket
{
	//友元
	template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >
	friend struct HTIterator;

	typedef BucketNode<T> Node;
public:
	typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
	typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

	//其他核心操作……
	
private:
	vector<Node*> _tables;  //指针数组
	size_t _n = 0;          //表中数据的个数
};
}

2. 对哈希桶节点结构的改造

template <class T>
struct BucketNode
{
	BucketNode<T>* _next;
	T _data;

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

3. 哈希表的迭代器

3.1 迭代器类

(1) 这里的迭代器需要：构造节点指针和哈希表对象指针。

(2) 这里的迭代器类需要用到哈希表类的结构，相互依存，要用前置声明。

//前置声明
template <class K, class T, class KeyOfT, class Hash >
class HashBucket;

template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >
struct HTIterator
{
	//需要节点指针，哈希表对象指针
	typedef BucketNode<T> Node;
	typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	 const HashBucket<K, T, KeyOfT, Hash>* _pht;
	Node* _node;

	HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht)
		:_node(node)
		,_pht(pht)
	{}

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

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

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

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			KeyOfT kot;
			Hash hs;
			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; //End()
			else
				_node = _pht->_tables[hashi];
		}
		return *this;
	}
};

3.2 Begin() 和 End()

Iterator Begin()
{
	if (_n == 0)
		return End();

	for (size_t i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		if (cur)
			return Iterator(cur, 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++)
	{
		Node* cur = _tables[i];
		if (cur)
			return ConstIterator(cur, this);
	}

	return End();
}

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

四，哈希表相关接口的改造

4.1 Find 函数的改造

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);
		else
			cur = cur->_next;
	}
	return End();
}

4.2 Insert 函数的改造

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

	Iterator it = Find(kot(data));
	if (it != End())
		return make_pair(it, false);
		
	//扩容
	if (_n == _tables.size())
	{
		vector<Node*> newTables;
		newTables.resize(_tables.size() * 2, nullptr);

		//把旧表的节点挪到新表
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				size_t hashi = hs(kot(cur->_data)) % newTables.size();
				Node* newnode = new Node(cur->_data);

				//头插
				newnode->_next = newTables[hashi];
				newTables[hashi] = newnode;

				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 make_pair(Iterator(newnode, this), true);
}

五，哈希表改造的完整代码

HashTable.h

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

//对string类型的特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t n = 0;
		for (auto ch : s)
		{
			n += ch;
			n *= 31;
		}
		return n;
	}
};

template <class T>
struct BucketNode
{
	BucketNode<T>* _next;
	T _data;

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

//前置声明
template <class K, class T, class KeyOfT, class Hash >
class HashBucket;

template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >
struct HTIterator
{
	//需要节点指针，哈希表对象指针
	typedef BucketNode<T> Node;
	//typedef HTIterator<K, T, KeyOfT, Hash> Self;
	typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

	 const HashBucket<K, T, KeyOfT, Hash>* _pht;
	Node* _node;

	HTIterator(Node* node, const HashBucket<K, T, KeyOfT, Hash>* pht)
		:_node(node)
		,_pht(pht)
	{}

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

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

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

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			KeyOfT kot;
			Hash hs;
			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; //End()
			else
				_node = _pht->_tables[hashi];
		}
		return *this;
	}
};

template <class K, class T, class KeyOfT,class Hash = HashFunc<K>>
class HashBucket
{
	//友元
	template <class K, class T, class Ref, class Ptr,class KeyOfT, class Hash >
	friend struct HTIterator;

	typedef BucketNode<T> Node;
public:
	typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
	typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;


	Iterator Begin()
	{
		if (_n == 0)
			return End();

		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			if (cur)
				return Iterator(cur, 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++)
		{
			Node* cur = _tables[i];
			if (cur)
				return ConstIterator(cur, this);
		}

		return End();
	}

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

	HashBucket()
	{
		_tables.resize(10, nullptr);
	}

	//依次把每个桶释放
	~HashBucket()
	{
		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;
		}
	}

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

		Iterator it = Find(kot(data));
		if (it != End())
			return make_pair(it, false);
			

		//扩容
		if (_n == _tables.size())
		{
			vector<Node*> newTables;
			newTables.resize(_tables.size() * 2, nullptr);

			//把旧表的节点挪到新表
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					size_t hashi = hs(kot(cur->_data)) % newTables.size();
					Node* newnode = new Node(cur->_data);

					//头插
					newnode->_next = newTables[hashi];
					newTables[hashi] = newnode;

					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 make_pair(Iterator(newnode, this), true);
	}

	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);
			else
				cur = cur->_next;
		}
		return End();
	}

	bool Erase(const T& data)
	{
		Hash hs;
		KeyOfT kot;
		size_t hashi = hs(kot(data)) % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;

		while (cur)
		{
			if (cur->_data == data)
			{
				//第一个节点
				if (prev == nullptr)
				{
					_tables[hashi] = nullptr;
				}
				else
				{
					//在节点中间
					prev->_next = cur->_next;
				}
				delete cur;
				_n--;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}
private:
	vector<Node*> _tables;  //指针数组
	size_t _n = 0;          //表中数据的个数
};

六，unordered_set 的封装实现

unordered_set 的底层为哈希表，因此只需在unordered_set 内部封装哈希表，即可将该容器实现出来。

unordered_set .h

#include "HashTable.h"

namespace bit
{
	template <class K, class Hash = HashFunc<K>>
	class unordered_set
	{
		struct SetOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename HashBucket<K, const K, SetOfT, Hash>::Iterator iterator;
		typedef typename HashBucket<K, const K, SetOfT, Hash>::ConstIterator const_iterator;

		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);
		}

	private:
		bit::HashBucket<K,const K, SetOfT, Hash> ht;

	};

	void Print(const unordered_set<int>& s)
	{
		unordered_set<int>::const_iterator it = s.begin();
		while (it != s.end())
		{
			// *it += 1;
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void Test_set()
	{
		//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		int a[] = { 16,3,7,11,9,26,18,14,15 };
		unordered_set<int> s;

		for (auto e : a)
			s.insert(e);

		for (auto e : s)
			cout << e << " ";

		cout << endl;

		Print(s);
	}
}

七，unordered_map 的封装实现

unordered_map 的底层结构就是哈希表，因此在map中直接封装一个哈希表，然后将其接口包装下即可。

unordered_map.h

#include "HashTable.h"

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

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


		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);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = ht.Insert(make_pair(key, V()));

			return ret.first->second;
		}

	private:
		bit::HashBucket<K, pair<const K, V>, MapOfT, Hash> ht;
	};

	void Test_map()
	{
		unordered_map<string, string> dict;

		dict.insert({ "left","左边" });
		dict.insert({ "right","右边" });
		dict.insert({ "insert","插入" });

		dict["left"] = "剩余，左边";

		bit::unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			//it->first += 'x'; //err
			it->second += 'y'; //ok

			cout << it->first << ":" << it->second << endl;
			++it;
		}

		cout << endl;
	}
}