DS11-查找与散列结构

第9章查找与散列结构主要内容

基本概念 静态查找表动态查找表 哈希（Hash）表及其查找

查找查找表：由同一类型的数据元素（或记录）构成的集合。查找表的基本操作

1)查询某个“特定的”数据元素是否在表中 2)检索某个“特定的”数据元素的各种属性

3)插入一个数据元素

4)删去某个数据元素静态查找表：只作查询和检索操作的查找表。动态查找表：在查找过程中同时作插入或删除操作的查找表。查找关键字：能标识一个数据元素（或记录）的数据项。主关键字：能唯一地标识一个记录的关键字。次关键字：用以识别若干记录的关键字。学号姓名专业年龄

20030001李莫愁计算机1720030002高手计算机1820030003王重阳计算机1820030004张无忌信息工程2020030005高手信息工程19查找学号姓名专业年龄

20030001李莫愁计算机1720030002高手计算机1820030003王重阳计算机1820030004张无忌信息工程2020030005高手信息工程19查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的记录，则称查找成功，查找结果为记录信息或其位置；否则称为查找不成功，查找结果通常为0或NULL。查找查找方法评价：平均查找长度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度。 用于度量查找算法的效率（时间复杂度）

Ci：查找到第i个记录所需的比较次数

Pi：查找到第i个记录的概率

平均查找长度ASL=PiCi(Pi=1)

查找静态查找 在指定的表中查找某一个“特定”的数据元素是否存在，检索某一个“特定”数据元素的各种属性。动态查找 在查找的过程中同时插入表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。静态查找 顺序表的查找：顺序查找 有序表的查找：折半查找 索引顺序表的查找：分块查找静态查找表查找表 可用线性表表示L1=(45,61,12,3,37,24,90,53,98,78）顺序查找从最后一个（第一个）记录开始，逐个进行比较

查找不成功的标记用顺序表表示静态查找表用线性链表表示静态查找表

静态查找表第10

页第10

页顺序表类型定义

typedefstruct{ElemType*elem;//0号单元留空

intlength;}SSTable;静态查找表

012345678910m-1

456112

3372490539878ST.elemSSTableST;第11

页第11

页intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。

ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(key,ST.elem[i].Key);--i)；

returni;//若表中不存在待查元素,i=0}//Search_Seq静态查找表

012345678910m-1

456112

3372490539878ST.elemkey免去查找过程中每一步都要检测整个表是否查找完毕第12

页第12

页例1：在下表中查找key=8的结点。静态查找表8012n-3n-2n-1nST.elemkey………………100100713iiiiiii查找不成功，i=08012n-3n-2n-1nST.elemkey例2：在下表中查找key=8的结点。………………100100813iii查找成功，i=n-2顺序查找特点 无排序要求； 算法简单； 存储结构：顺序、链式；

效率不高

静态查找表查找表：用有序表表示查找方法：折半查找（二分查找）查找过程：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。 例：有原始查找表{45,61,12,3,37,24,90,53,98,78}

为进行折半查找，需要先进行排序：

L=(3,12,24,37,45,53,61,78,90,98)

静态查找表-有序表查找例：查找Key=24

的记录。

静态查找表-有序表查找

12345678910

3122437455361789098lowmid

high

12345678910

3122437455361789098lowmid

high

24＜45

24＞12

123456789103122437455361789098Low

highmidboolSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找法查找其关键字等于key的数据元素。若找到，则返回该元素在表中的位置，否则返回false。

low=1;high=ST.length;while(low<=high

){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)high=mid-1;elselow=mid+1;}returnfalse;//表中不存在待查元素}

静态查找表-有序表查找例2：在下表中查找key=5

的结点。

静态查找表-有序表查找012key4891011131934567elem此时ST.elem[mid].key＝10>key，因此令high＝mid－1high=7mid=4low=1low=1high=3mid=2此时ST.elem[mid].key＝5>key，因此令high＝mid－1low=1mid=1此时ST.elem[mid].key＝4<key，因此令low=mid＋1high=1high=1low=2mid=1此时low>high查找不成功折半查找的特点 要求元素按关键字有序。 存储结构：顺序。

静态查找表-有序表查找查找表的组织：分块有序，除表本身以外，尚需建立一个“索引表”。查找方法：查找索引表；在数据块内顺序查找

静态查找表-索引顺序表的查找12345678910111213141516171822121389203342443824486058745786532248861713索引表查38查找方法比较

静态查找表ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表顺序查找折半查找分块查找动态查找

二叉排序树：或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；（3）根结点的左、右子树也分别为二叉排序树。

动态查找表二叉排序树的查找过程1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行递归查找；3）若给定值大于根结点的关键字，则继续在右子树上进行递归查找。从根结点开始，若二叉排序树为空，则查找不成功；否则，在查找过程中，生成了一条查找路径：

从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者

从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

——查找成功

——查找不成功性能分析查找表：{3,12,24,37,45,53,61,78,90,98}

动态查找表

45

12

3

37

53

90

24

78

98

61ASL=(1+2+3+4+5+6+7+8+9+10)/10=5.5ASL=(1+22+34+43)/10=2.9

4512337539024789861单支树 一般情况下，没有对二叉排序树的深度进行控制。在构造二叉排序树的过程中进行“平衡化”处理，成为平衡二叉树（AVL树）。平衡二叉树：左子树和右子树的深度之差的绝对值不超过1。

动态查找表二叉排序树的特点 动态查找(插入删除的时机) 含有n个结点的二叉排序树不唯一，与结点插入的顺序有直接关系。 删除某个结点后，二叉排序树要重组。 可得到平衡二叉树。二叉排序树的适用范围 用于组织规模较小的、内存中可以容纳的数据。对于数据量较大必须存放在外存中的数据，则无法快速处理。

动态查找表问题引入：前面讨论的各种结构，记录在结构中的相对位置是随机的，和记录的关键字之间不存在确定关系，因此，在结构中查找记录时需要进行一系列和关键字的比较。

哈希表理想情况是希望不经过任何比较，一次存取就能得到所查记录解决方法：在记录的存储位置和其关键字之间建立一个确定的对应关系f，使每个关键字和结构中的唯一的存储位置相对应。 在查找时，只要根据该对应关系f可找到给定值K的存储位置f(K)。若结构中存在关键字和K相等的记录，则一定在f(K)的存储位置上，所以不需要进行比较即可直接得到所查记录。哈希表：对应关系f为哈希函数，根据上述思想建立的表为哈希表。

哈希表

哈希表基本概念哈希函数构造方法哈希函数冲突处理 基本思想：

在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。即：通过简单计算直接得到数据的地址。 1)哈希(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。 哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字。

哈希表关键字集合存储地址集合hash 2)由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1key2，而

f(key1)=f(key2)。

3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。

哈希表

1235152年份人数

1949195019511999200020002100220044004420例某地区的人口统计表H(年度）=年度-1948

哈希表例30个地区的各民族人口统计表编号地区总人口汉族回族…...1

北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。

哈希表哈希函数的构造方法

构造哈希函数的准则：使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀地分布在逐个地址区间，从而减少冲突。常用的构造方法：（1）直接定址法：取关键字或关键字的某个线性函数值为哈希地址,如年龄。（2）数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址

哈希表常用的构造方法：（2）数字分析法：若事先知道关键字集合，且关键字的位数比哈希表的地址位数多，则可选取数字分布比较均匀的若干位作为散列地址。例如，有一组8位数字组成的关键字：

经过分析可知，前三位和第五位分布不均匀，所以，若表长为1000，则可取4、6、7位的数字作为哈希地址，若表长为100，则可取4、6与7、8位之和并舍去进位作为散列地址。关键字散列地址1散列地址2871426538717223287182745871071368712728187137394465723874013228339990432370327

哈希表（3）平方取中法：取关键字平方后的中间几位为哈希地址。

通常，要预先估计关键字的数字分布并不容易，要找数字均匀分布的位数更难。此时可采用平方取中法：即先通过求关键字的平方来扩大差别，再取其中的几位或其组合作为散列地址。例如：一组关键字：

(0100，0110，1010，1001，0111)平方结果为：(0010000，0012100，1020100，1002001，0012321)若表长为3位，则可取中间三位作为散列地址集：

(100，121，201，020，123)

哈希表（4）折叠法：若关键字位数较多，可将关键字分割成位数相同的几段（最后一段的位数可以不同），段的长度取决于哈希表的地址位数，然后将各段的迭加和（舍去进位）作为哈希地址。例如，对于key=58242324169582423241+69[1]315H(key)=315移位迭加582324241+96[1]243H(key)=243间界迭加

哈希表（5）除留余数法：选择一个适当的正整数P，用P去除关键字，取所得的余数作为哈希地址，即：

H(key)=key%P这个方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大素数比较好。例如：

m=8，16，32，64，128，256，512，1024P=7，13，31，61，127，251，503，1019除余法的地址计算公式简单，而且在很多情况下效果较好，因此是一种常用的构造哈希函数的方法。

哈希表

实际工作中需视情况的不同而采用不同的哈希函数。通常需要考虑的因素有：

A.计算哈希函数所需时间;

B.关键码的长度;

C.哈希表的大小;

D.关键码的分布情况;

E.记录的查找频率。

哈希表 在构造这种特殊的“查找表”时，除了需要选择一个“好”（尽可能少产生冲突）的哈希函数之外，还需要找到一种“处理冲突”的方法。 “处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。 常用的解决冲突的方法：开放定址法，链地址法，再哈希法，建立一个公共溢出区。

哈希表处理冲突的方法1开放定址法

用开放地址法解决冲突的基本思想是：当冲突发生时，使用某种方法在散列表中形成一个探测序列，按此序列逐个单元的查找，直到找到一个指定的关键字或碰到一个开放的地址（单元为空）为止。 插入时碰到开放的地址，即可将待插入新结点放到该地址单元中；查找时碰到开放的地址，则说明表中没有待查的关键字。形成探测的方法不同，所得到的解决冲突的方法也不同。

哈希表1开放定址法在基本区域内形成一个探测序列

Hi=(H(key)+di)MODm,i=1,2,…,k(km-1)其中：m为表长，di为增量序列，可有多种取法：

A.di=1,2,3,…,m-1,称线性探测再散列;B.di=12,-12,22,-22,…,k2,-k2(km/2)

称为二次探测再散列；

C.di=伪随机数序列，称伪随机探测再散列。

哈希表例：在长度为11的哈希表中已有关键字分别为17，60，29的记录（哈希函数H(key)=keyMOD11）,现有第四个记录，其关键字为38，由哈希函数得到的哈希地址是5，产生冲突。若用线性探测再散列方法处理，得到下一个地址6，仍冲突；再求一个地址7，仍冲突；直到哈希地址是8的位置为“空”时止，处理冲突过程结束，将记录填入哈希表中序号为8的位置。

哈希表60172901234567891011601729382再哈希法

Hi=RHi(key)i=1,2,…,kRHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。

哈希表3链地址法将所有关键字为同义词的