第四节 - 散列表查找

发布时间：2020-09-20 11:19来源：未知

第四节散列表查找

当前讲授

一、散列表的概念

1、散列的概念

"散列"既是一种存储方式，又是一种查找方法。这种查找方法称为散列查找。散列的基本思想是通过由散列函数决定的键值与散列地址之间的对应关系来实现存储组织和查找运算。

2、实例分析

【例】有个线性表A=（3l，62，74，36，49，77），散列函数为H(key)=key％m即用元素的关键字key整除m，取其余数作为存储该元素的散列地址，m一般取小于或等于散列表长的最大素数，在这里取m=1l，表长也为ll，因此可得到每个元素的的散列地址：

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％11=0；

散列表

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

采用散列技术时需要考虑的两个主要问题是：①如何构造（选择）"均匀的"散列函数？②用什么方法解决冲突？

二、散列函数的构造方法

1、直接地址法

直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)为：H(key)=key+C

特点：方法计算简单，并且没有冲突。它适合于关键字的分布基本连续的情况，若关键字分布不连续，空号较多，将会造成较大的空间浪费。

2、数字分析法

数字分析法是假设有一组关键字，每个关键字由n位数字组成，数字分析法是从中提取数字分布比较均匀的若干位作为散列地址。

3、除余数法

除余数法是一种最简单也最常用的一种散列函数构造方法。散列函数：H(k)=k％p

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

4、平方取中法

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

5、折叠法

折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些)，段的位数取决于散列地址的位数，由实际情况而定，然后将它们的叠加和(舍去最高进位)作为散列地址的方法。

【例】关键字k=98 123 658，散列地址为3位，则将关键字从左到右每三位一段进行划分，得到的三个段为981、236和58，叠加后值为1275，取低3位275作为关键字98 123 658的元素的散列地址

三、处理冲突的方法

1、开放定址法

开放定址法的思想：使用某种方法在散列表中形成一个探查序列，沿着此序列逐个单元进行查找，直到找到一个空闲的单元时将新结点存入其中。

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

（1）线性探插法

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

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

【例】设散列函数为h（key）=key％1l；散列地址表空间为0～l0，对关键字序列{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；

散列表

查找成功时的平均查找长度ASL=（1×5＋2×2＋3×1＋4×1）/9≈1.78

（2）二次探查法

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

d₀=H（K），

d₁=（d₀+1²）% m

d₂=（d₀ -1²）% m，

d₃=（d₀+2²）% m，

d₄=（d₀ -2²）% m，

……

（3）双重散列法

双重散列法是几种方法中最好的方法，它的探查序列为：hi=（H（key）+i*H1（key））％m （0≤i≤m-1）

即探查序列为：d=H（key），（d+l*H₁（key））％m，（d+2*H₁（key））％m，…等。

2、拉链法(链地址法)

用拉链法处理冲突的办法是：把具有相同散列地址的关键字（同义词）值放在同一个单链表中，称为同义词链表。

【例】设散列函数为h（key）=key％1l；，对关键字序列{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×5＋2×3＋3×1）/9≈1.55

四、散列表的查找

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

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

# define M 997 　　　　　　　　　　　//M定义为表长，一般M为一个素数

typedef struct　　　　　　　　　　　　 //定义散列表结点类型

　　{KeyType key；

　　 DataType data；

　　}NodeType；

typedef NodeType HashTable[M]；　　　//散列表类型

（1）采用线性探查法的散列表查找算法

int HashSearchl (HashTable HT，KeyType K，int m)

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

　　int d，temp；

　　d= K％m；　　　　　　　　　　　　//计算散列地址

　　temp=d；　　　　　　　　　　　　　 //temp作为哨卡，防止进入重复循环

　　while (HT[d].key!=-32768)　　　　　　 //当散列地址中的key域不为空，则循环

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

　　　　return d；　　　　　　　　　　　 //查找成功返回其下标d

　　　else

　　　　d=(d+1)％m；　　　　　　　　//计算下一个地址

　　　if(d==temp)

　　　　return -l；　　　　　　　　　　//查找一周仍无空位置，返回-1表示失败

　　}

　return d；　　　　　　　　　　　　　 //遇到空单元，查找失败

}

（2）在散列表上插入一个结点的算法

int HashInsertl (HashTable HT，NodeType s，int m)

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

　　int d；

　　d=HashSearchl (HT，s.key，m)；　　　　　　//查找插入位置

　　if(d==-1) return -1；　　　　　　　　　　　 //表满，不能插入

　　else

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

　　　　return 0；　　　　　　　　　　　　　 //表中已有该结点!

　　　else　　　　　　　　　　　　　　　　 //找到一个开放的地址

　　　{HT[d]=s；　　　　　　　　　　　　　 //插入新结点S

　　　return 1；　　　　　　　　　　　　　//插入成功

　　　｝

　　}

｝

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

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

typedef struct node{ //定义结点类型

　　KeyType key；

　　DataType data；

　　struct node * next；

｝HTNode；

typedef HTNode * HT[M]； //定义散列表类型

（1）查找算法

HTNode * HashSearch2 (HT T，KeyType K，int m)

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

　　HTNode *p=T[K％m]； //取K所在链表的头指针

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

　　　p=p->next； //顺链查找

　　return p； //查找成功p指向K结点的位置，不成功返回NULL

（2）插入算法

int HashInsert2 (HT T，HTNode * s，int m)

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

　int d；

　HTNode *p=HashSearch2 (T，s->key，m)；　　　　 //查找表中有无待插结点

　if(P!=NULL) return 0；　　　　　　　　　　　　　//说明表中已有该结点

　else 　　　　　　　　　　　　　　　　　　　　　//将*s插入在相应链表的表头上

　　{d= s->key%m；

　　s->next=T[d]；

　　T[d]=s；

　　return 1；　　　　　　　　　　　　　　　　　//说明插入成功

　}

｝

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）线性探查法解决冲突构造散列表：