数据结构第讲哈希表和插入排序

数据结构第讲哈希表和插入排序第1页，共58页，2023年，2月20日，星期六9.3.1什么是哈希表哈希表技术的主要目标是提高查找效率。1.哈希函数：根据关键字直接计算出元素所在位置的函数。

例：设哈希函数为：H(K)=K/3+1，则构造关键字序列为1、2、5、9、11、13、16、21、27的散列表（哈希表）为：序号12345678910H(K)15913162127211第2页，共58页，2023年，2月20日，星期六2.冲突两个不同的关键字具有相同的存储位置。序号12345678910H(K)15913162127211第3页，共58页，2023年，2月20日，星期六3.哈希表根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。第4页，共58页，2023年，2月20日，星期六在哈希存储中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。(1)装填因子α；装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即α=n/m（α<=1）。α越小，发生冲突的可能性越小，反之，发生冲突的可能性就越大。但是，α太小又会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两个方面。(2)所构造的哈希函数;(3)解决冲突的方法。第5页，共58页，2023年，2月20日，星期六①构造好的哈希函数，使冲突尽可能的少②设计有效的解决冲突的方法第6页，共58页，2023年，2月20日，星期六第9章查找9.1静态查找表9.2动态查找表9.3哈希表

9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法9.3.4哈希表的查找及其分析第7页，共58页，2023年，2月20日，星期六9.3.2哈希函数的构造方法例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：1.直接定址法取关键字或关键字的某个线性函数值为散列地址，即（K）=K或H（K）=a*K+b（其中a、b为常数）。0123456789900800700500300100优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。缺点：要占用连续地址空间，空间效率低。

第8页，共58页，2023年，2月20日，星期六2.除后余数法取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数。即H（K）=Kmodp（p≤m）经验得知：一般可选p为质数或不包含小于20的质因素的合数。3.平方取中法取关键字平方后的中间几位为哈希函数。因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。

第9页，共58页，2023年，2月20日，星期六选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。34705243491487348269634852703486305349805834796713473919例：有一组（例如80个）关键码，其样式如下：讨论：①

第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号：①②③④⑤⑥⑦②若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。4.数字分析法第10页，共58页，2023年，2月20日，星期六5.折叠法

是将关键字按要求的长度分成位数相等的几段，最后一段如不够长可以短些，然后把各段重叠在一起相加并去掉进位，以所得的和作为地址。适用于：每一位上各符号出现概率大致相同的情况。

移位法：将各部分的最后一位对齐相加。

间界叠加法：从一端向另一端沿分割界来回折叠后，最后一位对齐相加。例：元素42751896,移位法：

427＋518＋96=1041间界叠加法：

42751896—>724+518+69=1311第11页，共58页，2023年，2月20日，星期六6.随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。第12页，共58页，2023年，2月20日，星期六实际工作中需视不同情况采用不同的哈希函数。通常考虑的因素：(1)计算哈希函数所需时间(包括硬件指令的因素)；(2)关键字的长度；(3)哈希表的大小；(4)关键字的分布情况；(5)记录的查找频率。第13页，共58页，2023年，2月20日，星期六第9章查找9.1静态查找表9.2动态查找表9.3哈希表

9.3.1什么是哈希表

9.3.2哈希函数的构造方法

9.3.3处理冲突的方法9.3.4哈希表的查找及其分析第14页，共58页，2023年，2月20日，星期六9.3.3处理冲突的方法1.开放地址法

开放地址就是表中尚未被占用的地址，当新插入的记录所选地址已被占用时，即转而寻找其它尚开放的地址。（1）线性探测法设散列函数H（K）=Kmodm（m为表长），若发生冲突，则沿着一个探查序列逐个探查，那么，第i次计算冲突的散列地址为：Hi=(H(K)+di)modm(di=1,2,…,m-1)第15页，共58页，2023年，2月20日，星期六例关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=keymod11；拟用线性探测法处理冲突。建哈希表：012345678910477291116922283第16页，共58页，2023年，2月20日，星期六线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。可采用二次探测法或伪随机探测法，以改善“堆积”问题。

第17页，共58页，2023年，2月20日，星期六1.开放地址法（2）二次探测法二次探测法对应的探查地址序列的计算公式为：Hi=(H(k)+di)modm其中di

=12,-12,22,-22,…,j2,-j2(j≤m/2)。第18页，共58页，2023年，2月20日，星期六012345678910112234792167298若di＝伪随机序列，就称为伪随机探测法例关键码集为{47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=keymod11；拟用二次探测法处理冲突。建哈希表如下：Hi=(H(k)+di)modm其中di

=12,-12,22,-22,…,j2,-j2(j≤m/2)第19页，共58页，2023年，2月20日，星期六2.链地址法优点：插入、删除方便。缺点：占用存储空间多。基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。第20页，共58页，2023年，2月20日，星期六例：设{47,7,29,11,16,92,22,8,3,50,37,89}的哈希函数为：Hash(key)=keymod11，用拉链法处理冲突，建表。

01234567891022118934737922971650810有冲突的元素可以插在表尾,也可以插在表头。第21页，共58页，2023年，2月20日，星期六3.再哈希法Hi=RHi(key)RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产生“聚集”，但是增加了计算时间。

4.建立一个公共溢出区第22页，共58页，2023年，2月20日，星期六第9章查找9.1静态查找表9.2动态查找表9.3哈希表

9.3.1什么是哈希表

9.3.2哈希函数的构造方法9.3.3处理冲突的方法

9.3.4哈希表的查找及其分析第23页，共58页，2023年，2月20日，星期六9.3.4哈希表的查找及其分析散列表的目的主要是用于快速查找。在建表时采用何种散列函数及何种解决冲突的办法，在查找时，也采用同样的散列函数及解决冲突的办法。第24页，共58页，2023年，2月20日，星期六例：设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函数为：H（k）=kmod13。采用开放地址的线性探测法解决冲突，试在0～18的散列地址空间中，对该关键字序列构造哈希表。解：依题意m=19，得到线性探测法对应的探查地址序列计算公式为：di=(H(k)+j)mod19;j=1,2,……,18其计算函数如下：

第25页，共58页，2023年，2月20日，星期六H(19)=19mod13=6H(01)=01mod13=1H(23)=23mod13=10H(14)=14mod13=1(冲突)H(14)=(1+1)mod19=2H(55)=55mod13=3H(20)=20mod13=7H(84)=84mod13=6

(冲突)H(84)=(6+1)mod19=7

(冲突)H(84)=(6+2)mod19=8H(27)=27mod13=1（冲突）H(27)=(1+1)mod19=2

(冲突)H(27)=(1+2)mod19=3

(冲突)H(27)=(1+3)mod19=4012345678910111213141516171819{19,01,23,14,55,20,84,27,68,11,10,77}0123145520842777101168……第26页，共58页，2023年，2月20日，星期六哈希查找的性能分析哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。第27页，共58页，2023年，2月20日，星期六1.线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的哈希函数H及装填因子α的值和该处理方法有关。这时的成功的平均查找长度为：ASL=(1+1/(1-α))/2第28页，共58页，2023年，2月20日，星期六2.链地址法查找的性能分析由于链地址法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。平均查找长度：ASL=1+α/2第29页，共58页，2023年，2月20日，星期六例：给定关键字序列{11，78，10，1，3，2，4，21}，试分别用顺序查找、二分查找、二叉排序树查找、平衡二叉树查找、哈希查找(用线性探查法和拉链法)来实现查找，试画出它们的对应存储形式(顺序查找的顺序表，二分查找的判定树，二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树，两种哈希查找的哈希表)，并求出每一种查找的成功平均查找长度。设哈希函数为：H(k)=kmod11，哈希表表长m=11。第30页，共58页，2023年，2月20日，星期六顺序查找的顺序表（一维数组）由图可得：顺序查找的成功平均查找长度为ASL=(1+2+3+4+5+6+7+8)/8=4.5第31页，共58页，2023年，2月20日，星期六二分查找的判定树（中序序列为从小到大排列的有序序列）由图可得：二分查找的成功平均查找长度为ASL=(1+2*2+3*4+4)/8=2.625第32页，共58页，2023年，2月20日，星期六二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图(b)所示。由图(a)可得：二叉排序树查找的成功平均查找长度为ASL=(1+2*2+3*2+4+5*2)/9=3.125由图(b)可得：平衡二叉树的成功平均查找长度为ASL=(1+2*2+3*3+4*2)/8=2.75

11

10

1

3

2

4

78

213

1

11

2

10

4

78

21

(a)二叉排序树

(b)平衡二叉树第33页，共58页，2023年，2月20日，星期六线性探查法解决冲突的哈希表如图所示。由图可得：线性探查法的成功平均查找长度为ASL=（1+1+2+1+3+2+8+1）/8=2.375第34页，共58页，2023年，2月20日，星期六链地址法解决冲突的哈希表如图所示。由图可得：链地址法的成功平均查找长度为ASL=(1*6+2*2)/8=1.25第35页，共58页，2023年，2月20日，星期六小结1.掌握查找的基本概念；2.熟练掌握静态查找表的查找算法思想并灵活应用；3.熟练掌握动态查找表的特点以及二叉排序树、平衡二叉树的各种操作思想4.了解B-、B+树的概念及插入和删除操作；5.熟练掌握哈希表的基本概念、哈希函数的构造方法和解决冲突的方法，并能计算平均查找长度。第36页，共58页，2023年，2月20日，星期六第10章内部排序10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较第37页，共58页，2023年，2月20日，星期六10.1排序的基本概念1.排序设含有n个记录的文件｛R1，R2，…Rn｝，相应的关键字为｛K1，K2，…Kn｝，需确定一种排列P(1),P(2)…P(n)使其相应的关键字满足递增(或递减)关系：KP(1)≤KP(2)≤…KP(n)或KP(1)≥KP(2)≥…KP(n)使上述文件成为一个按其关键字线性有序的文件｛RP(1)，RP(2)，…RP(n)｝，这种运算就称为排序。将数据元素的无序序列调整为有序序列的过程。第38页，共58页，2023年，2月20日，星期六2.排序算法的稳定性

排序码（Key）作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。如果待排序的序列中，存在多个具有相同排序码的数据元素，若经过排序这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，若经过排序，这些数据元素的相对次序发生了改变，则称这种排序算法是不稳定的。第39页，共58页，2023年，2月20日，星期六3.内部排序与外部排序

内部排序指当文件的数据量不太大时，全部信息放内存中处理的排序方法。

外部排序当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的，这种排序称为外排序。第40页，共58页，2023年，2月20日，星期六4.内部排序的方法内部排序的过程是一个逐步扩大记录的有序序长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或几个的操作称为一趟排序。内部排序的方法很多，每种方法都有各自的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。第41页，共58页，2023年，2月20日，星期六排序简单排序方法，其时间复杂度为O(n2)先进排序方法，其时间复杂度为O(nlogn)基数排序，其时间复杂度为O(d·n)按内部排序过程中所需的工作量来区分：第42页，共58页，2023年，2月20日，星期六插入类（直插排序、二分排序、希尔排序）交换类（冒泡排序、快速排序）选择类（直选排序、树型排序、堆排序）归并类（二路归并排序、多路归并排序）分配类（多关键字排序、基数排序）按排序过程中依据的原则分排序第43页，共58页，2023年，2月20日，星期六#defineMAXSIZE20//一个顺序表的最大长度typedefintKeyType;//定义关键字为整数类型Typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;//记录类型Typedefstruct{RedTyper[MAXSIZE+1];//r[0]用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型第44页，共58页，2023年，2月20日，星期六第10章内部排序10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较第45页，共58页，2023年，2月20日，星期六10.2插入排序直接插入排序折半插入排序2-路插入排序表插入排序希尔排序第46页，共58页，2023年，2月20日，星期六1）一趟直接插入排序的基本思想将记录L.r[i]插入到有序子序列L.r[1..i-1]中，使记录的有序序列从L.r[1..i-1]变为L.r[1..i]。完成这个“插入”分三步进行：1．查找L.r[i]在有序子序列L.r

[1..i-1]中的插入位置j；2．将L.r

[j..i-1]中的记录后移一个位置；3．将L.r

[i]复制到L.r

[j]的位置上。整个排序过程进行n–1趟插入，即：先将序列中的第1个记录着成一个有序的子序列，然后从第2个记录起逐个插入，直至整个序列变成接关键字非递减有序序列为止。1.直接插入排序第47页，共58页，2023年，2月20日，星期六待排元素序列：[53]2736156942第一次排序：(27)[2753]36156942第二次排序：(36)[273653]156942第三次排序：(53)[15273653]6942第四次排序：(69)[1527365369]42第五次排序:(42)[152736425369]

直接插入排序示例（插入操作要进行n-1次）第48页，共58页，2023年，2月20日，星期六2）直接插入排序算法描述

voidInsertionSort(SqList&L){//对记录序列R[1..L.length]作直接插入排序。for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//复制为监视哨for(j=i-1;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}//InsertSort第49页，共58页，2023年，2月20日，星期六3）直接插入排序性能分析

实现排序的基本操作有：（1）“比较”关键字的大小（2）“移动”记录对于直接插入排序：最好情况“比较”次数：n-1；“移动”次数：2(n-1)最坏的情况“比较”和“移动”的次数均达到最大值，分别为：(n+2)(n-1)/2；(n+4)(n-1)/2由于待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的时间复杂度为O(n2)。

直接插入排序是“稳定的”：关键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换。第50页，共58页，2023年，2月20日，星期六2.折半插入排序1）基本思想考虑到L.r[1..i-1]是按关键字有序的有序序列，则可以利用折半查找实现“L.r[1…i-1]中查找L.r[i]的插入位置”如此实现的插入排序为折半插入排序。第51页，共58页，2023年，2月20日，星期六(high<low，查找结束，插入位置为low或high+1)(42>36)(42<53)折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42

[1527365369]42

[1527365369]42

[152736425369]highmidlowlowhighmid

highlow第52页，共58页，2023年，2月20日，星期六voidBinsertSort(SqList&L){inti,low,high,mid;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];

low=1;high=i-1;While(low<=high){mid=(low+high)/2;if(L.r[0].key<L.r[mid].key)high=mid-1;elselow=mid+1;}

for(j=i-1;j>=low;

j)L.r[j+1]=L.r[j];L.r[low]=L.r[0];}}2)折半插入排序算法第53页，共58页，2023年，2月20日，星期六3)折半插入排序性能分析折半插