第9章 散列结构及其应用.ppt

9 1集合的概念9 2集合的散列存储9 3散列表及其运算9 4散列结构下的查找性能分析9 5散列结构的应用 LZW压缩问题 第9章散列结构及其应用 集合是具有相同属性的数据元素按任何次序排列而成 任一非空集合可表示为 a1 a2 ai ai 1 an 其中i为该元素的编号 是为了区别而任意标注的 不代表任何次序 集合中元素的个数称为集合的长度 当长度n 0时 为空集 说明 集合中的元素可以按任何次序排列 集合的长度是可变化的 当向它插入一个元素后 其长度加1 从中删除一个元素 长度减1 集合中元素的数据类型相同 且可以为任何一种类型 9 1集合的概念 9 2集合的散列存储9 3散列表及其运算9 4散列结构下的查找性能分析9 5散列结构的应用 LZW压缩问题 第9章散列结构及其应用 9 2 1散列的概念9 2 2散列函数的构造9 2 3处理冲突的方法 9 2集合的散列存储 散列 Hash 同顺序 链接和索引一样 是存储数据的又一种方法 散列存储的基本思想是 以所需存储的节点 数据元素 中的关键字 key 作为自变量 通过某种确定的函数H 称作散列函数或者哈希函数 进行计算 把求出的函数值作为该节点的存储地址 并将该节点或节点的关键字存储在这个地址中 散列存储中使用的函数H key 称为散列函数或哈希函数 散列函数实现关键字到存储地址的映射 或称转换 H key 的值称为散列地址或哈希地址 使用的数组空间或文件空间是数据进行散列存储的地址空间 这种存储结构被称为散列表或哈希表 例 假定一个集合为 16 35 23 31 45 70 若规定每个元素key的存储地址H key key 注 H key key称为散列函数 请画出存储结构图 解 根据散列函数H key key 可知元素16应当存入地址为16的单元 元素23应当存入地址为23的单元 对应散列存储表 哈希表 如下 31 23 16 35 45 70 散列存储下的插入与删除 在该存储方式下 若向集合中插入key 25的元素 可根据散列函数H key key 计算出元素25的散列地址为25 即下标为25的存储单元 若在该集合中删除key 31的元素 同样可根据散列函数H key key 计算出元素31的散列地址为31 即从下标为31的存储单元中取出该元素 冲突 上例讨论的散列表是一种理想的情况 实际应用中 常常出现一个待插元素的散列地址已被占用的情况 使得该元素无法直接存入到此单元中 我们称此现象为 冲突 例如 若上例中的散列函数H key 为H key key 10 则元素35和45的散列地址相同 当向散列表中插入元素45时 散列地址 下标为5的单元 已被占用 致使元素45无法存入到下标为5的单元中 冲突产生的原因 散列存储中 虽然冲突很难避免 但发生冲突的可能性却有大有小 这主要与三个因素有关 1 与装填因子 有关 越小 冲突的可能性就越小 越大 最大取1 时 冲突的可能性就越大 2 与所采用的散列函数有关若散列函数选择得当 就能够使散列地址尽可能均匀分布在散列空间上 减少冲突的发生 3 与解决冲突的方法有关方法选择的好坏也将减少或增加发生冲突的可能性 9 2 1散列的概念 9 2 2散列函数的构造9 2 3处理冲突的方法 9 2集合的散列存储 构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上 同时使计算尽可能简单 以节省计算时间 常用的散列函数构造方法有 直接定址法除留余数法数字分析法平方取中法折叠法 Hash key a key b a b为常数 优点 以关键码key的某个线性函数值为哈希地址 不会产生冲突 缺点 要占用连续地址空间 空间效率低 例 关键码集合为 100 300 500 700 800 900 选取哈希函数为Hash key key 100 则存储结构 哈希表 如下 1 直接定址法 Hash key keymodp p是一个整数 特点 以关键字除以p的余数作为哈希地址 关键 如何选取合适的p 技巧 若设计的哈希表长为m 则一般取p m且为质数 也可以是不包含小于20质因子的合数 2 除留余数法 例 已知待散列元素为 18 75 60 43 54 90 46 表长m 10 p 7 则有 H 18 18 7 4H 75 75 7 5H 60 60 7 4H 43 43 7 1H 54 54 7 5H 90 90 7 6H 46 46 7 4 此时冲突较多 为减少冲突 可取较大的m值和p值 如m p 13 结果如下 H 18 18 13 5H 75 75 13 10H 60 60 13 8H 43 43 13 4H 54 54 13 2H 90 90 13 12H 46 46 13 7 0123456789101112 特点 某关键字的某几位组合成哈希地址 所选的位应当是 各种符号在该位上出现的频率大致相同 3 数字分析法 34705243491487348269634852703486305349805834796713473919 例 有一组 例如80个 关键字 其样式如下 讨论 第1 2位均是 3和4 第3位也只有 7 8 9 因此 这几位不能用 余下四位分布较均匀 可作为哈希地址选用 位号 若哈希地址取两位 因元素仅80个 则可取这四位中的任意两位组合成哈希地址 也可以取其中两位与其它两位叠加求和后 取低两位作哈希地址 特点 对关键字平方后 按哈希表大小 取中间的若干位作为哈希地址 理由 平方后中间几位和关键字中每一位都相关 故不同关键字会以较高的概率产生不同的哈希地址 例 2589的平方值为6702921 可以取中间的029为地址 4 平方取中法 5 折叠法 特点 将关键字自左到右分成位数相等的几部分 最后一部分位数可以短些 然后将这几部分叠加求和 并按哈希表表长 取后几位作为哈希地址 适用于 每一位上各符号出现概率大致相同的情况 法1 移位法 将各部分的最后一位对齐相加 法2 间界叠加法 从一端向另一端沿分割界来回折叠后 最后一位对齐相加 例 元素42751896 用法1 427 518 96 1041用法2 42751896 724 518 69 1311 9 2 1散列的概念9 2 2散列函数的构造 9 2 3处理冲突的方法 9 2集合的散列存储 常见的冲突处理方法有 开放定址法 开地址法 链地址法 拉链法 1 开放定址法 这种方法也称再散列法 其基本思想是 当关键字key的哈希地址p H key 出现冲突时 以p为基础 产生另一个哈希地址p1 如果p1仍然冲突 再以p为基础 产生另一个哈希地址p2 直到找出一个不冲突的哈希地址pi 将相应元素存入其中 这种方法有一个通用的再散列函数形式 i 1 2 n 其中H key 为哈希函数 m为表长 di称为增量序列 增量序列的取值方式不同 相应的再散列方式也不同 主要有以下三种 线性探测再散列 di 1 2 3 m 1 这种方法的特点是 冲突发生时 顺序查看表中下一单元 直到找出一个空单元或查遍全表 二次探测再散列 di 12 12 22 22 k2 k2 k m 2 这种方法的特点是 冲突发生时 在表的左右进行跳跃式探测 比较灵活 伪随机探测再散列 di 伪随机数序列 具体实现时 应建立一个伪随机数发生器 如i i p m 并给定一个随机数做起点 例 已知哈希表长度m 11 哈希函数为 H key key 11 则H 47 3 H 26 4 H 60 5 假设下一个关键字为69 则H 69 3 与47冲突 用线性探测再散列处理冲突 下一个哈希地址为H1 3 1 11 4 仍然冲突 再找下一个哈希地址为H2 3 2 11 5 还是冲突 继续找下一个哈希地址为H3 3 3 11 6 此时不再冲突 将69填入6号单元 012345678910 用二次探测再散列处理冲突 因H 69 3与47冲突 下一个哈希地址为H1 3 12 11 4 仍然冲突 再找下一个哈希地址为H2 3 12 11 2 此时不再冲突 将69填入2号单元 012345678910 用伪随机探测再散列处理冲突 且伪随机数序列为 2 5 9 则下一个哈希地址为H1 3 2 11 5 仍然冲突 再找下一个哈希地址为H2 3 5 11 8 此时不再冲突 将69填入8号单元 012345678910 2 链地址法 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表 并将单链表的头指针存在哈希表的第i个单元中 因而查找 插入和删除主要在同义词链中进行 链地址法适用于经常进行插入和删除的情况 例 已知一组关键字 32 40 36 53 16 46 71 27 42 24 49 64 哈希表长度为13 哈希函数为 H key key 13 则用链地址法处理冲突的结果如图所示 同一链表中关键字自小到大有序 一组关键字 32 40 36 53 16 46 71 27 42 24 49 64 哈希函数为 H key key 13 9 1集合的概念9 2集合的散列存储 9 3散列表及其运算9 4散列结构下的查找性能分析9 5散列结构的应用 LZW压缩问题 第9章散列结构及其应用 对散列表的运算主要有 散列表的初始化 清除散列表 向散列表中插入元素 查找散列表 从散列表中删除元素等 在集合的散列存储中 处理冲突的方法不同 其散列表的类型定义也不同 假定使用HashMaxSize常量表示待定义的散列表类型的长度 下面分别给出与开放定址法和链地址法对应的散列表类型下散列表的运算 9 3 1采用开放定址法解决冲突的散列表及其运算9 3 2采用链地址法解决冲突的散列表及其运算 9 3散列表及其运算 用线性探测法处理冲突 散列表的数据结构如下 defineMAX LENGTH100 散列表的最大长度typeofstruct 定义节点类型intkey 关键字 也可以采用其它数据类型chardata 其它数据项 可以采用其它数据类型 ElemType typeofstruct 定义散列表类型ElemTypeelems MAX LENGTH 节点数组intlen 散列表长度 HashTable intstored MAX LENGTH 标志数组 初始化散列表初始化散列表的算法需要完成两项操作 一是设置散列表的长度 二是初始化标志数组的元素为0 初始化散列表的算法如下 voidinitHashTable HashTableht intn ht 散列表 n 散列表长度ht len n 设置散列表的长度inti for i 0 i n i 初始化标志数组stored i 0 向散列表中插入一个元素将一个节点插入到散列表中 其算法分为以下几步 1 根据节点关键字 计算散列地址 2 根据标志判断是否发生冲突 如果发生冲突 进行线性探测再散列 直到找到空地址 3 找到空地址 把节点插入到散列表中 修改标志数组 4 如果散列表中已经没有空地址 则报错算法如下 voidinsert HashTableht ElemTypeele ht 散列表 ele 插入节点inti add i Hash ele key 计算散列地址 Hash 是散列函数 if stored i 0 没发生冲突ht elems i ele stored i 1 else 发生冲突 再散列add i i i 1 ht len while i add stored i 1 i i 1 ht len if stored i 0 找到空地址ht elems i ele stored i 1 else 散列表中已经没有空地址 报错printf erroroccurred 从散列表中查找一个元素在线性探测散列表中查找一个节点 其算法分为以下几步 1 根据待查节点关键字 计算散列地址 2 如果该地址存储的节点关键字等于待查节点关键字 则找到 否则进行线性探测再散列 直到待查关键字或遇到空地址或找遍散列表 3 如果找到待查关键字 则返回散列地址 如果遇到空地址或找遍散列表 则说明散列表中没有待查节点 返回 1 算法如下 intsearch HashTableht ElemTypeele ht 散列表 ele 待查找节点inti add i Hash ele key 计算散列地址if stored i 1 ht elems i key ele key 找到returni else 线性探测再散列add i i i 1 ht len while i add stored i 1 ht elems i key ele key i i 1 ht len if ht elems i key ele key 找到待查节点returni else 散列表中找不到该节点printf cannotfind return 1 从散列表中删除一个元素在线性探测散列表中删除一个节点 其过程分为两步 1 首先查找节点 2 如果找到则删除 方法是更新标志数组 否则报错算法如下 voiddelete HashTableht ElemTypeele inti i search ht ele if i 1 找到待删除节点 删除stored i 0 else 没有找到 报错printf erroroccurred 对于线性探测散列表 删除节点会引起 信息丢失 的问题 因为在线性探测在散列法中 我们处理冲突的方式是把同义词放到散列表中的下一个空地址 而查找是沿着同一个路径进行 因此当我们删除了一个节点后 由于标志数组被更新 其后的同义词也将不再被查找到 9 3 1采用开放定址法解决冲突的散列表及其运算 9 3 2采用链地址法解决冲突的散列表及其运算 9 3散列表及其运算 在链地址法中 每个节点对应一个链表节点 它由三个域组成 其中 key为关键字域 存放节点的关键字 data为数据域 存放节点的其他数据信息 next为链域 存放指向下一个同义词节点的指针 采用C语言定义的数据类型如下所示 defineMAX LENGTH100 散列表的最大长度typeofstruct 定义节点节点类型intkey 关键字 可以采用其它数据类型ElemTypedata 存储节点的全部数据ElemNode next 指向下一个同义词节点的指针 ElemNode typeofstruct 定义表头节点类型和散列表类型ElemNode first 指向同义词链表中第一个节点的指针 ElemHeader HashTable MAX LENGTH 所有的同义词构成一个单链表 再由一个表头节点指向这个单链表的第一个节点 这些表头节点组成一个一维数组 即散列表 数组元素的下标对应由散列函数求出的散列地址 初始化散列表初始化拉链散列算法只需要把散列表中所有表头节点的指针域置为NULL即可 算法如下 voidinitHashTable HashTableht intn ht 散列表 n 散列表长度inti for i 0 i n i 初始化标志数组ht i first NULL 向散列表插入一个元素将一个节点插入到拉链散列表中 算法分为以下几步 1 根据节点关键字 计算散列地址 2 根据散列地址找到表头节点 并将节点插入到对应的单链表中算法如下 voidinsert HashTableht ElemTypeele inti ElemNode p i Hash ele key 计算散列地址 Hash 是散列函数 p ElemNode malloc sizeof ElemNode 分配节点存储代插入节点p key ele key p data ele p next ht i first 插入到单链表中ht i first p 从散列表中查找一个元素在散列链表中查找一个节点 其算法分为以下几步 1 根据待查节点关键字 计算散列地址 2 在散列地址所指向的单链表中顺次查找待查节点关键字 3 如果找到待查关键字 则返回指向该节点的指针 否则说明散列表中没有待查节点 返回NULL 算法如下 intsearch HashTableht ElemTypeele ht 散列表 ele 待查找节点inti ElemNode p i Hash ele key 计算散列地址 Hash 是散列函数p ht i first while p NULL p key ele key 顺次查找单链表p p next returnp 从散列表中删除一个元素在拉链散列表中删除一个节点 其算法分为两步 1 首先查找节点 2 如果找到则删除 方法和在单链表中删除一个节点一样 否则报错 算法如下 voiddelete HashTableht ElemTypeele ht 散列表 ele 待删除节点inti ElemNode p q i Hash ele key 计算散列地址 Hash 是散列函数p ht i first if p NULL 没有找到 报错printf erroroccurred else q p next while q NULL q key ele key p q q q next if q NULL 没有找到 报错printf erroroccurred else 找到 删除p next q next free q 释放空间 通过上述算法可以看出 采用链地址法构造的散列表不会出现因删除而引起的 信息丢失 的问题 但采用拉链法 散列表所占的存储空间要比开放定址法的大 9 1集合的概念9 2集合的散列存储9 3散列表及其运算 9 4散列结构下的查找性能分析9 5散列结构的应用 LZW压缩问题 第9章散列结构及其应用 明确 散列函数没有 万能 通式 要根据元素集合的特性而分别构造 讨论 散列查找的速度是否为真正的O 1 不是 由于冲突的产生 使得散列表的查找过程仍然要进行比较 仍然要以平均查找长度ASL来衡量 一般地 ASL依赖于散列表的装填因子 它标志着散列表的装满程度 越大 表中记录数越多 说明表装得越满 发生冲突的可能性就越大 查找时比较次数就越多 0 1 在散列表的插入和查找算法中 平均查找长度与表的大小m无关 只与自己所取的散列函数 的值和处理冲突的方法有关 假定所选取的散列函数能够使任意关键字等概率的映射到散列空间的任一地址上 则理论上已经证明 当采用线性探查法 处理冲突时 平均查找长度为 1 1 1 a 2 当用链地址法处理冲突时 平均查找长度为1 a 2 当用开放定址法中的平方探查法 双散列函数探查法处理冲突时 平均查找长度为 ln 1 a a 即 ASL与装填因子 有关 既不是严格的O 1 也不是O n 在散列存储中 插入和查找的速度是相当快的 它优于前面其他任一方法 特别是当数据量很大时更是如此 散列存储的缺点是 根据关键字计算散列地址需要花费一定的计算时间 若关键字不是整数 则首先要把它转化为整数 为此也要花费一定的转化时间 占用的存储空间比较多 因为采用开放定址法解决冲突的散列总是取a值小于1 采用链接法处理冲突的散列表同数据的链接的存储相比多占用一个具有m个位置的指针数组空间 在散列表中只能按关键字查找元素 而很难按非关键字查找元素 若用散列表存储线性表 数据中元素之间的逻辑关系无法体现出来 例给定关键字序列11 78 10 1 3 2 4 21 试分别用顺序查找 二分查找 二叉排序树查找 散列查找 用线性探查法和拉链法 来实现查找 试画出它们的对应存储形式 顺序查找的顺序表 二分查找的判定树 二叉排序树查找的二叉排序树及两种散列查找的散列表 并求出每一种查找的成功平均查找长度 散列函数H k k 11 顺序查找的顺序表 一维数组 如图所示 从图中可以得到顺序查找的成功平均查找长度为 ASL 1 2 3 4 5 6 7 8 8 4 5 012345678910 二分查找的判定树 中序序列为从小到大排列的有序序列 如图所示 从图中可以得到二分查找的成功平均查找长度为 ASL 1 2 2 3 4 4 8 2 625 二叉排序树 关键字顺序已确定 该二叉排序树应唯一 如图所示 从图中可以得到二叉排序树查找的成功平均查找长度为 ASL 1 2 2 3 2 4 5 2 8 3 125 散列函数H k k 11线性探查法解决冲突的散列表如图所示 从图中可以得到线性探查法的成功平均查找长度为 ASL 1 1 2 1 3 2 1 8 8 2 375 012345678910 012345678910 拉链法解决冲突的散列表如图所示 从图中可以得到拉链法的成功平均查找长度为 ASL 1 6 2 2 8 1 25 9 1集合的概念9 2集合的散列存储9 3散列表及其运算9 4散列结构下的查找性能分析 9 5散列结构的应用 LZW压缩问题 第9章散列结构及其应用 LZW压缩就是将输入的数据流转换成输出的编码流 在转换过程中动态构建编译表 其过程可以分为如下几步 1 初始化编译表 包括开辟编译表空间 把根字符放入编译表中 2 定义一个前缀对象CurrentPrefix 记为p 初始时p 定义一个当前字符串CurrentString p记为p k 其中k为当前读取的数据流中的字符 3 依次读取数据流中的字符 做 3 1 CurrentString p k 代表字符串连接操作 3 2 检查CurrentString是否在编译表中 如果在 则p p k 继续读取下一个字符 否则输出p在编译表中的索引到编码流中 把CurrentString加入到编译表中 p k 读取下一个字符 4 输出p在编译表中的索引到编码流中 例9 21 输入的数据流是abacababad 采用LZW压缩 过程中各变量的变化如表9 5所示 其中编译表的索引从0开始 3 1 CurrentString p k 代表字符串连接操作 3 2 检查CurrentString是否在编译表中 如果在 则p p k 继续读取下一个字符 否则输出p在编译表中的索引到编码流中 把CurrentString加入到编译表中 p k 读取下一个字符 下面给出LZW压缩算法 voidlzw comp char charStream charStream为输入数据流 由a b c d四种字符组成chark 当前读入的字符char p 前缀char currStr 当前字符串charStringTable 1024 编译表inti 0 j m 初始化编译表StringTable 0 a StringTable 1 b StringTable 2 c StringTable 3 d for m 4 m 1024 m StringTable m 0 m 4 k charStream i p malloc sizeof char p 0 currStr malloc sizeof char currStr 0 while k 0 依次读取数据流strcpy currStr p strcat currStr k j search StringTable currStr 在编译表中查找当前字符串 if j 1 没有找到printf search StringTable p 输出前缀在编译表中的索引strcpy StringTable m currStr 当前字符串加入到编译表中strcpy p k else 找到s