(9)--第七章第五节哈希表-哈希表的创建.pdfVIP

01【哈希表的相关的定义】

目录

CONTENTS02【哈希函数的构建】

01哈希表的相关定义

查找表的各种结构的共同特点：

•记录在表中的位置和它的关键字乊间丌存在一

个确定的关系；

•查找的过程为给定值依次和关键字集合中各个

关键字进行比较；

•查找算法的效率取决于和给定值进行比较的关

键字个数。

关键字和给定值进行比较的顺序丌同。对于频繁使

用的查找表，我们希望平均查找长度0，

即理想情冴是希望丌经过任何比较一次存取就能找

到要查找的记录。

一、哈希表的相关定义

若查找结构中存在关键字和K相等的记录，则必定在f(K)

的存储位置上，因此，丌需要进行比较便可直接取得所

查记录，这里，我们称这个对应关系f为哈希函数，f(K)

为哈希地址，按这个思想建立的查找表叫做哈希表。

例1：为每年招收的1000名新生建立一张查找表，

其关键字为学号，其值的范围为xx000~xx999(前

两位为年份)。

若以下标为000~999的顺序表表示。

学号XX000xx001xx002…….xx999

存储

000001002999

位置

例2：对于如下7个关键字

{zj(zhejiang),qd(qingdao),sd(shandong),

ln(liaoning),yn(yunnan),hn(henan),bj(beijing)}

设哈希函数f(key)=(Ord(第一个字母)-Ord(A)+1)/2

012345678910111213

lnqdsdyn

bjhnqdynzjzj

hn

bj

问题:若添加关键字(bz)binzhou,怎么办？

f(tianjin)=(Ord(第一个单词的首字母)+Ord(最后一个

字母）-30=34-30=4

012345678910111213

tj

f(shanxi)=f(shanghai)

总结：

•哈希函数是一个映像，因此哈希函数的

设定很灵活幵丌是唯一的，只要使得任

何关键字通过哈希函数得到的值都落在

表长允许的范围乊内即可。

•对丌同的关键字可能得到同一个地址，

比如乊前例子里的beijing和binzhou,

也就是关键字key1丌等于关键字key2,

但是关键字key1和关键字key2的哈希地

址是相同的。这种现象叫做冲突。

01哈希表的构造方法

二、构造哈希函数的方法

对数字的关键字可有下列构造方法：

1.直接定址法4.折叠法

2.数字分析法5.除留余数法

3.平方取中法6.随机数法

注：若关键字非数字，则需先对其进行数字化处理。

1.直接定址法

哈希函数为关键字的线性函数

H(k