unordered_map和unordered_set的模拟实现

Posted on by hackdl

一、链地址法实现哈希表

想要模拟实现unordered_map和unordered_set，首先必须得先实现一个哈希表作为它们的底层结构，我们尝试用链地址法来实现哈希表。

1、哈希节点的结构

template
struct HashNode//哈希表节点
{
	HashNode* _next;//指向下一个节点
	pair _kv;//键值对
	HashNode(const pair& kv)//构造函数
		:_next(nullptr)
		,_kv(kv)
	{}
};

2、哈希函数

如果key是能够直接转化为整形的类型，就直接使用，如果不能直接转化为整形（比如string类型），就需要用哈希函数来进行处理，下面对string类型采用了BKDR的方法处理。

//哈希函数
template
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template//对于Key为字符串类型的数据进行特化处理
struct HashFunc
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

3、哈希表的基础结构

template>
class HashTable//哈希表
{
typedef HashNode Node;
public:
	//各种成员方法
private:
	vector _tables;//表
	size_t _n = 0;//计数
};

我们希望哈希表能够呈现下面这个结构

4、构造函数

HashTable()//构造函数
{
	_tables.resize(10);//一开始先开10个大小的空间
}

5、析构函数

~HashTable()//析构函数
{
	for (size_t i = 0;i next;
			delete cur;//释放
			cur = next;
		}
		_tables[i] = nullptr;
	}
  _n=0;
}

6、insert函数

bool Insert(const pair& kv)//插入
{
	Compare com;
	if (find(kv.first))//如果find函数返回值不为空，就代表kv已经存在了
	{
		return false;//返回false
	}

	if (_n == _tables.size())//负载因子到1就扩容
	{
		vector newTables;//创建新的哈希表
		newTa服务器托管网bles.resize(_tables.size() * 2);//表容量扩大为两倍
		for (size_t i = 0;i _next;//记录当前节点的下一个节点
				//头插
				size_t hashi = com(cur->_kv.first) % newTables.size();
				cur->_next = newTables[hashi];
				newTables[hashi] = cur;
				cur = next;
			}
			_tables[i] = nullptr;//置空
		}
		swap(newTables, _tables);//交换新旧哈希表
	}
  
	size_t hashi = com(kv.first) % _tables.size();//先算出这个新节点应该在哈希表什么位置
	Node* newNode = new Node(kv);
	//头插
	newNode->_next = _tables[hashi];
	_tables[hashi] = newNode;
	++_n;
	return true;
}

7、find函数

Node* find(const K& key)//查找
{
	Compare com;
	size_t hashi = com(key) % _tables.size();
	Node* cur = _tables[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return nullptr;
}

8、erase函数

bool erase(const K& key)//删除
{
	Compare com;
	size_t hashi = com(key) % _tables.size();
	Node* cur = _tables[hashi];
	Node* prev = nullptr;
	while (cur)
	{
		if (cur->_kv.first == key)//找到了
		{
			if (prev == nullptr)//如果要删除的是第一个节点
			{
				_tables[hashi] = cur->_next;
			}
			else//如果要删除的不是第一个节点
			{
				prev->_next = cur->_next;
			}
			delete cur;
			--_n;
			return true;
		}
		prev = cur;
		cur = cur->_next;
	}
	//没找到
	return false;
}

9、完整代码

using namespace std;

template
struct HashNode//哈希表节点
{
	HashNode* _next;//指向下一个节点
	pair _kv;//键值对
	HashNode(const pair& kv)//构造函数
		:_next(nullptr)
		,_kv(kv)
	{}
};

//哈希函数
template
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template//对于Key为字符串类型的数据进行特化处理
struct HashFunc
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}
		return hash;
	}
};

template>
class HashTable//哈希表
{
	typedef HashNode Node;
public:
	HashTable()//构造函数
	{
		_tables.resize(10,nullptr);//一开始先开10个大小的空间
	}
	~HashTable()//析构函数
	{
		for (size_t i = 0;i _next;
				delete cur;//释放
				cur = next;
			}
			_tables[i] = nullptr;
		}
		_n = 0;
	}
	bool insert(const pair& kv)//插入
	{
		Compare com;
		if (find(kv.first))//如果find函数返回值不为空，就代表kv已经存在了
		{
			return false;//返回false
		}

		if (_n == _tables.size())//负载因子到1就扩容
		{
			vector newTables;//创建新的哈希表
			newTables.resize(_tables.size() * 2);//表容量扩大为两倍
			for (size_t i = 0;i _next;//记录当前节点的下一个节点
					//头插
					size_t hashi = com(cur->_kv.first) % newTables.size();
					cur->_next = newTables[hashi];
					newTables[hashi] = cur;
					cur = next;
				}
				_tables[i] = nullptr;//置空
			}
			swap(newTables, _tables);//交换新旧哈希表
			cout _next = _tables[hashi];
		_tables[hashi] = newNode;
		++_n;
		return true;
	}
	Node* find(const K& key)//查找
	{
		Compare com;
		size_t hashi = com(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr;
	}
	bool erase(const K& key)//删除
	{
		Compare com;
		size_t hashi = com(key) % _tables.size();
		Node* cur = _tables[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (cur->_kv.first == key)//找到了
			{
				if (prev == nullptr)//如果要删除的是第一个节点
				{
					_tables[hashi] = cur->_next;
				}
				else//如果要删除的不是第一个节点
				{
					prev->_next = cur->_next;
				}
				delete cur;
				--_n;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		//没找到
		return false;
	}
	size_t size()const
	{
		return _n;
	}
private:
	vector _tables;//表
	size_t _n = 0;//计数
};

二、哈希表封装实现unordered_map和unordered_map

当我们实现了哈希表之后，需要对哈希表进行修改与封装从而实现unordered_map和unordered_map。

1、unordered_map和unordered_set的基本结构

template
class MyUnordered_Set
{
public:
private:
	HashTable _HashTable;
};
template
class MyUnordered_Map
{
public:
private:
	HashTable> _HashTable;
};

2、先对哈希表节点进行修改

3、实现KeyOfT仿函数

因为HashTable模板参数的第二个类型可能是key，能直接使用，也可能是pair，不能直接使用，此时我们需要实现KeyOfT仿函数从中提取key。

template
class MyUnordered_Set
{
public:
	struct KeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	HashTable _ht;
};
template
class MyUnordered_Map
{
public:
	struct KeyOfT
	{
		const K& operator()(const pair& kv)
		{
			return kv.first;
		}
	};
private:
	HashTable, KeyOfT> _ht;
};

此时相应的也需要对哈希表进行修改，在哈希表的成员方法中，只要需要从T中取key的时候，都需要使用KeyOfT仿函数，下面列举部分：

4、实现哈希表迭代

我们先实现哈希表的迭代器，之后在对哈希表的迭代器进行封装，实现unordered_map和unordered_set的迭代器。

  1. 首先要确定迭代器结构体内要定义那些成员变量
  • 指向节点的指针
  • 指向哈希表的指针
  • 标记当前节点所在的哈希桶的下标
  1. 接下来要实现++
  • 如果当前节点_node的下一个节点不为空，则代表当前哈希桶还没遍历完，直接让_node等于它的下一个节点即可。
  • 如果_node的下一个节点为空，则代表当前哈希桶已经遍历完了，此时我们需要先让_hashi++，走到下一个哈希桶，如果下一个哈希桶也为空，则继续_hashi++，以此类推，直到找到不为空的哈希桶，让_node指向哈希桶的第一个节点即可。
  • 如果找完了整个哈希表，都没有找到不为空的桶，那就代表哈希表已经遍历完了，此时让_node等于nullptr表示最后一个节点的下一个位置（即end()）
  1. 最后把其它方法定义出来即可，参考下面的代码。
template
class HashTable;//因为迭代器需要使用哈希表，而哈希表的定义在迭代器的下面
//所以在此处声明

template>
struct HTIterator
{
	typedef HTIterator Self;
	typedef HashNode Node;

	Node* _node;//指向节点
	HashTable* _pht;//指向哈希表
	size_t _hashi;//记录当前在哪个哈希桶

	HTIterator(Node* node, HashTable* pht, size_t hashi)
		:_node(node)
		, _pht(pht)
		, _hashi(hashi)
	{}

	Self operator++()
	{
		if (_node->_next)//如果还有下一个节点
		{
			_node = _node->_next;
		}
		else//没有下一个节点了，当前桶已遍历完
		{
			++_hashi;
			//寻找下一个不为空的哈希桶
			while (_hashi _tables.size())
			{
				if (_pht->_tables[_hashi])//找到了不为空的桶
				{
					_node = _pht->_tables[_hashi];
					break;
				}
				++_hashi;
			}
			if (_hashi == _pht->_tables.size())//遍历完整个哈希表都没有不为空的桶了
			{
				_node = nullptr;//此为end
			}
			return *this;
		}
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s服务器托管网)
	{
		return _node == s._node;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
};

5、在哈希表内定义迭代器并实现begin()等函数

因为在迭代器中，需要访问哈希表的成员变量，而哈希表的成员变量是被封装起来的，此时需用到友元。

template>
class HashTable//哈希表
{
	typedef HashNode Node;
  
	template
	friend struct HTIterator;//声明友元
public:
//迭代器
	typedef HTIterator iterator;
	typedef HTIterator const_iterator;
	iterator begin()
	{
		for (int i = 0;i

6、处理迭代器的一个问题

7、改造哈希表里的find函数

既然find函数改了，我们在insert函数中使用了find函数，也需要进行相应的修改。

8、实现unordered_map和unordered_set里的各项功能

下面先不实现insert，接下来会实现

template
class MyUnordered_Set
{
public:
	struct KeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	//因为unordered_set的T是完全禁止修改的。
	//所以不管是iterator还是const_iterator都要用哈希表的const_iterator来实现。
	typedef typename HashTable::const_iterator iterator;
	typedef typename HashTable::const_iterator const_iterator;
	//因为iterator和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();
	}
	bool erase(const K& key)
	{
		return _ht.erase(key);
	}
	iterator find(const K& key)
	{
		return _ht.find(key);
	}
private:
	HashTable _ht;
};
template
class MyUnordered_Map
{
public:
	struct KeyOfT
	{
		const K& operator()(const pair& kv)
		{
			return kv.first;
		}
	};
	typedef typename HashTable, KeyOfT>::iterator iterator;
	typedef typename HashTable, KeyOfT>::const_iterator 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();
	}
	bool erase(const K& key)
	{
		return _ht.erase(key);
	}
	iterator find(const K& key)
	{
		return _ht.find(key);
	}
private:
	//因为unordered_map的T里的K是禁止修改的，所以需要加上const,而V是允许修改的，所以不需要加const
	HashTable, KeyOfT> _ht;
};

9、处理unordered_set里find函数的问题

解决办法也很简单，先接收HashTable里find方法的返回值，再用返回值里的成员变量来构造unordered_set的iterator即可。

iterator find(const K& key)
{
	auto it = _ht.find(key);
	return iterator(it._node, it._pht, it._hashi);
}

10、实现unordered_map里的operator[]功能

首先operator[]的实现需要实现insert，先对HashTable里的insert进行修改，修改返回值类型即可

然后实现unordered_map和unordered_set的insert

template
class MyUnordered_Map
{
public:
  //其他方法。。。
	pair insert(const pair& kv)
	{
		return _ht.insert(kv);
	}
private:
	//因为unordered_map的T里的K是禁止修改的，所以需要加上const,而V是允许修改的，所以不需要加const
	HashTable, KeyOfT> _ht;
};
template
class MyUnordered_Set
{
public:
  //其他方法。。。。
	pair insert(const K& key)
	{
		auto ret = _ht.insert(key);//这里和上面所讲的find有相同的问题，不能直接返回
		return make_pair(iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
	}
private:
	HashTable _ht;
};

接下来用insert来实现unordered_map的operator[]。

template
class MyUnordered_Map
{
public:
	pair insert(const pair& kv)
	{
		return _ht.insert(kv);
	}
	V& operator[](const K& key)
	{
		auto ret = _ht.insert(make_pair(key,V()));
		return ret.first->second;
	}
	const V& operator[](const K& key)const
	{
		auto ret = _ht.insert(make_pair(key, V()));
		return ret.first->second;
	}
private:
	//因为unordered_map的T里的K是禁止修改的，所以需要加上const,而V是允许修改的，所以不需要加const
	HashTable, KeyOfT> _ht;
};

三、全部代码

哈希表封装unordered_map和unordered_set

完结。。。。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 浅析KV存储之长尾时延解决办法

本文分享自华为云社区《浅析KV存储之长尾时延问题，华为云 GeminiDB Redis 探寻行业更优解决方案！》，作者：华为云数据库GaussDB NoSQL团队。 目前，KV存储的广泛使用极大程度上源于快速访问的业务需求，而这种业务通常对时延敏感度高，在较好…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: