8.5.2 解决冲突的方法在线视频

同学们大家好

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

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

上一节课介绍了哈希表的基本概念和哈希函数构造的方法

这节课，我们主要讨论哈希表中处理冲突的方法

处理冲突的基本方法是

为发生冲突的关键字记录，找到另一个空的哈希地址

当然，下一个哈希地址也可能非空

那么需要继续再找下一个

这样得到的可能是一个地址序列

观察图，如果关键字key的哈希地址是i

图中用黄色块表示该地址已经被其它记录占据

随后计算下一个哈希地址H1，如果H1也被占据

继续计算H2，H2也被占据

继续计算后续的Hi，直到某个Hk不发生冲突问题

怎么计算下一个Hi呢？

处理冲突的第1种方法称为开放定址法

开放定址法中，Hi的计算方法是

Hi=(H(key)+di) mod m

H(key)为哈希函数

di为增量序列；m为哈希表长

增量序列的取法，我们介绍三种

第1种是：d1取1，d2取2

以此类推，这种增量序列取法称为线性探测再散列

第2种是：d1取1平方

d2取负的1平方2，d3取2平方

d4取负的2平方，以此类推

这种取法称为二次探测再散列

第3种是取自一个伪随机数序列

预先生成一个伪随机数序列

如9，30等的随机数序列

按照序列，d1取9，d2取30

按随机数序列依次确定di

这种取法称为伪随机探测再散列

结合一个例子说明一下开放定址法

有长度为11的哈希表

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

表中已填有关键字为17，60，29的纪录

现在插入包含关键字38的记录

首先计算38的哈希地址，哈希地址为5

哈希表中5号单元已被60占据

采用线性探测再散列计算Hi，H1是5+1对表长11求余

结果为6，考察6号单元被17占据，继续求H2

结果为7，7号单元被29占据，求H3等于8

8号单元为空

把包含关键字38的记录存储在哈希表的8号单元

完成插入

通过这样依次插入纪录，哈希表逐渐构造出来

那么，在哈希表中如何查找呢

哈希表的查找过程和哈希表的构造过程是类似的

结合这个实例说明一下，如果要查找的给定值是60

首先按照哈希函数计算它的哈希地址，计算的结果是5

考察5号单元，如果5号单元为空

我们知道查找失败了，哈希表中没有关键字等于60的纪录

如果有，它应该存在5号单元

如果5号单元非空

把给定值60和5号单元记录的关键字比较

发现二者相等，那么查找成功

60的查找成功需要和关键字比较一次

同理，可以查找的给定值17和29

同样是和记录的关键字比较一次就查找成功了

但是，如果查找的是38，按照造表过程

38先和5号单元的60比较不等

此时，不能说查找失败

应该继续试探下一个哈希地址H1，H1等于6

和6号单元中的17比也不等，继续计算H2

7号单元的29也不等，计算H3

8号单元记录的关键字和38相等，查找成功

从刚才的过程来看，给定值38查找成功

需要和关键字比较4次

我们当然希望

在哈希表中查找成功只需要和关键字比较一次

但是因为冲突，给定值仍然可能需要和关键字比较多次

所以哈希表的查找也需要通过计算平均查找长度来度量查找的效率

例子中，如果设等概率的话

当前哈希表查找成功的平均查找长度ASL是7/4

注意，随着新记录的插入，ASL会变化

哈希表中同样要考虑查找失败的平均查找长度

仍然以图中的哈希表为例，除了表中的4个关键字

其它给定值的查找肯定是失败的

首先的问题仍然是对失败的给定值进行归类

哈希表中失败情形的分类和哈希函数有关

例子中，按照哈希函数，哈希地址的范围是0到10

基于此，失败的情形分为11种情形

哈希地址为0失败是一种失败的情形

就是如果给定值对11求余结果为0的话

所有这些给定值归为一种失败的情形

因哈希表中0号单元为空

这种情形的失败不需要和关键字进行比较

其它10中情形类似，如哈希地址为5失败的情形

如16,27等等，为5的失败

需要和4个关键字各比较一次，到H4=9时

9号单元为空，才能说查找失败

需要和关键字比较4次

假设11种情况是等概率的

查找失败的平均查找长度是10/11

采用不同的散列方法最后获得的哈希表是不一样的

如果采用的是二次探测再散列

同样是再图1的基础上插入38

计算H2是5-1对表长求余，结果是4

包含关键字38的记录存在4号单元

如果采用的是伪随机探测再散列，d1=9

计算H1是3，包含关键字38的记录存在3号单元

考虑采用什么样探测方式的时候

应该结合问题中关键字的特征，尽量避免二次聚集

二次聚集是指，在处理冲突的过程中

发生的两个哈希地址不同的记录

争夺同一个后继的哈希地址的现象，称为二次聚集

看一个例子，有关键字49和72

按照本例中的哈希函数，49的哈希地址是5

72的是6。它们的哈希地址是不同的

但是，在图4的例子中

因为5和6号单元已经被占据

它们两个会争夺同一个后继地址9，二次聚集

第二种解决冲突的方法，称为再哈希法

再哈希法中，同样需要计算下一哈希地址Hi

不过Hi的计算利用哈希函数RHi

就是说每个Hi都有自己的哈希函数

造成的问题是可能增加计算的时间

第3种解决冲突的方法，称为链地址法

基本策略是把所有关键字为哈希同义词的记录

存储在一个单链表中，不再找下一个哈希地址

结合例子看一下链地址法

链地址法的哈希表是一个指针数组

每个单元存储一个指针

指向该单元对应单链表的首元结点

例子中包含12个记录，哈希函数为H(key)=key mod 13

每个记录插入哈希表时，首先生成一个链表结点

把记录存储在data成员

根据记录的关键字计算哈希地址i

随后把该结点插入哈希表中

第i个单元指针所指的单链表中

插入12个记录以后，哈希表如图所示

观察哈希表1号单元，指针所指的单链表中有4个结点

4个关键字的哈希地址都是1

链地址法中把它们组成一个单链表

哈希表有的单元中是空指针

表示没有哈希地址为这些下标的关键字

结合例子，讨论一下链地址法的查找

查找过程中，首先仍然是根据给定值

计算哈希地址i，随后考察哈希表第i个单元

如果该单元中的指针为空，意味查找失败

非空的话，需要扫描该指针所指的单链表进行查找

扫描过程中用给定值和每个结点的关键字进行比较

如果和某个关键字相等，说明查找成功

如果扫描完整个单链表以后仍然没有成功

那么说明查找失败

先考虑查找成功的情况

以查找给定值27为例

按照查找上述查找过程

要和关键字01,14,27各比较一次

查找成功需要3次比较

我们注意到，其比较次数就是它在单链表中的位置

总结一下12个记录的情况

比较1次成功的有6个结点

2次成功有4个结点，3次和4次成功的各一个结点

等概率情况下，查找成功的平均查找长度是7/4

再考虑查找失败的情况

根据哈希函数，查找失败的情形有0~12

就是13种情形，其中不需要和关键词比较

就知道失败的情形有7种

哈希地址为7和11的失败情形

需要和关键字比较1次，3,6,10需要比较2次

1需要比较4次

那么，查找失败的平均查找长度是11/13

不到1次比较就知道失败了

最后一种解决冲突的方法是建立一个公共溢出区

就是除了哈希基本表之外，另外建立一个溢出表

一旦发生冲突

不再为发生冲突的记录在基本表中寻找下一个哈希地址

而是直接把发生冲突的记录填入溢出表

留两个问题给同学们思考

这样处理冲突怎么进行查找？

怎样计算ASL

请同学们课后考虑

好，同学们

这节课我们讲到这，下次课再见