指除1和此整数本身外
发布时间：2025-06-24 19:22:39 作者：北方职教升学中心 阅读量：368
指除1和此整数本身外，
特别注意：关于删除操作。
寻找目标20，计算目标元素存储地址：20=7； 20搜索成功，寻找长度=1。链地址法)︰在链表中存储所有“同义词”。
删除目标#xff1a;27 ，计算目标元素存储地址：27=1； 27搜索成功删除成功。对比位置#1关键字不等于1;
根据线性探测法的探测序列，继续比较位置#2关键字不等于1;
根据线性探测法的探测序列，继续比较位置#3该位置的原始关键字已删除#xff0c;继续探测后一个位置；
根据线性探测法的探测序列，继续比较位置#4关键字等于1查找成功。
拉链法(又称链接法、但默认情况下，
设计散列函数时应注意：
除留余数法——H(key) = key % p。
注释：一些教科书还将“空指针对比”计入搜索长度。
寻找目标21计算目标元素存储地址：21=8； 21发现失败，寻找长度=0。
寻找目标66计算目标元素存储地址：66=1； 66发现失败寻找长度=4。
搜索长度-搜索计算，比较关键字的次数称为搜索长度.。链地址法)︰在链表中存储所有“同义词”。
开放定址法:如有“冲突”，为新元素找到另一个空闲位置。
删除散列表(拉链法解决冲突)。 散列函数（哈希函数)︰Addr=H(key)建立了“关键词”→“存储地址”的映射关系。
正确示范：搜索元素1。
1=1。
开放定址法︰如果发生“冲突”，为新元素找到另一个空闲位置。
设置关键字为r进制数〈如十进制数，R个数字出现在你身上的频率不一定相同，可能在某些位置分布均匀，出现每个数字的机会是平等的；在某些位置分布不均匀，只有几个数字经常出现，此时，可以选择数码分布均匀的多个位置作为散列地址。
散列表表长为m，取一个不大于m但最接近或等于m的质数p。
删除目标#xff1a;20 ，计算目标元素的存储地址：20=7； 20成功搜索删除成功。
冲突（碰撞)︰将数据元素插入散列表时，存储地址需要根据关键字的值来确定c;如果地址已经存储了其他元素，这种情况称为“冲突(碰撞)”。
7.5.2 散列函数的结构。
#xff08;哈希表，Hash Table)︰它是一种数据结构。
注：d表示第一次发生冲突时下一个探测地址与初始散列地址的相对偏移。若匹配，“成功搜索”。
适用场景：关键字分布基本连续。
如何处理冲突#xff1f;
拉链法(又称链接法、
23=11。
Step 2∶如果关键字不匹配，
如何在散列表(拉链法解决冲突)中插入新元素？
Step 1:新元素的散列地址结合散列函数计算。
其中，a和b是常数。从而减少“冲突”。该方法获得的散列地址与每个关键字都有关系，因此，根据散列函数计算散列地址，比较关键字是否匹配。
删除目标#xff1a;66 ，计算目标元素存储地址：66=1； 66发现失败删除失败。散列地址的分布更加均匀。
数字分析法-选择数字分布均匀的位置作为散列地址。
扩展：除了剩余数法，
7.5.3_2 处理冲突的方法_开放定址法。
例︰长度为13的散列表状态如下图所示，散列函数H(key)=key，冲突采用线性探测法解决。
计算元素1的初始散列地址=1=1。如果发生冲突，
7.5.1 散列表的基本概念。
如何减少“冲突”？
散列函数 H(key)=key 说，1 和 14 是“同义词”，可构建更合适的散列函数，让每个关键字尽可能地映射到不同的存储位置，
注︰质数又称素数。
散列表的插⼊操作（拉链法解决冲突#xff09;
查找散列表(拉链法解决冲突)。
H根据散列函数(key)，获取初始散列地址。
适用场景：关键字集已知，而且关键字的某些数字位分布均匀。
具体取多少位取决于实际情况。
7.5.3_1 处理冲突的方法_拉链法。
散列函数（哈希函数)︰Addr=H(key)建立了“关键词”→映射关系“存储地址”。
Step 2:将新元素插入散列地址对应的链表（可用的头插法尾插法也可以使用)。特点是∶它在散列表中的存储地址可以根据数据元素的关键字来计算。#xff00c;如何找到“另一个空闲位置”？
如何删除一个元素：。
开放定址法的基本原则。
Eg:将散列函数改为H(key)=key，没有冲突。不能被其他自然数整除的数字。
Step 3:如果“搜索成功”，删除找到的元素。
适用场景:比较通用，只要关键字是整数。
平方取中法-取关键字平方值的中间位数作为散列地址。
19=7。如果关键字分布不连续空间更多会造成存储空间的浪费。为什么要对质数进行剩余？f;
直接定址法——H(key) = key或H(key) = a*key + b。考试只有统计数据 “关键词比较次数”。
同义词:如果不同的关键字通过散列函数映射到相同的存储地址，称之为“同义词”。
14=2。
Step 1∶首先，计算这种方法最简单而且不会发生冲突。#xff00c;然后将下一个地址的关键字与“探测序列”进行比较c;直到“搜索成功”或“搜索失败”。
适用场景：关键字的每个值都不够均匀。
