閉散列的回顧

在前面的學習中我們知道了閉散列的運算規(guī)則，當兩個數(shù)據(jù)計算得到的位置發(fā)生沖突時，它會自動的往后尋找沒有發(fā)生沖突的位置，比如說當前數(shù)據(jù)的內(nèi)容如下：

當插入的數(shù)據(jù)為33時計算的位置為3，可是位置3已經(jīng)被占領(lǐng)了并且4也被占領(lǐng)了，但是位置5沒有被占領(lǐng)所以插入數(shù)據(jù)33就會占領(lǐng)位置5，那么這里的圖片就如下：

這就是閉散列的插入原則，并且每個節(jié)點都有一個變量用來表示狀態(tài)，這樣在查找就不會出現(xiàn)漏查的情況，但是這樣的實現(xiàn)會存在一個問題，擴容是根據(jù)有效數(shù)據(jù)的個數(shù)和vector容量來確定的，但是查找的時候是根據(jù)當前元素的狀態(tài)是否為空來判斷后面還有沒有要查找的數(shù)據(jù)，如果為空的話則說明當前元素的后面沒有我們要查找的元素，如果為存在或者被刪除的話就說明當前元素的后面還有我們要查找的數(shù)據(jù)，如果我們不停的插入數(shù)據(jù)并且刪除數(shù)據(jù)的話就會導致容器中的每個元素的狀態(tài)都變成了被刪除這樣在查找一個不存的數(shù)據(jù)時，就會陷入死循環(huán)的狀態(tài)那么這就是我們之前模擬實現(xiàn)的一個缺點，那么這里我們就來看看第二個解決數(shù)據(jù)不集中的方法：拉鏈法或者叫哈希桶法。

拉鏈法/哈希桶的原理

這個方法就是每個位置上都是一個鏈表，如果有多個位置發(fā)生沖突了，那么就掛在這個位置的鏈表上，這樣就不會導致占領(lǐng)別人的位置，當我們要查找的時候就是先找到插入數(shù)據(jù)的位置，然后再通過這個位置的鏈表來按照順序來進行查找，比如說下面的圖片

當我們想要插入一個數(shù)據(jù)13時就會先計算13對應(yīng)在哈希表上的位置，根據(jù)之前的計算原則這里得到的位置就是3，所以圖片就變成了下面這樣：

如果再插入數(shù)據(jù)23的話這里計算的位置依然是3，但是此時3上已經(jīng)有元素了，所以這時就會使用鏈表的頭插將數(shù)據(jù)23插入到13的前面，那么這里的圖片就是下面這樣：

如果再插入數(shù)據(jù)33的話計算的位置依然是3，所以就會把33放到3號位置對應(yīng)的鏈表的頭部，那么這里的圖片就變成下面這樣：

那么這就是哈希桶的插入規(guī)則，找到對應(yīng)位置的鏈表將數(shù)據(jù)插入到頭部即可，如果要查找的話也是相同的原理先找到數(shù)據(jù)對應(yīng)的鏈表然后循環(huán)遍歷這個鏈表找到出現(xiàn)的數(shù)據(jù)即可，刪除也是相同的道理，先找到數(shù)據(jù)對應(yīng)的下標然后根據(jù)下標找到對應(yīng)的鏈表，最后遍歷鏈表找到要刪除的數(shù)據(jù)進行鏈表的刪除即可，那么這就是哈希桶的實現(xiàn)思路接下來我們就來看看這種方法的準備工作。

準備工作

哈希的底層是一個vector的數(shù)組，數(shù)組中的每個節(jié)點都有一個pair類型的數(shù)據(jù)，其次還有一個指針指向當前鏈表節(jié)點的下一個節(jié)點，所以每個節(jié)點中有個一個pair類型的數(shù)據(jù)和一個指向節(jié)點的指針，所以這里得創(chuàng)建一個類來描述每個節(jié)點，并且類中有一個構(gòu)造函數(shù)來初始化節(jié)點，這里的構(gòu)造函數(shù)就需要一個pair類型的參數(shù)，在構(gòu)造函數(shù)里面就將指針初始化為nullptr將pair類型的參數(shù)賦值為傳遞過來的參數(shù)，有因為這里的節(jié)點可能要存儲各種各樣的數(shù)據(jù)，所以這里得創(chuàng)建個模板來接收各種各樣的參數(shù)，并且模板的參數(shù)得是兩個，那么這里的代碼就如下：

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

根據(jù)前面的學習我們知道要想計算數(shù)據(jù)對應(yīng)在哈希表上的位置就得添加對應(yīng)的仿函數(shù)，那么這里的代碼就如下

template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};
template<>
struct HashFunc<string>
{
	size_t operator()(const string& s)
	{
		size_t res = 0;
		for (auto& ch : s)
		{
			res *= 131;
			res += ch;
		}
		return res;
	}
};

最后就是哈希bucket類的準備工作，首先這個類有一個模板，模板中有三個參數(shù)，前兩個表示存儲數(shù)據(jù)的類型，最后一個表示的是仿函數(shù)，因為哈希的地城是vector數(shù)組，所以這里得添加一個vector容器用來存儲數(shù)據(jù)和一個整型變量用來記錄容器中有效字符的個數(shù)即可，并且vector中的每個元素都是節(jié)點類型，那么該類的構(gòu)造函數(shù)就將vector容器的resize到10個元素即可，那么這里的代碼就如下：

template<class K, class V, class Hash = HashFunc<K>>
class BucketTable
{
	typedef HashNode<K, V> Node;
public:
typedef HashNode<K, V> Node;
	BucketTable()
		:_n(0)
	{
		_tables.resize(10);
	}
private:
	vector<Node*> _tables;
	size_t _n;
};

看到這里我們的準備工作就完成了接下來就要實現(xiàn)哈希的每個函數(shù)。

find函數(shù)

find函數(shù)就是先根據(jù)傳遞過來參數(shù)找到這個參數(shù)可能出現(xiàn)的位置，找到了位置就意味著找了一個鏈表的頭節(jié)點，所以這個時候就可以通過循環(huán)遍歷的方式來一一對比鏈表中是否含有想要查找的數(shù)據(jù)，如果存在的話就返回這個節(jié)點所在的地址，如果不存在的話就返回一個空指針，所以該函數(shù)的第一步就創(chuàng)建一個仿函數(shù)對象，并計算數(shù)據(jù)出現(xiàn)的位置：

Node* Find(const K& key)
{
	Hash hf;
	size_t pos = hf(key) % _tables.size();
	Node* cur=_tables[pos]
}

cur指向的是鏈表的第一個元素，所以接下來就可以使用while循環(huán)一個一個的遍歷每個元素，每次循環(huán)都會改變cur的指向讓其指向下一個元素，知道cur本身變?yōu)榭站屯Ｖ共檎?，在循環(huán)體的內(nèi)部如果出現(xiàn)了跟查找變量一樣的值就直接返回這個節(jié)點的地址，如果循環(huán)結(jié)束了也沒有找到想要的值的話就返回一個空指針，那么這里的代碼就如下：

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

插入函數(shù)

將數(shù)據(jù)插入的鏈表的時候得先判斷一下要插入的元素當前是否已經(jīng)存在，所以這里可以使用find函數(shù)來進行查找，根據(jù)find函數(shù)的返回值來判斷是否存在，那么這里的代碼就如下：

bool insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
	{
		return false;
	}
}

如果當前的元素不存在的話就開始插入數(shù)據(jù)，這種實現(xiàn)方法也得根據(jù)傳遞過來的元素找到應(yīng)該插入的位置，所以該函數(shù)的第一步就是創(chuàng)建一個仿函數(shù)對象然后根據(jù)傳遞過來的參數(shù)計算得出應(yīng)該插入的位置，找到插入位置之后就使用頭插來插入對應(yīng)的數(shù)據(jù)，這里的頭插就是先讓newnode的_next指向當前位置的鏈表，然后修改vector中當前位置的指向使其指向newnode，那么這里的代碼就如下：

bool insert(const pair<K, V>& kv)
{
	if (Find(kv.first))
	{
		return false;
	}
	Hash hf;
	size_t pos = hf(kv.first) % _tables.size();
	Node* newnode = new HashNode<K,V>(kv);
	newnode->_next = _tables[pos];
	_tables[pos] = newnode;
	++_n;
	return true;
}

這里依然得添加負載因子，官方庫中可以通過一些函數(shù)來得到當前容器的負載因子和最大的負載因子，如果負載因子等于1了我們就擴容，將其容量變?yōu)橹暗膬杀?，但是擴容不能直接把鏈表對應(yīng)的移動到新的容器上去因為這里的映射關(guān)系已經(jīng)改變了比如說當前容器的容量為10則數(shù)據(jù)18對應(yīng)的位置就是8上面的鏈表，如果容器發(fā)生了擴容使得容量變成了20的話18就對應(yīng)的不再是8而是18上面的鏈表，所以我們這里解決的方法就是創(chuàng)建一個新的哈希表，然后遍歷容器中的每個位置，如果當前位置不為空就往這個位置里面進行遍歷對每個元素都進行插入操作，如果當前位置為空的話就跳轉(zhuǎn)到下一個元素，那么這里的代碼就如下：

bool insert(const pair<K, V>& kv)
{
	if (!Find(kv.first))
	{
		return false;
	}
	if (_n / _tables.size() == 1)//平衡因子為1就更新
	{
		vector<Node*> newBH;
		newBH._tables.resize(_n * 2);
		for (auto& cur : _tables)
		{
			while (cur)
			{
				newBH.insert(cur->_kv);
				cur = cur->_next;
			}
		}
		_tables.swap(newBH._tables);
	}
	Hash hf;
	size_t pos = hf(kv.first) % _tables.size();
	Node* newnode = new HashNode<K,V>(kv);
	newnode->_next = _tables[pos];
	_tables[pos] = newnode;
	++_n;
	return true;
}

erase函數(shù)

erase函數(shù)也是分為三步來完成，首先找到節(jié)點對應(yīng)的鏈表，然后再找鏈表中是否存在該元素，如果不存在的話就返回false，如果存在的話就對該鏈表的該節(jié)點進行刪除，因為這里刪除的時候得保證鏈表之間的上下鏈接，所以這里創(chuàng)建一個指向指向被刪除節(jié)點的前一個節(jié)點，以此來保證刪除前后的鏈接，這里大家要注意的一點就是當刪除的節(jié)點是頭節(jié)點時，得改變vector容器中的指針的指向，那么這里的代碼就如下：

bool erase(const K& key)
{
	HashFunc<K> HF;
	size_t pos = HF(key) % _tables.size();
	Node* cur = _tables[pos];
	Node* prev = cur;
	while (cur)
	{
		if (cur->_kv.first == key)
		{
			if (cur == _tables[pos])
			{
				_tables[pos] = cur->_next;
			}
			else
			{
				prev->_next = cur->_next;
			}
			delete cur;
			_n--;
			return true;
		}
		else
		{
			prev = cur;
			cur = cur->_next;
		}
	}
	return false;
}

代碼測試

可以通過下面的代碼來進行相應(yīng)的測試看看我們上面寫的代碼是否是正確的：

void TestHT1()
{
	BucketTable<int, int> ht;
	int a[] = { 18, 8, 7, 27, 57, 3, 38, 18 };
	for (auto e : a)
	{
		ht.insert(make_pair(e, e));
	}
	ht.insert(make_pair(17, 17));
	ht.insert(make_pair(5, 5));
	if (ht.Find(7)) { cout << "存在" << endl; }
	else { cout << "不存在" << endl; }
	ht.erase(7);
	if (ht.Find(7)) { cout << "存在" << endl; }
	else { cout << "不存在" << endl; }
}
int main()
{
	TestHT1();
	return 0;
}

代碼的運行結(jié)果如下：

我們可以再用下面的代碼來進行一下測試：

void TestHT2()
{
	string arr[] = { "蘋果", "西瓜", "香蕉", "草莓", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };
	//HashTable<string, int, HashFuncString> countHT; 
	BucketTable<string, int> countHT;
	for (auto& e : arr)
	{
		HashNode<string, int>* ret = countHT.Find(e);
		if (ret)
		{
			ret->_kv.second++;
		}
		else
		{
			countHT.insert(make_pair(e, 1));
		}
	}
}

這段代碼的運行結(jié)果如下：

有了這個游戲之后就可以對insert函數(shù)進行改進，但是這里先不要急還有一個地方需要我們改進的就是插入數(shù)據(jù)的時候，上面擴容在插入數(shù)據(jù)的時候是創(chuàng)建一個哈希桶然后再調(diào)用哈希桶來插入原來哈希桶的每個數(shù)據(jù)，如果這么做的話，在新的哈希桶里面又會不斷地創(chuàng)建地節(jié)點，并且在函數(shù)結(jié)束地時候又會刪除節(jié)點，如果節(jié)點的個數(shù)非常多的話這就會導致效率低下，所以我們這里就有一個改進思路就是能不能用已有的節(jié)點來插入到新創(chuàng)建的哈希表呢？答案是可以的，我們依然是創(chuàng)建一個新的哈希表然后改變其內(nèi)部的大小，然后遍歷之前的老哈希表找到里面的元素并計算他在新表上的位置，然后修改其節(jié)點內(nèi)部指針的指向，那么這里的代碼如下：

if (_n / _tables.size() == 1)//平衡因子為1就更新
{
	/*vector<Node*> newBH;;
	newBH.resize(_n * 2);
	for (auto& cur : _tables)
	{
		while (cur)
		{
			newBH.insert(cur->_kv);
			cur = cur->_next;
		}
	}
	_tables.swap(newBH._tables);*/
	vector<Node*> newBH;
	newBH._tables.resize(__stl_next_prime(_tables.size()));
	for (int i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;
			size_t pos = Hash()(cur->_kv.first);
			cur->_next = newBH[pos];
			newBH[pos] = cur;
			cur = next;
		}
		_tables[i] = nullptr;
	}
}

以上就是C++實現(xiàn)哈希桶的詳細教程的詳細內(nèi)容，更多關(guān)于C++哈希桶的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論