大学《数据结构》第八章：查找-第四节-散列表查找

第四节散列表蛰找

一、散列表的概念

1、散列的概念

"散列”既是一种存储方式，又是一种查找方法。这种查找方法称为

散列查找。散列的基本思想是通过由散列函数决定的键值与散列地址

之间的对应关系来实现存储组织和查找运算。

2、实例分析

【例】有个线性表A=(31,62,74,36,49,77),散列函数为

H(key)=key%m即用元素的关键字key整除m,取其余数作为存储

该元素的散列地址，m一般取小于或等于散列表长的最大素数，在这

里取m=ll,表长也为II,因此可得到每个元素的的散列地址：

H(31)=31%11=9;H(62)=62%ll=7;H(74)=74%ll=8;

H(36)=36%11=3;H(49)=49%11=5;H(77)=77%ll=0;

0123456789K)

散列表口7|88||36||49||62|74|31|7

若在上面散列表中插入元素88、7等会出现冲突。

采用散列技术时需要考虑的两个主要问题是：①如何构造(选择)

“均匀的"散列函数？②用什么方法解决冲突？

二、散列函数的构造方法

1、直接地址法

直接地址法是以关键字key本身或关键字加上某个常量C作为散列

地址的方法。对应的散列函数H(key)为：H(key)=key+C

特点：方法计算简单，并且没有冲突。它适合于关键字的分布基本

连续的情况，若关键字分布不连续，空号较多，将会造成较大的空间

浪费。

2、数字分析法

数字分析法是假设有一组关键字，每个关键字由n位数字组成，数

字分析法是从中提取数字分布比较均匀的若干位作为散列地址。

3、除余数法

除余数法是一种最简单也最常用的一种散列函数构造方法。散列函

数:H（k）=k%p

其中，p最好选取小于或等于表长m的最大素数。

4、平方取中法

平方取中法是取关键字平方的中间几位作为散列地址的方法

5、折叠法

折叠法是首先把关键字分割成位数相同的几段（最后一段的位数可少

一些），段的位数取决于散列地址的位数，由实际情况而定，然后将它

们的叠加和倍去最高进位）作为散列地址的方法。

【例】关键字k=98123658,散列地址为3位，则将关键字从左

到右每三位一段进行划分，得到的三个段为981、236和58,叠加后

值为1275,取低3位275作为关键字98123658的元素的散列地址

三、处理冲突的方法

1、开放定址法

开放定址法的思想：使用某种方法在散列表中形成一个探查序列，

沿着此序列逐个单元进行查找，直到找到一个空闲的单元时将新结点

存入其中。

开放定址法又分为线性探插法、二次探查法和双重散列法。

(1)线性探插法

探查序列可以由下述公式得到：di=(d+i)%m

其中：di表示第i次探查的地址，m表示散列表的长度。

【例】设散列函数为h(key)=key%ll;散列地址表空间为0~

10,对关键字序列｛27,13,55,32,18,49,24,38,43),利用

线性探测法解决冲突，构造散列表。并计算查找成功时的平均查找长

度。

【解答】首先根据散列函数计算散列地址

h(27)=5;h(13)=2;h(55)=0;h(32)=10;

h(18)=7;h(49)=5;h(24)=2;h(38)=5;

h(43)=10;

散列表

下标01234567891a

554313242749183832

探查次数131212141

查找成功时的平均查找长度ASL=(lx5+2x2+3xl+4xl)/9«

1.78

(2)二次探直法

二次探查法的探查序列为：

do=H(K),

di=(do+12)%m

d2=(do-I2)%m,

ds=(do+22)%m,

d4=(do-22)%m,

(3)双重散列法

双重散列法是几种方法中最好的方法，它的探查序列为：hi二(H

(key)+i*Hl(key))%m(0<i<m-l)

即探查序列为：d=H(key),(d+l*Hi(key))%m,

(d+2*Hi(key))%m,…等。

2、拉链法(链地址法)

用拉链法处理冲突的办法是：把具有相同散列地址的关键字(同义

词)值放在同一个单链表中，称为同义词链表。

【例】设散列函数为h(key)=key%ll;,对关键字序列｛27,

13,55,32,18,49,24,38,43),用拉链法构造散列表,并计

算查找成功时的平均查找长度。

【解答】首先根据散列函数计算散列地址

h(27)=5;h(13)=2;h(55)=0;h(32)=10;

h(18)=7;h(49)=5;h(24)=2;h(38)=5;

h(43)=10;

四、散列表的查找

1、线性探查法解决冲突的直找和插入算法

采用开放定值法构造散列表的类型定义：

#defineM997//M定义为表长，一般

M为一个素数

typedefstruct〃定义散列表结点类型

{KeyTypekey;

DataTypedata;

}NodeType;

typedefNodeTypeHashTable[M];〃散列表类型

(1)采用线性探直法的散列表有找算法

intHashSearchl(HashTableHT,KeyTypeK,intm)

{〃在长度为m的散列表HT中查找关键字值为K的元素位置

intd,temp;

d=K%m;〃计算散列地址

temp=d;//temp作为哨卡,

防止进入重复循环

while(HT[d].key!=-32768)〃当散列地址中的

key域不为空，则循环

{if(HT[d].key==K)

returnd;〃查找成功返回其下

标d

else

d=(d+l)%m;〃计算下一个地址

if(d==temp)

return-I;〃直找一周仍无空位

置，返回-1表示失败

)

returnd;〃遇到空单元，直找失

败

)

(2)在散列表上插入一个结点的算法

intHashlnsertl(HashTableHT,NodeTypes,intm)

〃在HT表上插入一个新结点s

intd;

d=HashSearchl(HT,s.key,m);〃查找插入

位置

if(d==-l)return-1;〃表满，不能

插入

else

{if(HT[d].key==s.key)

return0;〃表中已有该结

占

/\\\*i

else〃找到一个开放的

地址

{HT[d]=s;〃插入新结点S

return1;〃插入成功

)

)

)

2、拉链法建立散列表上的查找和插入运算

采用拉链法的散列表类定义：

typedefstructnode{〃定义结点类型

KeyTypekey;

DataTypedata;

structnode*next;

}HTNode;

typedefHTNode*HT[M];〃定义散列表类型

(1)直找算法

HTNode*HashSearch2(HTT,KeyTypeK,intm)

{〃在长度为m的散列表T中查找关键字值为K的元素位置

HTNode*p=T[K%m];〃取K所在链表的头指针

while(p!=NULL&&p->key!=K)

p=p->next;〃顺链查找

returnp;〃查找成功p指向K结点的位置，不成功返回

NULL

(2)插入算法

intHashlnsert2(HTT,HTNode*s,intm)

{〃采用头插法在T表上插入一个新结点

intd;

HTNode*p=HashSearch2(T,s->key,m);〃查找

表中有无待插结点

if(P!=NULL)return0;〃说明表

中已有该结点

else〃将*s插入

在相应链表的表头上

{d=s->key%m;

s->next=T[d];

T[d]=s;

return1;〃说明插入

成功

)

)

3、几种处理冲突方法的散列表的平均查找长度比较

【例】设散列函数h(k)=k%13,散列表地址空间为0~12,对给

定的关键字序列(19,14,01,68,20,84,27,26,50,36)分

别以拉链法和线性探查法解决冲突构造散列表，画出所构造的散列

表，指出在这两个散列表中查找每一个关键字时进行比较的次数，并

分析在等概率情况下查找成功和不成功时的平均查找长度以及当结点

数为n=10时的顺序查找和二分查找成功与不成功的情况。

【解答】首先根据散列函数计算散列地址

h(19)=6;h(14)=1;h(01)=1;h(68)=3;

h(20)=7;h(84)=6;h(27)=1;h(26)=0;

h(50)=11;h(36)=10;

(1)线性探直法解决冲突构造散列表：

下标012345678910n12

26140168271920843650

探查次数1121411311

查找成功的平均查找长度=(lx7+2xl+3xl+4xl)/10=1.6

查找不成功的平均查找长度=(6+5+4+3+2+1+4+3+2+1

+3+2+1)/13-2.85

(2)拉链法解决冲突构造散列表

1

查找成功的平均查找长度=(Ix7+2x2+3xl)/10=1.4

查找不成功的平均查找长度(不包括空指针的比较)

=(1+3+0+14-0+0+2+1+0+0+1+1+0)/13-0.7

当n=10时，顺序查找成功的平均查找长度=(10+1)/2=5.5

顺序查找不成功的平均查找长度=10+1=11

n=10的有序表的判定树：

当n=10时，二分查找成功的平均查找长度=(Ixl+2x2+3x3

+4x3)/10~3

二分查找不成功的平均查找长度=(3x2+3xl+4x2

+3x1+4x23x1+4x2)/11~3.2

注意：结点