第九章 查找-2.ppt

哈希查找表 前述的查找方法建立在“比较”的基础上，查找的次数依赖于查找过程中进行比较的次数。 问题：能否不用比较就能直接计算出记录的存储地址，从而找到所要的结点？ ----采用散列（hash）方法。 散列表和查找 散列表--- 是根据设定的散列函数和相应解决冲突的方法将一组关键字映射到一个有限的地址集，并以关键字在地址集中的像作为记录到表中的存储位置，这种表叫做哈希表。 散列（又称杂凑、哈希）的基本思想： 以结点的键值k为自变量，通过一定的函数关系h计算出 对应的函数值h(k),把这个值解释为结点的存储地址 （散列地址），将结点存入该地址中去。 函数h---散列函数 h(k)---散列地址 基本区---分配给散列表的连续存储空间。 哈希查找表 哈希查找表 哈希查找表 选择哈希函数考虑因素： （1）计算哈希函数所需时间 (2)关键字的长度 （3）哈希表的长度 （4）关键字的分布情况 （5）记录的查找频率 冲突的解决办法 冲突： 初级冲突：不同关键字值的结点得到同一个散列地址。 若对于不同的键值k1和k2,且k1k2,但h(k1)=h(k2)，即具 有相同的散列地址，称为冲突。 二次聚集：同不同散列地址的结点争夺同一个单元。 结果：冲突加剧，最坏时可能达到 O（n）级代价。 同义词---发生冲突的两个或多个键值。 H( 17 ) = 6 H( 60 ) = 5 H( 29 ) = 7 H( 38 ) = 5 0 1 2 3 4 5 6 7 8 9 10 Hashing 表 17 60 29 38 38 1.开放定址法 假定采用的 hashing 函数为：H(key) = key MOD 11 假定 的关键字序列为：17、60、29、38 …… ；它们的散列过程 为： 处理冲突的方法 当散列 38 时发生冲突，同 60争夺第 5 个单元解决 办法： Hi=(H(key)+di) MOD m i=1,2、、、k(k=m-1) H(key)为哈希函数 M为哈希表表长 di为增量序列 （1）di=1，2，3…m-1 线性探测再散列 （2） 二次探测再散列 （3）di=伪随机数序列 伪随机探测再散列 hashing 函数 2.再 hashing 法： 出现冲突时，采用多个不同 hashing 函数计算散列地址，直到找到空单元为止。 冲突的解决办法 * 平衡二叉树 平衡因子（平衡度）： 结点的平衡度是结点的左子树的高度－右子树的高度。 平衡二叉树： 每个结点的平衡因子都为 ＋1、－1、0 的二叉树。 或者说每个结点的左右子树的高度最多差一的二叉树。 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 是平衡树 不是平衡树 14 5 3 9 28 63 53 60 50 17 18 30 +1 +2 -1 -1 0 0 0 0 0 +1 -1 平衡二叉树 平衡树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入数据为 2 的结点。 插入之后仍应保持平衡分类二叉树的性质不变。 平衡树 如何用最简单、最有效的办法保持平衡分类二叉树的性质不变？ 平衡二叉树 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 2 +1 +1 +2 原平衡度为 0 危机结点 解决方案： 不涉及到危机结点的父结点，即以危机结点为根的子树的高度应保持不变（左图为 3 ） 新结点插入后，找到第一个平衡度不为 0 的结点（如左图结点9）即可。新插入的结点和第一个平衡度不为 0 的结点（也可能是危机结点）之间的结点 在调整中，仅调整那些在平衡度变化的路径上的结点（如：3 5 9 ），其它结点不予调整。 仍应保持分类二叉树的性质不变。 平衡二叉树 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 2 +1 +1 +2 原平衡度为 0 危机结点 2 3 5 9 7 12 2 3 5 9 7 12 平衡二叉树 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 +1 -1 -1 -1 0 0 0 0 0 0 0 0 2 +1 +1 +2 原平衡度为 0 危机结点