C++哈希表之线性探测法怎么实现

蜗牛 互联网技术资讯 2022-05-07 26 0

今天小编给大家分享一下C++哈希表之线性探测法怎么实现的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

1、哈希表-线性探测法理论

C++哈希表之线性探测法怎么实现  c++ 第1张

线性探测法的理论我们在上一篇博客已经阐述了。

现在我们来看看线性探测法的增删查的代码思想:

1.1、哈希表的增加元素

C++哈希表之线性探测法怎么实现  c++ 第2张

注意:

往后遍历寻找空闲位置的时候,要注意是环形遍历哦!不然访问数组就越界了。

在添加元素,发生位置被占用,即发生哈希冲突后,在向后遍历寻找空闲位置的时候,我们要知道,这个空闲的位置是有两种情况的:

1、这个位置一直是空的,没放过元素。

2、这个位置是空的,以前放过元素,后来被删除了。

1.2、哈希表的查询操作

C++哈希表之线性探测法怎么实现  c++ 第3张

C++哈希表之线性探测法怎么实现  c++ 第4张

  • 当用哈希函数计算得出的下标值是3,然后去访问数组,查询时,发现该值不等于要查询的元素的值val,说明当时放val的时候发生了哈希冲突,这时候就要向后遍历了;

  • 访问4下标的时候发现这个位置是空的(空的有两种情况),如果这个位置一直是空的,则就不用继续向后找了,val不存在!因为是线性探测法,所以当时val如果要放的时候肯定是要放在这里的。

  • 但是如果这个位置是空的,但是之前放过元素,后来被删除了,这个位置之前存放了元素,然后val插入的时候,就插到后面的空闲的位置了,所以此时我们还要继续往后遍历寻找val值。

C++哈希表之线性探测法怎么实现  c++ 第5张

所以我们需要定义一个Bucket节点来表示每一个元素的所有的内容。

C++哈希表之线性探测法怎么实现  c++ 第6张

//桶的状态
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、哈希表的删除操作

C++哈希表之线性探测法怎么实现  c++ 第7张

2、哈希表-线性探测法代码实现

2.1、素数表中的素数

求素数的代码:(用于素数表中的素数取值)

C++哈希表之线性探测法怎么实现  c++ 第8张

C++哈希表之线性探测法怎么实现  c++ 第9张

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

以上就是“C++哈希表之线性探测法怎么实现”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注蜗牛博客行业资讯频道。

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:niceseo99@gmail.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

评论