精编制作哈希表PPT课件

第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 所构造的哈希函数 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为地址 选用关键字的某几位组合成哈希地址 选用原则应当是 各种符号在该位上出现的频率大致相同 34705243491487348269634852703486305349805834796713473919 例 有一组 例如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 计算哈希函数所需时间 包括硬件指令的因素 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 二次探测法二次探测法对应的探查地址序列的计算公式为 Hi H k di modm其中di 12 12 22 22 j2 j2 j m 2 012345678910 若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 2 链地址法 优点 插入 删除方便 缺点 占用存储空间多 基本思想 将具有相同哈希地址的记录链成一个单链表 m个哈希地址就设m个单链表 然后用一个数组将m个单链表的表头指针存储起来 形成一个动态的结构 例 设 47 7 29 11 16 92 22 8 3 50 37 89 的哈希函数为 Hash key keymod11 用拉链法处理冲突 建表 有冲突的元素可以插在表尾 也可以插在表头 3 再哈希法Hi RHi key RHi均是不同的哈希函数 即在同义词产生地址冲突时计算另一个哈希函数地址 直到冲突不再发生 不易产生 聚集 但是增加了计算时间 4 建立一个公共溢出区 1 4哈希表的查找及其分析 散列表的目的主要是用于快速查找 在建表时采用何种散列函数及何种解决冲突的办法 在查找时 也采用同样的散列函数及解决冲突的办法 例 设有一组关键字 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其计算函数如下 H 19 19mod13 6 H 01 01mod13 1 H 23 23mod13 10 H 14 14mod13 1 冲突 H 14 1 1 mod19 2 H 55 55mod13 3 H 20 20mod13 7 H 84 84mod13 6 冲突 H 84 6 1 mod19 7 冲突 H 84 6 2 mod19 8 H 27 27mod13 1 冲突 H 27 1 1 mod19 2 冲突 H 27 1 2 mod19 3 冲突 H 27 1 3 mod19 4 19 19 01 23 14 55 20 84 27 68 11 10 77 01 23 14 55 20 84 27 哈希查找的性能分析哈希查找按理论分析 它的时间复杂度应为O 1 它的平均查找长度应为ASL 1 但实际上由于冲突的存在 它的平均查找长度将会比1大 下面将分析几种方法的平均查找长度 1 线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的 平均查找长度与表的大小m无关 只与所选取的哈希函数H及装填因子 的值和该处理方法有关 这时的成功的平均查找长度为 ASL 1 1 1 2 2 链地址法查找的性能分析由于链地址法查找就是在单链表上查找 查找单链表中第一个结点的次数为1 第二个结点次数为2 其余依次类推 平均查找长度 ASL 1 2 例 给定关键字序列 11 78 10 1 3 2 4 21 试分别用顺序查找 二分查找 二叉排序树查找 平衡二叉树查找 哈希查找 用线性探查法和拉链法 来实现查找 试画出它们的对应存储形式 顺序查找的顺序表 二分查找的判定树 二叉排序树查找的二叉排序树及平衡二叉树查找的平衡二叉树 两种哈希查找的哈希表 并求出每一种查找的成功平均查找长度 设哈希函数为 H k kmod11 哈希表表长m 11 顺序查找的顺序表 一维数组 由图可得 顺序查找的成功平均查找长度为ASL 1 2 3 4 5 6 7 8 8 4 5 二分查找的判定树 中序序列为从小到大排列的有序序列 由图可得 二分查找的成功平均查找长度为ASL 1 2 2 3 4 4 8 2 625 二叉排序树 关键字顺序已确定 该二叉排序树应唯一 如图 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 3 1 11 2 10 4 78 21 线性探查法解决冲突的哈希表如图所示 由图可得 线性探查法的成功平均查找长度为ASL 1 1 2 1 3 2 8 1 8 2 375 链地址法解决冲突的哈希表如图所示 由图可得 链地址法的成功平均查找长度为ASL 1 6 2 2 8 1 25 小结1 掌握查找的基本概念 2 熟练掌握静态查找表的查找算法思想并灵活应用 3 熟练掌握动态查找表的特点以及二叉排序树 平衡二叉树的各种操作思想4 了解B B 树的概念及插入和删除操作 5 熟练掌握哈希表的基本概念 哈希函数的构造方法和解决冲突的方法 并能计算平均查找长度