1、哈希表-線性探測法理論

線性探測法的理論我們在上一篇博客已經闡述了。

現在我們來看看線性探測法的增刪查的代碼思想：

1.1、哈希表的增加元素

注意：

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

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

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

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

1.2、哈希表的查詢操作

• 當用哈希函數計算得出的下標值是3，然后去訪問數組，查詢時，發現該值不等于要查詢的元素的值val，說明當時放val的時候發生了哈希沖突，這時候就要向后遍歷了；
• 訪問4下標的時候發現這個位置是空的（空的有兩種情況），如果這個位置一直是空的，則就不用繼續向后找了，val不存在！因為是線性探測法，所以當時val如果要放的時候肯定是要放在這里的。
• 但是如果這個位置是空的，但是之前放過元素，后來被刪除了，這個位置之前存放了元素，然后val插入的時候，就插到后面的空閑的位置了，所以此時我們還要繼續往后遍歷尋找val值。

所以我們需要定義一個Bucket節點來表示每一個元素的所有的內容。

//桶的狀態
enum State
{
	STATE_UNUSE, //從未使用過的桶
	STATE_USING, //正在使用的桶 放著是一個有效的元素，沒有被刪過 
	STATE_DEL,  //元素被刪除了的桶，認為桶里的元素無效了 
};
//我們刪除桶里的元素，并不是真正把值刪除掉，而是把桶的狀態置為STATE_DEL就認為桶里的元素無效了 
//桶的類型
struct Bucket
{
	Bucket(int key = 0, State state = STATE_UNUSE)
		: key_(key)
		, state_(state)
	{}
	int key_;      //存儲的數據
	State state_;  //桶的當前狀態
};

1.3、哈希表的刪除操作

2、哈希表-線性探測法代碼實現

2.1、素數表中的素數

求素數的代碼：（用于素數表中的素數取值）

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;
}