【C++】哈?；A(chǔ)1-創(chuàng)新互聯(lián)

文章目錄

• 哈希概念
• 哈希函數(shù)
• 哈希沖突
• • 閉散列
  • • 線性探測
  • 開散列
  • • 開散列增容
  • 開散列與閉散列比較

成都創(chuàng)新互聯(lián)公司是專業(yè)的河曲網(wǎng)站建設(shè)公司，河曲接單;提供網(wǎng)站制作、成都做網(wǎng)站,網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行河曲網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!哈希概念

順序結(jié)構(gòu)以及平衡樹中，元素關(guān)鍵碼與其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個(gè)元素時(shí)，必須要經(jīng)過關(guān)鍵碼的多次比較，順序查找的時(shí)間復(fù)雜度為O(N)，平衡樹中為樹的告訴，搜索的效率取決于搜索過程中元素的比較次數(shù)。

所以我們?nèi)绻胍岣咚阉餍?，自然就想到要減小比較次數(shù)，甚至是有沒有一種辦法能不經(jīng)過任何比較，一次直接從表中得到要搜索的元素，這是我們理想中的搜索方法。

那如果構(gòu)造一種存儲結(jié)構(gòu)，通過某種函數(shù)使元素的存儲位置和它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時(shí)通過該函數(shù)可以很快的找到該元素。

當(dāng)向該結(jié)構(gòu)中插入元素時(shí)：

• 根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計(jì)算出該元素的存儲位置并按此位置進(jìn)行存放

當(dāng)在該結(jié)構(gòu)中搜索元素時(shí)：

• 對元素的關(guān)鍵碼進(jìn)行同樣的計(jì)算，把求得的函數(shù)值當(dāng)作元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功

該方法即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)也叫散列函數(shù)，構(gòu)造出來的結(jié)構(gòu)稱為哈希表，也叫散列表

哈希函數(shù)

當(dāng)我們的哈希函數(shù)設(shè)計(jì)的不合理的時(shí)候，可能會引起哈希沖突。

哈希函數(shù)的設(shè)計(jì)原則：

• 哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果哈希表允許有m個(gè)地址，那哈希函數(shù)的值域必須在0-m-1之間
• 哈希函數(shù)計(jì)算出來的地址能均勻的分布在整個(gè)空間中
• 哈希函數(shù)應(yīng)該比較簡單

常見哈希函數(shù)的設(shè)計(jì)方法有：直接定制法、除留余數(shù)法、平方取中法、折疊法、隨機(jī)數(shù)法、數(shù)字分析法。

我們最常用的兩種方法就是直接定制法和除留余數(shù)法。

直接定制法：取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址：Hash(Key) = A*Key + B，優(yōu)點(diǎn)：簡單且均勻
缺點(diǎn)：需要事先知道關(guān)鍵字的分布情況
使用場景：適合查找比較小且連續(xù)的情況

除留余數(shù)法：設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：Hash(Key) = key%p，將關(guān)鍵碼轉(zhuǎn)換成哈希地址。

哈希沖突

哈希沖突：不同的關(guān)鍵字通過相同的哈希函數(shù)計(jì)算出相同的哈希地址，該種現(xiàn)象稱為哈希沖突或者哈希碰撞
把具有不同關(guān)鍵碼而具有相同哈希地址的數(shù)據(jù)元素稱為“同義詞”

哈希沖突的解決方式有兩種：開散列和閉散列

閉散列

閉散列法也叫開放地址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被填滿，說明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置的“下一個(gè)”空位置中去，關(guān)于如何尋找下一個(gè)空位置，我們有線性探測法。

線性探測

從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個(gè)空位置為止。

插入：通過哈希函數(shù)獲取待插入元素在哈希表中的位置，如果該位置沒有元素則直接插入新元素，如果該位置有元素發(fā)生哈希沖突，使用線性探測找到下一個(gè)空位置，插入新元素

刪除：采用閉散列處理哈希沖突時(shí)，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會影響其他元素的搜索，因此線性探測采用標(biāo)記的偽刪除法來刪除一個(gè)元素，意思就是哈希表給每個(gè)空間一個(gè)標(biāo)記。

線性探測的缺點(diǎn)：一旦發(fā)生了哈希沖突，所有的沖突連在一起，容易產(chǎn)生數(shù)據(jù)“堆積”，即：不同關(guān)鍵碼占據(jù)了可利用的空位置，使得尋找某關(guān)鍵碼的位置需要許多次比較，導(dǎo)致搜索效率降低。

此時(shí)思考一個(gè)問題，哈希表在什么情況下進(jìn)行擴(kuò)容？如何進(jìn)行擴(kuò)容？

哈希表的載荷因子定義為：α = 填入表中的元素個(gè)數(shù) / 哈希表的長度。
α是哈希表裝滿程度的標(biāo)志因子，由于表長是定值，α與“填入表中的元素個(gè)數(shù)成正比”，所以α越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性越大，反之，α越小，標(biāo)明填入表中的元素越少，產(chǎn)生沖突的可能性就越小，實(shí)際上，哈希表的平均查找長度是載荷因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。

對于開放地址法，載荷因子是特別重要的因素，應(yīng)嚴(yán)格限制在0.7-0.8以下。研究表明：當(dāng)表的長度為質(zhì)數(shù)且表裝載因子不超過0.5時(shí)，新的表項(xiàng)一定能夠插入，而且任何一個(gè)位置都不會被探查兩次，因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時(shí)可以不考慮表裝滿的情況，但是在插入時(shí)必須確保表的裝載因子不超過0.5，如果超出必須考慮增容。

因此：閉散列大的缺陷就是空間利用率比較低，這也是哈希的缺陷。

閉散列哈希表的模式實(shí)現(xiàn)，代碼如下：

enum State {EMPTY, EXIST, DELETE };
//給每個(gè)空間一個(gè)標(biāo)記，分別表示空，有元素，元素已被刪除
templateclass HashTable
{struct Elem
	{pair_val;
		State _state;
	};
public:
	HashTable(size_t sz) :m_ht(sz), m_size(0)
	{for (int i = 0; i< sz; ++i)
		{	m_ht[i]._state = EMPTY;
			//構(gòu)造，將哈希表每一個(gè)位置都置為空
		}
	}
public:
	void Insert(const pair&val)
	{//找到哈希位置
		//判斷是否為空
		//為空直接插入，不為空線性探測

		size_t hash_idx = Hash(val);
		size_t origin_idx = hash_idx;

		CheckCapacity();//檢查容量

		while (m_ht[hash_idx]._state == EXIST)
		{	hash_idx = (hash_idx + 1) % m_ht.capacity();
			if (hash_idx == origin_idx)//?????
				return;
		}
		Elem e = {val,EXIST };
		m_ht[hash_idx] = e;
		m_size++;
	}

	int Find(const pair&key)
	{//去該在的哈希位置找
		//找到返回，找不到線性探測找下一個(gè)
		size_t hash_idx = Hash(key);
		size_t origin_idx = hash_idx;
		while (m_ht[hash_idx]._state == EXIST && m_ht[hash_idx]._val != key)
		{	hash_idx = (hash_idx + 1) % m_ht.capacity();
			if (hash_idx == origin_idx)//找一圈沒找到返回
				return -1;
		}
		//兩種情況跳出循環(huán)，都需要考慮
		if (m_ht[hash_idx]._state == EXIST)
			return hash_idx;
		return -1;
	}

	void Remove(const pair&key)
	{//首先判斷是否有key元素，有了再刪，沒了就不刪，直接退出
		int hash_idx = Find(key);

		if (hash_idx != -1)
		{	m_ht[hash_idx]._state = DELETE;//標(biāo)記刪除
			m_size--;
		}
	}
	//如果在某種結(jié)構(gòu)里面進(jìn)行了插入或者刪除操作，一定記得對計(jì)數(shù)器進(jìn)行操作

	int GetNextPrime(int cur_prime)
	{static int prime_table[] = {7,13,19,23,29,43,53,93,103 };
		int n = sizeof(prime_table) / sizeof(prime_table[0]);

		int i;
		for (i = 0; i< n; ++i)
		{	if (cur_prime == prime_table[i])
				//找到當(dāng)前的n
				break;
		}
		return i< n ? prime_table[i + 1] : prime_table[n - 1];
	}

	void CheckCapacity()
	{if (m_size * 10 / m_ht.capacity() >= 7)//a=0.7
		{	HashTablenew_ht(GetNextPrime(m_ht.capacity()));

			for (size_t i = 0; i< m_ht.capacity(); ++i)
			{		if (m_ht[i]._state == EXIST)
					new_ht.Insert(m_ht[i]._val);
			}
			m_ht.swap(new_ht.m_ht);
		}
	}
public:
	void Show()const
	{for (int i = 0; i< m_size; ++i)
		{	cout<< m_ht[i]._val.first;
			cout<< " ";
		}
	}
protected:
	size_t Hash(const pair&val)
	{return val.first % m_ht.capacity();//除留余數(shù)法
		//哈希內(nèi)部元素是vector，可以計(jì)算出容量
	}
private:
	vectorm_ht;
	size_t       m_size;
};
void main()
{int ar[] = {1,9,4,10,8,22,20 };
	int n = sizeof(ar) / sizeof(ar[0]);
	HashTableht(7);
	
	for (int i = 0; i< n; ++i)
	{pairv = make_pair(ar[i], ar[i]);
		ht.Insert(v);
	}

	//pairv = make_pair(15, 15);
	//ht.Insert(v);
	ht.Show(); 
	int idx = ht.Find(make_pair(10,10));

}

開散列

開散列法又叫鏈地址法，首先對關(guān)鍵碼集合利用哈希函數(shù)計(jì)算哈希地址，具有相同哈希地址的關(guān)鍵碼歸于同一個(gè)子集合，每一個(gè)子集稱為一個(gè)桶，各個(gè)桶中的元素通過一個(gè)單鏈表鏈接起來，各鏈表的頭結(jié)點(diǎn)存儲在哈希表中。每個(gè)桶中放的都是發(fā)生哈希沖突的元素。

開散列哈希表的模擬實(shí)現(xiàn)，代碼如下：

templateclass HashTable;

templateclass HashNode
{friend class HashTable;
public:
	HashNode(Type d=Type(),HashNode*n = nullptr):data(d),next(n)
	{}
	~HashNode()
	{}
private:
	Type data;
	HashNode *next;
};

templateclass HashTable
{public:
	HashTable()
	{memset(m_ht, 0, sizeof(m_ht));
	}
public:
	HashNode* Find(const Type& key)
	{//先去對應(yīng)的hash位置上進(jìn)行查找
		//在去對應(yīng)位置的hash節(jié)點(diǎn)進(jìn)行查找
		size_t idx = Hash(key);
		HashNode*p = m_ht[idx];
		//當(dāng)沒找到的時(shí)候就繼續(xù)循環(huán)
		while (p != nullptr&&key != p->next)
			p = p->next;
		return p;
	}

	void Remove(const Type& key)
	{size_t idx = Hash(key);
		HashNode*p = m_ht[idx];
		if (p == nullptr)
			return;
		
		if (m_ht[idx]->data == key)
			m_ht[idx] = p->next;
		else
		{	while (p != nullptr&&p->next->data != key)
				p = p->next;//p是要被刪除節(jié)點(diǎn)的prev節(jié)點(diǎn)

			if (p == nullptr)
				return;

			HashNode*prev = p;
			p = p->next;
			prev->next = p->next;
		}
		delete(p);
	}

	void Insert(const Type& v)
	{//找到位置
		size_t idx = Hash(v);
		//插入數(shù)據(jù)
		HashNode*node = new HashNode(v);
		node->next = m_ht[idx];
		m_ht[idx] = node;
	}

	void Show()const
	{for (int i = 0; i< HASH_TABLE_SIXE; ++i)
		{	cout<< i<< " : ";
			HashNode*p = m_ht[i];
			while (p != nullptr)
			{		cout<< p->data<< "-->";
				p = p->next;
			}
			cout<< "Nil."<< endl;
		}
	}

protected:
	size_t Hash(const Type &Key)
	{return Key % HASH_TABLE_SIXE;
		//除留余數(shù)法找到hash位置
	}
protected:
	enum {HASH_TABLE_SIXE = 7 };
private:
	HashNode* m_ht[HASH_TABLE_SIXE];
};

void main()
{int ar[] = {19,14,23,1,68,20,84,27,55,11,10,79 };
	int n = sizeof(ar) / sizeof(ar[0]);

	HashTableht;
	for (int i = 0; i< n; ++i)
	{ht.Insert(ar[i]);
	}
	ht.Show();

	ht.Remove(1);
	ht.Show();
	
	HashNode*p = ht.Find(20);
}

開散列增容

桶的個(gè)數(shù)是一定的，隨著元素的不斷插入，每個(gè)桶中元素的個(gè)數(shù)不斷增多，極端情況下，可能會導(dǎo)致一個(gè)桶中鏈表結(jié)點(diǎn)非常多，會影響哈希表的性能，因此在一定條件下需要對哈希表進(jìn)行增容，那在什么情況下進(jìn)行增容呢？開散列最好的情況是每個(gè)哈希桶中剛好掛一個(gè)節(jié)點(diǎn)，再繼續(xù)插入元素時(shí)，每一次都會發(fā)生哈希沖突，因此，在元素個(gè)數(shù)剛好等于桶的個(gè)數(shù)時(shí)，可以給哈希表增容。

開散列與閉散列比較

應(yīng)用鏈地址法處理溢出，需要增設(shè)鏈接指針，似乎增加了存儲開銷。事實(shí)上：由于開地址法必須保持大量的空閑空間以確保搜索效率，如二次探查法要求裝載因子小于0.7，而表項(xiàng)所占空間又比指針大的多，所以使用鏈地址法反而比開地址法節(jié)省存儲空間。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：【C++】哈希基礎(chǔ)1-創(chuàng)新互聯(lián)
URL鏈接：http://muchs.cn/article34/dooese.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、建站公司、定制網(wǎng)站、Google、網(wǎng)頁設(shè)計(jì)公司、微信小程序

廣告

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