Guff_9hys

这个屌丝很懒，什么也没留下！

热门标签

C++——unordered_set、unordered_map容器和底层模拟实现（哈希）_c++的map容器的底层实现

作者：Guff_9hys | 2024-08-09 23:31:17

踩

c++的map容器的底层实现

3.封装哈希桶模拟unordered系列容器

1.unordered关联式容器

set和map的关联式容器，底层为红黑树，最多查找树的高度次，效率非常高。

unordered系列用了不同的底层结构，又让效率变得更高。插入和删除比map和set差一点点，但是find效率特别高。

原因是哈希结构把数据和位置信息关联（映射），找数据的时候是直接找到。

1.1接口

count计算的是key值个数，因为map和set都不允许重复key，所以只会返回0或1。

unordered_map的count返回的不是key值对应的val。

unordered_multimap的count返回的也是关键值为key的节点个数。

2. 底层结构

底层使用哈希结构。

2.1 哈希概念

通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希函数(散列函数)，构造出来的结构称为哈希表(Hash Table)(或者称散列表)。

2.2 常见哈希函数

1.直接定址法：Hash（Key）= A*Key + B

要求数据为整型+范围相对集中。

可以是绝对位置（把1存到下标1的位置），也可以是相对位置（把100存到下标0的位置）。数据范围集中才适用，太分散会导致数组空间浪费严重。

2.除留余数法：Hash=Key%len

这个方法适用整型等其他类型数据（包括自定义类型，定义哈希函数将数据转换为整形）。len是哈希表大小。

key目前只考虑是整型，把整型数据key%len结果只会是[0,len-1]（数据范围集中还是分散都适用）。这个公式计算出的结果就是该数据在哈希表中的位置。

2.3 哈希碰撞/冲突

不同关键字通过相同哈希函数，计算出相同哈希地址，这种现象称为哈希冲突。

冲突处理方法：常用的方法是闭散列和开散列

2.3.1 开放定址法

使用开放定址法解决冲突的散列表叫闭散列。

2.3.1.1 线性探测

1.插入、删除、查找规则

插入

查找

找38（存在的数），用哈希函数计算地址，来到8找，没找到，就一直往后找，看数据相不相等。直到找到位置2找到了。如果找28（不存在的数），计算哈希地址，来到8，没有就继续往后，一直找到下标3还是没有。下一个位置为空，找到空就结束，没有找到。

删除

删除27，先找到27，然后置空。

删除后再找28和38。置空后影响后面的数据查找，发现找不到，走到0位置为空就停止了。

怎么解决？不用置空来表示删除，而是给每个位置添加一个状态标志。查找到删除状态不能停止，查找到空才能停止。还要注意，万一没有遇到空，最多找一轮。

2.闭散列的哈希表是不能存满的（有效数据个数等于size就存满了）。

快满的时候，发生哈希冲突的概率非常大。存满了之后，插入任何数都会失败（找不到状态为删除和空的位置，全都是存在）。故引入载荷因子来控制哈希表，每当快满的时候就扩容。

负载因子或载荷因子=有效数据个数/表的大小

用来计算表的已用空间占比。

哈希表在负载因子超过一定大小之后，就会让哈希表扩容。绝对不能让表存满。

负载因子越小，冲突概率越小，消耗空间越多。

负载因子越大，冲突概率越大，空间利用率越高。

实现：

1.insert

1）插入前检查是否和已有数据重复

2）检查负载因子，判断是否需要扩容

需要注意第一次插入时，size为0，不能这么*2扩容，而且if (_n * 10 / _tables.size() > 7),0不能做除数。处理方法有：1.再添加一个判断，if（_tables.size()==0）_tables.resize(10); 2.构造函数，构造的时候就把size处理好

3）在计算映射地址的时候，数据%size。数据一定要转换成整型才能进行映射。

如何转换？利用仿函数。HashTable添加一个仿函数的模板参数，给好缺省值（适用int，char），特殊类型（string）可以特化。

find

思路是先取%算起始地址，如果非空就一直往下找，找到才空停止。

erase

只需要把状态转换成DELETE，不需要释放。


template<class K>
struct HashFunc
{
	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 ch : key)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};
 
 
 
namespace closehash
{
	enum State
	{
		EMPTY,
		EXIST,
		DELETE,
 
	};
	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state;
 
		HashData()
			:_state(EMPTY)
		{}
	};
 
 
	template<class K, class V,class Hash=HashFunc<K>>
	class HashTable
	{
		typedef HashData<K, V> Data;
	public:
		HashTable()
			:_n(0)
		{
			_tables.resize(10);
		}
 
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))//Insert前先检查是否重复，因为是实现的是key结构，返回false就行。
			{
				return false;
			}
 
			//数不存在，决定插入，插入前检查是否需要扩容
			if (_n * 10 / _tables.size() > 7)//注意看这里。因为运算符的计算结果一定是整型，_n/_tables.size()>0.7。这么算结果永远都是0，不会大于0.7。也可以强转成double。
			{
				//方法一，创建新的vector<Data>
				//vector<Data> newTable;
				//newTable.resize(_tables.size() * 2);
				//for (auto& e : _tables)
				//{
				//	if (e._state == EXIST)
				//	{
				//		size_t hashi = e._kv.first % newTable.size();
				//		while (newTable[hashi]._state == EXIST)
				//		{
				//			++hashi;
				//			hashi %= newTable.size();//每当hashi等于size的时候，重头开始。
				//		}
				//		//探测到删除，或空的时候跳出循环，在hashi插入
				//		newTable[hashi]._kv = e._kv;
				//		newTable[hashi]._state = EXIST;
				//	}
				//}
				//_tables.swap(newTable);
 
				//方法二，创建新的HashTable对象
				HashTable<K, V> newHashTable;
				newHashTable._tables.resize(2 * _tables.size());
				for (auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						newHashTable.Insert(e._kv);
					}
				}
 
				_tables.swap(newHashTable._tables);
			}
 
 
			Hash hf;
			size_t hashi = hf(kv.first) % _tables.size();//一定是模size，不能模capacity。因为插入数据使用vector的[]，模capacity的时候，计算出的下标可能会超过size，[]会检查报错。
 
			while (_tables[hashi]._state == EXIST)
			{
				++hashi;
				hashi %= _tables.size();//每当hashi等于size的时候，重头开始。
			}
			//探测到删除，或空的时候跳出循环，在hashi插入
			_tables[hashi]._kv = kv;
			_tables[hashi]._state = EXIST;
 
			++_n;
 
			return true;
		}
 
		Data* Find(const K& key)
		{
			Hash hf;
			size_t hashi = hf(key) % _tables.size();
			size_t start = hashi;
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._kv.first == key && _tables[hashi]._state == EXIST)//*如果是DELETE状态，还能访问到数据，但是不能算是找到了。
				{
					return &_tables[hashi];
				}
				++hashi;
				hashi %= _tables.size();
 
				//特殊情况：当_n数量在不会扩容的范围之内，有效数据位置之外的，其他位置都是删除状态。找不到空，会死循环。
				//所以限制最多走一圈。
				if (hashi == start)
				{
					break;
				}
			}
			return nullptr;
		}
 
		bool Erase(const K& key)
		{
			Data* ret = Find(key);
			if (ret)
			{
				ret->_state = DELETE;
				--_n;
				return true;
			}
			else
			{
				return false;
			}
		}
 
	private:
		vector<Data> _tables;
		size_t _n=0;//有效数据个数
	};
}

拷贝构造，赋值，析构。

不用。vector都有，整形不需要。

2.3.1.2 二次探测

线性探测：hashi=start+i

start是计算出的地址，i是连续往后探测的次数。线性探测是从起始位置一个一个挨着往后访问。数据可能放的太集中，增加碰撞发生的概率。

二次探测：hashi=start+i^2

跳跃式的去探测，数据也会放的更分散。

闭散列的存放数据方法是发生碰撞就往后放，占用其他数据的位置。这样的方式并不好，所以采用更优方式——开散列。

2.3.1 链地址法

采用连地址法解决冲突的散列表叫开散列（哈希桶）。

数据存放方式：地址相同的数据，存在同一个位置，放到一个单链表里面。vector<HashNode*>

当数据过多的时候，链表过长，效率可能还是不够高。开散列的哈希表也叫哈希桶。

析构函数？拷贝构造？

存的是指针，要深拷贝。析构也需要，没有的话当vector释放之后，new出来的节点没有释放。
insert

1）数据要能够转整型，然后%size计算映射地址。找到后头插到单链表（单链表头插效率高）。

2）负载因子等于1的时候扩容

_n==vector.size()

可能没有碰撞，vector刚好存满，再存就一定会发生碰撞。

可能已经发生碰撞，v没有存满（有空桶）。碰撞程度不一，最严重就是_n个不同的数全部碰撞，在同一条单链表上。轻微一点的就是有的桶的链表长，有的桶的短。

3）把原来的节点直接拿来用，不用再重新一个一个Insert插入。


template<class K>
struct HashFunc
{
	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 ch : key)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};
namespace HashBucket 
{
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K,V>* _next;
 
		HashNode(const pair<K, V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
 
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		HashTable()
			:_n(0)
		{
			_tables.resize(10);
		}
		~HashTable()
		{
			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;
			}
			
		}
		bool Insert(const pair<K,V>& kv)
		{
			if (Find(kv.first))
			{
				return false;//找到了，说明已经存在，返回false
			}
 
			if (_n == _tables.size())//扩容
			{
				//创建新的_tables
				vector<Node*> newTables;
				newTables.resize(2*_n,nullptr);
 
				for (auto& e: _tables)
				{
					if (e != nullptr)
					{
						Node* cur = e;
						while (cur != nullptr)
						{
							Node* next = cur->_next;
							size_t newhashi = Hash()(cur->_kv.first) % newTables.size();//原来在同一个桶里的数，扩容之后可能就不在同一个桶里了
							cur->_next = newTables[newhashi];
							newTables[newhashi] = cur;
							cur = next;
						}
 
						e = nullptr;
					}
				}
				_tables.swap(newTables);
			}
 
 
			size_t hashi = Hash()(kv.first) % _tables.size();
			//头插
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
		}
 
		//单链表的删除，必须要有被删除节点的前一个节点。如果直接利用find，只有节点的地址，是没办法删除的。
		bool Erase(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_kv.first == key)//找到了，删除
				{
					//cur在头
					if (cur == _tables[hashi])
					{
						_tables[hashi] = cur->_next;
					}
 
					//cur在中间，或尾
					//prev cur cur->_next
					else
					{
						prev->_next = cur->_next;
					}
					
					delete cur;
					--_n;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
 
			return false;//如果cur为空了，说明一直没找到等于key的节点，或者hahi位置一开始就没有节点。
		}
 
		Node* Find(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
	
	private:
		vector<Node*> _tables;
		size_t _n=0;
	};
}

标准库unordered容器里提供get和set负载因子的两个接口。

3.封装哈希桶模拟unordered系列容器

HashTable.h

这里都是简单讲。比如封装的是同一个底层，但能同时实现unordered_map和unordered_set。在map和set那里详细讲解。为哈希桶的模板参数添加KeyOfT仿函数类型，该仿函数获取kv结构的key，或key结构的key，由上层unorderedmap/set定义仿函数并传递给哈希桶。

哈希桶的模板参数不给Hash缺省参数了，因为Hash是什么是由上层unorder在实例化的时候决定的，Hash一定得由上层传递，这个缺省值根本就不会用上。

哈希桶的遍历方法：一个桶走完了，通过计算得知现在在几号桶，然后再去哈希表里去找下一个桶。


//HashTable.h
template<class K>
struct HashFunc
{
	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 ch:key)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};
 
 
namespace HashBucket
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;
 
		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};
 
	template<class K, class T, class KeyOfT, class Hash >
	class HashTable;
	//前置声明。HashTable里用迭代器，迭代器里面也要用HashTable，他们互相引用。HashTable能顺利使用迭代器，因为迭代器在前。
	
	template<class K,class T,class KeyOfT,class Hash>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, KeyOfT, Hash> Self;
		typedef HashTable<K, T, KeyOfT, Hash> HT;//{*}
		
		Node* _node;
		HT* _ht;
		
 
		__HTIterator(Node* node, HT* ht)
			:_node(node)
			,_ht(ht)
		{}
 
		T& operator*()
		{
			return _node->_data;
		}
 
		T* operator->()
		{
			return &(_node->_data);
		}
 
		bool operator!=(const Self& s)const
		{
			return _node != s._node;
		}
 
 
		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				Hash hash;
				size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
				++hashi;
				while (hashi < _ht->_tables.size())
				{
					if (_ht->_tables[hashi])
					{
						_node = _ht->_tables[hashi];
						break;
					}
					else
					{
						++hashi;
					}
				}
 
				//走到这里有两种情况1.找到下一个桶，从while循环break出来的 
				//2._node在的桶就是最后一个桶，或_node在的桶后面全部都是空桶
				if (hashi == _ht->_tables.size())
				{
					_node = nullptr;//让空指针作为end
				}
			}
			return *this;
		}
	};
 
	template<class K, class T, class KeyOfT, class Hash >
	class HashTable
	{
		template<class K, class T, class KeyOfT, class Hash>
		friend struct __HTIterator;
 
		typedef HashNode<T> Node;
 
	public:
		typedef __HTIterator<K, T, KeyOfT, Hash> iterator;
 
		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i],this);
				}
			}
			return iterator(nullptr, this);//_tables里每个桶都是空的
		}
 
		iterator end()
		{
			return iterator(nullptr, this);
		}
 
		HashTable()
			:_n(0)
		{
			_tables.resize(10);
		}
 
		~HashTable()
		{
			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)
		{
			KeyOfT kot;
			Hash hash;
 
			iterator it = Find(kot(data));
			if (it!=end())
			{
				return make_pair(it,false);//找到了，说明已经存在，返回false
			}
 
			if (_n == _tables.size())//扩容
			{
				//创建新的_tables
				vector<Node*> newTables;
				newTables.resize(2 * _n, nullptr);
 
				for (auto& e : _tables)
				{
					if (e != nullptr)
					{
						Node* cur = e;
						while (cur != nullptr)
						{
							Node* next = cur->_next;
							size_t newhashi = hash(kot(cur->_data)) % newTables.size();//原来在同一个桶里的数，扩容之后可能就不在同一个桶里了
							cur->_next = newTables[newhashi];
							newTables[newhashi] = cur;
							cur = next;
						}
 
						e = nullptr;
					}
					_tables.swap(newTables);
				}
			}
 
 
			size_t hashi = Hash()(kot(data)) % _tables.size();
			//头插
			Node* newnode = new Node(data);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
 
			return make_pair(iterator(newnode,this), true);
		}
 
		//单链表的删除，必须要有被删除节点的前一个节点。如果直接利用find，只有节点的地址，是没办法删除的。
		bool Erase(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)//找到了，删除
				{
					//cur在头
					if (cur == _tables[hashi])
					{
						_tables[hashi] = cur->_next;
					}
 
					//cur在中间，或尾
					//prev cur cur->_next
					else
					{
						prev->_next = cur->_next;
					}
 
					delete cur;
					--_n;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
 
			return false;//如果cur为空了，说明一直没找到等于key的节点，或者hahi位置一开始就没有节点。
		}
 
		iterator Find(const K& key)
		{
			KeyOfT kot;
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur,this);
				}
				cur = cur->_next;
			}
			return iterator(nullptr,this);
		}
 
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};
}

unordered_map.h


//UnorderedMap.h
#include"HashTable.h"
namespace my
{
	template<class K, class V, class Hash = HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()( const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
 
	public:
		typedef typename  HashBucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash>::iterator iterator;
 
		pair<iterator, bool> insert(const pair<K,V>& data)
		{
			return _ht.Insert(data);
		}
 
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
 
		V& operator[](const K& key)
		{
			pair<iterator,bool> ret=_ht.Insert(make_pair(key,V()));
			return ret.first->second;
		}
 
	private:
		HashBucket::HashTable<K, pair<const K,V>, MapKeyOfT, Hash> _ht;
 
	};
 
	void test_unordered_map()
	{
		string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
 
		unordered_map<string,int> countMap;
		for (auto& e : arr)
		{
			countMap[e]++;
		}
 
		for (const auto& kv : countMap)
		{
			cout << kv.first << ":" << kv.second << endl;
		}
 
 
	}
}

unordered_set.h


#include"HashTable.h"
namespace my
{
	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, K, SetKeyOfT, Hash>::iterator iterator;//模板还没有实例化之前，要使用类模板中的类型，编译器无法区分该类型是自定义类型还是静态成员。加上typename告诉编译器这是一个类型。
 
		pair<iterator,bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
 
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
 
	private:
		HashBucket::HashTable<K,K,SetKeyOfT,Hash> _ht;
	};
 
	void test_unordered_set()
	{
		unordered_set<int> us;
		us.insert(1);
		us.insert(10);
		us.insert(5);
		us.insert(20);
		us.insert(23);
		us.insert(5);
 
		unordered_set<int>::iterator it =us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/955657