3.
字符串轉(zhuǎn)換為整型的場(chǎng)景還是比較常見的，所以有人整理了一篇字符串哈希算法，思路就是將每一個(gè)字符對(duì)應(yīng)的ascll碼分別拆下來，每次的hash值都為上一次的hash值×131后再加上字符的ascll碼值，遍歷完字符串后，最后的hash為字符串轉(zhuǎn)成整型的結(jié)果，這樣每個(gè)字符串轉(zhuǎn)換后的整型是極大概率不重復(fù)的，是一個(gè)非常不錯(cuò)的哈希算法，被人們稱為BKDRHash。

字符串哈希算法

template <class K>
struct BKDRHash
{
	size_t operator()(const K& key)
	{
		return (size_t)key;//只要這個(gè)地方能轉(zhuǎn)成整型，那就可以映射，指針浮點(diǎn)數(shù)負(fù)數(shù)都可以，但string不行
	}
};
template <>
struct BKDRHash<string>
{
	size_t operator()(const string& key)
	{
		//return key[0];//字符串第一個(gè)字符是整型，那就可以整型提升，只要是個(gè)整型能進(jìn)行%模運(yùn)算，完成映射即可。

		size_t hash = 0;
		for (auto ch : key)
		{
			hash = hash * 131 + ch;
		}
		return hash;
	}
};

四、開散列（掛哈希桶的方式）

1.哈希表結(jié)構(gòu) && 構(gòu)造和析構(gòu)函數(shù)

1.
開散列的哈希表是最常用的方式，庫(kù)里面的unordered_map和unordered_set用的也是哈希桶的方式實(shí)現(xiàn)的，我們模擬實(shí)現(xiàn)的哈希桶也仿照庫(kù)實(shí)現(xiàn)，哈希結(jié)點(diǎn)node里面存儲(chǔ)鍵值對(duì)和下一個(gè)結(jié)點(diǎn)指針。
在哈希表的模板參數(shù)中，也多加了一個(gè)缺省仿函數(shù)類的參數(shù)，也就是Hash，因?yàn)槲覀冃枰狧ash的仿函數(shù)對(duì)象或匿名構(gòu)造，將key轉(zhuǎn)成整型。

template <class K, class V>
struct hashNode
{
	hashNode(const pair<K,V>& kv)
		:_kv(kv)
		,_next(nullptr)
	{}

	pair<K, V> _kv;
	hashNode<K, V>* _next;
};
template <class K, class V, class Hash = BKDRHash<K>>
class hashTable
{
public:
	typedef hashNode<K, V> Node;

	…………省略
private:
	vector<Node*> _table;
	size_t _n;
};

2.
對(duì)于哈希桶，我們必須寫出析構(gòu)函數(shù)，因?yàn)榫幾g器默認(rèn)生成的析構(gòu)函數(shù)會(huì)調(diào)用vector的析構(gòu)，而vector的析構(gòu)僅僅只能將自己的空間還給操作系統(tǒng)，如果某些節(jié)點(diǎn)指針指向了具體的節(jié)點(diǎn)，則只歸還vector的空間是不夠的，還需要?dú)w還那些申請(qǐng)的節(jié)點(diǎn)空間。
所以需要遍歷每一個(gè)哈希桶，將每一個(gè)桶里面的節(jié)點(diǎn)都還給操作系統(tǒng)，這里就用到單鏈表的節(jié)點(diǎn)刪除的知識(shí)了，在刪除前需要保留下一個(gè)位置，要不然delete歸還空間之后就找不到下一個(gè)節(jié)點(diǎn)的位置了。

hashTable()
	:_n(0)
{
	_table.resize(10);
}
~hashTable()
{
	for (size_t i = 0; i < _table.size(); i++)
	{
		Node* cur = _table[i];
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;//把桶中所有結(jié)點(diǎn)空間的使用權(quán)還給操作系統(tǒng)，這就是析構(gòu)函數(shù)的作用
			cur = next;
		}
		_table[i] = nullptr;
	}
}

2.Insert()（單鏈表的頭插）

1.
我下面畫的圖只是想說明一下哈希桶的邏輯結(jié)構(gòu)和擴(kuò)容之后緩解哈希沖突的場(chǎng)景，但實(shí)際在插入節(jié)點(diǎn)時(shí)并不是像我下面畫的那樣對(duì)單鏈表進(jìn)行尾插，因?yàn)槲膊暹€需要找尾，那就需要遍歷桶，這樣的效率太低，并且桶中也不要求次序什么的，所以我們直接進(jìn)行頭插即可，頭插的效率很高，因?yàn)橛成湔业焦５刂分蠹纯蛇M(jìn)行頭插。

2.
哈希桶的負(fù)載因子，官方默認(rèn)值為1.0，那就是_n和vector.size()相等的時(shí)候進(jìn)行擴(kuò)容，擴(kuò)容的目的還是重新建立映射關(guān)系，緩解哈希沖突，因?yàn)槿绻骋粋€(gè)哈希桶的結(jié)點(diǎn)個(gè)數(shù)過多，在哈希映射之后還需要遍歷哈希桶尋找結(jié)點(diǎn)，會(huì)降低哈希查找的效率，所以擴(kuò)容就是多增加哈希桶的個(gè)數(shù)，減少平均哈希桶中結(jié)點(diǎn)的個(gè)數(shù)，提高哈希查找的效率。

3.
擴(kuò)容這里的思路和閉散列的哈希表比較相似，如果我們遍歷原有結(jié)點(diǎn)的數(shù)據(jù)，將每個(gè)結(jié)點(diǎn)的數(shù)據(jù)重新new一個(gè)結(jié)點(diǎn)出來，然后插入到新的vector里面，或者是代碼復(fù)用的方式進(jìn)行插入，這兩種都可以，但是效率太低了，上面所說的兩種代碼寫法都是新new結(jié)點(diǎn)插入到新表的，如果有1w個(gè)結(jié)點(diǎn)呢？我們平白無故的拷貝出來1w個(gè)結(jié)點(diǎn)，然后臨時(shí)對(duì)象銷毀的時(shí)候又析構(gòu)1w個(gè)結(jié)點(diǎn)？這不是冤大頭么。為什么不將原來的結(jié)點(diǎn)鏈接到新的vector上面呢？

4.
所以另一種寫法就是遍歷原表的每個(gè)結(jié)點(diǎn)指針，將每個(gè)指針指向結(jié)點(diǎn)的key重新計(jì)算哈希映射關(guān)系，頭插到新的vector里面，在每完成一個(gè)桶的重新映射關(guān)系后，將原vector中的桶位置的指針置為空，否則析構(gòu)的時(shí)候，結(jié)點(diǎn)會(huì)被析構(gòu)兩遍。等到原表的所有結(jié)點(diǎn)遍歷完之后，將新的vector和原來的vector一交換即可，臨時(shí)對(duì)象_newtable在離開函數(shù)棧幀時(shí)會(huì)被銷毀，調(diào)用vector的默認(rèn)析構(gòu)完成空間的歸還即可。

5.
研究表明，每次除留余數(shù)法最好模一個(gè)素?cái)?shù)，這會(huì)大概率降低哈希沖突的可能性。所以我們下面的擴(kuò)容大小每次挑選小于2倍的最大素?cái)?shù)作為擴(kuò)容后的vector大小，這里復(fù)用了一下stl庫(kù)里面的素?cái)?shù)表。

inline unsigned long __stl_next_prime(unsigned long n)
{
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
	  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 < __stl_num_primes; i++)
	{
		if (__stl_prime_list[i] > n)
		{
			return __stl_prime_list[i];
		}
	}

	return __stl_prime_list[__stl_num_primes - 1];
}
bool Insert(const pair<K, V>& kv)
{
	if (Find(kv.first))//不允許重復(fù)元素
		return false;

	//負(fù)載因子控制在1，超過就擴(kuò)容
	if (_n == _table.size())
	{
		/*hashTable<K, V, Hash> _newHT;
		_newHT._table.resize(2 * _table.size());*/

		//for (int hashi = 0; hashi < _table.size(); hashi++)
		//{
		//	Node* cur = _table[hashi];
		//	while (cur)
		//	{
		//		_newtable.Insert(cur);//需要重新改變映射關(guān)系
		//		cur = cur->_next;
		//	}
		//}
		//_table.swap(_newHT._table);
		
		//上面是冤大頭的做法，下面是正常的做法。
		vector<Node*> _newtable;
		_newtable.resize(__stl_next_prime(_table.size()), nullptr);//resize開空間后，默認(rèn)值為Node*()的構(gòu)造，我們也可以自己寫
		for (int i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = Hash()(cur->_kv.first) % _newtable.size();
				cur->_next = _newtable[hashi];
				_newtable[hashi] = cur;

				cur = next;
			}

			_table[i] = nullptr;
		}
		_table.swap(_newtable);
	}

	size_t hashi = Hash()(kv.first) % _table.size();
	Node* newnode = new Node(kv);
	newnode->_next = _table[hashi];//newnode的next指向當(dāng)前表哈希映射位置的結(jié)點(diǎn)地址
	_table[hashi] = newnode;//讓newnode做頭

	++_n;
	return true;
}

3.Erase()（歸還結(jié)點(diǎn)空間的使用權(quán)）

1.
哈希桶的erase其實(shí)就是單鏈表結(jié)點(diǎn)的刪除，如果是頭刪，那就是下一個(gè)指針作頭，如果是中間刪除，則記錄前一個(gè)結(jié)點(diǎn)位置，讓前一個(gè)結(jié)點(diǎn)的next指向刪除結(jié)點(diǎn)的next。
然后歸還結(jié)點(diǎn)空間的使用權(quán)，即為delete結(jié)點(diǎn)指針。

bool Erase(const K& key)
{
	Node* ret = Find(key);
	if (!ret)
		return false;

	size_t hashi = Hash()(key) % _table.size();
	Node* cur = _table[hashi];
	if (cur->_kv.first == key)//頭刪
	{
		_table[hashi] = cur->_next;
		delete cur;
		cur = nullptr;
	}
	else//中間刪除
	{
		while (cur)
		{
			Node* prev = cur;
			cur = cur->_next;
			if (cur->_kv.first == key)
			{
				prev->_next = cur->_next;
				delete cur;
				cur = nullptr;
			}
		}
	}
	--_n;
	return true;
}

4.Find()

1.
哈希桶的查找和閉散列的哈希表很相似，先通過key找到映射的哈希桶，然后去對(duì)應(yīng)的哈希桶里面找查找的結(jié)點(diǎn)即可，找到返回結(jié)點(diǎn)地址，未找到返回nullptr即可。

Node* Find(const K& key)
{
	size_t hashi = Hash()(key) % _table.size();
	Node* cur = _table[hashi];
	while (cur)
	{
		if (cur->_kv.first == key)
			return cur;
		cur = cur->_next;
	}
	return nullptr;
}

五、封裝實(shí)現(xiàn)unordered系列容器（不一樣的const迭代器）

1.普通迭代器（單向迭代器）

1.
封裝實(shí)現(xiàn)unordered系列容器的insert，find，erase等接口并不是什么難事，直接調(diào)用開散列哈希表的接口即可，而封裝的主要關(guān)鍵點(diǎn)其實(shí)是實(shí)現(xiàn)容器的迭代器操作，只要實(shí)現(xiàn)了迭代器的操作，那我們自己封裝的unordered系列容器基本上就能跑起來了。

2.
如果要實(shí)現(xiàn)迭代器++的操作，如果我們只有結(jié)點(diǎn)的指針是無法完成迭代器++的，因?yàn)槿绻闅v所有的哈希桶的結(jié)點(diǎn)，則必須需要哈希表本身，只有這樣才能確定下一個(gè)哈希桶的位置，所以開散列哈希表的迭代器需要多封裝一個(gè)哈希表指針，通過哈希表指針和哈希結(jié)點(diǎn)的指針，就可以訪問整個(gè)表里面所有的結(jié)點(diǎn)了。

3.
迭代器的++就是看當(dāng)前指針的下一個(gè)是否為空，如果為空說明當(dāng)前哈希桶里面只有他一個(gè)結(jié)點(diǎn)，那就需要尋找下一個(gè)哈希桶，將結(jié)點(diǎn)指針的指向移動(dòng)到下一個(gè)哈希桶的結(jié)點(diǎn)指針處，如果向后找的過程中結(jié)點(diǎn)指針都是nullptr，那就是沒有哈希桶，我們將_node置為空即可，說明此時(shí)迭代器已經(jīng)到end()的位置了，不能繼續(xù)遍歷下去了。

需要額外多說一點(diǎn)的是，由于迭代器內(nèi)部用了哈希表指針，所以需要在迭代器的前面加上哈希表的模板聲明。而且在迭代器內(nèi)部還訪問了哈希表的私有成員_table，則需要在哈希表里面進(jìn)行友元聲明，將迭代器模板聲明為哈希表的友元。

//前置聲明
template <class K, class T, class Hash, class KeyOfT>
class hashTable;

template <class K, class T, class Hash, class KeyOfT>
struct __HTIterator
{
	typedef hashNode<T> Node;
	typedef hashTable<K, T, Hash, KeyOfT> HT;
	typedef __HTIterator<K, T, Hash, KeyOfT> Self;
	Node* _node;
	HT* _ht;

	__HTIterator(Node* node, HT* ht)
		:_node(node)
		,_ht(ht)
	{}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			//當(dāng)前桶走完了，要去哈希表里面找下一個(gè)桶
			size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_table.size();
			hashi++;

			while (hashi != _ht->_table.size() && _ht->_table[hashi] == nullptr)
			{
				hashi++;
			}

			if (hashi == _ht->_table.size())
				_node = nullptr;
			else
				_node = _ht->_table[hashi];
		}

		return *this;
	}

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

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

2.為什么hashTable的const迭代器要重新寫一個(gè)類？

2.1 庫(kù)里面是怎么做的？

1.
我們可以先來看一下常規(guī)的迭代器操作，比如紅黑樹的迭代器，他的const迭代器并沒有重寫一個(gè)類，而是直接增加模板參數(shù)Ref和Ptr來完成對(duì)應(yīng)普通引用和常引用的值的返回。
并且支持普通迭代器構(gòu)造const迭代器的操作，實(shí)際上STL的所有容器在實(shí)現(xiàn)迭代器的時(shí)候，都會(huì)用下面的方式來支持普通迭代器構(gòu)造const迭代器，如果是普通迭代器調(diào)用，那這里就是普通和普通之間的拷貝，沒啥用因?yàn)榫幾g器也支持這樣的操作，但下面那段代碼目的不是支持普通迭代器之間的拷貝，而是支持普通到const迭代器的構(gòu)造操作。

2.
但是哈希表的迭代器卻沒有通過增加模板參數(shù)來解決，而是重寫了一個(gè)struct __hashtable_const_iterator { }類，以這樣的方式來實(shí)現(xiàn)unordered_map和unordered_set的const迭代器操作。

2.2 不能通過增加模板參數(shù)解決嗎？（權(quán)限不能放大）

1.
其實(shí)能否通過增加模板參數(shù)解決const迭代器主要取決于迭代器類中的構(gòu)造函數(shù)，之前能通過增加模板參數(shù)解決是因?yàn)闊o論是構(gòu)造const迭代器還是構(gòu)造普通迭代器，我們傳給構(gòu)造函數(shù)的指針都是普通指針，當(dāng)然可以構(gòu)造出普通迭代器和const迭代器了，因?yàn)閮蓚€(gè)迭代器的差別主要是*和→重載的返回值是可修改的還是不可修改的，這個(gè)并不難解決。

2.
而現(xiàn)在不一樣了，哈希迭代器傳的指針不是普通指針了，而是const指針，當(dāng)調(diào)用begin()或end()函數(shù)的對(duì)象是const對(duì)象時(shí)，this指針指向的內(nèi)容是不可修改的，并且由于對(duì)象是const對(duì)象，vector的[ ]返回的也是const引用，而vector存儲(chǔ)的是指針，那就說明哈希node結(jié)點(diǎn)指針指向的內(nèi)容也是不可修改的。
如果我們此時(shí)用這兩個(gè)指針去構(gòu)造const迭代器，而哈希迭代器類成員變量是兩個(gè)普通指針，那在構(gòu)造函數(shù)處就會(huì)發(fā)生const指針拷貝給普通指針的情況，此時(shí)權(quán)限會(huì)放大，所以如果你用增加模板參數(shù)來實(shí)現(xiàn)const迭代器，則編譯器一定會(huì)報(bào)錯(cuò)，因?yàn)橹羔樅鸵迷谫x值時(shí)，權(quán)限只能平移和縮小，不能放大。

3.
所以唯一的解決方式就是重寫const迭代器類，將const迭代器類的私有成員變量改為兩個(gè)const指針，這樣在構(gòu)造函數(shù)處構(gòu)造const迭代器時(shí)，就不會(huì)出現(xiàn)權(quán)限的放大了，只是發(fā)生權(quán)限的平移。

template <class K, class T, class Hash, class KeyOfT>
class hashTable
{
public:
	friend struct __HTIterator<K, T, Hash, KeyOfT>;

	typedef hashNode<T> Node;
	typedef __HTIterator<K, T, Hash, KeyOfT> iterator;

	iterator begin()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			if (_table[i])
			{
				return iterator(_table[i], this);//如果是const對(duì)象，這里返回const指針
			}
		}

		return iterator(nullptr, this);//如果哈希表是空的或者沒有桶，則構(gòu)造空迭代器。
	}
	iterator end()
	{
		return iterator(nullptr, this);
	}
	

2.3 哈希表和其他STL容器 支持普通迭代器構(gòu)造const迭代器的本質(zhì)是什么？（權(quán)限的縮小和平移）

1.
哈希表的迭代器是個(gè)特殊的存在，因?yàn)樗腸onst和非const迭代器是兩個(gè)類模板，而STL的其他容器的const和非const迭代器都是出自一個(gè)類模板。

2.
本質(zhì)還是因?yàn)楣１淼腸onst迭代器的私有成員變量得是const指針，而其他容器的const迭代器的私有成員變量只是普通指針。所以哈希表的普通迭代器構(gòu)造const迭代器其實(shí)是權(quán)限的縮小，由普通指針賦值到const指針。而其他容器的普通迭代器構(gòu)造const迭代器其實(shí)是權(quán)限的平移，因?yàn)闊o論是普通迭代器還是const迭代器，他們的成員變量都是普通指針。

3.unordered_map的[ ]操作

1.
支持map的[ ]操作并不困難，因?yàn)樗腫 ]操作其實(shí)就是通過insert返回迭代器和bool的鍵值對(duì)來實(shí)現(xiàn)的。當(dāng)[ ]內(nèi)的key不存在，則調(diào)用哈希表的Inset完成key和V()構(gòu)造的鍵值對(duì)的插入，并返回插入鍵值對(duì)的迭代器和true的bool值構(gòu)造的鍵值對(duì)。當(dāng)[ ]內(nèi)的key在哈希表中存在時(shí)，則哈希表的Insert也會(huì)返回指向key和value鍵值對(duì)的迭代器以及false的bool值構(gòu)造的鍵值對(duì)。

2.
所以實(shí)現(xiàn)[ ]的重?fù)?dān)主要是在Insert上面，只要Insert返回迭代器，那就能通過迭代器拿到鍵值對(duì)的value值，再通過返回value值的引用就可以修改哈希表中某一鍵值對(duì)的value值了。

下面是[ ]函數(shù)和哈希表底層的Insert函數(shù)，Insert的邏輯沒有變，只是將他的返回值從bool改為了鍵值對(duì)而已。文章來源地址http://www.zghlxwxcb.cn/news/detail-408260.html

V& operator[](const K& key)
{
	pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));

	return ret.first->second;
}

pair<iterator,bool> Insert(const T& data)
{
	KeyOfT kot;
	iterator it = Find(kot(data));
	if (it != end())
		return make_pair(it, false);//如果插入的值已經(jīng)存在那就不再進(jìn)行插入，返回對(duì)應(yīng)位置迭代器即可。

	if (_n == _table.size())
	{

		vector<Node*> _newtable;
		_newtable.resize(__stl_next_prime(_table.size()), nullptr);
		for (int i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				size_t hashi = Hash()(kot(cur->_data)) % _newtable.size();
				cur->_next = _newtable[hashi];
				_newtable[hashi] = cur;

				cur = next;
			}

			_table[i] = nullptr;
		}
		_table.swap(_newtable);
	}

	size_t hashi = Hash()(kot(data)) % _table.size();
	Node* newnode = new Node(data);
	newnode->_next = _table[hashi];
	_table[hashi] = newnode;

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

void test_unordered_map()
{
	string arr[] = { "蘋果", "西瓜", "香蕉", "草莓", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
		"蘋果", "香蕉", "蘋果", "香蕉" , "藍(lán)莓" ,"草莓" };

	unordered_map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
	}
	unordered_map<string, int>::iterator it = countMap.begin();
	//1.不用語(yǔ)法糖，一點(diǎn)一點(diǎn)遍歷也可以
	while (it != countMap.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	//2.我們實(shí)現(xiàn)了迭代器，直接用語(yǔ)法糖也可以。
	for (const auto& kv : countMap)//將解引用后的迭代器賦值給kv
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}

到了這里，關(guān)于【C++】開散列哈希表封裝實(shí)現(xiàn)unordered_map和unordered_set的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！