哈希表的引入---线性探测法&链地址法&&模拟实现&哈希函数&冲突处理

文章声明：仅供学习交流，主要是和哈希表相关的内容，部分图片来自于这个比特算法课的图片，侵权联系删除

1.哈希表的引入

下面的这个类似的题目实际上就是我们的哈希表的使用：

哈希表：关键字----映射关系-----对应位置

下面的这个题目，关键字就是字符，映射关系就是我们的for循环的处理流程，对应位置就是我们的数组里面的位置；

image-20250724140232055

哈希函数：映射关系的函数，也就是这个关键字是如何映射到我们的对应位置里面去的；

哈希冲突：两个或者是两个以上的这个关键字映射到相同的这个位置上面去，这个情况下就是冲突，也就是两个或者多个不同的关键字通过这个函数，对应到了一样的位置上面去；

下面的这个例子里面，我们的2和17除以7之后的余数是一样的，因此对应到一样的这个位置，因此这个时候就是哈希冲突，我们下面会介绍两个方式解决这个冲突

image-20250724140922166

2.常见的哈希函数

直接定址法：通过哈希函数直接确定这个对应的存放的地址，上面的这个字符存放其实就是我们的直接定地址法

除留余数法：也就是上面的第二个图片里面的数组除以7取余数的这个方法，根据这个余数的具体的数值确定我们的这个数字出现在的具体的位置；

3.处理哈希冲突

有些时候，无论我们选择什么样子的函数，都是无法解决哈希冲突的，因此我们需要看一下如何处理哈希冲突

3.1线性探测方法

线性探测：下面的这个例子也是非常的清楚啦，19和30对应的都是8这个下标的位置，因此这个30进去的时候，8这个下标存在了元素，我们的这个30就往后面去找，找打一个空闲的位置进行这个数据的存放即可；

image-20250724142217150

3.2链地址法

下面的这个就是我们的链地址法生动解释：也就是我们的这个hash表里面的每一个节点存放的不是我们的具体的数据，而是可以理解成为指针，这个指着指向的就是我们的链表，这个时候出现冲突元素的时候，直接插入到这个对应节点的链表里面即可（需要进行头插）；

image-20250724142635217

4.模拟实现链地址法

4.1初始化

image-20250724150511628

4.2负数补正

这个单独的列举出来主要还是想要说明一下这个问题，就是说的我们的这个取余数的这个方法里面如果出现了这个负数的情况，此时我们是需要把这个负数转换成为正数；

转换的这个方式就是我们的这个模数+模数的思想，但是这个负数转换成为这个正数的同时，我们的这个

4.3哈希函数的实现

下面的这个id的操作就是进行上面描述的这个负数补正的这个过程；

image-20250724150830566

4.4添加元素

通过哈希函数确定我们插入的这个数据的id大小，在这个id下标的位置放进去这个数据即可；

image-20250724155208573

4.5查找元素

通过这个哈希函数找到我们的这个元素的小标，看看这个位置的元素和我们的这个数字是不是一样的，返回这个布尔值即可；

image-20250724155226701

4.6测试代码

在这个测试代码里面，我们实际上包含的就是两个类型的操作，也就是插入元素和查找元素

我们设置这个op参数，op=1的时候就是进行这个数据的插入操作,op=2的时候检查我们的这个元素在这个哈希表里面是不是存在的；

image-20250724155316832

5.链地址法

因为这个事连地址方法，因此这个主要使用的还是我们的这个链表里面的相关操作；

但是对于这个链表里面的实现，我之前学习的一直都是这个结构体的方式进行实现的，但是这个教程里面针对于这个链表的相关的操作更多是使用我们的数值域数组和这个指针域数组进行实现的；

我们的h表示的就是哈希表，这个h里面的每一额元素就是我们的头结点，因此我们的这个insert插入操作的时候ne[id]也就是我们的这个新插入的节点需要指向我们的头结点，也就是这个h[idx]位置，这个时候我们的这个哨兵位指向这个新插入的节点即可，也就是id赋值给我们的这个h[idx]因为这个h[idx]表示的就是我们的这个头结点；

查找的过程就是对于我们的这个链表进行这个遍历的过程，I从h[idx]开始，也就是这个头结点开始，不为空，直到我们的这个ne[i]一直遍历到最后，也就是我们的这个ne数组里面代表的这个指针不断的向后面去进行这个查找的过程；