真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

c#如何實現(xiàn)哈希表線性探測

這篇文章主要介紹了c#如何實現(xiàn)哈希表線性探測，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

成都創(chuàng)新互聯(lián)服務(wù)項目包括侯馬網(wǎng)站建設(shè)、侯馬網(wǎng)站制作、侯馬網(wǎng)頁制作以及侯馬網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，侯馬網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到侯馬省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

    HashTable-散列表/哈希表，是根據(jù)關(guān)鍵字（key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。

   它通過一個關(guān)鍵值的函數(shù)將所需的數(shù)據(jù)映射到表中的位置來訪問數(shù)據(jù)，這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

  • 哈希沖突/哈希碰撞

    不同的Key值經(jīng)過哈希函數(shù)Hash(Key)處理以后可能產(chǎn)生相同的值哈希地址，我們稱這種情況為哈希沖突。任意的散列函數(shù)都不能避免產(chǎn)生沖突。

   我給大家介紹的是哈希表的線性探測，線性探測的基本思路：

       1.用一個數(shù)據(jù)除以散列表的長度，余數(shù)是多少，就把這個數(shù)放在散列表下標相同的地方。

       2.如果發(fā)生哈希沖突，就看下一個位置是否有數(shù)據(jù)，一直到?jīng)]有哈希沖突，就把這個數(shù)據(jù)放在此位置。

       3.如果已經(jīng)試探到最后一個位置，但前面還有位置沒有試探，那么我們就從開始位置繼續(xù)試探，直到全部位置試探成功。

實現(xiàn)代碼：

Hash.h中

//哈希表中存放數(shù)據(jù)的狀態(tài)
enum State
{
	EMPTY,//沒有數(shù)據(jù)
	DELETE,//刪除數(shù)據(jù)后
	EXIST//有數(shù)據(jù)
};
template 
class HashTable
{
public:
	//構(gòu)造函數(shù)
	HashTable()
		:_table(NULL)
		, state(NULL)
		, _size(0)
		, _capatity(0)
	{}
	//構(gòu)造函數(shù)
	HashTable(size_t size)
		:_table(new K[size])
		, _state(new State[size])
		, _capatity(size)
		, _size(0)
	{
		for (int i = 0; i < _capatity; i++)
		{
			_state[i] = EMPTY;
		}
	}
	//插入數(shù)據(jù)
	bool Insert(const K& key)
	{
		//檢測靜態(tài)哈希表是否已滿
		if (_size == _capatity)
		{
			cout << "哈希表已滿!" << endl;
			return false;
		}
		int index = _HashFunc(key);
		while (_state[index] == EXIST)
		{
			index++;//哈希沖突，找下一個位置
			//最后一個位置有數(shù)據(jù)，從頭開始找位置
			if (index == _capatity)
			{
				index = 0;
			}
		}
		//哈希不沖突，直接放數(shù)據(jù)
		_table[index] = key;
		_state[index] = EXIST;
		_size++;
		return true;
	}
	//查找
	int Find(const K& key)
	{
		int index = _HashFunc(key);
		while (_state[index] != EMPTY)
		{
			//找到元素
			if (_table[index] == key&&_state[index] == EXIST)
			{
				return index;
			}
			//如果算出的位置，不是要找的元素，index++;
			index++;
			//最后一個位置不是，就從頭開始找
			if (index == _capatity)
			{
				index = 0;
			}
		}
		return -1;
	}
	void print()
	{
		for (int i = 0; i < _capatity; i++)
		{
			if (_state[i] == EXIST)
			{
				printf("[%d]EXIST:%d\n",i, _table[i]);
			}
			else if (_state[i] == DELETE)
			{
				printf("[%d]DELETE:NULL\n", i, _table[i]);
			}
			else
			{
				printf("[%d]EMPTY:NULL\n", i);
			}
		}
	}
	//刪除某一位置元素
	bool Remove(const K& key)
	{
		int index = Find(key);//找到這個元素
		//刪除這個元素
		if (index != -1)
		{
			_state[index] = DELETE;
			_size--;
			return true;
		}
		return false;
	}
protected:
	//算出數(shù)據(jù)在哈希表中的位置（哈希不沖突）
	int _HashFunc(const K& key)
	{
		return key%_capatity;
	}
protected:
	K* _table;//數(shù)組
	State* _state;//狀態(tài)數(shù)組
	size_t _size;//數(shù)組大小
	size_t _capatity;//數(shù)組的容量
};

test.cpp中

#include 
using namespace std;
#include "Hash.h"
void Test()
{
	HashTable ht(10);
	ht.Insert(24);
	ht.Insert(20);
	ht.Insert(36);
	ht.Insert(23);
	ht.Insert(30);
	ht.print();

	int ret = ht.Find(30);
	cout << "下標為："<
上面的代碼有不完善的地方，我們在處理哈希問題是，有這樣的問題存在。散列表載荷因子的問題。
    載荷因子=填入表中的元/散列表的長度
   載荷因子與“填在表中元素的個數(shù)”成正比，載荷因子越大，填入表中的元素越多，產(chǎn)生沖突的可能性越大。反之，則相反。
    載荷因子應(yīng)該限制在0.7—0.8以下，超過0.8，查找CPU緩存不命中，效率就比較低，所以一般載荷因子為0.8就應(yīng)該擴容。
   所以上面的檢查容量應(yīng)該稍微改一下
代碼：
bool Insert(const K& key)
	{
		//檢測靜態(tài)哈希表是否已滿
		/*if (_size == _capatity)
		{
			cout << "哈希表已滿!" << endl;
			return false;
		}*/
		//考慮到載荷因子在0.7~0.8一下比較好，這樣檢查容量比較好
		if (10 * _size >= 8 * _capatity)
		{
			_CheckCapatity();
		}
		int index = _HashFunc(key);
		while (_state[index] == EXIST)
		{
			index++;//哈希沖突，找下一個位置
			//最后一個位置有數(shù)據(jù)，從頭開始找位置
			if (index == _capatity)
			{
				index = 0;
			}
		}
		//哈希不沖突，直接放數(shù)據(jù)
		_table[index] = key;
		_state[index] = EXIST;
		_size++;
		return true;
	}
	
	//交換
	void _Swap(HashTable tmp)
	{
		swap(_size, tmp._size);
		swap(_capatity, tmp._capatity);
		swap(_state, tmp._state);
		swap(_table, tmp._table);
	}
	//檢查容量
	void _CheckCapatity()
	{
		HashTable tmp(2 * _capatity);
		for (int i = 0; i < _capatity; i++)
		{
			tmp.Insert(_table[i]);
		}
		_Swap(tmp);
	}
上面只能存儲數(shù)據(jù)，如果是字符串，怎么辦哪？所以我們想處理字符串，可以寫一個自定義類型，然后利用特化來處理字符串。
代碼如下：
#include 
//哈希表中存放數(shù)據(jù)的狀態(tài)
enum State
{
	EMPTY,//沒有數(shù)據(jù)
	DELETE,//刪除數(shù)據(jù)后
	EXIST//有數(shù)據(jù)
};
template 
//處理
struct DefaultFunc
{
	size_t operator()(const K& key)
	{
		return key;
	}
};
//自定義類型
template<>
struct DefaultFunc//特化
{
	size_t value = 0;
	size_t operator()(const string& str)
	{
		for (int i = 0; i < str.size(); i++)
		{
			value += str[i];
		}
		return value;
	}
};
template class HashFunc = DefaultFunc>
class HashTable
{
public:
	//構(gòu)造函數(shù)
	HashTable()
		:_table(NULL)
		, state(NULL)
		, _size(0)
		, _capatity(0)
	{}
	//構(gòu)造函數(shù)
	HashTable(size_t size)
		:_table(new K[size])
		, _state(new State[size])
		, _capatity(size)
		, _size(0)
	{
		for (int i = 0; i < _capatity; i++)
		{
			_state[i] = EMPTY;
		}
	}
	//插入數(shù)據(jù)
	bool Insert(const K& key)
	{
		//檢測靜態(tài)哈希表是否已滿
		/*if (_size == _capatity)
		{
			cout << "哈希表已滿!" << endl;
			return false;
		}*/
		//考慮到載荷因子在0.7~0.8一下比較好，這樣檢查容量比較好
		if (10 * _size >= 8 * _capatity)
		{
			_CheckCapatity();
		}
		int index = _HashFunc(key);
		while (_state[index] == EXIST)
		{
			index++;//哈希沖突，找下一個位置
			//最后一個位置有數(shù)據(jù)，從頭開始找位置
			if (index == _capatity)
			{
				index = 0;
			}
		}
		//哈希不沖突，直接放數(shù)據(jù)
		_table[index] = key;
		_state[index] = EXIST;
		_size++;
		return true;
	}
	//查找
	int Find(const K& key)
	{
		int index = _HashFunc(key);
		while (_state[index] != EMPTY)
		{
			//找到元素
			if (_table[index] == key&&_state[index] == EXIST)
			{
				return index;
			}
			//如果算出的位置，不是要找的元素，index++;
			index++;
			//最后一個位置不是，就從頭開始找
			if (index == _capatity)
			{
				index = 0;
			}
		}
		return -1;
	}
	void print()
	{
		/*for (int i = 0; i < _capatity; i++)
		{
			if (_state[i] == EXIST)
			{
				printf("[%d]EXIST:%d\n",i, _table[i]);
			}
			else if (_state[i] == DELETE)
			{
				printf("[%d]DELETE:NULL\n", i, _table[i]);
			}
			else
			{
				printf("[%d]EMPTY:NULL\n", i);
			}
		}*/
		for (int i = 0; i < _capatity; i++)
		{
			if (_state[i] == EXIST)
			{
				cout << i <<"-"<< "EXIST:" << _table[i] << endl;
			}
			else if (_state[i] == DELETE)
			{
				cout << i <<"-"<< "DELETE:" << "NULL" << endl;
			}
			else
			{
				cout << i <<"-"<< "EMPTY:" << "NULL" << endl;
			}
		}
	}
	//刪除某一位置元素
	bool Remove(const K& key)
	{
		int index = Find(key);//找到這個元素
		//刪除這個元素
		if (index != -1)
		{
			_state[index] = DELETE;
			_size--;
			return true;
		}
		return false;
	}
protected:
	//算出數(shù)據(jù)在哈希表中的位置（哈希不沖突）
	/*int _HashFunc(const K& key)
	{
		return key%_capatity;
	}*/
	int _HashFunc(const K& key)
	{
		HashFunc ht;
		return ht(key) % _capatity;
	}
	//交換
	void _Swap(HashTable tmp)
	{
		swap(_size, tmp._size);
		swap(_capatity, tmp._capatity);
		swap(_state, tmp._state);
		swap(_table, tmp._table);
	}
	//檢查容量
	void _CheckCapatity()
	{
		HashTable tmp(2 * _capatity);
		for (int i = 0; i < _capatity; i++)
		{
			tmp.Insert(_table[i]);
		}
		_Swap(tmp);
	}
protected:
	K* _table;//數(shù)組
	State* _state;//狀態(tài)數(shù)組
	size_t _size;//數(shù)組大小
	size_t _capatity;//數(shù)組的容量
};
test.cpp中
#include 
using namespace std;
#include "Hash.h"
//void Test()
//{
//	HashTable ht(10);
//	ht.Insert(24);
//	ht.Insert(20);
//	ht.Insert(36);
//	ht.Insert(23);
//	ht.Insert(30);
//	ht.print();
//
//	int ret = ht.Find(30);
//	cout << "下標為："< ht(10);
	ht.Insert("杭哥");
	ht.Insert("張哥");
	ht.Insert("詹姐");
	ht.Insert("亮哥");
	ht.Insert("蛋蛋");
	ht.print();

	int ret = ht.Find("蛋蛋");
	cout << "下標為：" << ret << endl;

	ht.Remove("亮哥");
	ht.print();
}
int main()
{
	//Test();
	Test1();
	system("pause");
	return 0;
}
感謝你能夠認真閱讀完這篇文章，希望小編分享的“c#如何實現(xiàn)哈希表線性探測”這篇文章對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識等著你來學習!
            
            
                        

            網(wǎng)頁標題：c#如何實現(xiàn)哈希表線性探測            

            文章轉(zhuǎn)載：http://weahome.cn/article/jjsddp.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部