閉散列的回顧

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

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

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

拉鏈法/哈希桶的原理

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

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

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

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

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

準(zhǔn)備工作

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

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

根據(jù)前面的學(xué)習(xí)我們知道要想計(jì)算數(shù)據(jù)對(duì)應(yīng)在哈希表上的位置就得添加對(duì)應(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類(lèi)的準(zhǔn)備工作，首先這個(gè)類(lèi)有一個(gè)模板，模板中有三個(gè)參數(shù)，前兩個(gè)表示存儲(chǔ)數(shù)據(jù)的類(lèi)型，最后一個(gè)表示的是仿函數(shù)，因?yàn)楣５牡爻鞘莢ector數(shù)組，所以這里得添加一個(gè)vector容器用來(lái)存儲(chǔ)數(shù)據(jù)和一個(gè)整型變量用來(lái)記錄容器中有效字符的個(gè)數(shù)即可，并且vector中的每個(gè)元素都是節(jié)點(diǎn)類(lèi)型，那么該類(lèi)的構(gòu)造函數(shù)就將vector容器的resize到10個(gè)元素即可，那么這里的代碼就如下：

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

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

find函數(shù)

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

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

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

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ù)插入的鏈表的時(shí)候得先判斷一下要插入的元素當(dāng)前是否已經(jīng)存在，所以這里可以使用find函數(shù)來(lái)進(jìn)行查找，根據(jù)find函數(shù)的返回值來(lái)判斷是否存在，那么這里的代碼就如下：

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

如果當(dāng)前的元素不存在的話就開(kāi)始插入數(shù)據(jù)，這種實(shí)現(xiàn)方法也得根據(jù)傳遞過(guò)來(lái)的元素找到應(yīng)該插入的位置，所以該函數(shù)的第一步就是創(chuàng)建一個(gè)仿函數(shù)對(duì)象然后根據(jù)傳遞過(guò)來(lái)的參數(shù)計(jì)算得出應(yīng)該插入的位置，找到插入位置之后就使用頭插來(lái)插入對(duì)應(yīng)的數(shù)據(jù)，這里的頭插就是先讓newnode的_next指向當(dāng)前位置的鏈表，然后修改vector中當(dāng)前位置的指向使其指向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;
}

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

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ù)也是分為三步來(lái)完成，首先找到節(jié)點(diǎn)對(duì)應(yīng)的鏈表，然后再找鏈表中是否存在該元素，如果不存在的話就返回false，如果存在的話就對(duì)該鏈表的該節(jié)點(diǎn)進(jìn)行刪除，因?yàn)檫@里刪除的時(shí)候得保證鏈表之間的上下鏈接，所以這里創(chuàng)建一個(gè)指向指向被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，以此來(lái)保證刪除前后的鏈接，這里大家要注意的一點(diǎn)就是當(dāng)刪除的節(jié)點(diǎn)是頭節(jié)點(diǎn)時(shí)，得改變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;
}

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

之前的寫(xiě)法當(dāng)中不需要添加析構(gòu)函數(shù)是因?yàn)関ector中本身就含有析構(gòu)函數(shù)，所以編譯器自己生成的析構(gòu)函數(shù)能夠自動(dòng)的調(diào)用vector的析構(gòu)函數(shù)來(lái)釋放空間，但是這里不一樣這里得寫(xiě)析構(gòu)函數(shù)，因?yàn)関ector釋放之后不會(huì)釋放里面的節(jié)點(diǎn)所申請(qǐng)的空間，所以這里的析構(gòu)函數(shù)要干的事情就是虛幻遍歷每個(gè)節(jié)點(diǎn)并且一個(gè)一個(gè)的釋放每個(gè)節(jié)點(diǎn)申請(qǐng)的空間，那么這里的代碼就如下：

~BucketTable()
{
	for (int i = 0; i < _tables.size(); i++)
	{
		Node* cur = _tables[i];
		while (cur)
		{
			Node* next = cur->_next;
			delete cur;
			cur = next;
		}
		_tables[i] = nullptr;
	}
}

代碼測(cè)試

可以通過(guò)下面的代碼來(lái)進(jìn)行相應(yīng)的測(cè)試看看我們上面寫(xiě)的代碼是否是正確的：

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

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

我們可以再用下面的代碼來(lái)進(jìn)行一下測(cè)試：

void TestHT2()
{
	string arr[] = { "蘋(píng)果", "西瓜", "香蕉", "草莓", "蘋(píng)果", "西瓜", "蘋(píng)果", "蘋(píng)果", "西瓜", "蘋(píng)果", "香蕉", "蘋(píng)果", "香蕉" };
	//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));
		}
	}
}

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

符合我們的預(yù)期說(shuō)明我們上面的代碼實(shí)現(xiàn)的是正確的。

insert函數(shù)的改進(jì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
};

然后我們就可以用這個(gè)數(shù)組封裝成為一個(gè)函數(shù)，這個(gè)函數(shù)的功能就是找到一個(gè)數(shù)據(jù)附件的素?cái)?shù)，這里就可以通過(guò)循環(huán)遍歷的方式來(lái)進(jìn)行查找，那么這里的代碼如下：

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 (int 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];
}

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

到此這篇關(guān)于c++實(shí)現(xiàn)哈希桶的步驟的文章就介紹到這了,更多相關(guān)c++ 哈希桶內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論