8.5.1 哈希表及哈希函数的构造在线视频

同学们，大家好

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

欢迎大家回到数据结构的课堂

这节课，我们讨论哈希表

上几节课，我们讨论了静态查找表和动态查找表

在这些查找表中进行查找，基本的操作都是比较

哈希表的查找和前面两类查找表是不一样的

哈希表的查找的主要是基于计算

先了解一下哈希函数

哈希函数在记录的关键字

和它的存储位置之间建立一个确定的对应关系f

使每个关键字和存储结构中一个唯一的存储位置相对应

一般是用数组存储，称这样的对应关系f为哈希(Hash)函数

结合图来看一下，设有一个记录R，R的关键字为key

那么，哈希函数f对key施加一个计算

计算的结果是一个整数值i

这个整数值叫做哈希地址

我们把记录R存在数组下标为i的单元

如果所有记录都按照同样的方式存储在数组中

那么，获得的这个查找表就被称为哈希表

下面我们看一个具体的例子

假设有30个地区的人口统计表

每个地区的人口统计情况形成一个记录

为了方便查找，以地区名字的拼音作为关键字

30个记录需要分配30个存储空间

也就是每个记录存在数组当中的一个存储单元

假设是数组的下标1~30

看一下哈希函数的构造，第1个哈希函数是f1

f1是把关键字首字母在字母表中的序号作为哈希地址

地址范围是1~26

有8个地区，按照f1计算这8个地区的哈希地址

结果如表中第f1行所示

观察这行

因为山西，上海，山东，四川4个地区的首字母都是s

它们的哈希函地址是相同的

按照哈希表的构造方法

这4各记录都应该存储在19号单元

但是19号单元只能存一个记录，这种情形称为冲突

这里冲突的比较严重的，f1并不是一个很理想的哈希函数

重新构造一个哈希函数f2

f2先求关键字的第一个

和最后一个字母在字母表中的序号之和

若大于表长（30），则减去30

用f2计算哈希地址，8个地区的结果如f2行所示

上海和山西两个关键字仍然出现的冲突，但比f1要好

f3是另外一种构造方法

仍然有两个地区发生冲突

记录关键字肯定是不相同的，

就哈希函数的构造来说

其本质是对关键字特征的抽取

抽取的关键字特征越多

发生冲突的可能性呢越小

f1仅抽取了关键字的第1个字母

f2抽取了关键字中的两个字母

抽取的特征多一些

冲突的可能性就比较小了

为什么不抽取所有特征呢？

道理上来说，抽取所有特征

冲突的可能性肯定更小，但是计算哈希函数的开销会增加

通过上述例子，我们注意到

在哈希表的设计中有两个问题

要引起我们的关注

一是应该首先确定哈希表的存储空间

哈希函数计算的结果必须落在表长的范围之内

二是，不同的关键字经哈希函数映射以后

可能有相同的哈希地址，这就要求我们

一个是设计一个好的哈希函数

好的哈希函数能够尽量避免冲突

二是在冲突不可避免的情况下

应该设计处理冲突的方法

我们先讨论哈希函数构造的方法

那么，什么叫一个好的哈希函数呢

哈希函数应该是均匀

均匀的哈希函数是说，若对于关键字集合中的任意关键字

经哈希函数，映射到地址集合中任意一个地址的概率是相等的

直观的看就是一组关键字的哈希地址

均匀分布在整个地址空间中

而不是集中在部分区间，目的呢是减少冲突

下面我们介绍一些哈希函数构造的方法

提醒同学们注意，这些方法可以在解决实际问题时参考

但是一般不能死板照搬

哈希函数的构造有很大的灵活性

应该根据设计的要求，针对具体的问题背景来构造

第1种方法称为直接定址法

具体做法是，取关键字

或者关键字的某个线性函数值为哈希地址

如H(key)=key，哈希地址就是关键字key本身

或者是H(key)=a*key+b

哈希地址是key的一个线性变换

直接定址法要求关键字为整数值

因为哈希地址必须是一个整数值，对应数组的下标

另外，地址集合和关键字集合的大小相同

直接定址法最大的好处是不会发生冲突

只要关键字不同，哈希地址一定不同

最大的问题是，如果关键字的集合太大

而实际的记录数很小

这样的哈希函数会造成地址空间极大的浪费

例如，云南大学学生的学号是10位数

如果把学号作为关键字，看做整数

关键字集合是百亿大小

但实际学生人数不过1到2万人。

第2种方法是数字分析法

假设关键字是以r为基的数

比如说10进制数

并且哈希表中的可能出现的关键字都是事先知道的

也就是可以事先进行分析

则可取关键字的若干位组成哈希地址

看个例子，关键字是8位的10进制数

通过观察这几组关键字

我们注意到最高的三位，基本上是一样的

最低的一位，大部分也是2和7

就是说关键字的这4位，并不具有明显的特征

大家是一样的

如果记录的个数不超过1万个

可以考虑抽取红色竖线之间的4位组成哈希地址

这4个位置的差异都比较明显

下一种是平方取中法

也就是说取关键字平方后的中间几位为哈希地址

前面我们提到过，哈希函数的本质

实际上是对关键字特征的抽取

抽取的特征越多，冲突的可能性越小

关键字平方后，中间的几位

比如说幻灯片上平方后的中间红色的三位

从乘法过程来看，这三位的值

和关键字的每一位都有关系

关键字的每一位都对这三位的值产生了一定的影响

换个角度

可以说这三位数值抽取的关键字中每位数的部分特征

折叠法将关键字分割成位数相同的几部分

当然分割成几位，主要是和需要存储的记录数有关

最后一部分的位数可以不同

然后，取这几部分的叠加和作为哈希地址

这样的做法

使得关键字中的每一位都对最终的哈希地址产生了一定的影响

算是抽取了部分特征

除留余数法

取关键字被某个不大于哈希表长m的数

p除后所得余数为哈希地址

例如H(key)=key mod p，p小于等于表长

以保证哈希地址落在表长的范围内

对p的选择要给予一定关注

p选不好，容易产生所谓同义词

这里的同义词是指不同的关键字

经哈希函数计算后却有相同的哈希地址

也可以把它们叫做哈希同义词

看一个例子，p=21，p中含有质因子7

那么含有因子7的关键字对21取模的哈希地址均为7的倍数

如表中。5个关键字都含有因子7

它们的哈希地址均为7的倍数

这样的话呢，就比较容易产生冲突

所以一般情况下，为了避免上述情况

可以选p为质数或不包含小于20的质数的合数

最后一种方法称为随机数法

就是选择一个随机函数

取关键词的随机函数值为它的哈希地址

因为随机函数的构造有多种办法

在这儿我们就不进一步讨论了

当然，需要保证哈希地址只能落在表长的范围之内

好同学们，这节课呢

我们就讲到这儿，下节课再见