C++深入探究哈希表如何封裝出unordered_set和unordered_map

更新時(shí)間：2022年06月13日 15:28:45 作者：你算哪一個(gè)bug?

哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu)，該結(jié)構(gòu)通過把關(guān)鍵碼映射的位置去尋找存放值的地方，說起來可能感覺有點(diǎn)復(fù)雜，我想我舉個(gè)例子你就會明白了，最典型的的例子就是字典

封裝前的哈希代碼

namespace HashBucket
{
	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode* _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:
		Node* Find(const K& key)//Find函數(shù)返回值一般都是指針，通過指針訪問這個(gè)自定義類型的成員
		{
			Hash hash;
			if (_tables.size() == 0)//表的大小為0，防止取余0
			{
				return nullptr;
			}
			size_t index = hash(key) % _tables.size();//找到桶號
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				else
				{
					cur = cur->_next;
				}
			}
			return nullptr;
		}
		size_t GetNextPrime(size_t prime)
		{
			const int PRIMECOUNT = 28;
			static const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 4294967291ul
			};
			//ul表示unsigned long
			size_t i = 0;
			for (; i < PRIMECOUNT; ++i)
			{
				if (primeList[i] > prime)
					return primeList[i];
			}
			return primeList[i];
		}
		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))//有相同的key直接返回false
			{
				return false;
			}
			//if(_n==0||_n==_tables.size())
			Hash hash;
			if (_n == _tables.size())//最開始_n為0，而_tables.size()也為0所以可以簡化為一行代碼
			{
				//增容
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());
				vector<Node*>newTables;
				newTables.resize(newSize, nullptr);
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;//記錄下一個(gè)位置
						size_t index = hash(cur->_kv.first) % newTables.size();
						cur->_next = newTables[index];//cur當(dāng)頭
						newTables[index] = cur;//更新vector里的頭
						cur = next;
					}
				}
				_tables.swap(newTables);//把新表的數(shù)據(jù)放入舊表中
			}
			size_t index = hash(kv.first) % _tables.size();//算出桶號
			//頭插
			Node* newNode = new Node(kv);
			newNode->_next = _tables[index];
			_tables[index]=newNode;
			++_n;//別忘記更新有效數(shù)據(jù)的個(gè)數(shù)
			return true;
		}
		bool Erase(const K& key)
		{ 
			//if (!Find(key))//找不到這個(gè)元素 
			// 這么寫也可以，但是后面刪除的過程中會順帶遍歷整個(gè)桶
			//{
			//	return false;
			//}
			if (_tables.size() == 0)//哈希表為空
			{
				return false;
			}
			Hash hash;
			size_t index = hash(key) % _tables.size();
			Node* cur = _tables[index];
			Node* prev = nullptr;//記錄前一個(gè)位置
			while (cur)
			{
				if (cur->_kv.first == key)//找到這個(gè)元素了
				{
					if(cur==_tables[index])//元素是頭結(jié)點(diǎn)
					{
						_tables[index] = cur->_next;
					}
					else//不是頭結(jié)點(diǎn)
					{
						prev->_next = cur->_next;
					}
					delete cur;
					cur = nullptr;
					_n--;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
		~HashTable()//哈希桶采用的鏈表結(jié)構(gòu) 需要釋放每個(gè)鏈表
		{
			for (int i=0;i<_tables.size();i++)
			{
				Node* cur = _tables[i];
				if (cur == nullptr)
				{
					continue;
				}
				else
				{
					cur = cur->_next;
				}
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
			_n = 0;
		}
		HashTable() {};
	private:
		vector<Node*>_tables;//存的是鏈表首元素的指針
		size_t _n=0;//有效數(shù)據(jù)
	};

泛型

封裝時(shí)想直接搭出unordered_set/unordered_map的結(jié)構(gòu),發(fā)現(xiàn)行不通

于是從哈希表的結(jié)構(gòu)入手，先把一些類型改成泛型

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

結(jié)點(diǎn)的KV結(jié)構(gòu)改成T ,改變結(jié)點(diǎn)的類型后HashTable里的結(jié)點(diǎn)類型也需要更改

typedef HashNode<K,V>的模板也需要改為typedef HashNode Node;

獲取key

明確unordered_map是KV結(jié)構(gòu)，unordered_set是K模型的結(jié)構(gòu)。

獲取key后可以做很多事情，比如查找和算出桶號

封裝前哈希結(jié)點(diǎn)的類型是pair<K,V>，現(xiàn)在的類型是T。

pair<K,V>kv , 可以通過kv.first來獲取key。

默認(rèn)int、double、string等類型的key就是本身。（也可以自定義）

類型T既可能是pair也可能是一個(gè)int類型等等，那應(yīng)該怎么得到類型T的key？借助模板+仿函數(shù)。

以unordered_map為例

unordered_map類中實(shí)現(xiàn)仿函數(shù)

哈希表中增加一個(gè)模板參數(shù)KeyOfT來獲取T類型的Key

同理unordered_set里仿函數(shù)的實(shí)現(xiàn)

之后把所有與.first有關(guān)的都用模板實(shí)例化的kot來獲取key

自定義哈希規(guī)則

去掉哈希表模板參數(shù)里哈希函數(shù)的默認(rèn)值在unordered_set/unordered_map加上第三個(gè)模板參數(shù)Hash自定義哈希規(guī)則

封裝前的哈希表

template<class K,class V,class Hash=HashFunc<K>>
class HashTable{};

現(xiàn)在的哈希表

template<class K, class T, class KeyOfT, class Hash>
//去掉哈希表的默認(rèn)值，哈希函數(shù)由unordered_map傳入
class HashTable{};
template<class K,class V,class Hash=HashFunc<K>>
class unordered_map{
    private:
		HashBucket::HashTable<K, pair<K, V>, MapKeyOfT,Hash> _ht;
};

解釋：實(shí)例化對象時(shí)便可以傳入模板參數(shù)達(dá)到自自定義哈希規(guī)則的效果。

哈希表模板參數(shù)解釋

template<class K, class T, class KeyOfT, class Hash>

看完上面的對這四個(gè)參數(shù)應(yīng)該有大概的了解了。這里一齊解釋一下為什么這么寫。

第一個(gè)參數(shù)K：key的類型就是K。查找函數(shù)是根據(jù)key來查找的，所以需要K。

第二個(gè)參數(shù)T：哈希表結(jié)點(diǎn)存儲的數(shù)據(jù)類型。比如int，double，pair,string等。

第三個(gè)參數(shù)KeyOfT：拿到T類型(結(jié)點(diǎn)數(shù)據(jù)類型)的key。

第四個(gè)參數(shù)Hash：表示使用的哈希函數(shù)

//哈希函數(shù)
template<class K>
struct HashFunc
{
	const K& operator()(const K& key)
	{
		return key;
	}
};
template<>//針對string的模板特化
struct HashFunc <string>
{
	size_t operator()(const string& key)
	{
		size_t value = 0;
		for (auto e : key)
		{
			value = value * 13 + (size_t)e;//*131是BKDR發(fā)明的字符串哈希算法，*131等數(shù)效率更高
		}
		return value;
	}
};

HashFunc（kot(T)）取出這個(gè)類型的key的映射值

迭代器

unordered_set/unordered_map的迭代器是單向迭代器

迭代器只能++，不能 –

結(jié)構(gòu)

Self表示自己

operator++()

前置++

實(shí)現(xiàn)思路：如果當(dāng)前結(jié)點(diǎn)的下一個(gè)不為空直接訪問即可

如果下一個(gè)結(jié)點(diǎn)為空，就得找下一個(gè)桶怎么找？根據(jù)當(dāng)前指向的數(shù)據(jù)算出桶號，再把桶號+1，一直往后面找，直到找到一個(gè)桶不為空，或者找完了整個(gè)容器都沒找到，就返回空

Self& operator++()//找到桶的下一個(gè)元素
{
	Hash hash;
	KeyOfT kot;
	Node* tmp = _node;//記錄當(dāng)前位置，用來計(jì)算當(dāng)前桶號
	_node = _node->_next;//當(dāng)前元素肯定不為空 所以不會有空指針引用的問題	
	//如果下一個(gè)為空，就找下一個(gè)不為空的桶
	if (_node == nullptr)//下一個(gè)元素為空
	{
		//找下一個(gè)不為空的桶，所以需要傳入這張表
		size_t index = hash(kot(tmp->_data)) % (_ht->_tables.size());
		index++;
		while (index < _ht->_tables.size() && _ht->_tables[index] == nullptr)//一直往后找
		{
			index++;
		}
		if (index == _ht->_tables.size())//找到最后一個(gè)元素了仍然沒找到，說明當(dāng)前已經(jīng)是最后一個(gè)元素了
		{
			_node = nullptr;
		}
		else
		{
			_node = _ht->_tables[index];
						
		}
		return *this;
	}
	else//下一個(gè)元素不為空
	{
		return *this;
	}
}

構(gòu)造函數(shù)

構(gòu)造函數(shù)得到結(jié)點(diǎn)所在的哈希表

HTIterator(Node* node, HT* ht)//不僅需要知道指向的結(jié)點(diǎn)，由于++需要找下一個(gè)桶，所以需要哈希結(jié)點(diǎn)所在的哈希表
	:_node(node)
	, _ht(ht)	
{}

重載運(yùn)算符

重載除了++以外的一些運(yùn)算符

T* operator->()//auto it=m.begin()  *it可以拿到數(shù)據(jù),所以返回值是T*
{
	return &(_node->_data);
}
T& operator*()
{
	return _node->_data;
}
bool operator!= (const Self& s)const
{
	return s._node != _node;
}

T為pair時(shí)可以通過it->first拿到key。

小問題

你會發(fā)現(xiàn)這樣一個(gè)現(xiàn)象，迭代器里面用了哈希表，哈希表里用了迭代器，也即兩個(gè)類互相引用

如果迭代器寫在哈希表前面，那么編譯時(shí)編譯器就會發(fā)現(xiàn)哈希表是無定義的（編譯器只會往前/上找標(biāo)識符）。

如果哈希表寫在迭代器前面，那么編譯時(shí)編譯器就會發(fā)現(xiàn)迭代器是無定義的。

為了解決這個(gè)問題，得用一個(gè)前置聲明解決，即在迭代器和哈希表的定義前加一個(gè)類的聲明。

template<class K, class T, class KeyOfT, class Hash>
class HashTable;//模板需要也需要進(jìn)行聲明
template<class K, class T, class KeyOfT, class Hash>
struct HTIterator{};
...
template<class K, class T, class KeyOfT, class Hash>
class HashTable{};//具體實(shí)現(xiàn)

迭代器里借助一個(gè)指針訪問了哈希表的數(shù)據(jù)。但是哈希表的數(shù)據(jù)被private修飾，所以在類外不能訪問，用友元解決。

在哈希表里面聲明迭代器友元類（表示迭代器是哈希表的朋友，可以訪問哈希表所有的數(shù)據(jù)）

const pair<const K,V>!=const pair<K,V>

寫代碼時(shí)的一個(gè)bug

相關(guān)的例子

解釋：調(diào)試看了一下地址，傳進(jìn)仿函數(shù)的時(shí)候參數(shù)用的引用接收，但是因?yàn)轭愋筒煌苑潞瘮?shù)參數(shù)接收時(shí)進(jìn)行了一次拷貝才拿到了sort和排序兩個(gè)字符串，但也因此那個(gè)參數(shù)成臨時(shí)變量了，所以返回了一塊被銷毀的空間的引用為什么變成空串？因?yàn)閟tring析構(gòu)后那塊空間成空串了

簡單來說仿函數(shù)沒有拿到真實(shí)的那塊空間而是拷貝后形參的空間

不能識別迭代器是類型還是成員導(dǎo)致模板報(bào)錯(cuò)，加上typename解決。

typedef typename HashBucket::HashTable<K, K, SetKeyOfT, Hash>::iterator iterator;

typename是告訴編譯器這是一個(gè)類型等這個(gè)類實(shí)例化了再去找里面的東西

代碼匯總

github代碼匯總

Hash.h

namespace ck
{
	template<class K>
	struct HashFunc
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
	template<>
	struct HashFunc <string>
	{
		size_t operator()(const string& key)
		{
			size_t value = 0;
			for (auto e : key)
			{
				value = value * 13 + (size_t)e;//*131是BKDR發(fā)明的字符串哈希算法，*131等數(shù)效率更高
			}
			return value;
		}
	};
	namespace HashBucket
	{
		template<class T>
		struct HashNode
		{
			T _data;
			HashNode* _next;
			HashNode(const T&data)
				:_data(data)
				, _next(nullptr)
			{}
		};
		template<class K, class T, class KeyOfT, class Hash>
		class HashTable;
		template<class K, class T, class KeyOfT, class Hash>
		struct HTIterator
		{
			typedef HTIterator<K, T, KeyOfT, Hash> Self;//自身
			typedef HashNode<T> Node;
			typedef HashTable<K, T, KeyOfT, Hash> HT;
			Node* _node;//通過Node*去訪問數(shù)據(jù) 不過自定義類型++不能訪問到下一個(gè)元素，所以需要封裝
			HT* _ht;
			HTIterator(Node* node, HT* ht)//不僅需要知道指向的結(jié)點(diǎn)，由于++需要找下一個(gè)桶，所以需要哈希結(jié)點(diǎn)所在的哈希表
				:_node(node)
				, _ht(ht)
			{}
			Self& operator++()//找到桶的下一個(gè)元素
			{
				Hash hash;
				KeyOfT kot;
				//const K& key = kot(_node->_data);//記錄這個(gè)不為空元素的key  有問題類型不匹配導(dǎo)致接收到的key是空串
				Node* tmp = _node;
				_node = _node->_next;//當(dāng)前元素肯定不為空 所以不會有空指針引用的問題	
				//如果下一個(gè)為空，就找下一個(gè)不為空的桶
				if (_node == nullptr)//下一個(gè)元素為空
				{
					//找下一個(gè)不為空的桶，所以需要傳入這張表
					size_t index = hash(kot(tmp->_data)) % (_ht->_tables.size());
					index++;
					while (index < _ht->_tables.size() && _ht->_tables[index] == nullptr)//一直往后找
					{
						index++;
					}
					if (index == _ht->_tables.size())//找到最后一個(gè)元素了仍然沒找到，說明當(dāng)前已經(jīng)是最后一個(gè)元素了
					{
						_node = nullptr;
					}
					else
					{
						_node = _ht->_tables[index];
					}
					return *this;
				}
				else//下一個(gè)元素不為空
				{
					return *this;
				}
			}
			T* operator->()//auto it=m.begin()  ‘it->' 去訪問數(shù)據(jù)成員所以返回值是T*
			{
				return &(_node->_data);
			}
			T& operator*()
			{
				return _node->_data;
			}
			bool operator!= (const Self& s)const
			{
				return s._node != _node;
			}
		};
		template<class K, class T,  class KeyOfT, class Hash>
		class HashTable
		{
			typedef HashNode<T> Node;
		public:
			template<class K, class T, class KeyOfT, class Hash>
			friend struct HTIterator;
			Node* Find(const K& key)//Find函數(shù)返回值一般都是指針，通過指針訪問這個(gè)自定義類型的成員
			{
				Hash hash;
				KeyOfT kot;
				if (_tables.size() == 0)//表的大小為0，防止取余0
				{
					return nullptr;
				}
				size_t index = hash(key) % _tables.size();//找到桶號
				Node* cur = _tables[index];
				while (cur)
				{
					if (kot(cur->_data) == key)
					{
						return cur;
					}
					else
					{
						cur = cur->_next;
					}
				}
				return nullptr;
			}
			size_t GetNextPrime(size_t prime)
			{
				const int PRIMECOUNT = 28;
				static const size_t primeList[PRIMECOUNT] =
				{
					53ul, 97ul, 193ul, 389ul, 769ul,
					1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
					49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
					1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
					50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
					1610612741ul, 3221225473ul, 4294967291ul
				};
				//ul表示unsigned long
				size_t i = 0;
				for (; i < PRIMECOUNT; ++i)
				{
					if (primeList[i] > prime)
						return primeList[i];
				}
				return primeList[i];
			}
			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);
			}
			iterator end()
			{
				return iterator(nullptr, this);//第二個(gè)指針就是自己
			}
			pair<iterator,bool> Insert(const T& data)
			{
				KeyOfT kot;
				Node* tmp = Find(kot(data));
				if (tmp)//有相同的key直接返回false
				{
					return make_pair(iterator(tmp, this), false);
				}
				//if(_n==0||_n==_tables.size())
				Hash hash;
				if (_n == _tables.size())//最開始_n為0，而_tables.size()也為0所以可以簡化為一行代碼
				{
					//增容
					//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
					size_t newSize = GetNextPrime(_tables.size());
					vector<Node*>newTables;
					newTables.resize(newSize, nullptr);
					for (int i = 0; i < _tables.size(); i++)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;//記錄下一個(gè)位置
							size_t index = hash(kot(cur->_data)) % newTables.size();
							cur->_next = newTables[index];//cur當(dāng)頭
							newTables[index] = cur;//更新vector里的頭
							cur = next;
						}
					}
					_tables.swap(newTables);//把新表的數(shù)據(jù)放入舊表中
				}
				size_t index = hash(kot(data)) % _tables.size();//算出桶號
				//頭插
				Node* newNode = new Node(data);
				newNode->_next = _tables[index];
				_tables[index] = newNode;
				++_n;//別忘記更新有效數(shù)據(jù)的個(gè)數(shù)
				return make_pair(iterator(newNode, this), true);
			}
			bool Erase(const K& key)
			{
				//if (!Find(key))//找不到這個(gè)元素 
				// 這么寫也可以，但是后面刪除的過程中會順帶遍歷整個(gè)桶
				//{
				//	return false;
				//}
				if (_tables.size() == 0)//哈希表為空
				{
					return false;
				}
				Hash hash;
				KeyOfT kot;
				size_t index = hash(key) % _tables.size();
				Node* cur = _tables[index];
				Node* prev = nullptr;//記錄前一個(gè)位置
				while (cur)
				{
					if (kot(cur->_data) == key)//找到這個(gè)元素了
					{
						if (cur == _tables[index])//元素是頭結(jié)點(diǎn)
						{
							_tables[index] = cur->_next;
						}
						else//不是頭結(jié)點(diǎn)
						{
							prev->_next = cur->_next;
						}
						delete cur;
						cur = nullptr;
						_n--;
						return true;
					}
					else
					{
						prev = cur;
						cur = cur->_next;
					}
				}
				return false;
			}
			~HashTable()//哈希桶采用的鏈表結(jié)構(gòu) 需要釋放每個(gè)鏈表
			{
				for (int i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					if (cur == nullptr)
					{
						continue;
					}
					else
					{
						cur = cur->_next;
					}
					while (cur)
					{
						Node* next = cur->_next;
						delete cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_n = 0;
			}
			HashTable() {};
		private:
			vector<Node*>_tables;//存的是鏈表首元素的指針
			size_t _n = 0;//有效數(shù)據(jù)
		};
	}
}

MyUnordered_map.h

#include "Hash.h"
namespace ck
{
	template<class K,class V,class Hash=HashFunc<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair< K, V>& kv) const
			{
				return kv.first;
			}
		};
		typedef typename HashBucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash>::iterator iterator;
	public:
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return  _ht.end();
		}
		pair<iterator, bool> insert(const pair<const K,V>& kv)
		{
			return _ht.Insert(kv);
		}
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
		bool find(const K& key)
		{
			return _ht.Find(key);
		}
		V& operator[](const K& key)
		{
			auto it = insert(make_pair(key, V()));
			return (it.first)->second;
		}
	private:
		HashBucket::HashTable<K, pair<K, V>, MapKeyOfT,Hash> _ht;
	};
}

MyUnordered_set.h

#include "Hash.h"
namespace ck
{
	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;
	public:
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return  _ht.end();
		}
		pair<iterator, bool> insert(const K& kv)
		{
			return _ht.Insert(kv);
		}
		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
		bool find(const K& key)
		{
			return _ht.Find(key);
		}
	private:
		HashBucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
	};
	private:
    	HashBucket::HashTable<K, pair<K, V>, MapKeyOfT,Hash> _ht;
    };
}

到此這篇關(guān)于C++深入探究哈希表如何封裝出unordered_set和unordered_map的文章就介紹到這了,更多相關(guān)C++哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: