【数据结构】C++的unordered_map/set模拟实现(开散列(哈希桶)作底层)

本篇建立在已经熟悉map/set模拟实现和开散列的模拟实现的基础上，关于开散列，可以看上一篇文章：

【数据结构】哈希——闭散列/开散列模拟实现(C++)-CSDN博客本文对比分析了C++中unordered_map/unordered_set与map/set的主要区别。底层实现上，前者采用哈希表（O(1)时间复杂度），后者使用红黑树（O(logN)）。重点探讨了哈希冲突的两种解决方案：闭散列（开放定址法）和开散列（哈希桶）。闭散列通过线性探测或二次探测解决冲突，但存在效率问题；开散列则通过链表存储冲突元素，效率更高。文章还提供了哈希表的模拟实现代码，包括插入、查找、删除等操作，并比较了两种容器在百万级数据下的性能差异。https://blog.csdn.net/suimingtao/article/details/149002209
【数据结构】C++的map/set模拟实现(红黑树作底层)-CSDN博客文章浏览阅读777次，点赞11次，收藏26次。本文介绍了基于红黑树实现C++中的map和set容器。通过复用单一红黑树结构，分别处理K模型(set)和KV模型(map)。重点内容包括：1) 红黑树改造，引入KeyOfValue仿函数解决不同类型值比较问题；2) 迭代器实现，包括++/--操作的中序遍历逻辑；3) map的[]运算符重载，通过insert返回pair 实现。相比传统双树实现方式，这种高级复用方案减少了代码冗余，同时保持了高效性能，插入操作时间复杂度为O(logN)。 https://blog.csdn.net/suimingtao/article/details/148928079

迭代器实现

在实现unordered_map/unordered_set之前，先将开散列的迭代器实现一下

迭代器的结构

对于迭代器来说，也需要传KOfT，Hash参数，还需要一个该哈希表的指针(即下面的_pht)，关于原因稍候早说

template<class K,class T,class KOfT,class Hash,class Ref,class Ptr>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KOfT, Hash> HT;
    typedef __HashIterator<K, T, KOfT, Hash,Ref,Ptr> Self;//迭代器本身
	HashIterator(Node* node,HT* pht)//默认构造
		:_node(node)
		,_pht(pht)
	{ }
private:
	Node* _node;//每个桶中的节点
	HT* _pht;//当一个桶走完时，为了可以找到下一个桶，需要该哈希表的指针

};

迭代器的解引用 

迭代器中主要存的还是一个节点的指针，即_node，对于operator*和operator->重载，了解过map/set的都知道，operator*重载对应set的解引用，因为set中只存key，解引用时也只需要"*"；operator->重载对应map的解引用，因为map中存key和value，解引用时肯定需要"->"指定对应的值

Ref operator*()//unordered_set的解引用
{
	return _node->_data;
}

Ptr operator->()//unordered_map的解引用
{
	return &_node->_data//在调用"it->first"时，其实是调用了"it->->first"，这里编译器省略了第一次"->"，而这里返回的就是第一次调用的结果，即pair类型的地址
}

 顺便将等于和不等于重载实现一下

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

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

 迭代器的++

unordered_map/unordered_set的迭代器是单向迭代器，因此只有++，没有--

假设现在的迭代器在第一个桶的第一个节点，当它遍历完该桶后，要怎么跳转到下一个有节点的桶？

此时传该哈希表的指针(即_pht)的意义就来了，有了该哈希表的指针，就可以遍历整个哈希表中所有的哈希桶，但要从哪开始遍历？程序怎么知道当前迭代器在哪个桶？

此时传KOfT和Hash的作用就来了，通过对当前迭代器的值除留余数法，就能算出当前迭代器在哪个桶，再去从该桶后面开始遍历即可

Self operator++()//前置++
{
	assert(_node);//防止节点本来就为空
	if (_node->_next)//如果该桶还有节点
	{
		_node = _node->_next;
	}
	else//该桶已被遍历完，需要找下一个桶
	{
		KOfT koft;//用于从T类型取出key
		size_t index = _pht->HashFunc(koft(_node->_data)) % _pht->_table.size();//除留余数法取出映射
		index++;
		for (; index < _pht->_table.size())//从下一个桶开始找非空桶
		{
			Node* cur = _pht->_table[index];
			if (cur)
			{
				_node = cur;
				return *this;//若找到，就直接返回本身迭代器
			}
		}
		_node = nullptr;//找不到就将迭代器置end()
	}
	return *this;
}

Self operator++(int)//后置++
{
	Self tmp = *this;
	++*this;
	return tmp;
}

改造哈希表

 首先哈希表内部与迭代器支持一下

template<class K,class T,class KOfT,class Hash>//T可能是K或pair，KOfT是为了从T中取出key的仿函数，Hash是将不同类型的K转换为整型的仿函数
class HashTable
{
	typedef HashNode<T> Node;
	typedef typename __HashIterator<K, T, KOfT, Hash, T&, T*> iterator;
	typedef typename __HashIterator<K, T, KOfT, Hash, const T&, const T*> const_iterator;//只读迭代器
	friend iterator;//将只读和读写迭代器都变为友元，迭代器不管什么类型就都可以访问HashTable的_table
	friend const_iterator;
public:

	iterator begin()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i])
				return iterator(_table[i], this);//将第一个节点转换为迭代器
		}
		return end();
	}

	iterator end()
	{
		return nullptr;//这里就实现的简单点吧
	}

	const_iterator begin() const
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i])
				return const_iterator(_table[i], this);//将第一个节点转换为迭代器
		}
		return end();
	}

	const_iterator end() const
	{
		return nullptr;
	}
    //.................
}

由于需要unordered_map需要支持operator[]，因此需要先将原来的哈希表的Insert改造一下，返回值改为pair<iterator,bool>

pair<iterator,bool> Insert(const T& data)
{
	KOfT koft;//用于取出T类型的Key
	if (_table.size() == _num)//负载因子到1时扩容
	{
		//1.开2倍大小空间(不一定是2倍)
		//2.遍历旧表数据，重新计算在新表中位置
		//3.释放旧表
		vector<Node*> newtable;
		size_t newsize = _table.size() ? _table.size() * 2 : 10;
		newtable.resize(newsize);
		for (auto& cur : _table)
		{
			//将旧表中的节点取下来重新计算在新表中的位置，并插入进去
			Node* head = cur;
			while (head)
			{
				Node* next = head->_next;
				size_t index = HashFunc(koft(head->_data)) % newtable.size();
				//头插进桶中
				head->_next = newtable[index];
				newtable[index] = head;

				head = next;
			}
			cur = nullptr;//将旧表该位置置空，否则最后析构旧表时就将节点都析构了
		}

		_table.swap(newtable);//旧表在出作用域后自动销毁
	}
	
	size_t index = HashFunc(koft(data)) % _table.size();//除留余数法取出映射
	//先查找值是否重复
	Node* cur = _table[index];
	while (cur)
	{
		if (koft(cur->_data) == koft(data))//如果是重复值，插入失败
			return make_pair(iterator(cur,this),false);
		else
			cur = cur->_next;
	}
	Node* newnode = new Node(data);//开辟新空间
	//头插到对应桶中(尾插也可以)
	newnode->_next = _table[index];
	_table[index] = newnode;
	_num++;
	return make_pair(iterator(newnode,this),true);
}

Find的返回值也改成迭代器

iterator Find(const K& key)
{
	KOfT koft;//用于取出T类型的key
	size_t index = HashFunc(key) % _table.size();//算出映射
	//去该映射桶中找
	Node* cur = _table[index];
	while (cur)
	{
		if (koft(cur->_data) == key)
			return iterator(cur,this);
		else
			cur = cur->_next;
	}
	return iterator(nullptr,this);//找不到返回空
}

模拟实现unordered_map/unordered_set

和map/set时一样，只需要将哈希表套进去就可以

unordered_map

#pragma once
#include "HashTable.h"


namespace valkyrie
{
	using namespace Open_Hash;
	template<class K,class V,class Hash = _Hash<K>>
	class unordered_map
	{
		struct KeyOfMap//用于从pair类型中取出K
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<K, V>, KeyOfMap, Hash>::iterator iterator;
		typedef typename HashTable<K, pair<K, V>, KeyOfMap, Hash>::const_iterator const_iterator;

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

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

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

		V& operator[](const K& key)
		{
			pair<iterator, bool> pr = _ht.Insert(make_pair(key, V()));//不管插入失败还是成功，first中存的都是该Key的迭代器
			return pr.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();
		}

		void clear()
		{
			_ht.clear();
		}

	private:
		HashTable<K, pair<K, V>, KeyOfMap, Hash> _ht;//哈希表作底层
	};

}

unordered_set

#pragma once
#include "HashTable.h"

namespace valkyrie
{
	using namespace Open_Hash;
	template<class K, class Hash = _Hash<K>>
	class unordered_set
	{
		struct KeyOfSet//为了适配KeyOfMap
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename HashTable<K, K, KeyOfSet, Hash>::iterator iterator;
		typedef typename HashTable<K, K, KeyOfSet, Hash>::const_iterator const_iterator;
	
		pair<iterator, bool> Insert(const K& key)
		{
			return _ht.Insert(key);
		}

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

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

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

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

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

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

		void clear()
		{
			_ht.clear();
		}

	private:
		HashTable<K, K, KeyOfSet, Hash> _ht;//内部结构是哈希表
	};

}

针对迭代器遍历的优化(思路)

在STL实现的unordered_map/unordered_set中，迭代器遍历的顺序就是插入数据的顺序，而目前我们自己实现的迭代器遍历是遍历桶来完成的，有没有什么办法可以完成像STL里的那种效果呢？

 我们可以在哈希表的节点结构中再加两个成员：_linknext和_linkprev

template<class T>
struct HashNode
{
	T _data;//K或KV
	HashNode* _next;//单链表
	HashNode* _linknext;//下一个插入的元素
	HashNode* _linkprev;//上一个插入的元素
	HashNode(const T& data)//默认构造，为下面的new HashNode而准备
		:_data(data)
		, _next(nullptr)
	{ }
};

 _linknext是为了遍历，_linkprev是为了在删除时可以找到上一个元素

虽然这样可以在遍历时按照插入的顺序，但这也会让哈希表的结构更加复杂.....这里就不作实现了