主頁 >  其他 > STL詳解（十三）—— 用一個哈希表同時封裝出unordered_map和unordered_set

STL詳解（十三）—— 用一個哈希表同時封裝出unordered_map和unordered_set

2022-01-17 19:54:41 其他

文章目錄

  • 哈希表源代碼
  • 哈希表模板引數的控制
  • string型別無法取模問題
  • 哈希表默認成員函式實作
  • 哈希表正向迭代器的實作
  • unordered_set的模擬實作
  • unordered_map的模擬實作
  • 封裝完成后的代碼
    • 哈希表的代碼
    • 正向迭代器的代碼
    • unordered_set的代碼
    • unordered_map的代碼

哈希表源代碼

下面我們將對一個KV模型的哈希表進行封裝，同時模擬實作出C++STL庫當中的unordered_map和unordered_set，所用到的哈希表源代碼如下：

//每個哈希桶中存盤資料的結構
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 HashTable
{
	typedef HashNode<K, V> Node; //哈希結點型別
public:
	//獲取本次增容后哈希表的大小
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		//素數序列
		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
		};
		size_t i = 0;
		for (i = 0; i < PRIMECOUNT; i++)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	//插入函式
	bool Insert(const pair<K, V>& kv)
	{
		//1、查看哈希表中是否存在該鍵值的鍵值對
		Node* ret = Find(kv.first);
		if (ret) //哈希表中已經存在該鍵值的鍵值對（不允許資料冗余）
		{
			return false; //插入失敗
		}

		//2、判斷是否需要調整哈希表的大小
		if (_n == _table.size()) //哈希表的大小為0，或負載因子超過1
		{
			//增容
			//a、創建一個新的哈希表，新哈希表的大小設定為原哈希表的2倍（若哈希表大小為0，則將哈希表的初始大小設定為10）
			vector<Node*> newtable;

			newtable.resize(GetNextPrime(_table.size()));
				
			//b、將原哈希表當中的結點插入到新哈希表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) //桶不為空
				{
					Node* cur = _table[i];
					while (cur) //將該桶的結點取完為止
					{
						Node* next = cur->_next; //記錄cur的下一個結點
						size_t index = cur->_kv.first%newtable.size(); //通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
						//將該結點頭插到新哈希表中編號為index的哈希桶中
						cur->_next = newtable[index];
						newtable[index] = cur;

						cur = next; //取原哈希表中該桶的下一個結點
					}
					_table[i] = nullptr; //該桶取完后將該桶置空
				}
			}
			//c、交換這兩個哈希表
			_table.swap(newtable);
		}

		//3、將鍵值對插入哈希表
		size_t index = kv.first % _table.size(); //通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
		Node* newnode = new Node(kv); //根據所給資料創建一個待插入結點
		//將該結點頭插到新哈希表中編號為index的哈希桶中
		newnode->_next = _table[index];
		_table[index] = newnode;

		//4、哈希表中的有效元素個數加一
		_n++;
		return true;
	}
	//查找函式
	HashNode<K, V>* Find(const K& key)
	{
		if (_table.size() == 0) //哈希表大小為0，查找失敗
		{
			return nullptr;
		}

		size_t index = key % _table.size(); //通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
		//遍歷編號為index的哈希桶
		HashNode<K, V>* cur = _table[index];
		while (cur) //直到將該桶遍歷完為止
		{
			if (cur->_kv.first == key) //key值匹配，則查找成功
			{
				return cur;
			}
			cur = cur->_next;
		}
		return nullptr; //直到該桶全部遍歷完畢還沒有找到目標元素，查找失敗
	}
	//洗掉函式
	bool Erase(const K& key)
	{
		//1、通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
		size_t index = key % _table.size();
		//2、在編號為index的哈希桶中尋找待洗掉結點
		Node* prev = nullptr;
		Node* cur = _table[index];
		while (cur) //直到將該桶遍歷完為止
		{
			if (cur->_kv.first == key) //key值匹配，則查找成功
			{
				//3、若找到了待洗掉結點，則洗掉該結點
				if (prev == nullptr) //待洗掉結點是哈希桶中的第一個結點
				{
					_table[index] = cur->_next; //將第一個結點從該哈希桶中移除
				}
				else //待洗掉結點不是哈希桶的第一個結點
				{
					prev->_next = cur->_next; //將該結點從哈希桶中移除
				}
				delete cur; //釋放該結點
				//4、洗掉結點后，將哈希表中的有效元素個數減一
				_n--;
				return true; //洗掉成功
			}
			prev = cur;
			cur = cur->_next;
		}
		//假洗掉可能會導致迭代器失效
			
		return false; //直到該桶全部遍歷完畢還沒有找到待洗掉元素，洗掉失敗
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素個數
};

哈希表模板引數的控制

首先需要明確的是，unordered_set是K模型的容器，而unordered_map是KV模型的容器，

要想只用一份哈希表代碼同時封裝出K模型和KV模型的容器，我們必定要對哈希表的模板引數進行控制，

為了與原哈希表的模板引數進行區分，這里將哈希表的第二個模板引數的名字改為T，

template<class K, class T>
class HashTable

如果上層使用的是unordered_set容器，那么傳入哈希表的模板引數就是key和key，

template<class K>
class unordered_set
{
public:
	//...
private:
	HashTable<K, K> _ht; //傳入底層哈希表的是K和K
};

但如果上層使用的是unordered_map容器，那么傳入哈希表的模板引數就是key以及key和value構成的鍵值對，

template<class K, class V>
class unordered_map
{
public:
	//...
private:
	HashTable<K, pair<K, V>> _ht; //傳入底層哈希表的是K以及K和V構成的鍵值對
};

也就是說，哈希表中的模板引數T的型別到底是什么，完全卻決于上層所使用容器的種類，
在這里插入圖片描述
而哈希結點的模板引數也應該由原來的K、V變為T：

  • 上層容器是unordered_set時，傳入的T是鍵值，哈希結點中存盤的就是鍵值，
  • 上層容器是unordered_map時，傳入的T是鍵值對，哈希結點中存盤的就是鍵值對，

更改模板引數后，哈希結點的定義如下：

//哈希結點的定義
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	//建構式
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

在哈希映射程序中，我們需要獲得元素的鍵值，然后通過哈希函式計算出對應的哈希地址進行映射，

現在由于我們在哈希結點當中存盤的資料型別是T，這個T可能就是一個鍵值，也可能是一個鍵值對，對于底層的哈希表來說，它并不知道哈希結點當中存盤的資料究竟是什么型別，因此需要由上層容器提供一個仿函式，用于獲取T型別資料當中的鍵值，

因此，unordered_map容器需要向底層哈希表提供一個仿函式，該仿函式回傳鍵值對當中的鍵值，

template<class K, class V>
class unordered_map
{
	//仿函式
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //回傳鍵值對當中的鍵值key
		{
			return kv.first;
		}
	};
public:
	//...
private:
	HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

而雖然unordered_set容器傳入哈希表的T就是鍵值，但是底層哈希表并不知道上層容器的種類，底層哈希表在獲取鍵值時會統一通過傳入的仿函式進行獲取，因此unordered_set容器也需要向底層哈希表提供一個仿函式，

template<class K>
class unordered_set
{
	//仿函式
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //回傳鍵值key
		{
			return key;
		}
	};
public:
	//...
private:
	HashTable<K, K, SetKeyOfT> _ht;
};

因此，底層哈希表的模板引數現在需要增加一個，用于接收上層容器提供的仿函式，

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

string型別無法取模問題

字串無法取模，是哈希問題中最常見的問題，

經過上面的分析后，我們讓哈希表增加了一個模板引數，此時無論上層容器是unordered_set還是unordered_map，我們都能夠通過上層容器提供的仿函式獲取到元素的鍵值，

但是在我們日常撰寫的代碼中，用字串去做鍵值key是非常常見的事，比如我們用unordered_map容器統計水果出現的次數時，就需要用各個水果的名字作為鍵值，

而字串并不是整型，也就意味著字串不能直接用于計算哈希地址，我們需要通過某種方法將字串轉換成整型后，才能代入哈希函式計算哈希地址，

但遺憾的是，我們無法找到一種能實作字串和整型之間一對一轉換的方法，因為在計算機中，整型的大小是有限的，比如用無符號整型能存盤的最大數字是4294967295，而眾多字符能構成的字串的種類卻是無限的，

鑒于此，無論我們用什么方法將字串轉換成整型，都會存在哈希沖突，只是產生沖突的概率不同而已，

經過前輩們實驗后發現，BKDRHash演算法無論是在實際效果還是編碼實作中，效果都是最突出的，該演算法由于在Brian Kernighan與Dennis Ritchie的《The C Programing Language》一書被展示而得名，是一種簡單快捷的hash演算法，也是Java目前采用的字串的hash演算法

因此，現在我們需要在哈希表的模板引數中再增加一個仿函式，用于將鍵值key轉換成對應的整型，

template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable

若是上層沒有傳入該仿函式，我們則使用默認的仿函式，該默認仿函式直接回傳鍵值key即可，但是用字串作為鍵值key是比較常見的，因此我們可以針對string型別寫一個函式模板的特化，此時當鍵值key為string型別時，該仿函式就會根據BKDRHash演算法回傳一個對應的整型，

template<class K>
struct Hash
{
	size_t operator()(const K& key) //回傳鍵值key
	{
		return key;
	}
};
//string型別的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash演算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};

哈希表默認成員函式實作

一、建構式
哈希表中有兩個成員變數，當我們實體化一個物件時：

  • _table會自動呼叫vector的默認建構式進行初始化，
  • _n會根據我們所給的預設值被設定為0，
vector<Node*> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素個數

因此我們不需要撰寫建構式，使用默認生成的建構式就足夠了，但是由于我們后面需要撰寫拷貝建構式，撰寫了拷貝建構式后，默認的建構式就不會生成了，此時我們需要使用default關鍵字顯示指定生成默認建構式，

//建構式
HashTable() = default; //顯示指定生成默認建構式

二、拷貝建構式
哈希表在拷貝時需要進行深拷貝，否則拷貝出來的哈希表和原哈希表中存盤的都是同一批結點，

哈希表的拷貝建構式實作邏輯如下：

  1. 將哈希表的大小調整為ht._table的大小，
  2. 將ht._table每個桶當中的結點一個個拷貝到自己的哈希表中，
  3. 更改哈希表當中的有效資料個數，
//拷貝建構式
HashTable(const HashTable& ht)
{
	//1、將哈希表的大小調整為ht._table的大小
	_table.resize(ht._table.size());
	//2、將ht._table每個桶當中的結點一個個拷貝到自己的哈希表中（深拷貝）
	for (size_t i = 0; i < ht._table.size(); i++)
	{
		if (ht._table[i]) //桶不為空
		{
			Node* cur = ht._table[i];
			while (cur) //將該桶的結點取完為止
			{
				Node* copy = new Node(cur->_data); //創建拷貝結點
				//將拷貝結點頭插到當前桶
				copy->_next = _table[i];
				_table[i] = copy;
				cur = cur->_next; //取下一個待拷貝結點
			}
		}
	}
	//3、更改哈希表當中的有效資料個數
	_n = ht._n;
}

三、賦值運算子多載函式
實作賦值運算子多載函式時，可以通過引數間接呼叫拷貝建構式，之后將拷貝構造出來的哈希表和當前哈希表的兩個成員變數分別進行交換即可，當賦值運算子多載函式呼叫結束后，拷貝構造出來的哈希表會因為出了作用域而被自動析構，此時原哈希表之前的資料也就順勢被釋放了，

//賦值運算子多載函式
HashTable& operator=(HashTable ht)
{
	//交換哈希表中兩個成員變數的資料
	_table.swap(ht._table);
	swap(_n, ht._n);

	return *this; //支持連續賦值
}

四、解構式
因為哈希表當中存盤的結點都是new出來的，因此在哈希表被析構時必須進行結點的釋放，在析構哈希表時我們只需要依次取出非空的哈希桶，遍歷哈希桶當中的結點并進行釋放即可，

//解構式
~HashTable()
{
	//將哈希表當中的結點一個個釋放
	for (size_t i = 0; i < _table.size(); i++)
	{
		if (_table[i]) //桶不為空
		{
			Node* cur = _table[i];
			while (cur) //將該桶的結點取完為止
			{
				Node* next = cur->_next; //記錄下一個結點
				delete cur; //釋放結點
				cur = next;
			}
			_table[i] = nullptr; //將該哈希桶置空
		}
	}
}

哈希表正向迭代器的實作

哈希表的正向迭代器實際上就是對哈希結點指標進行了封裝，但是由于在實作++運算子多載時，可能需要在哈希表中去尋找下一個非空哈希桶，因此每一個正向迭代器中都應該存盤哈希表的地址，

//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
	typedef HashNode<T> Node; //哈希結點的型別
	typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表的型別
	typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的型別

	Node* _node; //結點指標
	HT* _pht; //哈希表的地址
};

因此在構造正向迭代器時，我們不僅需要對應哈希結點的指標，還需要該哈希結點所在哈希表的地址，

//建構式
__HTIterator(Node* node, HT* pht)
	:_node(node) //結點指標
	, _pht(pht) //哈希表地址
{}

當對正向迭代器進行解參考操作時，我們直接回傳對應結點資料的有參考即可，

T& operator*()
{
	return _node->_data; //回傳哈希結點中資料的參考
}

當對正向迭代器進行->操作時，我們直接回傳對應結點資料的地址即可，

T* operator->()
{
	return &_node->_data; //回傳哈希結點中資料的地址
}

當我們需要比較兩個迭代器是否相等時，只需要判斷這兩個迭代器所封裝的結點是否是同一個即可，

bool operator!=(const Self& s) const
{
	return _node != s._node; //判斷兩個結點的地址是否不同
}

bool operator==(const Self& s) const
{
	return _node == s._node; //判斷兩個結點的地址是否相同
}

++運算子多載函式的實作邏輯并不是很難，我們只需要知道如何找到當前結點的下一個結點即可，

  • 若當前結點不是當前哈希桶中的最后一個結點，則++后走到當前哈希桶的下一個結點，
  • 若當前結點是當前哈希桶的最后一個結點，則++后走到下一個非空哈希桶的第一個結點，
//前置++
Self& operator++()
{
	if (_node->_next) //該結點不是當前哈希桶中的最后一個結點
	{
		_node = _node->_next; //++后變為當前哈希桶中的下一個結點
	}
	else //該結點是當前哈希桶中的最后一個結點
	{
		KeyOfT kot;
		HashFunc hf;
		size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通過哈希函式計算出當前所處哈希桶編號index（除數不能是capacity）
		index++; //從下一個位置開始找一個非空的哈希桶
		while (index < _pht->_table.size()) //直到將整個哈希表找完
		{
			if (_pht->_table[index]) //當前哈希桶非空
			{
				_node = _pht->_table[index]; //++后變為當前哈希桶中的第一個結點
				return *this;
			}
			index++; //當前哈希桶為空桶，找下一個哈希桶
		}
		_node = nullptr; //哈希表中已經沒有空桶了，++后變為nullptr
	}
	return *this;
}

注意： 哈希表的迭代器型別是單向迭代器，沒有反向迭代器，即沒有實作–運算子的多載，若是想讓哈希表支持雙向遍歷，可以考慮將哈希桶中存盤的單鏈表結構換為雙鏈表結構，

哈希表結構的其他實作方式

在其他地方可能將插入哈希表的哈希結點統一鏈接到同一個單鏈表上，此時實作哈希表的正向迭代器時就更簡單了，實作++運算子多載時，想要找到下一個結點就直接通過當前結點就可以找到，
在這里插入圖片描述
正向迭代器實作后，我們需要在哈希表的實作當中進行如下操作：

  1. 進行正向迭代器型別的typedef，需要注意的是，為了讓外部能夠使用typedef后的正向迭代器型別iterator，我們需要在public區域進行typedef，
  2. 由于正向迭代器中++運算子多載函式在尋找下一個結點時，會訪問哈希表中的成員變數_table，而_table成員變數是哈希表的私有成員，因此我們需要將正向迭代器類宣告為哈希表類的友元，
  3. 將哈希表中查找函式回傳的結點指標，改為回傳由結點指標和哈希表地址構成的正向迭代器，
  4. 將哈希表中插入函式的回傳值型別，改為由正向迭代器型別和布爾型別所構成的鍵值對，

然后我們就可以在哈希表中實作迭代器相關的成員函式了：

  • begin函式： 回傳哈希表中第一個非空哈希桶中的第一個結點的正向迭代器，
  • end函式： 回傳空指標的正向迭代器，
//哈希表的實作
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{
	//將正向迭代器類宣告為哈希表類的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend struct __HTIterator;

	typedef HashNode<T> Node; //哈希結點型別
public:
	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器的型別

	iterator begin()
	{
		size_t i = 0;
		while (i < _table.size()) //找到第一個非空哈希桶
		{
			if (_table[i]) //該哈希桶非空
			{
				return iterator(_table[i], this); //回傳該哈希桶中的第一個結點的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中無資料，回傳end()
	}
	iterator end()
	{
		return iterator(nullptr, this); //回傳nullptr的正向迭代器
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素個數
};

unordered_set的模擬實作

實作unordered_set的各個介面時，就只需要呼叫底層哈希表對應的介面就行了，

template<class K>
class unordered_set
{
	//仿函式
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //回傳鍵值key
		{
			return key;
		}
	};
public:
	//現在沒有實體化，沒辦法到HashTable里面找iterator，所以typename就是告訴編譯器這里是一個型別，實體化以后再去取
	typedef typename HashTable<K, K, SetKeyOfT>::iterator iterator;

	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}
	//插入函式
	pair<iterator, bool> insert(const K& key)
	{
		return _ht.Insert(key);
	}
	//洗掉函式
	void erase(const K& key)
	{
		_ht.Erase(key);
	}
	//查找函式
	iterator find(const K& key)
	{
		return _ht.Find(key);
	}
private:
	HashTable<K, K, SetKeyOfT> _ht;
};

unordered_map的模擬實作

實作unordered_map的各個介面時，也是呼叫底層哈希表對應的介面就行了，此外還需要實作[]運算子的多載，

template<class K, class V>
class unordered_map
{
	//仿函式
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //回傳鍵值對當中的鍵值key
		{
			return kv.first;
		}
	};
public:
	typedef typename HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;

	iterator begin()
	{
		return _ht.begin();
	}
	iterator end()
	{
		return _ht.end();
	}
	//插入函式
	pair<iterator, bool> insert(const pair<K, V>& kv)
	{
		return _ht.Insert(kv);
	}
	//賦值運算子多載
	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = insert(make_pair(key, V()));
		iterator it = ret.first;
		return it->second;
	}
	//洗掉函式
	void erase(const K& key)
	{
		_ht.Erase(key);
	}
	//查找函式
	iterator find(const K& key)
	{
		return _ht.Find(key);
	}
private:
	HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};

封裝完成后的代碼

哈希表的代碼

//哈希結點的定義
template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	//建構式
	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};
template<class K>
struct Hash
{
	size_t operator()(const K& key) //回傳鍵值key
	{
		return key;
	}
};
//string型別的特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s) //BKDRHash演算法
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};
//哈希表的實作
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class HashTable
{
	//將正向迭代器類宣告為哈希表類的友元
	template<class K, class T, class KeyOfT, class HashFunc>
	friend struct __HTIterator;
	//friend struct __HTIterator<K, T,KeyOfT, HashFunc>;
	typedef HashNode<T> Node; //哈希結點型別
public:
	typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator; //正向迭代器的型別

	iterator begin()
	{
		size_t i = 0;
		while (i < _table.size()) //找到第一個非空哈希桶
		{
			if (_table[i]) //該哈希桶非空
			{
				return iterator(_table[i], this); //回傳該哈希桶中的第一個結點的正向迭代器
			}
			i++;
		}
		return end(); //哈希桶中無資料，回傳end()
	}
	iterator end()
	{
		return iterator(nullptr, this); //回傳nullptr的正向迭代器
	}

	//建構式
	HashTable() = default; //顯示指定生成默認構造

	//拷貝建構式
	HashTable(const HashTable& ht)
	{
		//1、將哈希表的大小調整為ht._table的大小
		_table.resize(ht._table.size());
		//2、將ht._table每個桶當中的結點一個個拷貝到自己的哈希表中（深拷貝）
		for (size_t i = 0; i < ht._table.size(); i++)
		{
			if (ht._table[i]) //桶不為空
			{
				Node* cur = ht._table[i];
				while (cur) //將該桶的結點取完為止
				{
					Node* copy = new Node(cur->_data); //創建拷貝結點
					//將拷貝結點頭插到當前桶
					copy->_next = _table[i];
					_table[i] = copy;
					cur = cur->_next; //取下一個待拷貝結點
				}
			}
		}
		//3、更改哈希表當中的有效資料個數
		_n = ht._n;
	}
	//賦值運算子多載函式
	HashTable& operator=(HashTable ht)
	{
		//交換哈希表中兩個成員變數的資料
		_table.swap(ht._table);
		swap(_n, ht._n);

		return *this; //支持連續賦值
	}
	//解構式
	~HashTable()
	{
		//將哈希表當中的結點一個個釋放
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i]) //桶不為空
			{
				Node* cur = _table[i];
				while (cur) //將該桶的結點取完為止
				{
					Node* next = cur->_next; //記錄下一個結點
					delete cur; //釋放結點
					cur = next;
				}
				_table[i] = nullptr; //將該哈希桶置空
			}
		}
	}
	//獲取本次增容后哈希表的大小
	size_t GetNextPrime(size_t prime)
	{
		const int PRIMECOUNT = 28;
		//素數序列
		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
		};
		size_t i = 0;
		for (i = 0; i < PRIMECOUNT; i++)
		{
			if (primeList[i] > prime)
				return primeList[i];
		}
		return primeList[i];
	}
	//插入函式
	pair<iterator, bool> Insert(const T& data)
	{
		KeyOfT kot;
		//1、查看哈希表中是否存在該鍵值的鍵值對
		iterator ret = Find(kot(data));
		if (ret != end()) //哈希表中已經存在該鍵值的鍵值對（不允許資料冗余）
		{
			return make_pair(ret, false); //插入失敗
		}

		//2、判斷是否需要調整哈希表的大小
		if (_n == _table.size()) //哈希表的大小為0，或負載因子超過1
		{
			//增容
			//a、創建一個新的哈希表，新哈希表的大小設定為原哈希表的2倍（若哈希表大小為0，則將哈希表的初始大小設定為10）
			HashFunc hf;
			vector<Node*> newtable;
			//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
			//newtable.resize(newsize);

			newtable.resize(GetNextPrime(_table.size()));
				
			//b、將原哈希表當中的結點插入到新哈希表
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i]) //桶不為空
				{
					Node* cur = _table[i];
					while (cur) //將該桶的結點取完為止
					{
						Node* next = cur->_next; //記錄cur的下一個結點
						size_t index = hf(kot(cur->_data))%newtable.size(); //通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
						//將該結點頭插到新哈希表中編號為index的哈希桶中
						cur->_next = newtable[index];
						newtable[index] = cur;

						cur = next; //取原哈希表中該桶的下一個結點
					}
					_table[i] = nullptr; //該桶取完后將該桶置空
				}
			}
			//c、交換這兩個哈希表
			_table.swap(newtable);
		}

		//3、將鍵值對插入哈希表
		HashFunc hf;
		size_t index = hf(kot(data)) % _table.size(); //通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
		Node* newnode = new Node(data); //根據所給資料創建一個待插入結點
		//將該結點頭插到新哈希表中編號為index的哈希桶中
		newnode->_next = _table[index];
		_table[index] = newnode;

		//4、哈希表中的有效元素個數加一
		_n++;
		return make_pair(iterator(newnode, this), true);
	}
	//查找函式
	iterator Find(const K& key)
	{
		if (_table.size() == 0) //哈希表大小為0，查找失敗
		{
			return end();
		}

		KeyOfT kot;
		HashFunc hf;
		size_t index = hf(key) % _table.size(); //通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
		//遍歷編號為index的哈希桶
		HashNode<T>* cur = _table[index];
		while (cur) //直到將該桶遍歷完為止
		{
			if (kot(cur->_data) == key) //key值匹配，則查找成功
			{
				return iterator(cur, this);
			}
			cur = cur->_next;
		}
		return end(); //直到該桶全部遍歷完畢還沒有找到目標元素，查找失敗
	}
	//洗掉函式
	bool Erase(const K& key)
	{
		KeyOfT kot;
		HashFunc hf;
		//1、通過哈希函式計算出對應的哈希桶編號index（除數不能是capacity）
		size_t index = hf(key) % _table.size();
		//2、在編號為index的哈希桶中尋找待洗掉結點
		Node* prev = nullptr;
		Node* cur = _table[index];
		while (cur) //直到將該桶遍歷完為止
		{
			if (kot(cur->_data) == key) //key值匹配，則查找成功
			{
				//3、若找到了待洗掉結點，則洗掉該結點
				if (prev == nullptr) //待洗掉結點是哈希桶中的第一個結點
				{
					_table[index] = cur->_next; //將第一個結點從該哈希桶中移除
				}
				else //待洗掉結點不是哈希桶的第一個結點
				{
					prev->_next = cur->_next; //將該結點從哈希桶中移除
				}
				delete cur; //釋放該結點
				//4、洗掉結點后，將哈希表中的有效元素個數減一
				_n--;
				return true; //洗掉成功
			}
			prev = cur;
			cur = cur->_next;
		}
		//假洗掉可能會導致迭代器失效
			
		return false; //直到該桶全部遍歷完畢還沒有找到待洗掉元素，洗掉失敗
	}
private:
	vector<Node*> _table; //哈希表
	size_t _n = 0; //哈希表中的有效元素個數
};

正向迭代器的代碼

//前置宣告
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;

//正向迭代器
template<class K, class T, class KeyOfT, class HashFunc = Hash<K>>
struct __HTIterator
{
	typedef HashNode<T> Node; //哈希結點的型別
	typedef HashTable<K, T, KeyOfT, HashFunc> HT; //哈希表的型別
	typedef __HTIterator<K, T, KeyOfT, HashFunc> Self; //正向迭代器的型別

	Node* _node; //結點指標
	HT* _pht; //哈希表的地址

	//建構式
	__HTIterator(Node* node, HT* pht)
		:_node(node) //結點指標
		, _pht(pht) //哈希表地址
	{}

	T& operator*()
	{
		return _node->_data; //回傳哈希結點中資料的參考
	}

	T* operator->()
	{
		return &_node->_data; //回傳哈希結點中資料的地址
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node; //判斷兩個結點的地址是否不同
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node; //判斷兩個結點的地址是否相同
	}

	//前置++
	Self& operator++()
	{
		if (_node->_next) //該結點不是當前哈希桶中的最后一個結點
		{
			_node = _node->_next; //++后變為當前哈希桶中的下一個結點
		}
		else //該結點是當前哈希桶中的最后一個結點
		{
			KeyOfT kot;
			HashFunc hf;
			size_t index = hf(kot(_node->_data)) % _pht->_table.size(); //通過哈希函式計算出當前所處哈希桶編號index（除數不能是capacity）
			index++; //從下一個位置開始找一個非空的哈希桶
			while (index < _pht->_table.size()) //直到將整個哈希表找完
			{
				if (_pht->_table[index]) //當前哈希桶非空
				{
					_node = _pht->_table[index]; //++后變為當前哈希桶中的第一個結點
					return *this;
				}
				index++; //當前哈希桶為空桶，找下一個哈希桶
			}
			_node = nullptr; //哈希表中已經沒有空桶了，++后變為nullptr
		}
		return *this;
	}
};

unordered_set的代碼

namespace cl //防止命名沖突
{
	template<class K>
	class unordered_set
	{
		//仿函式
		struct SetKeyOfT
		{
			const K& operator()(const K& key) //回傳鍵值key
			{
				return key;
			}
		};
	public:
		//現在沒有實體化，沒辦法到HashTable里面找iterator，所以typename就是告訴編譯器這里是一個型別，實體化以后再去取
		typedef typename HashTable<K, K, SetKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		//插入函式
		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}
		//洗掉函式
		void erase(const K& key)
		{
			_ht.Erase(key);
		}
		//查找函式
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
	private:
		HashTable<K, K, SetKeyOfT> _ht;
	};
}

unordered_map的代碼

namespace cl //防止命名沖突
{
	template<class K, class V>
	class unordered_map
	{
		//仿函式
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv) //回傳鍵值對當中的鍵值key
			{
				return kv.first;
			}
		};
	public:
		typedef typename HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;

		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		//插入函式
		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}
		//賦值運算子多載
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			iterator it = ret.first;
			return it->second;
		}
		//洗掉函式
		void erase(const K& key)
		{
			_ht.Erase(key);
		}
		//查找函式
		iterator find(const K& key)
		{
			return _ht.Find(key);
		}
	private:
		HashTable<K, pair<K, V>, MapKeyOfT> _ht;
	};
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413429.html

標籤：其他

上一篇：資料結構--TopK問題

下一篇：C*指標進階（2）

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 2023年最新微信小程式抓包教程

    01 開門見山 隔一個月發一篇文章，不過分。 首先回顧一下《微信系結手機號資料庫被脫庫事件》，我也是第一時間得知了這個訊息，然后跟蹤了整件事情的經過。下面是這起事件的相關截圖以及近日流出的一萬條資料樣本： 個人認為這件事也沒什么，還不如關注一下之前45億快遞資料查詢渠道疑似在近日復活的訊息。 訊息是 ......

    uj5u.com 2023-04-20 08:48:24 more
  • web3 產品介紹：metamask 錢包 使用最多的瀏覽器插件錢包

    Metamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......

    uj5u.com 2023-04-20 08:47:46 more
  • vulnhub_Earth

    前言 靶機地址->>>vulnhub_Earth 攻擊機ip：192.168.20.121 靶機ip：192.168.20.122 參考文章 https://www.cnblogs.com/Jing-X/archive/2022/04/03/16097695.html https://www.cnb ......

    uj5u.com 2023-04-20 07:46:20 more
  • 從4k到42k，軟體測驗工程師的漲薪史，給我看哭了

    清明節一過，盲猜大家已經無心上班，在數著日子準備過五一，但一想到銀行卡里的余額……瞬間心情就不美麗了。最近，2023年高校畢業生就業調查顯示，本科畢業月平均起薪為5825元。調查一出，便有很多同學表示自己又被平均了。看著這一資料，不免讓人想到前不久中國青年報的一項調查：近六成大學生認為畢業10年內會 ......

    uj5u.com 2023-04-20 07:44:00 more
  • 最新版本 Stable Diffusion 開源 AI 繪畫工具之中文自動提詞篇

    🎈 標簽生成器 由于輸入正向提示詞 prompt 和反向提示詞 negative prompt 都是使用英文，所以對學習母語的我們非常不友好 使用網址：https://tinygeeker.github.io/p/ai-prompt-generator 這個網址是為了讓大家在使用 AI 繪畫的時候 ......

    uj5u.com 2023-04-20 07:43:36 more
  • 漫談前端自動化測驗演進之路及測驗工具分析

    隨著前端技術的不斷發展和應用程式的日益復雜，前端自動化測驗也在不斷演進。隨著 Web 應用程式變得越來越復雜，自動化測驗的需求也越來越高。如今，自動化測驗已經成為 Web 應用程式開發程序中不可或缺的一部分，它們可以幫助開發人員更快地發現和修復錯誤，提高應用程式的性能和可靠性。 ......

    uj5u.com 2023-04-20 07:43:16 more
  • CANN開發實踐：4個DVPP記憶體問題的典型案例解讀

    摘要：由于DVPP媒體資料處理功能對存放輸入、輸出資料的記憶體有更高的要求（例如，記憶體首地址128位元組對齊），因此需呼叫專用的記憶體申請介面，那么本期就分享幾個關于DVPP記憶體問題的典型案例，并給出原因分析及解決方法。 本文分享自華為云社區《FAQ_DVPP記憶體問題案例》，作者：昇騰CANN。 DVPP ......

    uj5u.com 2023-04-20 07:43:03 more
  • msf學習

    msf學習 以kali自帶的msf為例 一、msf核心模塊與功能 msf模塊都放在/usr/share/metasploit-framework/modules目錄下 1、auxiliary 輔助模塊，輔助滲透（埠掃描、登錄密碼爆破、漏洞驗證等） 2、encoders 編碼器模塊，主要包含各種編碼 ......

    uj5u.com 2023-04-20 07:42:59 more
  • Halcon軟體安裝與界面簡介

    1. 下載Halcon17版本到到本地 2. 雙擊安裝包后 3. 步驟如下 1.2 Halcon軟體安裝 界面分為四大塊 1. Halcon的五個助手 1) 影像采集助手：與相機連接，設定相機引數，采集影像 2) 標定助手：九點標定或是其它的標定，生成標定檔案及內參外參，可以將像素單位轉換為長度單位 ......

    uj5u.com 2023-04-20 07:42:17 more
  • 在MacOS下使用Unity3D開發游戲

    第一次發博客，先發一下我的游戲開發環境吧。 去年2月份買了一臺MacBookPro2021 M1pro(以下簡稱mbp)，這一年來一直在用mbp開發游戲。我大致分享一下我的開發工具以及使用體驗。 1、Unity 官網鏈接： https://unity.cn/releases 我一般使用的Apple ......

    uj5u.com 2023-04-20 07:40:19 more

Copyright © 2010-2020 有解無憂