C++下“hash“的簡單模拟實作以及實作中遇見的問題

目錄

• 1.線性探測
• 2.二次探測
• 3.載荷因子
• 4.擴容
• • 擴容一：
• 5.删除（查找，删除，判斷狀态）
• 6.插入特殊值時
• • 初試（字元串）
  • BKDR（解決字元串）
  • BKDR之後的負數和int
  • 預設的不需要傳第三個參數
• 7.哈希沖突
• 8.開散列
• • insert
  • Erase
  • 開散列整體代碼
• 9.key對象的要求
• 10.套用map和set
• • insert套用
  • ++
  • • UnorderedSet.h
    • UnorderedMap.h
    • HashTable.h
  • map[]
  • 拷貝構造
  • 深拷貝
  • 析構函數
• 11.延伸：擴容
• 12.最終代碼
• • UnorderedSet.h
  • UnorderedSet.h
  • HashTable.h

1.線性探測

bool Insert(const pair<K, V>& kv)
	{
		size_t start = kv.first % _tables.size();
		size_t i = 0;
		size_t index = start + i;
		while (_tables[index].first == EXITS)
		{
			i++;
			index = start + i;
			index %= _tables;
		}

		_tables[index]._kv = kv;
		_table[index]._status = EXIST;
		++_n;

	}
           

2.二次探測

bool Insert(const pair<K, V>& kv)
	{
		size_t start = kv.first % _tables.size();
		size_t i = 0;
		size_t index = start + i;
		while (_tables[index].first == EXITS)
		{
			i++;
			index = start + i*i;
			index %= _tables;
		}

		_tables[index]._kv = kv;
		_table[index]._status = EXIST;
		++_n;

	}
           

3.載荷因子

引入：當線性探測和二次探測中，清單中的值滿了，或者将近滿的時候，會導緻效率降低

問題：哈希表什麼情況下進行擴容？如何擴容？

散清單的載荷因子定義為：α=填入表中的元素個數/散清單的長度

α 是散清單裝滿程度的标志因子，由于表長是定值，α與“填入表中的元素個數”成正比，是以α越大，表明填入表中的元素越多，産生沖突的可能性就越大；反之，α越小，表明填入表中的元素越少，産生沖突的可能性就越小，實際上，散清單的平均查找長度是載荷因子的α的函數，隻是不同處理沖突的方法有不同的函數。

對于開放定址法，載荷因子是特别重要因素，應嚴格限制在 0.7到0.8以下，超多0.8，查表時的CPU緩存不命中按照指數曲線上升，是以，一些采用開放定址法的hash庫，如Java的系統庫限制了載荷因子為0.75，超過此值将resize散清單。

4.擴容

bool Insert(const pair<K, V>& kv)
	{
		//負載因子到0.7，擴容
		//負載因子越小，沖突機率越低，效率越高，空間浪費越多
		//負載因子越大，沖突機率越高，效率越低，空間浪費越少
		if (_tables.size()==0 || _n*10 / _tables.size() >= 7)
		{
			//擴容
			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
			//如何擴容
		}

		//線性探測和二次探測代碼省略。。。
	}
           

問題：當我們擴容時，原來的資料該如何？

擴容一：

#pragma once
#include<vector>

enum Status
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K, class V>
struct HashData
{
	pair<K, V> _kv;
	Status _status = EMPTY;
};



template<class K, class V>
class HashTable
{
public:
	bool Insert(const pair<K, V>& kv)
	{
		//負載因子到0.7，擴容
		//負載因子越小，沖突機率越低，效率越高，空間浪費越多
		//負載因子越大，沖突機率越高，效率越低，空間浪費越少
		if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
		{
			//擴容
			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

			HashTable<K, V> newHT;
			newHT._tables.resize(newSize);
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]._status == EXIST)
				{
					newHT.Insert(_tables[i]._kv);
				}
			}
			_tables.swap(newHT._tables);
		}

		size_t start = kv.first % _tables.size();
		size_t i = 0;
		size_t index = start;
		while (_tables[index]._status == EXIST)
		{
			++i;
			//index = start + i * i;//二次探測
			index = start + i;//線性探測
			index %= _tables.size();
		}

		_tables[index]._kv = kv;
		_tables[index]._status = EXIST;
		++_n;

		return true;
	}

private:
	vector<HashData<K, V>> _tables;
	size_t _n = 0;//有效資料個數
};

void TestHashTables()
{
	HashTable<int, int> ht;
	int a[] = { 2, 12, 22, 32, 42, 52, 62 };
	for (auto e : a)
	{
		ht.Insert(make_pair(e, e));
	}
	ht.Insert(make_pair(72, 72));

}
           

5.删除（查找，删除，判斷狀态）

#pragma once
#include<vector>

enum Status
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	Status _status = EMPTY;
};



template<class K, class V>
class HashTable
{
public:
	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_status = DELETE;
			--_n;
			return true;
		}
		return false;
	}

	HashData<K, V>* Find(const K& key)
	{
		if (_tables.size() == 0)
			return nullptr;
		size_t start = key % _tables.size();
		size_t i = 0;
		size_t index = start;
		while (_tables[index]._status != EMPTY)
		{
			if (_tables[index]._kv.first == key && _tables[index]._status==EXIST)
			{
				return &_tables[index];
			}
			++i;
			//index = start + i * i;//二次探測
			index = start + i;//線性探測
			index %= _tables.size();
		}
		return nullptr;
	}


	bool Insert(const pair<K, V>& kv)
	{
		//負載因子到0.7，擴容
		//負載因子越小，沖突機率越低，效率越高，空間浪費越多
		//負載因子越大，沖突機率越高，效率越低，空間浪費越少
		if (_tables.size()==0 || _n*10 / _tables.size() >= 7)
		{
			//擴容
			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

			HashTable<K, V> newHT;
			newHT._tables.resize(newSize);
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]._status == EXIST)
				{
					newHT.Insert(_tables[i]._kv);
				}
			}
			_tables.swap(newHT._tables);
		}

		size_t start = kv.first % _tables.size();
		size_t i = 0;
		size_t index = start;
		while (_tables[index]._status == EXIST)
		{
			++i;
			//index = start + i * i;//二次探測
			index = start + i;//線性探測
			index %= _tables.size();
		}

		_tables[index]._kv = kv;
		_tables[index]._status = EXIST;
		++_n;

		return true;
	}

private:
	vector<HashData<K, V>> _tables;
	size_t _n=0;//有效資料個數
};

void TestHashTables()
{
	HashTable<int, int> ht;
	int a[] = { 2,12,22,32,42,52,62 }; 
	for (auto e : a)
	{
		ht.Insert(make_pair(e,e));
	}
	ht.Insert(make_pair(72, 72));
	ht.Insert(make_pair(42,42));//測試查找重複值

	cout << ht.Find(12) << endl;
	ht.Erase(12);
	cout << ht.Find(12) << endl;
}
           

6.插入特殊值時

初試（字元串）

當插入的是字元串時，

struct HashStr
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value += ch;
		}
		return value;
	}
};

void Hashstring()
{
	HashStr hs;
	cout << hs("left") << endl;
	cout << hs("right") << endl;
	cout << hs("abcd") << endl;
	cout << hs("aadd") << endl;
	cout << hs("acbd") << endl;
}
           

缺點：

BKDR（解決字元串）

struct HashStr
{
	size_t operator()(const string& s)
	{
		//BKDR
		size_t value=0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
void Hashstring()
{
	HashStr hs;
	cout << hs("left") << endl;
	cout << hs("right") << endl;
	cout << hs("abcd") << endl;
	cout << hs("aadd") << endl;
	cout << hs("acbd") << endl;
}
           

BKDR之後的負數和int

/begin//

此處為相比之前的修改或難點

//end

#pragma once
#include<vector>

enum Status
{
	EXIST,
	EMPTY,
	DELETE
};

template<class K,class V>
struct HashData
{
	pair<K, V> _kv;
	Status _status = EMPTY;
};
//begin/
template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
//end/

struct HashStr
{
	size_t operator()(const string& s)
	{
		//BKDR
		size_t value=0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};
/begin//
template<class K, class V, class HashFunc>
/end//
class HashTable
{
public:
	bool Erase(const K& key)
	{
		HashData<K, V>* ret = Find(key);
		if (ret)
		{
			ret->_status = DELETE;
			--_n;
			return true;
		}
		return false;
	}

	HashData<K, V>* Find(const K& key)
	{
		if (_tables.size() == 0)
			return nullptr;

		HashFunc hf;
		size_t start = hf(key) % _tables.size();
		size_t i = 0;
		size_t index = start;
		while (_tables[index]._status != EMPTY)
		{
			if (_tables[index]._kv.first == key && _tables[index]._status==EXIST)
			{
				return &_tables[index];
			}
			++i;
			//index = start + i * i;//二次探測
			index = start + i;//線性探測
			index %= _tables.size();
		}
		return nullptr;
	}


	bool Insert(const pair<K, V>& kv)
	{
		//負載因子到0.7，擴容
		//負載因子越小，沖突機率越低，效率越高，空間浪費越多
		//負載因子越大，沖突機率越高，效率越低，空間浪費越少
		if (_tables.size()==0 || _n*10 / _tables.size() >= 7)
		{
			//擴容
			size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

			HashTable<K, V,HashFunc> newHT;
			newHT._tables.resize(newSize);
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				if (_tables[i]._status == EXIST)
				{
					newHT.Insert(_tables[i]._kv);
				}
			}
			_tables.swap(newHT._tables);
		}

		HashFunc hf;
		size_t start = hf(kv.first) % _tables.size();
		size_t i = 0;
		size_t index = start;
		while (_tables[index]._status == EXIST)
		{
			++i;
			//index = start + i * i;//二次探測
			index = start + i;//線性探測
			index %= _tables.size();
		}

		_tables[index]._kv = kv;
		_tables[index]._status = EXIST;
		++_n;

		return true;
	}

private:
	vector<HashData<K, V>> _tables;
	size_t _n=0;//有效資料個數
};

void test3()
{
	Hash<int> hint;
	cout << hint(-9) << endl;
	cout << hint(9) << endl;
}

           

當傳入int時，也可以隐式類型轉化

預設的不需要傳第三個參數

采用特化

//特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s)
	{
		//BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}

};

//struct HashStr
//{
//	size_t operator()(const string& s)
//	{
//		//BKDR
//		size_t value=0;
//		for (auto ch : s)
//		{
//			value *= 31;
//			value += ch;
//		}
//		return value;
//	}
//};

//...

void test4()
{
	HashTable<string, string> ht;
	ht.Insert(make_pair("red", "紅色"));
	ht.Insert(make_pair("blue", "藍色"));
}
           

7.哈希沖突

閉散列/開放定址法：不同位置沖突的資料會互相影響，相鄰位置的沖突會争搶位置，互相影響效率。

優化

開散列/拉鍊法/哈希桶：相鄰位置沖突，不會再争搶位置，不會互相影響

控制負載因子–負載因子到了就擴容

極端場景防止一個桶位置沖突太多，連結清單太長

當一個桶長度超過一定值以後，轉化紅黑樹

補充：不僅可以尾插，也可以頭插，頭插更友善點。

8.開散列

思路參考上一個标題“哈希沖突”，不同點：這裡是頭插

insert

namespace LinkHash
{
	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next = nullptr;

		HashNode(const pair<K,V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

	//特化
	template<>
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			//BKDR
			size_t value = 0;
			for (auto ch : s)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}

	};


	template<class K,class V,class HashFunc = Hash<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:

		Node* Find(const K& key)
		{
			if (_tables.empty())
				return nullptr;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}
		bool Insert(const pair<K, V>& kv)
		{
			Node* ret = Find(kv.first);
			if (ret)
				return false;
			if (_n ==  _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();

				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						Node* next = cur->_next;
						HashFunc hf;
						size_t index = hf(cur->_kv.first) % newTables.size();
						//頭插，效率比較高
						cur->_next = newTables[index];
						newTables[index] = cur;

						cur = next;

					}
					_tables[i] = nullptr;
				}
				newTables.swap(_tables);
			}
			HashFunc hf;
			size_t index = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			//頭插
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;
			return true;
		}

	private:
		vector<Node*> _tables;
		size_t _n=0;//有效資料個數
	};

	void TestHashTable()
	{
		int a[] = { 2,12,22,32,42,52,62,72,82,5,15,25};
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e,e));
		}

		ht.Insert(make_pair(1, 1));
	}
}
           

Erase

bool Erase(const K& key)
		{
			if (_tables.empty())
				return false;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr) {
						//頭删
						_tables[index] = cur->_next;
					}
					else {
						//中間删除and尾删
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
           

開散列整體代碼

namespace LinkHash
{
	template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* _next = nullptr;

		HashNode(const pair<K,V>& kv)
			:_kv(kv)
			,_next(nullptr)
		{}
	};
	template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

	//特化
	template<>
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			//BKDR
			size_t value = 0;
			for (auto ch : s)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}

	};


	template<class K,class V,class HashFunc = Hash<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	public:
		bool Erase(const K& key)
		{
			if (_tables.empty())
				return false;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					if (prev == nullptr) {
						//頭删
						_tables[index] = cur->_next;
					}
					else {
						//中間删除and尾删
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		Node* Find(const K& key)
		{
			if (_tables.empty())
				return nullptr;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}
		bool Insert(const pair<K, V>& kv)
		{
			Node* ret = Find(kv.first);
			if (ret)
				return false;
			if (_n ==  _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();

				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						Node* next = cur->_next;
						HashFunc hf;
						size_t index = hf(cur->_kv.first) % newTables.size();
						//頭插，效率比較高
						cur->_next = newTables[index];
						newTables[index] = cur;

						cur = next;

					}
					_tables[i] = nullptr;
				}
				newTables.swap(_tables);
			}
			HashFunc hf;
			size_t index = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			//頭插
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;
			return true;
		}

	private:
		vector<Node*> _tables;
		size_t _n=0;//有效資料個數
	};

	void TestHashTable()
	{
		int a[] = { 2,12,22,32,42,52,62,72,82,5,15,25};
		HashTable<int, int> ht;
		for (auto e : a)
		{
			ht.Insert(make_pair(e,e));
		}

		ht.Insert(make_pair(1, 1));
	}
}
           

9.key對象的要求

10.套用map和set

insert套用

#pragma once
#include"HashTable.h"

namespace sakeww
{
	template<class K,class hash= Hash<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}

	private:
		LinkHash::HashTable<K, K,SetKeyOfT,hash> _ht;
	};
}
           

#pragma once
#include"HashTable.h"

namespace sakeww
{
	template<class K,class V,class hash = Hash<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

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

	private:
		LinkHash::HashTable<K, pair<K, V>,MapKeyOfT,hash> _ht;
	};
}

           

++

困難點：

UnorderedSet ，HashTale二者要互相調用對方的命名空間

++的模拟實作

因為使用的是單向連結清單，是以隻能++，不能 減減

UnorderedSet.h

#pragma once
#include"HashTable.h"

namespace sakeww
{
	template<class K,class hash= Hash<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename LinkHash::HashTable<K, K, SetKeyOfT, hash>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		
		bool insert(const K& key)
		{
			return _ht.Insert(key);
		}

	private:
		LinkHash::HashTable<K, K,SetKeyOfT,hash> _ht;
	};
	
	void test2()
	{
		unordered_set<int> us;
		us.insert(2);
		us.insert(22);
		us.insert(12);
		us.insert(32);
		us.insert(42);
		us.insert(2);
		us.insert(33);
		us.insert(45);

		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
}
           

UnorderedMap.h

#pragma once
#include "HashTable.h"

namespace sakeww
{
	template<class K, class V, class hash = Hash<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash>::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);
		}

	private:
		LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash> _ht;
	};
	void testMap()
	{
		unordered_map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("string", "字元串"));
		dict.insert(make_pair("map", "地圖"));
		cout << dict["sort"] << endl;//充當查找
		cout << dict["left"] << endl;//插入
		dict["right"] = "右邊";//插入和修改

		unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
	}
}
           

HashTable.h

namespace LinkHash
{
	template<class T>
	struct HashNode
	{
		T _data;
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			,_next(nullptr)
		{}
	};
begin//
	template<class K, class T, class KeyOfT, class HashFunc>
	class HashTable;
///end///
	template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;
		 
		Node* _node; 
		HashTable<K, T, KeyOfT, HashFunc>* _pht;

		__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Ref& operator*()
		{
			return _node->_data;
		}
		Ptr& operator->()
		{
			return &_node->_data;
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t index = hf(kot(_node->_data)) % _pht->_tables.size();
				++index;

				// 找下一個不為空的桶
				while (index< _pht->_tables.size()) //_pht->_tables.size()表的大小
				{
					if (_pht->_tables[index])
					{
						break;
					}
					else
						++index;
				}

				if (index == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[index];
				}
			}
			return *this;
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};



	template<class K,class T,class KeyOfT,class HashFunc>
	class HashTable
	{
		typedef HashNode<T> Node;
/begin/
		template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
		friend struct __HTIterator;
//end
	public:
		typedef __HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i],this);
				}
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}

		bool Erase(const K& key)
		{
			if (_tables.empty())
				return false;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr) {
						//頭删
						_tables[index] = cur->_next;
					}
					else {
						//中間删除and尾删
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		Node* Find(const K& key)
		{
			if (_tables.empty())
				return nullptr;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)
					return cur;
				cur = cur->_next;
			}
			return nullptr;
		}
		bool Insert(const T& data)
		{
			KeyOfT kot;
			Node* ret = Find(kot(data));
			if (ret)
				return false;
			if (_n ==  _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();

				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						Node* next = cur->_next;
						HashFunc hf;
						size_t index = hf(kot(cur->_data)) % newTables.size();
						//頭插，效率比較高
						cur->_next = newTables[index];
						newTables[index] = cur;

						cur = next;

					}
					_tables[i] = nullptr;
				}
				newTables.swap(_tables);
			}
			HashFunc hf;
			size_t index = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			//頭插
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;
			return true;
		}

	private:
		vector<Node*> _tables;
		size_t _n=0;//有效資料個數
	};


}
           

map[]

V& operator[](const K& key)
		{
			auto ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}
           

将傳回值改為疊代器

iterator Find(const K& key)
		{
			if (_tables.empty())
				return end();

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)
					return iterator(cur, this);
				else
					cur = cur->_next;
			}
			return end();
		}
           

将傳回值改為 pair<iterator,bool> 類型

pair<iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			iterator ret = Find(kot(data));
			if (ret != end())
				return make_pair(ret,false);
			if (_n ==  _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : 2 * _tables.size();

				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					Node* cur = _tables[i];
					while(cur)
					{
						Node* next = cur->_next;
						HashFunc hf;
						size_t index = hf(kot(cur->_data)) % newTables.size();
						//頭插，效率比較高
						cur->_next = newTables[index];
						newTables[index] = cur;

						cur = next;

					}
					_tables[i] = nullptr;
				}
				newTables.swap(_tables);
			}
			HashFunc hf;
			size_t index = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			//頭插
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;
			return make_pair(iterator(newnode,this), true);
		}
           

拷貝構造

HashTable(const HashTable<K, T, KeyOfT, HashFunc>& ht)
		{
			_tables.resize(ht._tables.size());
			for (size_t i = 0; i < ht._tables.size(); ++i)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					copy->_next = _tables[i];
					_tables[i] = copy;
					cur = cur->_next;
				}
			}
		}
           

因為自己已經寫了拷貝構造函數，是以系統就不會預設生成一份拷貝構造函數

那麼

private:
		vector<Node*> _tables;
		size_t _n=0;//有效資料個數
           

系統就不會預設生成一份，

解決：

//方法一：
		//初始化清單，
		//HashTable()
		//{}

		//方法二：
		//顯示指定編譯器去生成預設構造函數
		HashTable() = default;

		HashTable(const HashTable<K, T, KeyOfT, HashFunc>& ht)
		{
			_tables.resize(ht._tables.size());
			for (size_t i = 0; i < ht._tables.size(); ++i)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					copy->_next = _tables[i];
					_tables[i] = copy;
					cur = cur->_next;
				}
			}
		}
           

深拷貝

//可以不寫模闆參數，拷貝構造和指派可以不寫
		//const HashTable<K, T, KeyOfT, HashFunc>& operator=(const HashTable<K, T, KeyOfT, HashFunc>)
		Self& operator=(Self copy)
		{
			swap(_n, copy._n);
			_tables.swap(copy._tables);
			return *this;
		}
           

析構函數

~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;
			}
		}
           

11.延伸：擴容

hash的大小為素數最好（大佬證明的）

那麼擴容時，應該如何擴容？

size_t GetNextPrime(size_t num)
		{
			static const unsigned long __stl_prime_list[28] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (size_t i = 0; i < 28; ++i)
			{
				if (__stl_prime_list[i] > num)
				{
					return __stl_prime_list[i];
				}
			}

			return __stl_prime_list[27];
		}

		pair<iterator, bool> Insert(const T& data)
		{
			KeyOfT kot;
			iterator ret = Find(kot(data));
			if (ret != end())
				return make_pair(ret, false);

			HashFunc hf;
			// 負載因子 == 1時擴容
			if (_n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());
				
				if (newSize > _tables.size())
				{
					vector<Node*> newTables;
					newTables.resize(newSize);
					for (size_t i = 0; i < _tables.size(); ++i)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;

							size_t index = hf(kot(cur->_data)) % newTables.size();
							// 頭插
							cur->_next = newTables[index];
							newTables[index] = cur;

							cur = next;
						}

						_tables[i] = nullptr;
					}

					_tables.swap(newTables);
				}
			}


			size_t index = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			// 頭插
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;
			return make_pair(iterator(newnode, this), false);;
		}
           

12.最終代碼

UnorderedSet.h

#pragma once
#include"HashTable.h"

namespace sakeww
{
	template<class K,class hash= Hash<K>>
	class unordered_set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename LinkHash::HashTable<K, K, SetKeyOfT, hash>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}
		iterator end()
		{
			return _ht.end();
		}
		
		pair<iterator, bool> insert(const K& key)
		{
			return _ht.Insert(key);
		}

	private:
		LinkHash::HashTable<K, K,SetKeyOfT,hash> _ht;
	};

	void test1()
	{
		unordered_set<int> us;
		us.insert(2);
		us.insert(22);
		us.insert(12);
		us.insert(32);
		us.insert(42);
		us.insert(2);
		us.insert(33);
		us.insert(45);
		
		unordered_set<string> uss;
		uss.insert("left");
		uss.insert("right");
		uss.insert("red");
	}
	void test2()
	{
		unordered_set<int> us;
		us.insert(2);
		us.insert(22);
		us.insert(12);
		us.insert(32);
		us.insert(42);
		us.insert(2);
		us.insert(33);
		us.insert(45);

		unordered_set<int>::iterator it = us.begin();
		while (it != us.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;


		unordered_set<int> copy(us);
		unordered_set<int>::iterator cit = copy.begin();
		while (cit != us.end())
		{
			cout << *cit << " ";
			++cit;
		}
		cout << endl;
	}
}


           

UnorderedSet.h

#pragma once
#include "HashTable.h"

namespace sakeww
{
	template<class K, class V, class hash = Hash<K>>
	class unordered_map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash>::iterator iterator;
		iterator begin()
		{
			return _ht.begin();
		}

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

		V& operator[](const K& key)
		{
			auto ret = _ht.Insert(make_pair(key, V()));
			return ret.first->second;
		}

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

	private:
		LinkHash::HashTable<K, pair<K, V>, MapKeyOfT, hash> _ht;
	};
	void testMap()
	{
		unordered_map<string, string> dict;
		dict.insert(make_pair("sort", "排序"));
		dict.insert(make_pair("string", "字元串"));
		dict.insert(make_pair("map", "地圖"));
		cout << dict["sort"] << endl;//充當查找
		cout << dict["left"] << endl;//插入
		dict["right"] = "右邊";//插入和修改

		unordered_map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;

		unordered_map<string, string> copy(dict);
		for (auto& kv : copy)
		{
			cout << kv.first <<":" << kv.second << endl;
		}

	}
}

           

HashTable.h

#pragma once
#include<vector>

namespace CloseHash
{
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		Status _status = EMPTY;
	};

	template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};

	//特化
	template<>
	struct Hash<string>
	{
		size_t operator()(const string& s)
		{
			//BKDR
			size_t value = 0;
			for (auto ch : s)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}

	};

	//struct HashStr
	//{
	//	size_t operator()(const string& s)
	//	{
	//		//BKDR
	//		size_t value=0;
	//		for (auto ch : s)
	//		{
	//			value *= 31;
	//			value += ch;
	//		}
	//		return value;
	//	}
	//};

	template<class K, class V, class HashFunc = Hash<K>>
	class HashTable
	{
	public:
		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);
			if (ret)
			{
				ret->_status = DELETE;
				--_n;
				return true;
			}
				
			return false;
		}

		HashData<K, V>* Find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;

			HashFunc hf;
			size_t start = hf(key) % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status != EMPTY)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == EXIST)
				{
					return &_tables[index];
				}
				++i;
				//index = start + i * i;//二次探測
				index = start + i;//線性探測
				index %= _tables.size();
			}
			return nullptr;
		}


		bool Insert(const pair<K, V>& kv)
		{
			//負載因子到0.7，擴容
			//負載因子越小，沖突機率越低，效率越高，空間浪費越多
			//負載因子越大，沖突機率越高，效率越低，空間浪費越少
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				//擴容
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;

				HashTable<K, V, HashFunc> newHT;
				newHT._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					if (_tables[i]._status == EXIST)
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			HashFunc hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start;
			while (_tables[index]._status == EXIST)
			{
				++i;
				//index = start + i * i;//二次探測
				index = start + i;//線性探測
				index %= _tables.size();
			}

			_tables[index]._kv = kv;
			_tables[index]._status = EXIST;
			++_n;

			return true;
		}

	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//有效資料個數
	};

	void TestHashTables()
	{
		HashTable<int, int> ht;
		int a[] = { 2,12,22,32,42,52,62 };
		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}
		ht.Insert(make_pair(72, 72));
		ht.Insert(make_pair(42, 42));

		cout << ht.Find(12) << endl;
		ht.Erase(12);
		cout << ht.Find(12) << endl;

		ht.Insert(make_pair(-1, -1));
		ht.Insert(make_pair(-5, -5));
	}

	//void Hashstring()
	//{
	//	HashStr hs;
	//	cout << hs("left") << endl;
	//	cout << hs("right") << endl;
	//	cout << hs("abcd") << endl;
	//	cout << hs("aadd") << endl;
	//	cout << hs("acbd") << endl;
	//
	//	HashTable<string, string, HashStr> ht;
	//	ht.Insert(make_pair("red", "紅色"));
	//	ht.Insert(make_pair("blue", "藍色"));
	//}

	void test3()
	{
		Hash<int> hint;
		cout << hint(-9) << endl;
		cout << hint(9) << endl;
	}

	void test4()
	{
		HashTable<string, string> ht;
		ht.Insert(make_pair("red", "紅色"));
		ht.Insert(make_pair("blue", "藍色"));
	}
}

template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

//特化
template<>
struct Hash<string>
{
	size_t operator()(const string& s)
	{
		//BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}

};

namespace LinkHash
{
	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 HashFunc>
	class HashTable;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
	struct __HTIterator
	{
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> Self;
		 
		Node* _node; 
		HashTable<K, T, KeyOfT, HashFunc>* _pht;

		__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Ref& operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}

		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				HashFunc hf;
				size_t index = hf(kot(_node->_data)) % _pht->_tables.size();
				++index;

				// 找下一個不為空的桶
				while (index< _pht->_tables.size()) //_pht->_tables.size()表的大小
				{
					if (_pht->_tables[index])
					{
						break;
					}
					else
						++index;
				}

				if (index == _pht->_tables.size())
				{
					_node = nullptr;
				}
				else
				{
					_node = _pht->_tables[index];
				}
			}
			return *this;
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}
	};



	template<class K,class T,class KeyOfT,class HashFunc>
	class HashTable
	{
		typedef HashNode<T> Node;

		template<class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
		friend struct __HTIterator; 

		typedef HashTable<K, T, KeyOfT, HashFunc> Self;
	public:
		typedef __HTIterator<K, T, T&, T*, KeyOfT, HashFunc> iterator;

		//初始化清單，
		//HashTable()
		//{}

		//顯示指定編譯器去生成預設構造函數
		HashTable() = default;

		HashTable(const HashTable<K, T, KeyOfT, HashFunc>& ht)
		{
			_tables.resize(ht._tables.size());
			for (size_t i = 0; i < ht._tables.size(); ++i)
			{
				Node* cur = ht._tables[i];
				while (cur)
				{
					Node* copy = new Node(cur->_data);
					copy->_next = _tables[i];
					_tables[i] = copy;
					cur = cur->_next;
				}
			}
		}

		//可以不寫模闆參數，拷貝構造和指派可以不寫
		//const HashTable<K, T, KeyOfT, HashFunc>& operator=(const HashTable<K, T, KeyOfT, HashFunc>)
		Self& operator=(Self copy)
		{
			swap(_n, copy._n);
			_tables.swap(copy._tables);
			return *this;
		}

		~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;
			}
		}


		iterator begin()
		{
			for (size_t i = 0; i < _tables.size(); i++)
			{
				if (_tables[i])
				{
					return iterator(_tables[i],this);
				}
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}

		bool Erase(const K& key)
		{
			if (_tables.empty())
				return false;

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[index];
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					if (prev == nullptr) {
						//頭删
						_tables[index] = cur->_next;
					}
					else {
						//中間删除and尾删
						prev->_next = cur->_next;
					}
					--_n;
					delete cur;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}

		iterator Find(const K& key)
		{
			if (_tables.empty())
				return end();

			HashFunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			KeyOfT kot;
			while (cur)
			{
				if (kot(cur->_data) == key)
					return iterator(cur, this);
				else
					cur = cur->_next;
			}
			return end();
		}
		size_t GetNextPrime(size_t num)
		{
			static const unsigned long __stl_prime_list[28] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (size_t i = 0; i < 28; ++i)
			{
				if (__stl_prime_list[i] > num)
				{
					return __stl_prime_list[i];
				}
			}

			return __stl_prime_list[27];
		}

		pair<iterator, bool> Insert(const T& data)
		{
			KeyOfT kot;
			iterator ret = Find(kot(data));
			if (ret != end())
				return make_pair(ret, false);

			HashFunc hf;
			// 負載因子 == 1時擴容
			if (_n == _tables.size())
			{
				//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				size_t newSize = GetNextPrime(_tables.size());
				if (newSize > _tables.size())
				{
					vector<Node*> newTables;
					newTables.resize(newSize);
					for (size_t i = 0; i < _tables.size(); ++i)
					{
						Node* cur = _tables[i];
						while (cur)
						{
							Node* next = cur->_next;

							size_t index = hf(kot(cur->_data)) % newTables.size();
							// 頭插
							cur->_next = newTables[index];
							newTables[index] = cur;

							cur = next;
						}

						_tables[i] = nullptr;
					}

					_tables.swap(newTables);
				}

			}


			size_t index = hf(kot(data)) % _tables.size();
			Node* newnode = new Node(data);
			// 頭插
			newnode->_next = _tables[index];
			_tables[index] = newnode;

			++_n;
			return make_pair(iterator(newnode, this), false);;
		}
	private:
		vector<Node*> _tables;
		size_t _n=0;//有效資料個數
	};
}