数据结构课件(c语言).pptVIP

1 第8章查找 8 1基本概念与基本运算8 2静态查找表8 3动态查找表1 树表8 4动态查找表2 哈希表查找 回顾 1静态查找表查找的ASL是 对应的时间复杂度2动态树表查找的ASL 对应的时间复杂度3一个查找算法最理想的的时间复杂度应该是什么 4在数组中按编号查找某个元素的时间复杂度是 5对给定的查找表 数据元素的集合 能否把它们采用特别的方法组织到数组中呢 把数据元素的关键码通过某种计算方法直接确它在数组中的存储位置 这样构造的数组就是哈希表 0 m 1 h k1 h k4 h k3 U universeofkeys k1 k2 k3 k5 k4 8 4动态查找表2 哈希表查找 8 4 1哈希表的概念1 哈希查找的基本思想在记录的存储地址和它的关键字之间建立一个确定的对应关系 这样不经过比较 或进行少量比较 一次存取就能得到所查元素的查找方法 2 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数 哈希函数可写成 addr ai H ki 其中 ai是表中的一个元素 addr ai 是ai的存储地址 ki是ai的关键字 3哈希表应用哈希函数 由记录的关键字确定记录在表中的地址 并将记录放入此地址 这样构成的表叫哈希表 数组的推广 4 哈希查找又叫散列查找 利用哈希函数进行查找的过程叫哈希查找 注意到哈希表建立的时候用哈希函数 以编号作关键字 构造哈希函数 H key keyH 1 1H 2 2 以地区作关键字 取地区名称第一个拼音字母的序号作哈希函数 H Beijing 2H Shanghai 19H Shenyang 19 5 冲突k1 k2 但H k1 H k2 的现象叫冲突 Collision 映射到同一哈希地址上的关键码称为 同义词 0 m 1 h k1 h k4 h k3 U universeofkeys k1 k2 k3 k5 k4 我们希望能找到尽可能产生均匀映射的哈希函数 从而尽可能降低发生冲突的概率 哈希方法需要解决以下两个问题 尽量构造好的哈希函数 好的哈希函数有三个方面的含义 一是所构造的函数应该尽可能简单 以便提高哈希地址的计算速度 二是所构造的函数应该尽量减少存储空间的浪费 三是根据所选函数计算出的地址 应在哈希地址集中大致均匀分布 减少冲突 制定解决冲突的方案 如果发生了冲突怎么解决 8 4 2哈希函数的构造方法 1 直接定址法 构造 取关键字或关键字的某个线性函数作哈希地址 即H key key或H key a key b比如 统计1 100岁的人口 用年龄做关键字 哈希函授可以就取关键字本身 特点 直接定址法所得地址集合与关键字集合大小相等 不会发生冲突实际中能用这种哈希函数的情况很少 2 数字分析法 构造 对关键字进行分析 取关键字的若干位或其组合作哈希地址 比如 取学号某些位排定学生宿舍号 110611201楼号层号房间号 特点 适于关键字位数比哈希地址位数大 且可能出现的关键字事先知道的情况 例有80个记录 关键字为8位十进制数 哈希地址为2位十进制数 怎么取合适 分析 只取8 只取1 只取3 4 只取2 7 5 数字分布近乎随机所以 取 任意两位或两位与另两位的叠加作哈希地址 3 平方取中法构造 取关键字平方后中间几位作哈希地址适于不知道全部关键字情况例如 若关键码K 1234 哈希表长为1000 则有 K2 1522756 取中间3位227作为哈希地址 4 折叠法构造 将关键字分割成位数相同的几部分 然后取这几部分的叠加和 舍去进位 做哈希地址种类移位叠加 将分割后的几部分低位对齐相加间界叠加 从一端沿分割界来回折送 然后对齐相加适于关键字位数很多 且每一位上数字分布大致均匀情况 5 除留余数法构造 取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址 即H key keyMODp p m特点简单 常用 可与上述几种方法结合使用p的选取很重要 p选的不好 容易产生同义词 例 设有关键码序列 2049 1756 0056 3187 4356 6349 若p 100 则对应的哈希地址就是关键码的后两位即49 56 56 87 56 49 很不均匀实践证明一般选取p m的最大质数效果比较好 6 随机数法构造 取关键字的随机函数值作哈希地址 即H key random key 适于关键字长度不等的情况 选取哈希函数应考虑的因素 计算哈希函数所需时间关键字长度哈希表长度 哈希地址范围 关键字分布情况记录的查找频率 8 4 3处理冲突的方法 1开放定址法2再哈希方法3拉链方法4建立公共溢出区 1 开放定址法 方法 当冲突发生时 形成一个探查序列 沿此序列逐个地址探查 直到找到一个空位置 开放的地址 将发生冲突的记录放到该地址中 即Hi H key di MODm i 1 2 k k m 1 其中 H key 哈希函数m 哈希表表长di 增量序列 分类 线性探测再散列 di 1 2 3 m 1二次探测再散列 di 1 1 2 2 3 k k m 2 伪随机探测再散列 di 伪随机数序列 例表长为11的哈希表中已填有关键字为17 60 29的记录 H key keyMOD11 现有第4个记录 其关键字为38 按三种处理冲突的方法 将它填入表中 1 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 2 MOD11 7冲突H3 5 3 MOD11 8不冲突 38 2 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 1 MOD11 4不冲突 38 3 H 38 38MOD11 5冲突设伪随机数序列为9 则 H1 5 9 MOD11 3不冲突 38 2 再哈希法方法 构造若干个哈希函数 当发生冲突时 计算下一个哈希地址 即 Hi Rhi key i 1 2 k其中 Rhi 不同的哈希函数特点 计算时间增加 3 链地址法 拉链法 方法 将所有关键字为同义词的记录存储在一个单链表中 并用一维数组存放头指针 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key keyMOD13 用链地址法处理冲突 0123456789101112 4 建立一个公共溢出区设哈希函数产生的哈希地址集为 0 m 1 则分配两个表 一个基本表 每个单元只能存放一个元素 一个溢出表 只要关键码对应的哈希地址在基本表上产生冲突 则所有这样的元素一律存入溢出表中 查找时 对给定值通过哈希函数计算出哈希地址 先与基本表的单元比较 若相等 查找成功 否则 再到溢出表中进行查找 8 4 4哈希查找过程及分析1 哈希查找过程 2 哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于 哈希函数处理冲突的方法哈希表的填满因子 表中填入的记录数 哈希表长度 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key keyMOD13 哈希表长为m 16 设每个记录的查找概率相等 1 用线性探测再散列处理冲突 即Hi H key di MODm H 55 3冲突 H1 3 1 MOD16 4冲突 H2 3 2 MOD16 5 H 79 1冲突 H1 1 1 MOD16 2冲突 H2 1 2 MOD16 3冲突 H3 1 3 MOD16 4冲突 H4 1 4 MOD16 5冲突 H5 1 5 MOD16 6冲突 H6 1 6 MOD16 7冲突 H7 1 7 MOD16 8冲突 H8 1 8 MOD16 9 ASL 1 6 2 3 3 4 9 12 2 5 14 1 68 27 55 19 20 84 79 23 11 10 H 19 6 H 14 1 H 23 10 H 1 1冲突 H1 1 1 MOD16 2 H 68 3 H 20 7 H 84 6冲突 H1 6 1 MOD16 7冲突 H2 6 2 MOD16 8 H 27 1冲突 H1 1 1 MOD16 2冲突 H2 1 2 MOD16 3冲突 H3 1 3 MOD16 4 H 11 11 H 10 10冲突 H1 10 1 MOD16 11冲突 H2 10 2 MOD16 12 2 用链地址法处理冲突 ASL 1 6 2 4 3 4 12 1 75 关键字 19 14 23 1 68 20 84 27 55 11 10 79 8 4 5哈希表算法实现 1线性探测哈希表的建立2线性探测哈希表的查找3拉链哈希表的建立4拉链哈希表的查找5哈希表的删除 1线性探测哈希表的建立voidCreateSeqHTbl datetypeSeqHTbl intm datatype eptr 用线性探测法处理冲突建立散列表SeqHTbl eptr为待放入散列表中的数据基址 Hash 为散列函数 m为散列表的长度 intd for i 0 idata key 0 待放入散列表的元素 其关键码0表示结束 d Hash eptr data key 求当前元素的散列地址 while SeqHTbl d 0 d d 1 m SeqHTbl d eptr 找到空单元 填装结点 eptr 2以线性探测法处理冲突构造的散列表中的查找intReSeqHTbl datetypeSeqHTbl intm keytypekey SeqHTbl散列表 散列函数Hash m为散列表的长度 查找关键码为key的元素 成功返回其地址 否则返回 1 intd begin 求当前元素的散列地址 并将起始点记录在begin中 begin d Hash key while SeqHTbl d key 0 查找成功返回的是地址 不成功为 1 3拉链法哈希表的建立存储结构 typedefstructhnode datatypedata 关键字 其它信息 structhnode next 指向下一个同义词的指针 HNode 定义散列表 指针向量或指针数组 definem m为散列表的容量 HNode HashTbl m 以拉链法构造散列表的算法voidCreateLHTbl HNode LHashTbl m datatype eptr 用拉链法处理冲突建立散列表LHashTbl eptr为待放入散列表中的数据基址 Hash 为散列函数 intd HNode q for i 0 i m i LHashTbl i NULL 散列表初始化 while eptr data key 0 待放入散列表的元素 其关键码0表示结束 d Hash eptr data key 求当前元素的散列地址 q HNode malloc sizeof HNode 申请新结点 q data key eptr data key 填装结点信息 q next LHashTbl d 插入到同义词的链表 LHashTbl d q 注意是向前插入eptr 指向下一个元素 4拉链法哈希表的查找HNode CreateLHTbl HNode LHashTbl m keytypekey LHashTbl是用拉链法处理冲突建立的散列表 散列函数为Hash m为散列表的长度 查找关键码为key的元素 成功返回其地址 否则返回NULL intd HNode q d Hash key 求当前元素的散列地址 q LhashTbl d 同义词链表的头指针 while q if q data key key break elseq q next returnq 5哈希表的删除 当在散列表上删除一个元素