欧美一区二区三区老妇人-欧美做爰猛烈大尺度电-99久久夜色精品国产亚洲a-亚洲福利视频一区二区

實現(xiàn)哈希桶（空間利用率較高的哈希表）-創(chuàng)新互聯(lián)

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

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

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

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

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

  • 實現(xiàn)哈希桶（空間利用率較高的哈希表）

  • #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ù)
};

得到哈希桶的結(jié)構(gòu)以后，我們來實現(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出結(jié)點
	if (_table[index] == NULL)
	{
		_table[index] = tmp;
	}
	else
	{
		//不為NULL則使用頭插法插入新結(jié)點
		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])//依次摘結(jié)點
				{
					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ù)可以減少哈希沖突，其實我也感覺很奇妙。

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

  在插入的時候使用頭插法是很高效的！！！

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

查找函數(shù)返回一個結(jié)點的指針方便我們在外部更改數(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ù)時最好別調(diào)用Find函數(shù)去查找要刪除的結(jié)點，如果要刪除的結(jié)點是頭節(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ù)比較的簡單，在這里我就不寫出來了；

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

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

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

廣告

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

網(wǎng)站優(yōu)化排名