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

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

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

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

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

[微信提示：高防服务器能助您降低 IT 成本，提升运维效率，使您更专注于核心业务创新。

[图文来源于网络，不代表本站立场，如有侵权，请联系高防服务器网删除]
[