C++哈希表之線性探測(cè)法實(shí)現(xiàn)詳解

更新時(shí)間：2022年05月04日 10:50:24 作者：liufeng2023

線性探測(cè)法的優(yōu)點(diǎn)：只要散列表未滿，總能找到一個(gè)不沖突的散列地址；缺點(diǎn)：每個(gè)產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機(jī)會(huì)

1、哈希表-線性探測(cè)法理論

在這里插入圖片描述

線性探測(cè)法的理論我們?cè)谏弦黄┛鸵呀?jīng)闡述了。

現(xiàn)在我們來看看線性探測(cè)法的增刪查的代碼思想：

1.1、哈希表的增加元素

在這里插入圖片描述

注意：

往后遍歷尋找空閑位置的時(shí)候，要注意是環(huán)形遍歷哦！不然訪問數(shù)組就越界了。

在添加元素，發(fā)生位置被占用，即發(fā)生哈希沖突后，在向后遍歷尋找空閑位置的時(shí)候，我們要知道，這個(gè)空閑的位置是有兩種情況的：

1、這個(gè)位置一直是空的，沒放過元素。

2、這個(gè)位置是空的，以前放過元素，后來被刪除了。

1.2、哈希表的查詢操作

在這里插入圖片描述

當(dāng)用哈希函數(shù)計(jì)算得出的下標(biāo)值是3，然后去訪問數(shù)組，查詢時(shí)，發(fā)現(xiàn)該值不等于要查詢的元素的值val，說明當(dāng)時(shí)放val的時(shí)候發(fā)生了哈希沖突，這時(shí)候就要向后遍歷了；
訪問4下標(biāo)的時(shí)候發(fā)現(xiàn)這個(gè)位置是空的（空的有兩種情況），如果這個(gè)位置一直是空的，則就不用繼續(xù)向后找了，val不存在！因?yàn)槭蔷€性探測(cè)法，所以當(dāng)時(shí)val如果要放的時(shí)候肯定是要放在這里的。
但是如果這個(gè)位置是空的，但是之前放過元素，后來被刪除了，這個(gè)位置之前存放了元素，然后val插入的時(shí)候，就插到后面的空閑的位置了，所以此時(shí)我們還要繼續(xù)往后遍歷尋找val值。

在這里插入圖片描述

所以我們需要定義一個(gè)Bucket節(jié)點(diǎn)來表示每一個(gè)元素的所有的內(nèi)容。

在這里插入圖片描述

//桶的狀態(tài)
enum State
{
	STATE_UNUSE, //從未使用過的桶
	STATE_USING, //正在使用的桶 放著是一個(gè)有效的元素，沒有被刪過 
	STATE_DEL,  //元素被刪除了的桶，認(rèn)為桶里的元素?zé)o效了 
};
//我們刪除桶里的元素，并不是真正把值刪除掉，而是把桶的狀態(tài)置為STATE_DEL就認(rèn)為桶里的元素?zé)o效了 
//桶的類型
struct Bucket
{
	Bucket(int key = 0, State state = STATE_UNUSE)
		: key_(key)
		, state_(state)
	{}
	int key_;      //存儲(chǔ)的數(shù)據(jù)
	State state_;  //桶的當(dāng)前狀態(tài)
};

1.3、哈希表的刪除操作

在這里插入圖片描述

2、哈希表-線性探測(cè)法代碼實(shí)現(xiàn)

2.1、素?cái)?shù)表中的素?cái)?shù)

求素?cái)?shù)的代碼：（用于素?cái)?shù)表中的素?cái)?shù)取值）

在這里插入圖片描述

int main()
{
	int data = 3;
	for (int i = data; i < 10000; i++)
	{
		int j = 2;
		for (; j < i; j++)
		{
			if (i % j == 0)
				break;
		}
		if (j == i)
			cout << i << " ";
	}
	cout << endl;
	return 0;
}

到此這篇關(guān)于C++哈希表之線性探測(cè)法詳解使用的文章就介紹到這了,更多相關(guān)C++線性探測(cè)法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: