【干貨】C++哈希桶（開(kāi)鏈法解決哈希沖突）類(lèi)的實(shí)現(xiàn)

    開(kāi)鏈法（哈希桶）是解決哈希沖突的常用手法，結(jié)構(gòu)如下：

創(chuàng)新互聯(lián)是一家集成都網(wǎng)站建設(shè)、做網(wǎng)站、網(wǎng)站頁(yè)面設(shè)計(jì)、網(wǎng)站優(yōu)化SEO優(yōu)化為一體的專(zhuān)業(yè)網(wǎng)站設(shè)計(jì)公司，已為成都等多地近百家企業(yè)提供網(wǎng)站建設(shè)服務(wù)。追求良好的瀏覽體驗(yàn),以探求精品塑造與理念升華,設(shè)計(jì)最適合用戶(hù)的網(wǎng)站頁(yè)面。 合作只是第一步，服務(wù)才是根本,我們始終堅(jiān)持講誠(chéng)信，負(fù)責(zé)任的原則，為您進(jìn)行細(xì)心、貼心、認(rèn)真的服務(wù),與眾多客戶(hù)在蓬勃發(fā)展的市場(chǎng)環(huán)境中,互促共生。

    數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)思路是這樣的，定義一個(gè)K—V的鏈?zhǔn)焦?jié)點(diǎn)（Node），以數(shù)組方式存儲(chǔ)節(jié)點(diǎn)指針

    實(shí)現(xiàn)代碼如下：

#include<vector>
#include"HashTable.h"
size_t GetSize()
{
	static size_t index = 0;
	const int _PrimeSize = 28;
	static const unsigned long _PrimeList[_PrimeSize] =
	{
		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
	};
	return _PrimeList[index++];
}
template<class K,class V>
struct HashBucketNode
{
	HashBucketNode(const K& key, const V& value)
	:_key(key)
	, _value(value)
	, _next(NULL)
	{}
	K _key;
	V _value;
	HashBucketNode* _next;
};
template<class K, class V, class HashFunc = DefaultHash<K> >
class HashBucket
{
public:
	typedef HashBucketNode<K,V> Node;
	HashBucket()
		:_size(0)
	{
			_tables.resize(0);
	}
	bool Push(const K& key, const V& value)
	{
		_CheckCapacity();
		size_t index = HashFunc()(key) % _tables.size();
		Node*cur = _tables[index];
		while (cur)
		{
			if (cur->_key == key&&cur->_value == value)
				return false;
			cur = cur->_next;
		}
		Node*tmp = new Node(key, value);
		if (_tables[index])
		{
			_tables[index]->_next = tmp->_next;
		}
		_tables[index] = tmp;
		++_size;
		return true;
	}
	void Swap(HashBucket & h)
	{
		swap(_size, h._size);
		_tables.swap(h._tables);
	}
	Node* find(const K& key, const V& value)
	{
		size_t index = HashFunc()(key) % _tables.size();
		Node*cur = _tables[index];
		while (cur)
		{
			if (cur->_key == key&&cur->_value == value)
				return cur;
			cur = cur->_next;
		}
		return NULL;
	}
	bool Remove(const K& key)
	{
		size_t index = HashFunc()(key) % _tables.size();
		if (_tables[index])
		{
			if (_tables[index]->key == key)
			{
				Node*tmp = _tables[index];
				_tables[index] = tmp->_next;
				delete tmp;
				return true;
			}
			else
			{
				Node*cur = _tables[index];
				while (cur->_next)
				{
					if (cur->_next->_key == key)
					{
						Node*tmp = cur->_next;
						cur->_next = cur->_next->_next;
						delete tmp;
						return true;
					}
					cur = cur->_next;
				}
			}
		}
		return false;
	}
protected:
	void _CheckCapacity()
	{
		if (_size >= _tables.size())
		{
			HashBucket tmp;
			tmp._tables.resize(GetSize());
			for (size_t i = 0; i < tmp._tables.size(); ++i)
			{
				Node*cur = tmp._tables[i];
				while (cur)
				{
					tmp.Push(cur->_key, cur->_value);
					cur = cur->_next;
				}
			}
			Swap(tmp);
		}
	}
protected:
	vector<Node*> _tables;
	size_t _size;
};

    如有不足希望指正，有疑問(wèn)希望提出

當(dāng)前名稱(chēng)：【干貨】C++哈希桶（開(kāi)鏈法解決哈希沖突）類(lèi)的實(shí)現(xiàn)
網(wǎng)頁(yè)URL：http://muchs.cn/article48/jehiep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、靜態(tài)網(wǎng)站、電子商務(wù)、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)