精编制作哈希表PPT课件
33页1、第1章Hashing 哈希表 1 1什么是哈希表1 2哈希函数的构造方法1 3处理冲突的方法1 4哈希表的查找及其分析 1 1什么是哈希表 哈希表技术的主要目标是提高查找效率 1 哈希函数 根据关键字直接计算出元素所在位置的函数 例 设哈希函数为 H K K 3 1 则构造关键字序列为1 2 5 9 11 13 16 21 27的散列表 哈希表 为 2 冲突两个不同的关键字具有相同的存储位置 3 哈希表根据设定的哈希函数H key 和处理冲突的方法将一组关键字映象到一个有限的连续的地址集 区间 上 并以关键字在地址集中的 象 作为记录在表中的存储位置 这种表便称为哈希表 这一映象过程称为哈希造表或散列 所得存储位置称为哈希地址或散列地址 在哈希存储中 若发生冲突 则必须采取特殊的方法来解决冲突问题 才能使哈希查找能顺利进行 虽然冲突不可避免 但发生冲突的可能性却与三个方面因素有关 1 装填因子 装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值 即 n m 1 越小 发生冲突的可能性越小 反之 发生冲突的可能性就越大 但是 太小又会造成大量存贮空间的浪费 因此必须兼顾存储空间
2、和冲突两个方面 2 所构造的哈希函数 3 解决冲突的方法 构造好的哈希函数 使冲突尽可能的少 设计有效的解决冲突的方法 1 2哈希函数的构造方法 例 关键码集合为 100 300 500 700 800 900 选取哈希函数为Hash key key 100 则存储结构 哈希表 如下 1 直接定址法取关键字或关键字的某个线性函数值为散列地址 即 K K或H K a K b 其中a b为常数 优点 以关键码key的某个线性函数值为哈希地址 不会产生冲突 缺点 要占用连续地址空间 空间效率低 2 除后余数法取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数 即H K Kmodp p m 经验得知 一般可选p为质数或不包含小于20的质因素的合数 3 平方取中法取关键字平方后的中间几位为哈希函数 因为中间几位与数据的每一位都相关 例 2589的平方值为6702921 可以取中间的029为地址 选用关键字的某几位组合成哈希地址 选用原则应当是 各种符号在该位上出现的频率大致相同 3470524349148734826963485270348630534980583479671347391
3、9 例 有一组 例如80个 关键码 其样式如下 讨论 第1 2位均是 3和4 第3位也只有 7 8 9 因此 这几位不能用 余下四位分布较均匀 可作为哈希地址选用 位号 若哈希地址取两位 因元素仅80个 则可取这四位中的任意两位组合成哈希地址 也可以取其中两位与其它两位叠加求和后 取低两位作哈希地址 4 数字分析法 5 折叠法是将关键字按要求的长度分成位数相等的几段 最后一段如不够长可以短些 然后把各段重叠在一起相加并去掉进位 以所得的和作为地址 适用于 每一位上各符号出现概率大致相同的情况 移位法 将各部分的最后一位对齐相加 间界叠加法 从一端向另一端沿分割界来回折叠后 最后一位对齐相加 例 元素42751896 移位法 427 518 96 1041间界叠加法 42751896 724 518 69 1311 6 随机数法选择一个随机函数 取关键字的随机函数值为它的哈希地址 即H key random key 其中random为随机函数 通常 当关键字长度不等时采用此法构造哈希函数较恰当 实际工作中需视不同情况采用不同的哈希函数 通常考虑的因素 1 计算哈希函数所需时间 包括硬件指
4、令的因素 2 关键字的长度 3 哈希表的大小 4 关键字的分布情况 5 记录的查找频率 1 3处理冲突的方法1 开放地址法开放地址就是表中尚未被占用的地址 当新插入的记录所选地址已被占用时 即转而寻找其它尚开放的地址 1 线性探测法设散列函数H K Kmodm m为表长 若发生冲突 则沿着一个探查序列逐个探查 那么 第i次计算冲突的散列地址为 Hi H K di modm di 1 2 m 1 例关键码集为 47 7 29 11 16 92 22 8 3 设 哈希表表长为m 11 哈希函数为Hash key keymod11 拟用线性探测法处理冲突 建哈希表 012345678910 29 22 8 3 线性探测法的优点 只要哈希表未被填满 保证能找到一个空地址单元存放有冲突的元素 线性探测法的缺点 可能使第i个哈希地址的同义词存入第i 1个哈希地址 这样本应存入第i 1个哈希地址的元素变成了第i 2个哈希地址的同义词 因此 可能出现很多元素在相邻的哈希地址上 堆积 起来 大大降低了查找效率 可采用二次探测法或伪随机探测法 以改善 堆积 问题 1 开放地址法 2 二次探测法二次探测法对
《精编制作哈希表PPT课件》由会员ahu****ng1分享,可在线阅读,更多相关《精编制作哈希表PPT课件》请在金锄头文库上搜索。
独立基础施工方案[53页]
熙和大唐太阳山风电施工合同范本[60页]
生命工程备忘录[59页]
电力水泥钢铁化工企业名单[94页]
珠海市政工程竣工档案验收整理指南(试行上)[50页]
珠海市政工程竣工档案验收整理指南(试行下)[54页]
合理用药宣传手册(共64页doc)
单体药店制度兴佳艺(共78页doc)
医疗质量持续改进记录本(共73页doc)
医疗器械电路维修的基础知识和维修思路(共100页doc)
医院管理知识练习题(共154页doc)
医学思维导图(药理学)全套完整打印版(共65页doc)
制药用水系统验证(共51页doc)
制药企业全套检验记录(共96页doc)
值得终生珍藏的经过验证有特效的药方(共62页doc)
医药代表销售经验(共128页doc)
医药市场营销重点整理考纲(上海中医药大学自学考版)(共51页doc)
中药034(共70页doc)
向阳制药改扩建可行报告(共69页doc)
化学药品使用安全手册(1)(共95页doc)
2023-09-09 110页
2023-09-09 107页
2023-03-07 70页
2023-03-07 178页
2022-07-14 64页
2022-07-14 95页
2022-07-14 52页
2022-07-14 56页
2022-07-13 43页
2022-07-13 44页