C++哈希表之线性探测法实现详解

目录
  • 1、哈希表-线性探测法理论
    • 1.1、哈希表的增加元素
    • 1.2、哈希表的查询操作
    • 1.3、哈希表的删除操作
  • 2、哈希表-线性探测法代码实现
    • 2.1、素数表中的素数

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++哈希表之线性探测法详解使用的文章就介绍到这了,更多相关C++线性探测法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++中使用哈希表(unordered_map)的一些常用操作方法

    目录 1.建立基本数据类型的哈希表 2.向哈希表中添加元素 1).insert函数 2).用数组方法直接添加 3.成员函数 begin(),end()函数 find()查找函数 count()查找函数 size()函数 empty()函数 clear()函数 swap()函数 哈希表的遍历 第一种遍历 第二种遍历 补充:实际应用 总结 1.建立基本数据类型的哈希表 unordered_map<int,int> m; //<string,string>,<char,char&g

  • C++ 实现哈希表的实例

    C++ 实现哈希表的实例 该散列表的散列函数采用了除法散列函数.乘法散列函数.全域散列函数,每一个槽都是使用有序单向链表实现. 实现代码: LinkNode.h #include<iostream> using namespace std; class Link; class LinkNode { private: int key; LinkNode* next; friend Link; public: LinkNode():key(-1),next(NULL){} LinkNode(int

  • C++基础算法基于哈希表的索引堆变形

    C++基础算法基于哈希表的索引堆变形

    目录 问题来源 问题简述 问题分析 代码展示 问题来源 此题来自于Hackerrank中的QHEAP1问题,考查了对堆结构的充分理解.成功完成此题,对最大堆或者最小堆的基本操作实现就没什么太大问题了. 问题简述 实现一个最小堆,对3种类型的输入能给出正确的操作: "1 v" - 表示往堆中增加一个值为v的元素 "2 v" - 表示删去堆中值为v的元素 "3" - 表示打印出堆中最小的那个元素 注意:题目保证了要删的元素必然是在堆中的,并且在任何时

  • C++哈希表之线性探测法实现详解

    C++哈希表之线性探测法实现详解

    目录 1.哈希表-线性探测法理论 1.1.哈希表的增加元素 1.2.哈希表的查询操作 1.3.哈希表的删除操作 2.哈希表-线性探测法代码实现 2.1.素数表中的素数 1.哈希表-线性探测法理论 线性探测法的理论我们在上一篇博客已经阐述了. 现在我们来看看线性探测法的增删查的代码思想: 1.1.哈希表的增加元素 注意: 往后遍历寻找空闲位置的时候,要注意是环形遍历哦!不然访问数组就越界了. 在添加元素,发生位置被占用,即发生哈希冲突后,在向后遍历寻找空闲位置的时候,我们要知道,这个空闲的位置是有

  • Python线性表种的单链表详解

    Python线性表种的单链表详解

    目录 1. 线性表简介 2. 数组 3. 单向链表 设计链表的实现 链表与顺序表的对比 1. 线性表简介 线性表是一种线性结构,它是由零个或多个数据元素构成的有限序列.线性表的特征是在一个序列中,除了头尾元素,每个元素都有且只有一个直接前驱,有且只有一个直接后继,而序列头元素没有直接前驱,序列尾元素没有直接后继. 数据结构中常见的线性结构有数组.单链表.双链表.循环链表等.线性表中的元素为某种相同的抽象数据类型.可以是C语言的内置类型或结构体,也可以是C++自定义类型. 2. 数组 数组在实际的

  • C语言实现顺序表的基本操作的示例详解

    C语言实现顺序表的基本操作的示例详解

    目录 一.认识顺序表 1.线性表 2.顺序表的概念及结构 二.顺序表的基本操作(接口实现) 1.初始化顺序表 2.打印顺序表 3.尾插 4.尾删 5.扩容 6.头插 7.头删 8.任意位置插入 9.任意位置删除 10.查找某个数的位置 三.顺序表演示及代码(含源码) 1.演示效果 2.完整源代码 一.认识顺序表 1.线性表 线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表有顺序表.链表.栈.队列.字符串……线性表在逻辑上是线性结构,也就是说是一条

  • MySQL 清除表空间碎片的实例详解

    MySQL 清除表空间碎片的实例详解

    MySQL 清除表空间碎片的实例详解 碎片产生的原因 (1)表的存储会出现碎片化,每当删除了一行内容,该段空间就会变为空白.被留空,而在一段时间内的大量删除操作,会使这种留空的空间变得比存储列表内容所使用的空间更大: (2)当执行插入操作时,MySQL会尝试使用空白空间,但如果某个空白空间一直没有被大小合适的数据占用,仍然无法将其彻底占用,就形成了碎片: (3)当MySQL对数据进行扫描时,它扫描的对象实际是列表的容量需求上限,也就是数据被写入的区域中处于峰值位置的部分: 例如: 一个表有1万行

  • thinkphp中的多表关联查询的实例详解

    thinkphp中的多表关联查询的实例详解 在进行后端管理系统的编程的时候一般会使用框架来进行页面的快速搭建,我最近使用比较多的就是thinkphp框架,thinkphp框架的应用其实就是把前端和后端进行分割管理,前端用户登录查询系统放在thinkphp中的home文件夹中进行管理,后端管理系统放在thinkphp中的admin文件夹中进行管理.对了,在使用thinkphp框架的时候是是要用到mvc架构的,mvc架构就是model(数据模型).view(视图).controller(控制器)的结

  • Oracle误删除表数据后的数据恢复详解

    Oracle误删除表数据后的恢复详解   测试环境: SYSTEM:IBM AIX 5L                         Oracle Version:10gR2 1. undo_retention参数的查询与修改 使用show parameter undo命令查看当前的数据库参数undo_retention设置. 显示如下: SQL> show parameter undo NAME                                 TYPE        VAL

  • Asp.Net MVC4通过id更新表单内容的思路详解

    用户需求是:一个表单一旦创建完,其中大部分的字段便不可再编辑.只能编辑其中部分字段. 而不可编辑是通过对input输入框设置disabled属性实现的,那么这时候直接向数据库中submit表单中的内容就会报错,因为有些不能为null的字段由于disabled属性根本无法在前端被获取而后更新至数据库. 有下面两种思路: 1.通过创建隐藏表单,为每一个disabled控件分别创建一个隐藏控件,但是这样的问题是工作量太大(如果表单有一千个属性,你懂的) 2.通过获取该表单在数据库中的id,把该id和可

  • 第七篇Bootstrap表单布局实例代码详解(三种表单布局)

    第七篇Bootstrap表单布局实例代码详解(三种表单布局)

    Bootstrap提供了三种表单布局:垂直表单,内联表单和水平表单.下面逐一给大家介绍,有兴趣的朋友一起学习吧. 创建垂直或基本表单: •·向父 <form> 元素添加 role="form". •·把标签和控件放在一个带有 class .form-group 的 <div> 中.这是获取最佳间距所必需的. •·向所有的文本元素 <input>.<textarea> 和 <select> 添加 class .form-cont

  • jQuery表单插件ajaxForm实例详解

    前端时间写项目用到了ajaxForm这个插件,可以用它提交表单和上传图片,听起来和正常的form表单提交没什么区别,只不过是ajax提交,无需刷新页面,如此可以增加用户体验度. 引入两个文件,PS:必须 <script type="text/javascript" src="http://img9.tongzhuo100.com/js/jquery-1.7.2.min.js"></script> <script type="t

  • C语言 表、栈和队列详解及实例代码

    C语言 表.栈和队列详解 表ADT 形如A1,A2,A3-An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素:CreateEmpty创建一个空表:Find返回关键字首次出现的位置:Insert和Delete从表的某个位置插入和删除某个关键字. 对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现.链表(linked list)由一系列不必在内存中相连的结构组成,每个结构均含有元素和指

随机推荐