前面幾篇博客已經(jīng)寫過了哈希表的閉散列法，也寫過哈希表的應用，在這里就不贅述。今天我們要實現(xiàn)的是一個哈希桶。什么哈希桶呢？

創(chuàng)新互聯(lián)公司專注于企業(yè)全網(wǎng)整合營銷推廣、網(wǎng)站重做改版、定襄網(wǎng)站定制設計、自適應品牌網(wǎng)站建設、H5頁面制作、商城網(wǎng)站建設、集團公司官網(wǎng)建設、外貿(mào)營銷網(wǎng)站建設、高端網(wǎng)站制作、響應式網(wǎng)頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為定襄等各大城市提供網(wǎng)站開發(fā)制作服務。

• 哈希桶：哈希桶就是盛放不同key鏈表的容器（即是哈希表），在這里我們可以把每個key的位置看作是一個孔，孔里放了一個鏈表

• 相信大家可以看出來，使用一個數(shù)組來存放記錄方法的哈希沖突太多，基于載荷因子的束縛，空間利用率不高，在需要節(jié)省空間的情況下，我們可以用哈希桶來處理哈希沖突。

• 哈希桶是使用一個順序表來存放具有相同哈希值的key的鏈表的頭節(jié)點，利用這個頭節(jié)點可以找到其它的key。

• 

• #pragma once
  #include<iostream>
  #include<string>
  #include<vector>
  
  using namespace std;
  
  template<class T>
  struct DefaultFunc
  {
  	size_t operator()(const T& data)
  	{
  		return (size_t)data;
  	}
  };
  
  struct StringFunc
  {
  	size_t operator()(const string& str)
  	{
  		size_t sum = 0;
  		for (size_t i = 0; i < str.size(); ++i)
  		{
  			sum += str[i];
  		}
  		return sum;
  	}
  };
  
  template<class K, class V>
  struct HashBucketNode
  {
  	K _key;
  	V _value;
  	HashBucketNode<K, V>* _next;
  	HashBucketNode(const K& key, const V& value)
  		:_key(key)
  		, _value(value)
  		, _next(NULL)
  	{}
  };
  
  template<class K, class V, class FuncModle = DefaultFunc<K>>
  class HashBucket
  {
  	typedef HashBucketNode<K, V> Node;
  public:
  	HashBucket();
  	//~HashBucket();
  	HashBucket(const HashBucket<K, V, FuncModle>& h);
  	HashBucket<K, V, FuncModle>& operator=(HashBucket<K, V, FuncModle> h);
  	bool Insert(const K& key, const V& value);
  	Node* Find(const K& key);
  	bool Remove(const K& key);
  	//bool Alter(const K& key);//用Find實現(xiàn)
  	void Print();
  protected:
  	void _CheckExpand();//檢查是否需要擴容
  	size_t _GetNextPrime(size_t size);//從素數(shù)表中得到比當前素數(shù)大的素數(shù)
  	size_t _HashFunc(const K& key,size_t mod);//哈希函數(shù)
  protected:
  	vector<Node*> _table;
  	size_t _size;//記錄的個數(shù)
  };

得到哈希桶的結構以后，我們來實現(xiàn)幾個比較重要的函數(shù)：

（一）bool Insert(const K& key, const V& value)

插入函數(shù)是最難實現(xiàn)的，它涉及到是否需要擴容。為插入函數(shù)我們寫了兩個內(nèi)部函數(shù)void _CheckExpand(); 和 size_t _GetNextPrime(size_t size);

template<class K, class V, class FuncModle>
bool HashBucket<K, V, FuncModle>::Insert(const K& key, const V& value)
{
	_CheckExpand();
	//使用頭插法插入
	size_t index = _HashFunc(key,_table.size());
	Node* tmp=new Node(key, value);//一定要用new出結點
	if (_table[index] == NULL)
	{
		_table[index] = tmp;
	}
	else
	{
		//不為NULL則使用頭插法插入新結點
		tmp->_next = _table[index];
		_table[index] = tmp;
	}
	_size++;
	return true;
}
template<class K, class V, class FuncModle>
size_t  HashBucket<K, V, FuncModle>::_GetNextPrime(size_t size)
{
	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
	};
	for (int i = 0; i < _PrimeSize; ++i)
	{
		if (_PrimeList[i] > size)
			return _PrimeList[i];
	}
	assert(false);
	return 4294967291ul;
}
template<class K, class V, class FuncModle>
void HashBucket<K, V, FuncModle>::_CheckExpand()
{
	if (_size == _table.size())
	{
		size_t newsize = _GetNextPrime(_size);//從素數(shù)表中取出下一個素數(shù)
		if (newsize == _size)
			return;
		vector<Node*> newtable;
		newtable.resize(newsize);
		for (size_t i = 0; i < _size; ++i)
		{
			size_t index = _HashFunc(_table[i]->_key,newsize);
			if (_table[i])
			{
				Node* head = _table[i];//保存頭節(jié)點
				newtable[index] = head;//摘下vector的第一個指針為新表的頭節(jié)點
				_table[i] = _table[i]->_next;
				while (_table[i])//依次摘結點
				{
					Node* tmp = _table[i];
					_table[i] = _table[i]->_next;
					head->_next = tmp;
					head = head->_next;
				}
			}
			else
				newtable[index] = NULL;
			_table[i] = NULL;
		}
		swap(_table, newtable);
	}
}

 在擴容的函數(shù)中我們使用了素數(shù)表，有大師證明Mod素數(shù)表中的素數(shù)可以減少哈希沖突，其實我也感覺很奇妙。

 在調用哈希函數(shù)HashFunc的時候一定要注意，我們用key取模一定模的是vector當前的容量。

  在插入的時候使用頭插法是很高效的?。。?/p>

（二）Node* Find(const K& key);

查找函數(shù)返回一個結點的指針方便我們在外部更改數(shù)據(jù)。

emplate<class K, class V, class FuncModle>
HashBucketNode<K,V>* HashBucket<K, V, FuncModle>::Find(const K& key)
{
	size_t index = _HashFunc(key, _table.size());
	while (_table[index])
	{
		if (_table[index]->_key == key)
		{
			return _table[index];
		}
		_table[index] = _table[index]->_next;
	}
	return NULL;
}

（三）bool Remove(const K& key);

我們在寫刪除節(jié)點函數(shù)時最好別調用Find函數(shù)去查找要刪除的結點，如果要刪除的結點是頭節(jié)點或者尾節(jié)點的話就無法修改要刪除指針的前一個指針的_next域；

template<class K, class V, class FuncModle>
bool HashBucket<K, V, FuncModle>::Remove(const K& key)
{
	//不能用find找到，然后刪。
	size_t index = _HashFunc(key,_table.size());
	if (_table[index] == NULL)
		return false;
	Node* cur = _table[index];
	if (cur->_key==key)
	{
		Node* del = cur;
		_table[index] = cur->_next;
		delete del;
		_size--;
		return true;
	}
	else
	{
		Node* prev = NULL;
		while (cur)
		{
			if (cur->_key == key)
			{
				prev->_next = cur->_next;
				delete cur;
				_size--;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}
}

 其他的函數(shù)比較的簡單，在這里我就不寫出來了；

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

當前名稱：實現(xiàn)哈希桶（空間利用率較高的哈希表）-創(chuàng)新互聯(lián)
標題網(wǎng)址：http://jinyejixie.com/article2/ccsiic.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、移動網(wǎng)站建設、網(wǎng)站設計、ChatGPT、域名注冊、網(wǎng)站設計公司

廣告

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