数据结构和算法——散列表的性能分析（开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能）

（优点）选择合适的h（key），散列表的查找效率期望是常数O（1），它几乎与关键字的空间的大小n无关！也适合于关键字直接比较计算量大的问题它是以较小的为前提。因此，散列方法是以空间换时间（缺点）散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适用与范围查找，或最大值最小值查找。开放地址法（优点）散列表是一个数组，存储效率高，随机查找（缺点）散列表有“聚集”现象分离链接法散列表顺序存储和链

qiyi.sky

1196人浏览 · 2023-08-12 08:00:00

qiyi.sky · 2023-08-12 08:00:00 发布

散列表的性能分析

平均查找长度（ASL）用来度量散列表查找效率：成功、不成功
关键词的比较次数，取决于产生冲突的多少，影响产生冲突多少有以下三个因素：

散列函数是否均匀；
处理冲突的方法；
散列表的装填因子 $\alpha$

开放地址法的查找性能

线性探测法

可以证明，线性探测法的期望探测次数满足下列公式：

$p=\frac{1}{2}\left [ 1+\frac{1}{{(1-\alpha )}^2} \right ]$ （对插入和不成功查找而言）

$p=\frac{1}{2}\left ( 1+\frac{1}{1-\alpha } \right )$ （对成功查找而言）

当 $\alpha =0.5$ 时，

插入操作和不成功查找的期望 $ASLu=0.5*\left [ 1+ \frac{1}{{(1-0.5)}^2}\right ]=2.5$
成功查找的期望 $ASLs=0.5*\left ( 1+\frac{1}{1-0.5} \right )=1.5$

在实际问题中，

H（key）	0	1	2	3	4	5	6	7	8	9	10	11	12
key	11	30		47				7	29	9	84	54	20
冲突次数	0	6		0				0	1	0	3	1	3

$\alpha =9/13=0.69$ ，于是，经过公式计算得：

ASLu=5.70次，ASLs=2.11（实际计算ASLs=2.56）

平方探测法和双散列探测法

可以证明，平方探测法和双散列探测法探测次数满足下列公式：

$p=\frac{1}{1-\alpha }$ （对插入和不成功查找而言）

$p=-\frac{1}{\alpha }\ln(1-\alpha )$ （对成功查找而言）

当 $\alpha =0.5$ 时，

插入操作和不成功查找的期望 $ASLu=\frac{1}{1-0.5}=2$
成功查找的期望 $ASLs=-\frac{1}{0.5}\ln (1-0.5)\approx 1.39$

在实际问题中，

H（key）	0	1	2	3	4	5	6	7	8	9	10
key	11	30	20	47			84	7	29	9	54
冲突次数	0	3	3	0			2	0	1	0	0

$\alpha =9/11=0.82$ ，于是，通过公式计算得：

ASLu=5.56次，ASLs=2.09次（实际计算ASLs=2）。

期望探测次数与装填因子的关系

当装填因子 $\alpha < 0.5$ 的时候，各种探测法的期望探测次数都不大，也比较接近。
随着 $\alpha$ 的增大，线性探测法的期望探测次数增加较快，不成功查找和插入操作的期望探测次数比成功查找的期望探测次数要大。
合理的最大装填因子应该不超过0.85

分离链接法的查找性能

所有地址链表的平均长度定义成装填因子 $\alpha$ ， $\alpha$ 有可能超过1。

不难证明：其期望探测次数p为：

$p=\alpha +e^{-\alpha }$ （对插入和不成功查找而言）

$p=1+\frac{\alpha }{2}$ （对成功查找而言）

当 $\alpha =1$ 时，

插入操作和不成功查找的期望 $ASLu=1+e^{-1}=1.37$
成功查找的期望 $ASLs=1+\frac{1}{2}=1.5$

在实际问题中，

前面例子14个元素分布在11个单链表中，所以 $\alpha =14/11\approx 1.27$ ，故

期望ALSu=1.55次，ASLs=1.64次（实际计算ASLs为1.36）.

总结

（优点）选择合适的h（key），散列表的查找效率期望是常数O（1），它几乎与关键字的空间的大小n无关！也适合于关键字直接比较计算量大的问题
它是以较小的 $\alpha$ 为前提。因此，散列方法是以空间换时间
（缺点）散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适用与范围查找，或最大值最小值查找。

开放地址法

（优点）散列表是一个数组，存储效率高，随机查找
（缺点）散列表有“聚集”现象

分离链接法

散列表顺序存储和链式存储的结合，链表部分的存储效率和查找效率都比较低
（优点）关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”
（缺点）太小的 $\alpha$ 可能导致空间浪费，大的 $\alpha$ 又将付出更多的时机代价。不均匀的链表长度导致时间效率的严重下降。

end

学习自：MOOC数据结构——陈越、何钦铭

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。