目录
散列查找
一、散列表
对于现在的我们已知的查找算法有以下几种：
那么还有其他的查找算法吗？
顺序查找在数量庞大的时候依然比较捞，二分查找又不支持动态的查找（可以一边还存在插入删除），而使用二叉搜索树可能面临着关键词的比较（关键词太长比较依然麻烦）。
1.1Hash table(HT)
查找的本质是什么？
已知对象找位置。就会有两种可能：
- 有序安排对象：全序，半序（例如二分查找）
- 直接计算出对象的位置：散列
散列表(hash table)和哈希表是一回事。 通过用空间换时间的方式，将查找时间从O(n)下降到O(1)，类似于python字典这种数据结构，只是键-值是用哈希函数计算出来的。
1.2哈希算法的基本工作
散列查找法的两项基本工作：
- 计算位置：构造散列函数确定关键词存储位置；
- 解决冲突：应用某种策略解决多个关键词位置相同的问题；
1.3时间复杂度
时间复杂度几乎是常量：O（1），即查找时间与问题规模无关！
散列表（哈希表）
1.4散列（Hashing）基本思想
“散列（Hashing）” 的基本思想是：
（1）以关键字key为自变量，通过一个确定的函数 h（散列函数）， 计算出对应的函数值h(key)，作为数据对象的存储地址。
（2）可能不同的关键字会映射到同一个散列地址上， 即h(keyi ) = h(keyj )（当keyi ≠keyj），称为“冲突(Collision)”。 ----需要某种冲突解决策略
例子：
1.5装填因子（Loading Factor）：
设散列表空间大小为m，填入表中元素个数是n，则称α＝ n / m为散列表的装填因子 α＝11 / 17 ≈ 0.65。其反映了哈希表中的元素充满程度。
1.6查找成功平均查找长度ASL(success)
在哈希表中，对每一个存在于哈希表中的元素计算查找成功时的比较次数后求和取平均数。
【2018 统考真题】
现有长度为 7、初始为空的散列表 HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字 22,43,15 依次插入HT后，查找成功的平均查找长度是（2）。
构建哈希表：
| 哈希地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 元素 | 22 | 43 | 15 | ||||
| 查找次数 | 1 | 2 | 3 |
查找成功的平均查找长度：
ASL：（1+2+3）/3 = 2
1.7查找失败的平均查找长度ASL(failure)
查找失败是指查找的元素在哈希表中不存在。失败查找的平均查找长度是进行查找时的平均比较次数，直到确定元素不在表中。
可以理解为根据哈希函数的所有能得出的键值，查找该键值下一个不存在的元素，能确定不存在所比较的次数。
【2019 统考真题】
现有长度为 11 且初始为空的散列表 HT,散列函数是H(key)=key%7,采用线性探查(线性探测再散列)法解决冲突。将关键字序列 87,40,30,6,11,22,98.20依次插入 HT后，HT 查找失败的平均查找长度是( )
构造哈希表：
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 元素 | 98 | 22 | 30 | 87 | 11 | 40 | 6 | 20 | |||
| 查找次数 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 0 | 0 | 0 | 0 |
查找失败的平均查找长度
注意：这个哈希函数只能计算出键值为：0，1，2，3，4，5，6
根据这些个键值查找不存在的元素的比较次数。
（9+8+7+6+5+4+3）/ 7 = 6
【2023统考真题】
现有长度为5，初始为空的散列表HT，散列表函数H(K)=(k+4)%5用线性探查再散列法解决冲突。若将关键字序列2022,12,25依次插入HT中，然后删除关键字25，则HT中查找失败的平均查找长度( )。
解：
线性探查再散列法解决冲突属于开放地址法：
使用开放地址法时不可以随意删除元素，若元素删除后需做上标记，否则会截断具有相同哈希地址的数据元素的查找地址。
查找时遇到有删除标记的原素应该继续向后查找。
计算每个元素的哈希地址：
| 2022 | 12 | 25 |
| 1 | 1 | 4 |
先构建哈希表：
| 哈希地址 | 0 | 1 | 2 | 3 | 4 |
| 数据元素 | 2022 | 12 | 25（删除） | ||
| 查找失败次数 | 1 | 3 | 2 | 1 | 2 |
查找失败的平均查找长度：
（1+3+2+1+2）/ 5 = 1.8
二、散列函数的构造方法
一个好的散列函数应该考虑一下两点：
- 计算简单，以便于提高转换速度。
- 关键词对应的地址空间分布均匀，以尽量减少冲突。
2.1数字关键词的构造方法
①直接定址法
②除留余数法
③数字分析法
④折叠法
⑤平方取中法
2.2字符关键词的构造方法
①ASCII码加和除余法
②前三个字符移位法
③移位法
④快速计算
其实一个数乘以32就相当于其左移五位（25=32）：
三、冲突解决方法
散列查找的冲突处理方法有两种常见的思路：
- 将冲突的对象另外找个地方放置【开放地址法】
- 把映射到同一个位置有冲突的对象全部放在一起，可由采用一种链表结构，把这些有冲突的对象全部放在一个链表里面，将来从计算出来的这个地址出发（作为一个指针指向单项链表），然后去链表里去寻找这个对象。【链地址法】
3.1开放定址法
一旦产生了冲突（该地址已有元素），就按某种规则去寻找另一空地址。
也就是说：线性探测，平方探测，双散列等等都是开放地址法中引出的不同方案，即其使用的是一个不同的增量序列d，来决定冲突后的对象所存储的位置。
①线性探测法
聚集现象
线性探测法可能使第i个散列地址的冲突对象存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址……从而造成大量元素在相邻的散列地址上聚集（或堆积）起来，大大降低了查找效率。
聚集现象是因选取不当的冲突处理方法而造成的。
聚集现象因冲突而产生，其对存储效率，散列函数和装填因子均不会产生影响。而平均查找长度ASL会因为堆积现象而增大。
查找性能分析
查找性能主要和其平均查找次数有关：
冲突次数+1就等于比较次数，将这些成功查找到的比较次数进行加和在除以查找对象的个数就等于平均查找次数。
由于散列函数最后是对11取余，所有H(key)=0~10，并且H(key)不可能等于11，故将查找不成功的数分为11类【H(key)=0,1,2,3,4,5,6,7,8,9,10】，最后将查找不成功的比较次数除以类数就是平均查找不成功的次数了。
当出现删除的情况时：
线性探测-字符串的例子
②平方探测法
平方探测法的性质
提出一个问题：是否有空间，平方探测（二次探测）就能找得到？
像以上这个情况就会找不到，其下一个地址永远都在0，2之间跳来跳去。
定理：
如果散列表的长度tablesize是某个4K+3（K是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间。
平方探测法的实现
需要注意的是在开放定址法中不能简单的将一个元素删除，需要将其打上delete的标号，防止查询其他元素的时候发生错误。
③双散列探测法
④再散列
3.2链地址法
分离链接法(拉链法)
四、散列表的性能分析
1.平均查找长度ASL用来度量散列表查找效率：成功，不成功
2.关键词的比较次数取决于产生冲突的多少
3.影响产生冲突多少有以下三个因素：
- 散列函数是否均匀；
- 处理冲突的方法；
- 散列表的装填因子α ；
4.1线性探测的性能
4.2平方探测的性能
4.3分离链接法的性能
【求ASL例子】
数据元素序列：
10,24,32,17,31,30,46,47,40,63,49
哈希函数：
H(K) = K%16
采用拉链法解决冲突问题；
根据题意建立哈希表：
查找成功的平均查找长度：
（6x1+4x2+1x3）/ 11 = 1.5
查找不成功的平均查找长度：
（1x2+2x3+3x1+10x1）/ 16 = 1.3
4.4期望探测次数与装填因子α的关系
【2011 统考真题】
为提高散列表的查找效率，可以采取的正确措施是（D）
Ⅰ.增大装填(载)因子x
Ⅱ.设计冲突(碰撞)少的散列函数
Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象
A.仅Ⅰ B.仅Ⅱ
C.仅Ⅰ，Ⅱ D.仅Ⅱ，Ш
【2014 统考真题】
用哈希(散列)方法处理波突(碰撞)时可能出现堆积(聚集)现象,下列选项中，会受堆积现象直接影响的是(D)
A.存储效率 B.散列函数。
C.装填(装载)因子 D.平约查找长度
存储效率和散列函数有关；
装填因子反应哈希表的装满度；
【2022 统考真题】
下列因素中，影响散列(哈希)方法平均查找长度的是(D).
Ⅰ.装填因子 Ⅱ.散列函数 Ⅲ.冲突解决策略
A. 仅Ⅰ、Ⅱ B.仅Ⅰ、Ⅲ C.仅Ⅰ、Ш D. Ⅰ、Ⅱ、Ⅲ
五、总结
选择合适的散列函数h(key)，散列法的查找效率期望是常数O（1），它几乎与关键字的空间的大小n无关！也适用于关键字直接比较计算量大的问题；
它是以较小的α为前提。因此，散列方法是一个以空间换时间的方法；
散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找，或最大值最小值查找。
对于开放地址法来说：
1.散列表是一个数组，存储效率高，随机查找。
2.散列表会存在“聚集”现象。
3.关键字删除需要“懒惰删除”法，从而产生存储“垃圾”。
对于分离链法来说：
1.散列表是顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低。
2.关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”。
3.太小的α可能导致空间浪费，大的α又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降。
标签：探测,地址,查找,冲突,哈希,散列 From： https://blog.csdn.net/weixin_65866298/article/details/143205319