大家好,数据结构与
算法这一讲我们学习第十章检索。
关于散列的最后内容,就是 我们来实现一个闭散列的字典。
然后我们对散列方法进行效率分析。
字典呢,它是一种特殊的集合,也就是说,我们有一
些,啊,元素,这个元素呢,它其实是一个key value对。
也就是说这个key呢,就是我们待检的这些词啊,或者是关键字啊,
那这里呢,我们用一种闭散列的方法来实现字典。
那,啊,这个定义呢,就是有这个散列表它其实是一个
这样的很大的数组。然后,啊,这个数组呢,有它的特定的这么一个大小长度。
还有就是我们当前里面有效的这个元素个数。另外呢,
我们要特别定义一种空槽这样的一种
值。那为我们后面的比较呢,提供一个基准。
那,还有就是,我们要定义散列函数以及啊,相应的这个
探测的序列。啊,也就是说探测序列我们采用什么样的步长的这个函数。
还有呢,就是对这个字典的一个初始化以及相应的
一些,哦,插入啊,删除啊,还有查找这些的操作。
那我们来看这个插入算法。 哦,对于一个啊,闭散列表,插入的过程呢,
首先就是根据我这个散列函数,找到一个基地址,
然后呢,我看一下基地址如果是空的,那我就可以插入,
否则的话,我就沿着这个探测序列,继续往后面找,
找到一个空的位置,然后插入待插入的元素。那在这个过程中,如果
有重复的关键码,那我就不允许它插入。我们来看这个插入的算法框架。
那首先呢,就是我得到这么一个基地址,然后呢, 我这么一个position
指针,我从基地址出发, 啊,开始往后面来看。哦,我这个循环呢,
就是判断一下,这个当前的这个position指针,
它是不是一个空槽? 如果不空的情况下呢,
那我就是在判断,当前这个position这个位置的值,
它是不是跟我待插入的这个key呢,是一样的。如果相同
的话我就报告说这次插入失败,我不允许重复关键码,
否则呢,我这个步长呢,就往后面加1,然后我看这个探测序列里面,
下一位是哪一个位置。那我根据这个
探测函数然后再加上这个基地址,就是我探测序列里面的
下一个要查找的这样的一个位置。继续这一层
的循环,然后再来一直找,找到一个,嗯,
空的一个可以插入的位置,然后我们
插入这个元素,那我就,啊,成功地完成了
一个插入的操作。检索算法呢,它跟插入是非常类似的。
那它的探测序列也是一样的。那我们这个检索的过程呢,就是在,
啊,基地址,然后以及它的探测序列里面去找,有没有这个元素,如果有,就,啊,成功返回。
那如果是没有的话,一直就找到了我们整个探测序列里面的
尾部。这个尾部呢,其实是用空槽来代替的。 那我们就表示检索失败,
那我们来看这个检索算法的框架。那前面是类似首先,哦,定位这个基地址,
以及起始的这样的一个比较的position。看一下这个position这个当前的元素,
它是不是空?啊,如果不空的情况下呢,我再看是不是跟我待找的
这样的一个元素值是相同的。如果是呢,我们就找到了这个元素而且返回真。
那否则的话呢,那我探测序列再往下面继续去找,那我们一直
找到这个元素,或者是说找到了某一个空槽,也就是探测序列已经结束了,
那我们返回假。
啊,在这样的一个闭散列表里面,我们不能够直接就删除这个元素。
哦,因为这个元素它可能处在很多个
探测序列里面。你把他删掉了以后,这些探测序列就
都是在这个位置,就变成了空。但其实后面它可能还需要
有更多的这个探测的位置。那这样的话呢,我们就会在这个地方,
哦,断掉。那,因此呢,啊,删除只能是做一个特殊的标记。
那我们来看一下这个删除的例子。对这么一个长为13 的散列表,
假设这个K1和K2 呢,它们的基地址分别是2和6,
那如果我们采用二次探测的方法, 那如果我们删除这个位置6所在的
这个值,这个时候呢,我们不能够直接把它删掉,
因为这是它的一个
基地址。其实将来要检索,哦,跟这个6的
基地址相关的一些其他的值的时候,那假设我有另外一个
key,那比如说 K3 ,它的基地址也是6,那它的这样的一个探测序列会
是去从这个6,然后再看7,再看5。
那这个6被删掉以后,它变成一个空槽,那它就会判断说,哎,
我找不到这个元素。其实,这个K3呢,它可能在 7 或者在 5 这个位置。
哦,另外呢,就是我也不能够 ,啊,用这个啊,K2的
探测序列里面的最后那个元素来代替槽6所在的这样的一个元素。
那我们来看这个K2的探测序列,它是,啊,6,7,5,10,2。那,
我们假设探测序列里面最后那个元素呢,就是在下标为2的那个槽里面。如果我把这个K2来
代替下标6所在的这个位置的值,
这个时候呢,这个K2呢,它就变成了一个空槽。
那我们下次要检K1的时候呢,它的基地址就是2,它检到这儿是个空。
那,其实呢,这个K1,它有可能是放在
这个位置3或者是位置1里面,那就是说,我原来这样一个K1 的
探测序列呢,因为这个K2的某一个关键码,被移走了,
那整个这个探测序列就被打断了。啊,那因此呢,我们删除的时候,
只能够在这个原位置填一个墓碑,不能进行其他的一些
移动啊,或者是直接删除这样的操作。墓碑,它不同于,
啊,空单元,也不同于有效值的情况。 那我们来看删除的算法。那当然我们是要
基于这个墓碑标记的。首先呢也还是找到这个基地址,
然后呢,我们从这个基地址出发,哦,来比较这个当前位置是不是空。
如果不空的情况下,我们再来看这个当前位置这个元素,它是不是
我们给定的,要删除的这个值。啊,如果是的话呢,那我们就,啊,
把这个位置呢,标记为墓碑,然后我们把这个删除的这个值的结果返回。
啊,否者呢就是如果我们现在当前这个位置的值还不等于,
啊,我们待删的这个元素,那我就继续在这个探测序列里面,
往下面找。
啊,一直到,找到这个待删的元素或者是呢,找到整个这个
探测序列里面的一个空位置,那就表示这个元素是不存在这个
散列表里面的。也就是说,删除是个失败的操作。
我们来看这个带墓碑的情况下呢, 它的插入算法也是需要进行一些修改的。
首先呢,就是说,插入的时候,如果是我在整个这个探
测链里面,碰到了这个墓碑元素,是不是就可以马上给它放进去呢?
其实不行,我还是必须在整个探测序列里面找到最后一个空槽的位置。
我们来看这个插入算法,啊,这个跟我们前面
不考虑删除的时候,是不一样的,我们有一点改进。
还是从这个基地址出发,然后呢我们还有一个特殊的
就是说,我发现了墓碑,这么一个标记,首先我让这个标记为假。
然后,我们从,啊,基地址出发呢,我来比较说,啊,如果还
没有找到这个空槽,那也就是说整个这个探测序列
还没有完成的情况下,那我看,啊, 如果是当前这个元素,它,啊,
等于我们待插入的这个值,那我就返回假。也就是说不允许你插入这样的重复关键码。
否则呢,再来看,当前这个元素呢,它是不是一个墓碑?
如果是一个墓碑的话呢,那我把这个位置记录下来。
等待着我将来一直找到墓尾以后返回来
再找这个第一个墓碑的位置来插入。然后呢,我们如果还一直
没有找到整个探测序列里面,那个最后的得那个空位置
那我们就是沿着这个探测序列 继续往下面走一步。
嗯,那,移到探测序列里面下一个位置,然后再继续这个循环。停止这个循环的时候
嗯,那,如果不是说在这里面return to false,这个时候呢就是说
相当于我们是停在一个找到了空位置的情况。就是探测序列里面的这个尾巴位置。
然后我们来看,前面是不是曾经有过墓碑?
如果是曾经有过墓碑的话呢?
那我们这个插入位置就要,嗯,插在墓碑上头。
嗯,否则的话呢?如果是没有过墓碑,那我就是
之后找的那个空巢的位置就是我要插入的这个位置。
那我们来看一下散列方法的效率。我们衡量一个数据结构的重要的标志呢,就是
它的插入,嗯,删除和检索操作是不是非常高效。
那在散列表里面呢,我们最主要的就是来考虑一下
在整个这个散列表中插入或者删除或者检索
我总共跟其中的这些元素各进行了多少次的比较。
那,嗯,可以说散列表的插入和删除它其实都是基于检索进行的。
插入呢,其实就是一次失败的检索,一直减到最后这个探测序列的尾巴。
嗯,有找到一个空巢,还没有找到跟待插入的
这个根关键码一样的东西,我才能够插入。删除呢,就是
成功的一次检索。我找到了这么一个
嗯,跟我待删的关键码一样的纪录,然后我在这个地方 进行删除的操作。
那我们来看一下这个影响
散列检索的效率的一个重要因素。
就是负载因子,这个负载因子呢就是我整个散列表里面
有效的元素个数N, 和整个散列表的大小M的一个比值。
嗯,可以说呢,如果是alpha等于 N除M这样的一个负载因子。
它如果很小的情况下,那我们可以,嗯,想象得到
那这个基地址被占用的这个可能性也更小,不太容易发生冲突碰撞。
而且即使发生冲突碰撞的话呢,后面,嗯,这个必散列方法我要找到一个合适的空巢
去解决这个冲突。也是不需要那么长的这么一个探测序列就很快找到一个空位置。
alpha很大的时候,那显然就跟它相反了。
所以呢,这个alpha它的一个大小是我们需要来
考量的一个指标。那我们,嗯,来看一下假设
我这个负载因子alpha, 那也就是说我当前呢
是N个有效元素然后它的散列表大小是M。
那我在,嗯,下面插入,嗯 下一个元素的冲突碰撞的可能性呢就是N除以M。
然后第二次发生冲突碰撞呢就是,
嗯,就是N减1除以M减1我假设待插的这个数据也少了一点。
然后我,嗯,整个这个表呢也小了一点。
然后,嗯,我第I次冲突的可能性呢,就是这么一个公式。
那我假设N和M都很大, 那这种情况下呢,我就给它近似的表示为
N除M的I次方。那他的这个期望值呢,
就是这样的一个概率和。那我假设对这个I呢
从1到无穷来求这么一个渐进的这个值。
那我就会得到1减alpha分之一这样的一个代价。这其实就是
一个插入代价,而且它是双散列的这个情况下的一个插入代价。
那我们知道,嗯,一次这个成功的检索或者是一次删除,它的这个代价呢
它其实是以前你怎么插进去的, 那现在我在检索的时候,那我可能就是跟他当时插入的
这个需要比较的这些次数呢是一样的。随着这个散列表里面
这个纪录的不断增加呢,嗯, 它的负载因子alpha其实是越来越大。
那我们就是从0到alpha 把这个,嗯,当前值的这个,嗯,积分
也就是说我们这样的一个,嗯,插入的这么代价我进行积分。
而且呢,我再除以alpha,那就是
导出的是这么一个查找;
或者是删除操作它的这么一个代价。
嗯,就是得到这样的一个值。这一个其实也是针对
双散列函数这样的一个,嗯,情况。那我们可以看到
就是刚才插入是这个值,嗯,成功的检索或者是删除是这一个值。
那相应的我们还可以,嗯,得出这个
线性探测的这样一个必散列方法它的插入和删除的这个代价,
以及开散列方法的这个代价。那我们来看一下,
嗯,这些函数它的图示。可以看到呢 嗯,开散列方法
它的效率是最高的,就是基本上接近于,嗯,
1这样的一个值。而且呢,我们可以看到开散列方法里面呢,嗯,它的这个
插入的这样一个代价,紫色的这个,嗯,曲线。
那它的代价是最低的,因为我们开散列里面
我这样的一个空表直接插入,其实是最快捷的。
而删除或这是检索,嗯,这样的代价呢是这样的浅蓝色的线。
那这个线呢,嗯,可以说它的代价比我们的插入要,嗯,高一点。
那我们再来看,嗯,双散列探测法
它的这两条线。那这两条线呢就是,嗯,它的一个,嗯,检索的代价。
就是,嗯,这样的一个黄色的线,
而这个插入的代价呢,是这个绿色的线。那可以看出
嗯,在双散列,嗯,这样的一个情况下呢,嗯,
它的这个检索是
比插入呢是要快一些的。线性探测它的这两条线
就是 嗯,蓝绿色的和蓝色的线,它比,嗯,
双散列里面的这个,嗯,黄色的还有这个绿色的线呢
它是,嗯,值呢是要高一些的。在上面,所以
线性探测它的效率呢是比双散列是要低一些的。
嗯,我们其实,嗯,还可以看到呢就是散列方法
它的这个效率呢其实它是非常接近于theta 1的这样的一个代价。
它比log n是要好很多。嗯,而且呢,嗯
刚才这样的一个图示呢,你可以看到随着alpha的增加呢
嗯,这个效率是变得更差一些。
嗯,那其实我们回到刚才这个图
可以看出,嗯,当这个,嗯,alpha它小于,嗯,
0.5的时候,他们的取值呢都是小于2。也就是说,顶多,嗯,
两次这样的一个平均查找长度就能够, 嗯,完成我们的相应的操作。
因此呢,在设计散列表的时候,嗯,这个alpha等于0.5就是一个经验值。
就是一定要保持这个散列表起码有一半以上的是空的。
如果是散列表里面插入和删除比较频繁的时候,
那插入的话呢,我们就会使得这个alpha变得越来越大;
而删除呢,会使得我们这个墓碑越来越多。虽然整体的元素;有效的元素个数
可能并不见得多了很多,但是,(你)这个墓碑占位站在那儿使得
我们探测序列越来越长。那么这两种情况下都导致散列表的性能会下降。
如果下降的话呢,我们都需要,嗯,重组这个散列表。 这个重组可能是需要申请一个更大的散列表的这个空间。
嗯,另外呢就是,我们可以,嗯,进行一些访问的这个统计计数。
就是把这些经常访问的这个元素呢,嗯,在重组的时候我尽量给它放到
基地址的地方,使得它在这个探测序列里面比较靠后的位置。
当然,这个墓碑是需要给它清除掉的。
最后给大家留几个思考。首先呢,就是说,嗯,我们这个墓碑是一种特殊的标记。
嗯,那因此呢,我们散列表里面就是有墓碑、空元素和有效的数据这几种情况。
那我们是不是能够,嗯,有一种方法就是把这个墓碑和空元素啊什么的
嗯,进行一个合并。嗯,使得到我们这个状态变得少一些呢?
另外呢,就是,嗯,散列方法是一种实现字典的,嗯,比较有效的方法。
其实,还可以有其他的一些实现字典的方法。嗯,大家可以去调研一下,
看看有那一些。谢谢大家。