数据结构-哈希表ppt课件

哈希表 什么是哈希表 哈希函数的构造方法 处理冲突的方法 哈希表的查找 哈希表的查找分析 小结和作业 课堂练习 A 0 A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 例1 有一批考试成绩 统计各分数段的人数 对成绩Grade 执行 A grade 10 什么是哈希表 例2 Ord Char asc char asc a 1 什么是哈希表 将1000个学生的信息存放在数组A 0 A 999 中 例3 为每年招收的1000名新生建立一张查找表 其关键字为学号 其值的范围为xx000 xx999 前两位为年份 什么是哈希表 number substring 学号 3 3 建立查找表 给定关键字key 计算f key 数组下标 查找表 使用数组存放n个关键字 数组的下标0 n 1 什么是哈希表 查找时 给定关键字key 计算f key 数组下标 建立查找表 给定grade 计算f grade 数组下标 例4 统计学生成绩各分数段的人数 什么是哈希表 查找时 给定grade 计算f grade 数组下标 Hash函数 f grade grade 10 什么是哈希表 Zhao Qian Sun Li Wu Chen Han Ye Dei 例5 对于如下9个关键字 设哈希函数f key Ord 第一个字母 Ord A 1 2 什么是哈希表 Chen Zhao Qian Sun Li Wu Han Ye Dei 序号 问题 若添加关键字Zhou 怎么办 什么是哈希表 由此可见 1 哈希 Hash 函数是一个映象 即 将关键字的集合映射到某个地址集合上 它的设置很灵活 只要这个地址集合的大小不超出允许范围即可 2 对不同的关键字可能得到同一哈希地址 即 key1 key2 而f key1 f key2 因此 很容易产生 冲突 现象 什么是哈希表 3 很难找到一个不产生冲突的哈希函数 一般情况下 只能选择恰当的哈希函数 使冲突尽可能少地产生 因此 在构造这种特殊的 查找表 时 除了需要选择一个 好 尽可能少产生冲突 的哈希函数之外 还需要找到一种 处理冲突 的方法 哈希表的定义 根据设定的哈希函数H key 和所选中的处理冲突的方法 将一组关键字映象到一个有限的 地址连续的地址集 区间 上 并以关键字在地址集中的 象 作为相应记录在表中的存储位置 如此构造所得的查找表称之为 哈希表 这一过程称为哈希造表或者散列 所得的存储位置成为哈希地址或者散列地址 哈希函数的构造方法 对数字的关键字可有下列构造方法 若是非数字关键字 则需先对其进行数字化处理 1 直接定址法 3 平方取中法 5 除留余数法 4 折叠法 6 随机数法 2 数字分析法 哈希函数为关键字的线性函数H key key或者H key a key b 1 直接定址法 哈希函数的构造方法 哈希函数的构造方法 2 数字分析法 假设关键字集合中的每个关键字都是由s位数字组成 u1 u2 us 分析关键字集中的全体 并从中提取分布均匀的若干位或它们的组合作为地址 此方法仅适合于 能预先估计出全体关键字的每一位上各种数字出现的频度 哈希函数的构造方法 有80个记录 关键字为8位十进制数 哈希地址为2位十进制数 分析 只取8 只取1 只取3 4 只取2 7 5 数字分布近乎随机所以 取 任意两位或两位与另两位的叠加作哈希地址 哈希函数的构造方法 以关键字的平方值的中间几位作为存储地址 求 关键字的平方值 的目的是 扩大差别 同时平方值的中间各位又能受到整个关键字中各位的影响 3 平方取中法 此方法适合于 关键字中的每一位都有某些数字重复出现频度很高的现象 哈希函数的构造方法 4 折叠法 将关键字分割成若干部分 然后取它们的叠加和为哈希地址 有两种叠加处理的方法 移位叠加和间界叠加 此方法适合于 关键字的数字位数特别多 而且关键字在每一位上的数字分布大致均匀的情况 哈希函数的构造方法 例关键字为 0442205864 哈希地址位数为4 5864 4220 04 10088 H key 0088 移位叠加 5864 0224 04 6092 H key 6092 间界叠加 4 折叠法 哈希函数的构造方法 5 除留余数法 设定哈希函数为 H key keyMODp其中 p m 表长 并且p应为不大于m的素数或是不含20以下的质因子 哈希函数的构造方法 给定一组关键字为 12 39 18 24 33 21若取p 9 则它们对应的哈希函数值将为 3 3 0 6 6 3 为什么要对p加限制 可见 若p中含质因子3 则所有含质因子3的关键字均映射到 3的倍数 的地址上 从而增加了 冲突 的可能 哈希函数的构造方法 6 随机数法 设定哈希函数为 H key Random key 其中Random为随机函数 此方法通常用于对长度不等的关键字构造哈希函数 哈希函数的构造方法 实际构造哈希表时1 采用哪种构造哈希函数的方法取决于建表的关键字集合的情况 包括关键字的范围和形态 2 总的原则是使产生冲突的可能性尽可能的小 3 如果哈希造表过程中产生冲突 应当如何处理这些冲突呢 处理冲突的方法 冲突 由关键字得到的哈希地址为j 0 j n 1 的位置上已存有记录 处理冲突 为产生冲突的地址寻找下一个空的哈希地址 1 开放定址法 2 再哈希法 3 链地址法 处理冲突方法 4 建立一个公共溢出区 处理冲突的方法 1 开放定址法 为产生冲突的地址H key 求得一个地址序列 H0 H1 H2 Hs1 s m 1其中 H0 H key Hi H key di MODmi 1 2 sm为哈希表表长 处理冲突的方法 1 线性探测再散列法 2 二次探测再散列法 3 随机探测再散列法 增量di的三种取法 处理冲突的方法 1 开放定址法 对增量di的三种取法 1 线性探测再散列di c i最简单的情况c 1即di 1 2 3 m 1 处理冲突的方法 例如 关键字集合 19 01 23 14 55 68 11 82 36 设定哈希函数H key keyMOD11 表长 11 采用线性探测再散列法来构造哈希表 19 19 01 01 23 23 23 14 14 55 55 68 68 68 11 82 11 36 11 82 36 112136251 处理冲突的方法 1 开放定址法 对增量di有三种取法 2 平方 二次 探测再散列di 12 12 22 22 处理冲突的方法 例如 关键字集合 19 01 23 14 55 68 11 82 36 19 19 01 01 23 23 23 14 14 55 55 68 68 68 11 82 11 36 11 82 36 36 设定哈希函数H key keyMOD11 表长 11 采用二次探测再散列法来构造哈希表 112121413 处理冲突的方法 1 开放定址法 对增量di有三种取法 3 随机探测再散列di是一组随机数列或者di i H2 key 又称双散列函数探测 处理冲突的方法 即 产生的Hi均不相同 且所产生的m 1个Hi值能覆盖哈希表中所有地址 则要求 注意 增量di应具有 完备性 随机探测时的m和di没有公因子 平方探测时的表长m必为形如4j 3的素数 如 7 11 19 23 等 处理冲突的方法 H2 key 是另设定的一个哈希函数 它的函数值应和m互为素数 若m为素数 则H2 key 可以是1至m 1之间的任意数 若m为2的幂次 则H2 key 应是1至m 1之间的任意奇数 处理冲突的方法 例如 当m 11时 可设H2 key 3key MOD10 1 19 01 23 14 55 68 11 82 36 111121122 处理冲突的方法 2 再哈希法 Hi RHi key i 1 2 3 k RHi均是不同的哈希函数 在同义词产生地址冲突时计算另一个哈希函数地址 直到冲突不再发生 缺点 增加了计算时间 处理冲突的方法 3 链地址法 所有关键字为同义词的记录存储在同一线性链表中 定义指针型向量ChainChainHash m 凡是哈希地址为i的记录都插入到头指针为ChainHash i 的链表中 处理冲突的方法 例如 关键字集合 19 01 23 14 55 68 11 82 36 采用链地址法来构造哈希表 哈希函数为H key keyMOD7 19 01 23 14 55 68 11 82 36 ASL 6 1 2 2 3 1 9 13 9 处理冲突的方法 4 建立一个公共溢出区 哈希函数的值域 0 m 1 向量HashTable 0 m 1 为基本表 每个分量存放一个记录向量OverTable 0 v 为溢出表对于关键字和基本表HashTable中关键字为同义词的记录 只要发生冲突 都填入溢出表 哈希表的查找算法 查找过程和造表过程一致 假设采用开放定址处理冲突 则查找过程为 1 对于给定值K 计算哈希地址i H K 2 若r i NULL则查找不成功 3 若r i key K则查找成功 4 否则 求下一地址Hi 直至r Hi NULL 查找不成功 或r Hi key K 查找成功 为止 哈希表的查找算法 inthashsize 997 typedefstruct ElemType elem intcount 当前数据元素个数intsizeindex 为当前容量 HashTable defineSUCCESS1 defineUNSUCCESS0 defineDUPLICATE 1 开放定址哈希表的存储结构 哈希表的查找算法 StatusSearchHash HashTableH KeyTypeK int p int c 在开放定址哈希表H中查找关键码为K的记录 SearchHash p Hash K 求得哈希地址 while H elem p key NULLKEY 求得下一探查地址p if EQ K H elem p key returnSUCCESS 查找成功 返回待查数据元素位置p elsereturnUNSUCCESS 查找不成功 哈希表的维护算法 StatusInsertHash HashTable H Elemtypee InsertHash c 0 if SearchHash H e key p c SUCCESS returnDUPLICATE 表中已有与e有相同关键字的元素 elseif c hashsize H sizeindex 2 冲突次数c未达到上限 阀值c可调 H elem p e H count returnOK else RecreateHashTable H returnUNSUCCESS 重建哈希表 哈希表的查找分析 从查找过程得知 1 由于冲突的产生 哈希表的查找过程仍然是一个给定值和关键字进行比较的过程 2 哈希表查找的平均查找长度实际上并不等于零 哈希表的查找分析 1 选用的哈希函数 2 选用的处理冲突的方法 3 哈希表饱和的程度 装载因子 n m值的大小 n 记录数 m 表的长度 决定哈希表查找的ASL的因素 哈希表的查找分析 一般情况下 可以认为选用的哈希函数是 均匀 的 则在讨论ASL时 可以不考虑它的因素 因此 哈希表的ASL是处理冲突方法和装载因子的函数 例如 前述例子 线性探测处理冲突时 ASL 链地址法处理冲突时 ASL 22 9 13 9 哈希表的查找分析 线性探测再散列 可以证明 查找成功时有下列结果 随机探测再散列 链地址法 哈希表的查找分析 从以上结果可见 哈希表的平均查找长度是 的函数 而不是n的函数 这说明 用哈希表构造查找表时 可