8.5.3 哈希表的查找和性能分析在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课，我们接着讨论哈希表

这节课我们总结一下哈希表的查找及其性能的分析

通过上节课的例子已经看到

在哈希表上进行查找的过程

和哈希表的造表过程基本上是一致的

当给定一个k值以后

就根据造表时设定的哈希函数，计算哈希地址

若哈希表中此位置上没有记录

则查找不成功，返回

若表中此位置上有记录

则比较记录的关键字和给定值

如果相等，则查找成功

如果不等

则的根据造表时设定的处理冲突的方法

找下一个哈希地址

直至哈希表中，某个地址为空

意味着查找不成功

或是哈希地址中所填记录的关键字

等于给定值

这是查找成功

在哈希表中进行查找

除非哈希表完全被填满

否则查找失败都是在哈希表中遇到空单元

我们知道查找失败了

空单元的多少对哈希表的查找性能有决定性的影响

下面对哈希表的查找分析做一个总结

用哈希表作为动态查找表

希望平均查找长度为1

但构建哈希表的过程中可能会产生冲突

因此，在哈希表上进行查找

还是需要通过比较来确定查找是否成功

仍然存在平均查找长度的问题

一般情况下

在哈希函数为"均匀"的前提下

哈希表的平均查找长度仅取决于

处理冲突的方法和哈希表的装填因子

装填因子定义为：α=表中记录数/哈希表长度

装填因子描述了哈希表装满的程度

下面看一个例子，直观了解一下装满程度对查找性能的影响

哈希函数为H(key)=key mod 13

利用线性探测再散列处理冲突

这个哈希表长度是14

有12个单元都已经存储了记录，装的比较满了

考虑查找成功，装的满

意味着插入记录时可能需要多次计算下一个哈希地址

那么查找时比较的次数就会增加

例如，设给定值是84，查找成功需要比较三次

考虑查找失败，从上述的讨论我们知道

只有哈希地址对应的单元为空，才知道查找失败

装的满，意味着空单元少

例如，设给定值为36，哈希地址是10

10号单元不空，关键字不等，计算H1

哈希地址是11，也是不空不等，计算H2

是12也是不空不等

继续计算H3，是13,13号单元为空，知道查找失败

同学们可以考虑，如果要查找的给定值是40

哈希地址1，要知道不等

给定值40需要和哈希表中1单元

至12单元的12个关键字进行比较

才知道失败，需要和关键字比较12次

之所以需要比较那么多次

最核心的原因是整个哈希表装的太满

1~12之间如果有空的单元

比如6号单元为空的话，比较6次就知道失败了

比较次数会大大降低，其它失败的情形也类似

从刚才的讨论可以看到，如果哈希表中装的很满

对哈希表的查找性能影响是非常巨大的

在等概率查找情况下可以证明

线性探测再散列的哈希表

查找成功的平均查找长度为：(1+1/(1- α))/2

从公式可以看出

α越接近1，说明装的越满

平均查找长度越大。α越接近0

说明哈希表比较空，平均查找长度越小

随机或平方探测再散列的哈希表

查找成功的平均查找长度为：–(ln(1- α))/ α

链地址处理冲突的哈希表查找成功的平均查找长度为：1+ α/2

查找成功的平均查找长度也是和α有关

同样是装的越满，平均查找长度越大

从上面关于哈希表查找性能的讨论可以看出

哈希表的平均查找长度，不是哈希表中记录个数n的函数

而是α的函数

也就是说哈希表的平均查找长度

和哈希表中记录的个数无关

因此，虽然不能做到平均查找长度为1

但是，可以设计一个哈希表，通过控制装满的程度

也就是α的值

使哈希表的平均查找长度控制在一个期望值之内

最后要说明的一点是，对开放定址的哈希表

不能随意删除表中的记录

如果删除一个记录

必须在该记录所在的位置做一个特殊的标记

表示这里曾经存储过记录

不然会影响哈希表后续的查找

同时需要修改查找算法

添加识别已被删除记录的功能

好同学们，关于哈希表

我们就介绍到这，下次课再见