第9章 查找48567

第9章查找 静态查找表动态查找表哈希表 查找 Search 的概念 所谓查找 就是在数据集合中寻找满足某种条件的数据对象 搜索的结果通常有两种可能 搜索成功 即找到满足条件的数据对象这时 作为结果 可报告该对象在结构中的位置 还可给出该对象中的具体信息 搜索不成功 或搜索失败 作为结果 应报告一些信息 如失败标志 位置等 通常称用于搜索的数据集合为查找表 它是由同一数据类型的对象 或记录 组成 在每个对象中有若干属性 其中有一个属性 其值可唯一地标识这个对象 称为关键码 使用基于关键码的搜索 搜索结果应是唯一的 但在实际应用时 搜索条件是多方面的 可以使用基于属性的搜索方法 但搜索结果可能不唯一 实施搜索时有两种不同的环境 静态环境 搜索结构在插入和删除等操作的前后不发生改变 静态搜索表动态环境 为保持较高的搜索效率 搜索结构在执行插入和删除等操作的前后将自动进行调整 结构可能发生变化 动态搜索表 查找算法的基本操作为 将记录的关键字和给定值进行比较 因此通常以 关键字和给定值进行过比较的记录个数的平均值 作为衡量查找算法好坏的依据平均查找长度 ASL 为确定记录在查找表中的位置 需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度 ASL 静态查找表 静态查找表 顺序表的查找有序表的查找索引顺序表的查找 1 顺序表的查找 顺序搜索 SequentialSearch 所谓顺序搜索 又称线性搜索 主要用于在线性结构中进行搜索 设若表中有CurrentSize个对象 则顺序搜索从表的先端开始 顺序用各对象的关键码与给定值x进行比较 直到找到与其值相等的对象 则搜索成功 给出该对象在表中的位置 若整个表都已检测完仍未找到关键码与x相等的对象 则搜索失败 给出失败信息 typedefstruct ElemType elem 存储空间基址intlength SSTable 不设监视哨方法 intseqSearch SSTableST KeyTypekey inti for i 1 i ST length i if ST i key key return i found return 0 Nofound 012345 length 查找方向 未用 intSearch Seq SSTableST KeyTypekey 算法9 1inti ST elem 0 key key 哨兵 for i ST length ST elem i key key i 从后往前找returni 找不到时 i为0 Search Seq 哨兵 的作用 免去查找过程中每一步都要检测整个表是否查找完毕 实践证明 在表长 1000时 效率提高50 012345 n X 查找方向 监视哨 哨兵 的作用 顺序搜索的平均搜索长度 设搜索第i个元素的概率为pi 搜索到第i个元素所需比较次数为ci 则搜索成功的平均搜索长度 在顺序搜索并设置 监视哨 情形 ci n i 1 i 1 2 n 因此 在等概率情形 pi 1 n i 1 2 n 在搜索不成功情形 ASLunsucc n 1 2 基于有序顺序表的顺序搜索算法 顺序搜索关键码为x的数据对象for inti 1 ix break return0 顺序搜索失败 返回失败信息 246810 012345 length 查找方向 未用 有序顺序表的顺序搜索 10 20 30 40 50 60 10 50 60 20 30 40 有序表的查找 折半查找查找过程 每次将待查记录所在区间缩小一半适用条件 采用顺序存储结构的有序表算法实现设表长为n low high和mid分别指向待查元素所在区间的上界 下界和中点 k为给定值初始时 令low 1 high n mid low high 2 让k与mid指向的记录比较若k r mid key 查找成功若kr mid key 则low mid 1重复上述操作 直至low high时 查找失败 intSearch Bin SSTableST KeyTypekey 算法9 2 在有序表ST中折半查找其关键字等于key的数据元素 若找到 则函数值为该元素在表中的位置 否则为0 intlow high mid low 1 high ST length 置区间初值while low high mid low high 2 if EQ key ST elem mid key returnmid 找到待查元素elseif LT key ST elem mid key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 找70 算法评价判定树 树中每个结点表示表中一个记录 结点中的值为该记录在表中的位置 通常称描述这个查找过程的二叉树为判定树 算法评价在折半查找中 有n个结点的判定树的深度为 log2n 1折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度 log2n 1折半查找的ASL 折半查找性能分析 ASLbs log2 n 1 1 搜索成功时检测指针停留在树中某个结点 搜索不成功时检测指针停留在某个外结点 失败结点 35 15 45 50 25 10 20 30 搜索22 搜索45 有序顺序表的折半搜索的判定树 10 20 30 40 50 60 10 50 30 20 40 60 ASLunsucc 2 1 3 6 7 20 7 ASLsucc 1 2 2 3 3 6 14 6 1 Fibonaqisearch斐波那契查找设n Fu 1 key与有序表中第Fu 1项进行比较 若相等则查找成功 若小于则在表中第Fu 1 1项前查找 若大于则在表中第Fu 1 1项后查找平均性能优于折半查找 最坏情况下的性能比折半查找差 2 interpolationsearch插值查找 有序表的其它查找方法 插值查找适用于关键字均匀分布的表结构 表长较大时 平均性能优于折半查找 2 interpolationsearch插值查找 插值查找适用于关键字均匀分布的表结构 表长较大时 平均性能优于折半查找 2 interpolationsearch插值查找 3 静态树表的查找 对于各记录查找概率不等时 使用折半查找判定树进行查找性能不一定是最优的 例如 有序表中含有5个记录 10 20 30 40 50 查找概率不同 分别为P1 0 1 P2 0 2 P3 0 1 P4 0 4 P5 0 2 如果按判定树进行折半查找 则查找成功时的平均查找长度ASL是 如果在查找时令给定值先和第4个记录的关键字进行比较 比较不相等时再继续在左子序列或右序列中进行折半查找 则查找成功时的平均查找长度ASL是 2 5 4 3 1 P1 0 1 P2 0 2 P3 0 1 P4 0 4 P5 0 2 静态最优查找树 PH 带权内路径长度 PH取最小值的二叉树为查找性能最佳的判定树 n为二叉树上结点的个数 有序表的长度 hi为第i个结点在二叉树上的层次树 结点的权值wi 其中pi为结点的查找概率 c为某个常量 称PH值取最小的二叉树为静态最优查找树 适用条件 分块有序表 分块有序指的是后一分块中所有记录的关键字均大于前一个分块中的最大关键字 3 分块查找 索引顺序表的查找 查找过程 将表分成几块 块内无序 块间有序 先确定待查记录所在块 再在块内查找算法实现用数组存放待查记录 每个数据元素至少含有关键字域建立索引表 每个索引表结点含有最大关键字域和指向本块第一个结点的指针 3 分块查找 索引顺序表的查找 索引顺序表方法评价 动态查找表 动态查找表 二叉排序树和平衡二叉树B 树和B 树 定义二叉搜索树或者是一棵空树 或者是具有下列性质的二叉树 每个结点都有一个作为搜索依据的关键码 key 所有结点的关键码互不相同 左子树 如果存在 上所有结点的关键码都小于根结点的关键码 右子树 如果存在 上所有结点的关键码都大于根结点的关键码 左子树和右子树也是二叉搜索树 二叉搜索 排序 树 BinarySearchTree 在二叉搜索树上进行搜索 是一个从根结点开始 沿某一个分支逐层向下进行比较判等的过程 它可以是一个递归的过程 二叉搜索树上的搜索 假设想要在二叉搜索树中搜索关键码为x的元素 搜索过程从根结点开始 如果根指针为NULL 则搜索不成功 否则用给定值x与根结点的关键码进行比较 如果给定值等于根结点的关键码 则搜索成功 如果给定值小于根结点的关键码 则继续递归搜索根结点的左子树 否则 递归搜索根结点的右子树 35 15 45 50 40 25 10 20 30 搜索45搜索成功 搜索28搜索失败 二叉搜索树的插入 35 15 45 50 40 25 10 20 30 28 每次结点的插入 都要从根结点出发搜索插入位置 然后把新结点作为叶结点插入 插入新结点28 为了向二叉搜索树中插入一个新元素 必须先检查这个元素是否在树中已经存在 在插入之前 先使用搜索算法在树中检查要插入元素有还是没有 搜索成功 树中已有这个元素 不再插入 搜索不成功 树中原来没有关键码等于给定值的结点 把新元素加到搜索操作停止的地方 同样3个数据 1 2 3 输入顺序不同 建立起来的二叉搜索树的形态也不同 这直接影响到二叉搜索树的搜索性能 如果输入序列选得不好 会建立起一棵单支树 使得二叉搜索树的高度达到最大 2 1 3 1 2 3 1 3 2 2 3 1 3 1 2 3 2 1 1 2 3 1 1 1 1 3 2 2 2 3 3 2 3 二叉排序树的查找分析 关键字序列不同构造的二叉排序树形态不同 序列a 45 24 53 12 37 93 序列b 12 24 37 45 53 93 假如查找概率相同 二叉排序树 最好的情况是二叉排序树的ASL和折半查找的判定树相同 log2n 平衡二叉树定义平衡二叉树又称AVL树 它或者是一棵空树 或者是具有下列性质的二叉树 它的左右子树均为平衡二叉树 且左右子树的深度之差的绝对值不超过1 定义二叉树上结点的平衡因子BF BalanceFactor 为该结点的左子树的深度减去右子树的深度 在平衡二叉树上所有结点平衡因子只可能为 1 0 1 平衡二叉树 对于平衡二叉树来说 它的深度和logn是同数量级的 因此我们希望任何初始序列构成的二叉排序树都是AVL树 平衡二叉树 不平衡二叉树 使二叉排序树成为平衡树 插入序列 13 24 37 90 53 013 最小不平衡子树 指离插入结点最近 且以平衡因子绝对值大于1的结点为根的子树 调整平衡的方法 在插入一个新结点后 需要从插入位置沿通向根的路径回溯 检查各结点左 右子树的高度差 如果在某一结点发现不平衡 停止回溯 从发生不平衡的结点起 沿刚才回溯的路径取直接下两层的结点 如果这三个结点处于一条直线上 则采用单旋转进行平衡化 如果这三个结点处于一条折线上 则采用双旋转进行平衡化 调整原则 既要保持二叉排序树的特性 又要平衡 设最小不平衡子树的根为 a 调整的规律可归纳为下列四种 单向右旋平衡处理 LL型调整单向左旋平衡处理 RR型调整双向旋转平衡处理 LR型调整双向旋转平衡处理 RL型调整 LL型调整操作示意图 B A B A 调整规则是 将A的左孩子B提升为新二叉树的根 原来的根A连同其右子树 向右下顺时针旋转成为B的右子树 B的原右子树 作为A的左子树 LL型调整操作示例 RR型调整操作示意图 A B A B 调整规则 将A的右孩子B提升为新二叉树的根 原来的根A连同其左子树向左下逆时针旋转成为B的左子树 B的原左子树作为A的右子树 RR型调整操作示例 LR型调整操作示意图 B C A B C A 调整规则 设C为A的左孩子的右孩子 将A的孙子结点C提升为新二叉树的根 原C的父结点B连同其左子树 向左下逆时针旋转成为新根C的左子树 原C的左子树 成为B的右子树 原根A连同其右子树 向右下顺时针旋转成为新根C的右子树 原C的右子树 成为A的左子树 LR型调整操作示例 RL型调整操作示意图 A C B A C B 调整规则 设C为A的右孩子的左孩子 将A的孙子结点C提升为新二叉树的根 原来C的父结点B连同其右子树 向右下顺时针旋转成为新根C的右子树 C的原右子树 成为B的左子树 原来的根A连同其左子树 向左下逆时针旋转成为新根C的左子树 原来C的左子树 成为A的右子树 RL型调整操作示例 无论哪种情况 在经过平衡旋转处理后 新子树的深度和插入新结点前的子树深度相同因此 当平衡的二叉排序树因插入结点失去平衡时 仅需对最小不平衡子树进行平衡旋转处理 例 输入关键码序列为 16 3 7 11 9 26 18 14 15 插入和调整过程如下 1 1 从发生不平衡的结点起 得到一棵子树 如果这子树上结点处于一条直线上 则采用单旋转进行平衡化 如果这子树上的结点处于一条折线上 则采用双旋转进行平衡化 双旋转分为先左后右和先右后左两类 右单旋转 左单旋转 左右双旋转 右左双旋转 AVL树的高度 设在新结点插入前AVL树的高度为h 结点个数为n 则插入一个新结点的时间是O h 对于AVL树来说 h多大 设Nh是高度为h的AVL树的最小结点数 根的一棵子树的高度为h 1 另一棵子树的高度为h 2 这两棵子树也是高度平衡的 因此有N0 0 空树 N1 1 仅有根结点 Nh Nh 1 Nh 2 1 h 0可以证明 对于h 0 有Nh Fh 2 1成立 平衡二叉数查找性能分析 练习 依次把结点 50 20 10 100 120 30 70 90 80 110 60 插入到初始状态为空的平衡二叉树中 使得在每次插入后保持该树仍然是平衡二叉树 依次画出每次插入后所形成的平衡二叉树 B 树的定义一棵m阶的B 树 或为空树 或是满足下列特性的m叉树 树中每个节点至多有m棵子树 若根结点不是叶子结点 则至少有两棵子树 除根之外的所有非终端结点至少有 m 2 棵子树 所有非终端 非叶子 结点中包含的信息为 n A0 K1 A1 K2 Kn An 其中Ki i 1 n 为关键码 且Ki Ki 1 i 1 n 1 即K1 K2 Kn Ai i 0 n 为指向子树根结点的指针 且Ai 1所指子树中所有结点的关键码均小于Ki i 1 2 n An所指子树中所有结点的关键码均大于Kn n m 2 1 n m 1 为关键码的个数 所有叶子结点都在同一层上 并且不带任何信息 9 2 2B 树和B 树 用于外存文件的索引 一棵6阶的B 树 1 3 5 B 树实现 B 树主要用于文件的索引结点类型可以如下说明 definem3typedefstructBTNode intkeyNum 关键字个数 structBTNode parent 指向父结点 KeyTypekey m 1 关键字向量 0单元未用 structBTNode ptr m 1 子树指针向量 Record recPtr m 1 指向文件中的记录号 BTNode BTree B 树的操作B 树的查找key首先在根结点的关键码集合中进行检索若key ki 则检索成功 否则 若keyki且key ki 1则key可能在Ai所指的子树内 存在某个i 顺着指针继续查找 重复上述过程 直到检索成功 或找到叶子节点 则查找失败 B 树的查性能分析在B 树是进行查找包含两种基本操作 在B 树中找结点在结点中找关键字由于B树通常存储在磁盘上 因此前一操作是在磁盘上进行的 而后一操作是在内存中进行的 即在磁盘上找到指针p所指结点后 先将结点中信息读入内存 然后查询 而在磁盘上进行操作比在内存中操作慢得多 因此在磁盘上进行查找的次数 即待查关键字所在结点在B树是的层次数 是决定B树查找效率的关键因素 考虑最坏的情况 含n个关键字的m阶B树的最大深度为log m 2 n 1 2 1 B 树树的插入深度为h 不计叶子结点 的m阶B 树 新结点一般插入到h层 首先检索到第h层 确定插入结点位置 若被插入结点中关键码个数小于m 1 则插入 若被插入结点中关键码个数等于m 1 则引起结点 分裂 可如下实现 分裂 假设 p结点中含有信息为 m p0 k1 p1 km pm 将 p分裂为 p和 p 两个结点 分别含有信息为 p m 2 1 p0 k1 p1 k m 2 1 p m 2 1 p m m 2 p m 2 k m 2 1 p m 2 1 km pm 把关键字k m 2 和指针 p 一起插入到 p的双亲结点中 插入460 一棵6阶的B树 375490 045112236 392400 560631670 040008 110050 212142135 297240237 388381378 471460435 396393 553502492 629626557 一棵6阶B树的插入示例插入460 经过2次分裂的结果 3 B 树的删除在深度为h的m阶B 树中删除一个关键码 首先检索到该关键码所在的结点 然后根据不同情况进行删除 2 若结点在第h层 且关键码数目大于 m 2 1 方法 则只需从该结点中删去该关键码ki 1 若结点不在第h层 假设所删除结点为非终端结点中的ki 则可取指针Ai中所指子树最小的关键字Y代替ki 然后在终端结点中删去Y 3 B 树的删除 3 若结点在第h层 且关键码数目等于 m 2 1 该结点左兄弟 或右兄弟 结点中的关键码数目大于 m 2 1 则需调整被删除关键码的结点 兄弟结点 以及父结点中的信息 方法 则需要将其兄弟节点中最小 或最大 的关键字上移至双亲节点中 而将双亲节点中小于 或大于 且紧靠该上移关键字的关键字移至被删除关键字的节点中 4 若结点在h层 且关键码数目及其相邻的兄弟结点中的关键码数目均等于 m 2 1 则需合并结点 假设该结点有右兄弟 且其右兄弟结点由双亲结点中的指针pi所指 则在删去关键码之后 它所在结点中剩余的关键码和指针 加上双亲结点中的关键码ki一起 合并到pi所指兄弟结点中 若没有右兄弟结点 则合并到左兄弟结点中 50 63 2035 2330 6690 56 42 37 30 一棵三阶B 树从a 中删除关键码66从b 中删除关键码42从c 中删除关键码35 35 50 63 2030 90 56 35 37 e 从 d 中删除关键码56 2330 56 e 从d 中删除关键码56 B 树是B 树的变形 是一种索引树 B 树的定义 一棵m阶的B 树 或为空树 或是满足下列条件的m叉树 树中每个结点至多有m棵子树 除根之外的所有分支结点至少有 m 2 棵子树 若根结点不是叶子结点 则至少有两棵子树 有n棵子树的结点有n个关键码 叶结点中存放数据文件中记录的关键码及指向该记录的指针 或存放数据文件分块后每块的最大关键码及指向该块的指针 B 树 一棵m阶的B 树和B树的差异在于 有n棵子树的结点中含有n个关键码 所有的叶子结点中包含了全部关键码的信息 及指向含这些关键码记录的指针 且叶子结点的本身依关键码的大小从小到大顺序链接 所有的非终端结点可以看成是索引部分 结点中仅含有其子树 根结点 中最大 或最小 关键码 5096 1550 627896 7178 848996 5662 20264350 3815 sq root 作业 请阅读书本中有关B B 树的内容并结合相关的课外资料 撰写一篇有关B B 树的读书报告 哈希表 以上两节讨论的表示查找表的各种结构的共同特点 记录在表中的位置和它的关键字之间不存在一个确定的关系 哈希表是什么 查找的过程为给定值依次和关键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数 理想的情况是能直接找到需要的记录 因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f 使每个关键字和结构中一个唯一的存储位置相对应 若以下标为000 999的顺序表表示 例如 为每年招收的1000名新生建立一张查找表 其关键字为学号 其值的范围为xx000 xx999 前两位为年份 则查找过程可以简单进行 取给定值 学号 的后三位 不需要经过比较便可直接从顺序表中找到待查关键字 9 4哈希查找基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系 这样 不经过比较 一次存取就能得到所查元素的查找方法定义哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关系叫 哈希函数是一种映象 是从关键字空间到存储地址空间的一种映象哈希函数可写成 addr ai H ki ai是表中的一个元素addr ai 是ai的存储地址ki是ai的关键字 以编号作关键字 构造哈希函数 H key keyH 1 1H 2 2 以地区作关键字 取地区名称第一个拼音字母的序号作哈希函数 H Beijing 2H Shanghai 19H Shenyang 19 从例子可见 哈希函数只是一种映象 所以哈希函数的设定很灵活 只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突 key1 key2 但H key1 H key2 的现象叫 同义词 具有相同函数值的两个关键字 叫该哈希函数的 哈希函数通常是一种压缩映象 所以冲突不可避免 只能尽量减少 同时 冲突发生后 应该有处理冲突的方法 哈希表 应用哈希函数和处理冲突的方法 将一组关键字确定在表中的地址 并将记录放入此地址 这样构成的表叫 哈希查找 又叫散列查找 利用哈希函数进行查找的过程叫 1 哈希函数是一个映象 即 将关键字的集合映射到某个地址集合上 它的设置很灵活 只要这个地址集合的大小不超出允许范围即可 从例子可见 从例子可见 2 由于哈希函数是一个压缩映象 因此 在一般情况下 很容易产生 冲突 现象 即 key1 key2 而H key1 H key2 3 很难找到一个不产生冲突的哈希函数 一般情况下 只能选择恰当的哈希函数 使冲突尽可能少地产生 因此 在构造这种特殊的 查找表 时 除了需要选择一个 好 尽可能少产生冲突 的哈希函数之外 还需要找到一种 处理冲突 的方法 哈希表的定义 根据设定的哈希函数H key 和所选中的处理冲突的方法 将一组关键字映象到一个有限的 地址连续的地址集 区间 上 并以关键字在地址集中的 象 作为相应记录在表中的存储位置 如此构造所得的查找表称之为 哈希表 构造哈希函数的方法 对数字的关键字可有下列构造方法 若是非数字关键字 则需先对其进行数字化处理 1 直接定址法 3 平方取中法 5 除留余数法 4 折叠法 6 随机数法 2 数字分析法 哈希函数的构造方法直接定址法构造 取关键字或关键字的某个线性函数作哈希地址 即H key key或H key a key b特点直接定址法所得地址集合与关键字集合大小相等 不会发生冲突实际中能用这种哈希函数的情况很少 数字分析法构造 对关键字进行分析 取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大 且可能出现的关键字事先知道的情况 例有80个记录 关键字为8位十进制数 哈希地址为2位十进制数 分析 只取8 只取1 只取3 4 只取2 7 5 数字分布近乎随机所以 取 任意两位或两位与另两位的叠加作哈希地址 平方取中法构造 取关键字平方后中间几位作哈希地址一个数平方后的中间几位数和数的每一位都相关 由此令到随机分布的关键字得到的哈希地址也是随机的适于不知道全部关键字情况 折叠法构造 将关键字分割成位数相同的几部分 然后取这几部分的叠加和 舍去进位 做哈希地址种类移位叠加 将分割后的几部分低位对齐相加间界叠加 从一端沿分割界来回折送 然后对齐相加适于关键字位数很多 且每一位上数字分布大致均匀情况 例关键字为 0442205864 哈希地址位数为4 除留余数法构造 取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址 即H key keyMODp p m特点简单 常用 可与上述几种方法结合使用p的选取很重要 p选的不好 容易产生同义词一般情况下 可以选p为质数或不包含小于20的质因子的合数 随机数法构造 取关键字的随机函数值作哈希地址 即H key random key 适于关键字长度不等的情况 选取哈希函数 考虑以下因素 计算哈希函数所需时间关键字长度哈希表长度 哈希地址范围 关键字分布情况记录的查找频率 实际造表时 采用何种构造哈希函数的方法取决于建表的关键字集合的情况 包括关键字的范围和形态 总的原则是使产生冲突的可能性降到尽可能地小 处理冲突的方法开放定址法方法 当冲突发生时 形成一个探查序列 沿此序列逐个地址探查 直到找到一个空位置 开放的地址 将发生冲突的记录放到该地址中 即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 伪随机数序列 例表长为13的哈希表中已填有关键字为17 60 29的记录 H key keyMOD11 现有第4个记录 其关键字为38 按三种处理冲突的方法 将它填入表中 0123456789101112 601729 1 H 38 38MOD11 5冲突H1 5 1 MOD13 6冲突H2 5 2 MOD13 7冲突H3 5 3 MOD13 8不冲突 38 2 H 38 38MOD11 5冲突H1 5 1 MOD13 6冲突H2 5 1 MOD13 4不冲突 38 3 H 38 38MOD11 5冲突设伪随机数序列为11 则 H1 5 11 MOD13 3不冲突 38 再哈希法方法 构造若干个哈希函数 当发生冲突时 计算下一个哈希地址 即 Hi Rhi key i 1 2 k其中 Rhi 不同的哈希函数特点 计算时间增加链地址法方法 将所有关键字为同义词的记录存储在一个单链表中 并用一维数组存放头指针 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key keyMOD13 用链地址法处理冲突 哈希查找过程及分析哈希查找过程 给定关键字k 计算哈希地址i H K 若r i NULL则查找不成功若r i key k则查找成功否则 求下一个地址Hi 直到r i NULL 查找不成功 或r i key k 查找成功 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key keyMOD13 处理冲突的方法是线性探测再散列 哈希表a elem 0 15 查找K 8484mod13 6a elem 6 84H1 6 1 mod16 7a elem 7 84H2 6 2 mod16 8a elem 8 84 查找K 3838mod13 12a elem 12 38H1 12 1 mod16 13a elem 13 NULL 哈希查找算法实现用线性探测再散列法处理冲突实现查找过程 同前删除 只能作标记 不能真正删除插入 遇到空位置或有删除标记的位置就可以插入算法描述 用外链表处理冲突算法 哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用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 MOD1