unordered_set 和unordered_map的模拟实现（使用开散列）

实现步骤：（与红黑树实现set相似）

1、实现哈希表

2、封装unordered_map和unordered_set 解决KeyOfT

3、iterator

4、const_iterator

5、修改key的问题

6、operator[ ]

开散列的实现

#pragma once
#include<iostream>
#include<vector>
using namespace std;
	//  1、实现哈希表
	//  2、封装unordered_map和unordered_set  解决KeyOfT
	//  3、iterator
	//  4、const_iterator
	//  5、修改key的问题
	//  6、operator[]


template<class K>
struct HashFunc  //默认int
{
	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 *= 31;
			hash += e;
		}

		return hash;
	}
};
namespace HashBucket
{
	


	template<class K, class T>
	struct HashNode
	{
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
		T _data;
		HashNode<K, T>* _next;
	};

	//解决相互依赖，前置声明
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

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

		HashNode<K, T>* _node;
		const HashTable<K, T, KeyOfT , Hash>* _pHashTable;//因为要往下遍历所以要有类对象的指针this，来使用vector

		HashTableIterator(Node* node ,const HashTable<K, T, KeyOfT ,Hash>* Phst )
			:_node(node)
			, _pHashTable(Phst)
		{}

		Self& operator++()
		{
			if (_node->_next)//此桶不为空
			{
				_node = _node->_next;
			}
			else//此桶为空 ,找下一个不为空的桶
			{
				//算出哈希值
				KeyOfT Kot;
				Hash hs;
				size_t hashi = hs(Kot(_node->_data)) % _pHashTable->_table.size();//_table 是HashTable的私有，用友元
				++hashi;
				while (hashi< _pHashTable->_table.size())
				{
					if (_pHashTable->_table[hashi])
					{
						break;
					}
					++hashi;
				}
														//容易忘
				if (hashi == _pHashTable->_table.size())//加到最后也没有找到返回end()
				{
					_node = nullptr;
				}
				else
				{
					_node = _pHashTable->_table[hashi];
				}
			}

			return *this;
		}

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

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

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

		
	};

	template<class K, class T,  class KeyOfT ,class Hash >
	class HashTable
	{
		typedef HashNode<K, T> Node;
		//友元 ，类模板的友元要带参数template<class ...>
		template< class K, class T, class Ptr, class Ref,class KeyOfT, class Hash>
		friend struct HashTableIterator;

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

		HashTable()
		{
			_table.resize(10, nullptr);
		}

		~HashTable()
		{
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}

		Iterator Begin()
		{				//容易忘
			if (_n == 0)//没有值直接返回空
			{
				return End();
			}
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[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 < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}
			return End();
		}

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

		pair<Iterator ,bool> Insert(const T& data)
		{
			Hash hs;
			KeyOfT Kot;
			Iterator it = Find(Kot(data));
			if ( it !=  End())
			{
				return make_pair(it ,false);
			}
			size_t hashi = hs(Kot(data)) % _table.size();
			//负载因子等于1就扩容，这里的扩容与散列表（开放地址）扩容不同
			//如果复用Insert ，这里的结点都需要重新new 和delete，效率太低，代价太大
			//使用挪动节点的方法
			if (_n == _table.size())
			{
				/*HashTable<K, V> newhs;//效率低
				newhs._table.resize(2*_table.size(),nullptr);
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while(cur)
					{
						newhs.Insert(cur->_kv);
						cur = cur->_next;
					}
				}
				_table.swap(newhs._table);*/

				vector<Node*> newtable(_table.size() * 2, nullptr);
				for (size_t i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];
					while (cur)
					{	//存储旧表的下一个，便于循环
						Node* curnext = cur->_next;
						//在新表中的映射
						Hash hs;
						KeyOfT Kot;
						size_t hashi = hs(Kot(cur->_data)) % newtable.size();

						Node* newnext = newtable[hashi];
						newtable[hashi] = cur;
						cur->_next = newnext;

						cur = curnext;
					}
					_table[i] = nullptr;
				}
				_table.swap(newtable);
			}

		
			Node* newnode = new Node(data);
			Node* next = _table[hashi];
			_table[hashi] = newnode;//进行头插，不用找尾了
			newnode->_next = next;
			++_n;

			return make_pair(Iterator(newnode,this ), true);
		}

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

		bool Erase(const K& key)
		{
			Hash hs;
			KeyOfT Kot;
			size_t hashi = hs(key) % _table.size();
			Node* prev = nullptr;//用于判断删除节点位于链表第一个位置，还是中间位置（最后位置与中间位置处理方法一致）
			Node* cur = _table[hashi];
			while (cur)
			{
				if (Kot(cur->_data) == key)
				{
					if (prev == nullptr)
					{
						_table[hashi] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;//容易忘
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

	private:
		vector<HashNode<K, T>*> _table;//指针数组
		size_t _n = 0;
	};
}

unordered_set的实现

#pragma once
#include"MyHash.h"

namespace BMH
{
	
	template<class K , class Hash = HashFunc<K>>
	class unordered_set
	{

		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashBucket::HashTable< K,const K, SetKeyOfT, Hash>::Iterator iterator;//将第二个模板参数传成const,使set的key不能修改
		typedef typename HashBucket::HashTable< K,const K, SetKeyOfT, Hash>::ConstIterator const_iterator;//将第二个模板参数传成const

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

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

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

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

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

		iterator find(const K& key)
		{
			return _hst.Find(key);
		}
		bool erase(const K& key)
		{
			return _hst.Erase(key);
		}

	private:
		HashBucket::HashTable< K,const K, SetKeyOfT, Hash>  _hst; // 将第二个模板参数传成const, 使set的key不能修改
	};

	struct Date
	{
		int _year;
		int _month;
		int _day;

		bool operator==(const Date& d) const
		{
			return _year == d._year
				&& _month == d._month
				&& _day == d._day;
		}
	};

	struct HashDate
	{
		size_t operator()(const Date& date)
		{
			return (((date._year * 31) + date._month) * 31) + date._day;
		}
	};

	void Print(const BMH::unordered_set<int>& s)
	{
		BMH::unordered_set<int>::const_iterator it = s.begin();
		while (it != s.end())
		{
			//*it += 2;  set不能修改
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
	void test_set()
	{
		BMH::unordered_set<int> s;
		int a[] = {4,2,6,1,3,5,15,7,16,14 ,3,3,15,15};
		for (auto e : a)
		{
			s.insert(e);
		}
		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;


		BMH::unordered_set<int>::iterator it = s.begin();
		//*it += 10;
		while (it != s.end())
		{
			cout << *it << " ";
			//*it += 10;//set应该不能改key
			++it;
		}
		cout << endl;
		Print(s);

	/*	for (auto e : a)
		{
			s.erase(e);
		}

		for (auto e : s)
		{
			cout << e << " ";
		}
		cout << endl;*/

		BMH::unordered_set<Date, HashDate> sdate;
		sdate.insert({2024,11,22});
		sdate.insert({2024,11,23});

	}
}

unordered_map的实现

#pragma once
#include"MyHash.h"

namespace BMH
{
	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::HashTable<  K, pair<const K, V>, MapKeyOfT , Hash>::Iterator iterator;// 将pair的第1个模板参数传成const, 使pair的key不能修改能修改
		typedef typename HashBucket::HashTable< K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;// 将pair的第1个模板参数传成const, 使pair的key不能修改

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

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

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

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

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

		V& operator[](const K& key)
		{
			pair<iterator, bool > ret = _hst.Insert(make_pair(key,V()));
			return ret.first->second;
		}

		iterator find(const K& key)
		{
			return _hst.Find(key);
		}
		bool erase(const K& key)
		{
			return _hst.Erase(key);
		}


	private:
		HashBucket::HashTable< K, pair<const K ,V> , MapKeyOfT , Hash>  _hst;// 将pair的第1个模板参数传成const, 使pair的key不能修改
	};

	void test_map()
	{
		BMH::unordered_map<string, string> dict;
		dict.insert({ "sort", "排序" });
		dict.insert({ "left", "左边" });
		dict.insert({ "right", "右边" });

		dict["left"] = "左边，剩余";
		dict["insert"] = "插入";
		dict["string"];

		BMH::unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			// 不能修改first，可以修改second
			//it->first += 'x';
			it->second += 'x';

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

			dict.erase("sort");
			dict.erase("left");
			dict.erase("insert");
			dict.erase("right");
			dict.erase("string");
			BMH::unordered_map<string, string>::iterator it2 = dict.begin();
			while (it2 != dict.end())
			{
				cout << it2->first << ":" << it2->second << endl;
				++it2;
			}
	}
}

这个博客如果对你有帮助，给博主一个免费的点赞就是最大的帮助❤

欢迎各位点赞，收藏和关注哦❤

如果有疑问或有不同见解，欢迎在评论区留言哦❤

后续我会一直分享双一流211西北大学软件（C，数据结构，C++，Linux，MySQL）的学习干货以及重要代码的分享