CHAP009_查找

1 第九章查找 2 表中一行为一条记录 即一个数据元素 数据项 组合项 主关键字 次关键字 3 查找的基本概念 数据项具有独立含义的标识单位 是数据不可分割的最小单位 如 学号 姓名 也称为字段或项 组合项由若干项组合构成 表中 出生日期 就是组合项 它由 年 月 日 三项组成 关键字关键字是数据元素 记录 中某个项或组合项的值 用它可以标识一个数据元素 记录 1 主关键字 能唯一标识一个记录的关键字 如 学号 2 次关键字 不能唯一标识一个记录的关键字 如 姓名 4 查找表是由具有同一类型的记录组成的集合 分为静态查找表和动态查找表两类 1 静态查找表 仅对查找表进行查找操作 而不能改变的表 2 动态查找表 除可进行查找操作外 还可进行向表中插入 或删除记录的表 查找给定一个值K 在查找表中进行搜索 寻找关键字值等于K的记录 如果找到则输出该记录 否则输出查找不成功的信息 也称为检索 查找的基本概念 5 对查找表经常进行的操作 1 查询某个 特定的 数据元素是否在查找表中 2 检索某个 特定的 数据元素的各种属性 3 在查找表中插入一个数据元素 4 从查找表中删去某个数据元素 6 查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL AverageSearchLength 为确定记录在表中的位置 需进行的关键字比较次数的期望值叫查找算法的 查找的基本概念 其中 n是表中记录的个数 Pi是查找第i个记录的查找概率 通常我们认为每个记录的查找概率相等 即Pi 1 n Ci是找到第i个记录时所经历的比较次数 7 如何进行查找 查找的方法取决于查找表的结构 8 9 1静态查找表 9 2动态查找树表 9 3哈希表 9 9 1静态查找表 10 数据对象D 数据关系R D是具有相同特性的数据元素的集合 每个数据元素含有类型相同的关键字 可唯一标识数据元素 数据元素同属一个集合 ADTStaticSearchTable 11 Create Destroy Search ST key Traverse ST Visit 基本操作P ADTStaticSearchTable 12 构造一个含n个数据元素的静态查找表ST Create 操作结果 13 销毁表ST Destroy 初始条件 操作结果 静态查找表ST存在 14 若ST中存在其关键字等于key的数据元素 则函数值为该元素的值或在表中的位置 否则为 空 Search ST key 初始条件 操作结果 静态查找表ST存在 key为和查找表中元素的关键字类型相同的给定值 15 按某种次序对ST的每个元素调用函数Visit 一次且仅一次 一旦Visit 失败 则操作失败 Traverse ST Visit 初始条件 操作结果 静态查找表ST存在 Visit是对元素操作的应用函数 16 typedefstruct 数据元素存储空间基址 建表时 按实际长度分配 0号单元留空intlength 表的长度 SSTable 假设静态查找表的顺序存储结构为 ElemType elem 17 数据元素类型的定义为 typedefstruct keyTypekey 关键字域 其它属性域 ElemType TElemType 18 一 顺序查找表 二 有序查找表 三 静态查找树表 四 索引顺序表 19 以顺序表或线性链表表示静态查找表 一 顺序查找表 20 1 顺序查找查找过程 从表的一端开始逐个进行记录的关键字和给定值的比较 直到找到关键字等于K的记录或到达表的另一端 可以采用从前向后查 也可采用从后向前查的方法 21 ST elem 回顾顺序表的查找过程 假设给定值e 64 要求ST elem k e 问 k k k 22 intlocation SqListL ElemType 23 1 顺序表查找算法描述 64 监视哨 比较次数 5 比较次数 查找第n个元素 1查找第n 1个元素 2 查找第1个元素 n查找第i个元素 n i 1查找失败 n 1 24 监视哨 returni 4 intSearch Seq SSTableST KeyTypekey ST elem 0 key key for i ST length ST elem i key key i returni 使用了监视哨 在查找过程中 不用每一步都去判断是否查找结束 找到 返回元素在线性表中的存储位置 未找到 返回0 25 intSearch Seq SSTableST KeyTypekey 在顺序表ST中顺序查找其关键字等于 key的数据元素 若找到 则函数值为 该元素在表中的位置 否则为0 ST elem 0 key key 哨兵 for i ST length ST elem i key key i 从后往前找returni 找不到时 i为0 顺序查找 26 在等概率查找的情况下 顺序表查找的平均查找长度为 对顺序表而言 Ci n i 1 ASL nP1 n 1 P2 2Pn 1 Pn Ci为找到该记录时的比较次数 27 顺序表查找 特点 在平均情况下 大约要与表中一半以上元素进行比较 效率较低 平均查找长度较大 在下面两种情况下只能采取顺序查找 a 线性表为无序表 元素排列是无序的 b 即使是有序线性表 但采用的是链式存储结构 28 上述顺序查找表的查找算法简单 但平均查找长度较大 特别不适用于表长较大的查找表 二 有序查找表 若以有序表表示静态查找表 则查找过程可以基于 折半 进行 29 2折半查找查找过程 每次将待查记录所在区间缩小一半适用条件 采用顺序存储结构的有序表算法实现设表长为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时 查找失败 30 折半查找算法描述 31 折半查找 32 从折半查找过程看 以表的中点为比较对象 并以中点将表分割为两个子表 对定位到的子表继续这种操作 所以对表中每个数据元素的查找过程可用二叉树来描述 称这个描述查找过程的二叉树为判定树 33 折半查找的c语言算法程序 intSearch Bin SSTableST intn intkey intlow high mid low 1 high n while low high mid low high 2 if ST mid key key return mid 查找成功 elseif key ST mid key high mid 1 在前半区间继续查找elselow mid 1 在后半区间继续查找 return 0 查找不成功 34 算法评价判定树 描述查找过程的二叉树叫 有n个结点的判定树的深度为 log2n 1折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度折半查找的ASL 折半查找 时间复杂度T n O log2n 35 ST elem ST length 例如 key 64的查找过程如下 low high mid low mid high mid low指示查找区间的下界high指示查找区间的上界mid low high 2 36 intSearch Bin SSTableST KeyTypekey 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 37 先看一个具体的情况 假设 n 11 分析折半查找的平均查找长度 6 3 9 1 4 2 5 7 8 10 11 判定树 1 2 2 3 3 3 3 4 4 4 4 38 假设n 2h 1并且查找概率相等则在n 50时 可得近似结果 一般情况下 表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同 索引顺序表 39 关键字 ABCDEPi 0 20 30 050 30 15Ci 23123 三 静态查找树表 在不等概率查找的情况下 折半查找不是有序表最好的查找方法 例如 此时ASL 2 0 2 3 0 3 1 0 05 2 0 3 3 0 15 2 4 若改变Ci的值21323 则ASL 2 0 2 1 0 3 3 0 05 2 0 3 3 0 15 1 9 40 使达最小的判定树称为最优二叉树 定义 41 为计算方便 令wi pi选择二叉树的根结点 使达最小 介绍一种次优二叉树的构造方法 为便于计算 引入累计权值和并设wl 1 0和swl 1 0 则推导可得 42 0 2 3 8 11 15 18 23 例如 l h 21 18 12 4 3 10 18 h 9 6 0 8 E C 2 1 A h 5 3 l h G 3 0 1 3 43 E C G A B D F 所得次优二叉树如下所示 查找比较 总次数 3 2 4 1 2 5 3 3 1 4 3 3 2 5 52 查找比较 总次数 3 2 2 1 3 5 1 3 3 4 2 3 3 5 59 和折半查找相比较 D B A C F E G 44 StatusSecondOptimal BiTree 生成结点 构造次优二叉树的算法 CONTINUE 45 if i low T lchild NULL 左子树空elseSecondOptimal T lchild R sw low i 1 构造左子树if i high T rchild NULL 右子树空elseSecondOptimal T rchild R sw i 1 high 构造右子树returnOK SecondOptimal 46 次优查找树采用二叉链表的存储结构 StatusCreateSOSTre SOSTree 47 四 索引顺序表 分块查找 将表分成几块 块内无序 块间有序 先确定待查记录所在块 再在块内查找建立索引表 每个索引表结点含有最大关键字域和指向本块第一个结点的指针 48 3分块查找 索引顺序查找 查找过程 将表分成几块 块内无序 块间有序 先确定待查记录所在块 再在块内查找适用条件 分块有序表算法实现用数组存放待查记录 每个数据元素至少含有关键字域建立索引表 每个索引表结点含有最大关键字域和指向本块第一个结点的指针算法描述 49 查找38 分块查找 块内最大关键字 块起始地址 50 分块查找方法评价 b n s 当s取n1 2时 ASLbs最小 为n1 2 1 51 52 53 分块查找方法评价 b n s 54 55 9 2动态查找树表 56 ADTDynamicSearchTable 抽象数据类型动态查找表的定义如下 数据对象D 数据关系R 数据元素同属一个集合 D是具有相同特性的数据元素的集合 每个数据元素含有类型相同的关键字 可唯一标识数据元素 57 InitDSTable DT 基本操作P DestroyDSTable DT SearchDSTable DT key InsertDSTable DeleteDSTable TraverseDSTable DT Visit ADTDynamicSearchTable 58 操作结果 构造一个空的动态查找表DT InitDSTable 59 销毁动态查找表DT DestroyDSTable 初始条件 操作结果 动态查找表DT存在 60 若DT中存在其关键字等于key的数据元素 则函数值为该元素的值或在表中的位置 否则为 空 SearchDSTable DT key 初始条件 操作结果 动态查找表DT存在 key为和关键字类型相同的给定值 61 动态查找表DT存在 e为待插入的数据元素 InsertDSTable 初始条件 操作结果 若DT中不存在其关键字等于e key的数据元素 则插入e到DT 62 动态查找表DT存在 key为和关键字类型相同的给定值 DeleteDSTable 初始条件 操作结果 若DT中存在其关键字等于key的数据元素 则删除之 63 动态查找表DT存在 Visit是对结点操作的应用函数 TraverseDSTable DT Visit 初始条件 操作结果 按某种次序对DT的每个结点调用函数Visit 一次且至多一次 一旦Visit 失败 则操作失败 64 一 二叉排序树 二叉查找树 二 二叉平衡树 三 B 树 四 B 树 五 键树 65 一 二叉排序树 二叉查找树 1 定义 2 查找算法 3 插入算法 4 删除算法 5 查找性能的分析 66 1 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 1 定义 二叉排序树或者是一棵空树 或者是具有如下特性的二叉树 3 它的左 右子树也都分别是二叉排序树 2 若它的右子树不空 则右子树上所有结点的值均大于根结点的值 67 50 30 80 20 90 10 85 40 35 25 23 88 例如 是二叉排序树 66 不 68 通常 取二叉链表作为二叉排序树的存储结构 typedefstructBiTNode 结点结构structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree TElemTypedata 69 2 二叉排序树的查找算法 1 若给定值等于根结点的关键字 则查找成功 2 若给定值小于根结点的关键字 则继续在左子树上进行查找 3 若给定值大于根结点的关键字 则继续在右子树上进行查找 否则 若二叉排序树为空 则查找不成功 70 50 30 80 20 90 85 40 35 88 32 例如 二叉排序树 查找关键字 50 50 50 35 50 30 40 35 50 90 50 80 90 95 71 从上述查找过程可见 在查找过程中 生成了一条查找路径 从根结点出发 沿着左分支或右分支逐层向下直至关键字等于给定值的结点 或者 从根结点出发 沿着左分支或右分支逐层向下直至指针指向空树为止 查找成功 查找不成功 72 算法描述如下 BiTreeSearchBST BiTreeT KeyTypekey 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素 若查找成功 则返回指向该数据元素结点的指针 查找不成功 返回空指针 if T EQ key T data key elseifLT key T data key else returnT 查找结束 returnSearchBST T lchild key 左子树中查找 returnSearchBST T rchild key 右子树中查找 73 或者用参数返回指针 StatusSearchBST BiTreeT KeyTypekey BiTree否则表明查找不成功 返回空指针p if T elseif EQ key T data key elseif LT key T data key else p NULL returnFALSE 查找不成功 p T returnTRUE 查找成功 SearchBST T lchild key p 在左子树中继续查找 SearchBST T rchild key p 在右子树中继续查找 74 30 20 10 40 35 25 23 T 设key 48 T T 22 p T T T T T p 75 根据动态查找表的定义 插入 操作在查找不成功时才进行 3 二叉排序树的插入算法 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 76 10 18 3 8 12 2 7 3 10 10 18 3 8 12 2 7 3 77 StatusInsertBST BiTree 78 s BiTree malloc sizeof BiTNode 为新结点分配空间s data e s lchild s rchild NULL if p T s 插入s为新的根结点 elseif LT e key p data key p lchild s 插入 s为 p的左孩子elsep rchild s 插入 s为 p的右孩子 returnTRUE 插入成功 79 1 被删除的结点是叶子 2 被删除的结点只有左子树或者只有右子树 3 被删除的结点既有左子树 也有右子树 4 二叉排序树的删除算法 可分三种情况讨论 和插入相反 删除在查找成功之后进行 并且要求在删除二叉排序树上某个结点之后 仍然保持二叉排序树的特性 80 50 30 80 20 90 85 40 35 88 32 1 被删除的结点是叶子结点 例如 被删关键字 20 88 其双亲结点中相应指针域的值改为 空 81 50 30 80 20 90 85 40 35 88 32 2 被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 指向被删除结点的左子树或右子树 被删关键字 40 80 82 50 30 80 20 90 85 40 35 88 32 3 被删除的结点既有左子树 也有右子树 40 40 以其前驱替代之 然后再删除该前驱结点 被删结点 前驱结点 被删关键字 50 83 StatusDeleteBST BiTree 不存在关键字等于key的数据元素else 算法描述如下 84 if EQ key T data key 找到关键字等于key的数据元素elseif LT key T data key else Delete T returnTRUE DeleteBST T lchild key 继续在左子树中进行查找 DeleteBST T rchild key 继续在右子树中进行查找 85 voidDelete BiTree p 从二叉排序树中删除结点p 并重接它的左子树或右子树if p rchild elseif p lchild else 其中删除操作过程如下所描述 86 右子树为空树则只需重接它的左子树 q p p p lchild free q p p 87 左子树为空树只需重接它的右子树 q p p p rchild free q p p 88 q p s p lchild while s rchild q s s s rchild s指向被删结点的前驱 左右子树均不空 p data s data if q p q rchild s lchild elseq lchild s lchild 重接 q的左子树free s p q s 89 5 查找性能的分析 对于每一棵特定的二叉排序树 均可按照平均查找长度的定义来求它的ASL值显然 由值相同的n个关键字 构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同 甚至可能差别很大 90 由关键字序列3 1 2 5 4构造而得的二叉排序树 由关键字序列1 2 3 4 5构造而得的二叉排序树 例如 2 1 3 4 5 3 5 4 1 2 ASL 1 2 3 4 5 5 3 ASL 1 2 3 2 3 5 2 2 91 下面讨论平均情况 不失一般性 假设长度为n的序列中有k个关键字小于第一个关键字 则必有n k 1个关键字大于第一个关键字 由它构造的二叉排序树 n k 1 k 的平均查找长度是n和k的函数 P n k 0 k n 1 92 假设n个关键字可能出现的n 种排列的可能性相同 则含n个关键字的二叉排序树的平均查找长度 在等概率查找的情况下 93 94 由此 可类似于解差分方程 此递归方程有解 95 二 二叉平衡树 何谓 二叉平衡树 二叉平衡树的查找性能分析 如何构造 二叉平衡树 96 二叉平衡树是二叉查找树的另一种形式 其特点为 树中每个结点的左 右子树深度之差的绝对值不大于1 例如 5 4 8 2 5 4 8 2 1 是平衡树 不是平衡树 97 构造二叉平衡 查找 树的方法是 在插入过程中 采用平衡旋转技术 例如 依次插入的关键字为5 4 2 8 6 9 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转一次 先向右旋转再向左旋转 98 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字9 99 在平衡树上进行查找的过程和二叉排序树相同 因此 查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度 平衡树的查找性能分析 问 含n个关键字的二叉平衡树可能达到的最大深度是多少 100 因此 在二叉平衡树上进行查找时 查找过程中和给定值进行比较的关键字的个数和log n 相当 含有n个结点的二叉平衡树能达到的最大深度hn log 5 n 1 2 101 哈希函数可写成 addr ai H ki ai是表中的一个元素addr ai 是ai的存储地址ki是ai的关键字 哈希表 应用哈希函数 由记录的关键字确定记录在表中的地址 并将记录放入此地址 这样构成的表叫 哈希查找 又叫散列查找 利用哈希函数进行查找的过程叫 哈希查找基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系 这样 不经过比较 一次存取就能得到所查元素的查找方法 定义哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关系叫 哈希函数是一种映象 是从关键字空间到存储地址空间的一种映象 102 以编号作关键字 构造哈希函数 H key keyH 1 1H 2 2 以地区别作关键字 取地区名称第一个拼音字母的序号作哈希函数 H Beijing 2H Shanghai 19H Shenyang 19 从上例子可见 哈希函数只是一种映象 所以哈希函数的设定很灵活 只要使任何关键字的哈希函数值都落在表长允许的范围之内即可冲突 key1 key2 但H key1 H key2 的现象叫 同义词 具有相同函数值的两个关键字 叫该哈希函数的 哈希函数通常是一种压缩映象 所以冲突不可避免 只能尽量减少 同时 冲突发生后 应该有处理冲突的方法 103 有关问题 哈希查找是对给定的关键字按哈希函数直接求得记录位置的 不需进行比较关键字 为提高查找效率 哈希表的空间m要比记录个数n大 定义 n m为装填系数 有时也叫装填因子 实际应用中一般取 0 65 0 85 为求得哈希地址 有时须对关键字进行算术或逻辑运算 若关键字为非数值型 可先转化为数值 称为关键字的内部码 而且求得的哈希地址的值域必须在哈希表长的范围内 哈希查找 104 哈希方法需解决的两个问题 1 构造好的哈希函数 所选函数尽量简单 以便提高转换速度 所选函数对关键字计算的地址应在哈希地址集中大致均匀分布 以减少空间浪费 2 制定解决冲突的方案 哈希查找 105 哈希函数的构造方法选取哈希函数 考虑以下因素 计算哈希函数所需时间关键字长度哈希表长度 哈希地址范围 关键字分布情况记录的查找频率 106 哈希函数的构造方法直接定址法构造 取关键字或关键字的某个线性函数作哈希地址 即H key key或H key a key b特点直接定址法所得地址集合与关键字集合大小相等 不会发生冲突实际中能用这种哈希函数的情况很少 例 关键字集合为 100 300 500 700 800 900 选取哈希函数为Hash key key 100 则存放如下 107 哈希函数的构造方法平方取中法构造 取关键字平方后中间几位作哈希地址适于不知道全部关键字情况 例如有一组关键字 0100 1100 1200 1160 2060 2061 2163 2261 2262 设存储空间为1000 将关键字平方后再取第2 3 4位构成哈希地址为 010 210 440 345 243 247 678 112 116 108 哈希函数的构造方法数字分析法构造 对关键字进行分析 取关键字的若干位或其组合作哈希地址适于关键字位数比哈希地址位数大 且可能出现的关键字事先知道的情况 例有80个记录 关键字为8位十进制数 哈希地址为2位十进制数 分析 只取8 只取1 只取3 4 只取2 7 5 数字分布近乎随机所以 取 任意两位或两位与另两位的叠加作哈希地址 109 哈希函数的构造方法折叠法构造 将关键字分割成位数相同的几部分 然后取这几部分的叠加和 舍去进位 做哈希地址种类移位叠加 将分割后的几部分低位对齐相加间界叠加 从一端沿分割界来回折送 然后对齐相加适于关键字位数很多 且每一位上数字分布大致均匀情况 例关键字为 0442205864 哈希地址位数为4 110 哈希函数的构造方法除留余数法构造 取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址 即H key keyMODp p m特点简单 常用 可与上述几种方法结合使用p的选取很重要 p选的不好 容易产生同义词 p一般选取小于m的最大素数 随机数法构造 取关键字的随机函数值作哈希地址 即H key random key 适于关键字长度不等的情况 111 处理冲突的方法开放定址法 在哈希表中找空位置 方法 当冲突发生时 形成一个探查序列 沿此序列逐个地址探查 直到找到一个空位置 开放的地址 将发生冲突的记录放到该地址中 即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 伪随机数序列双哈希函数探测法 di i ReHash key 112 例表长为11的哈希表中已填有关键字为17 60 29的记录 H key keyMOD11 现有第4个记录 其关键字为38 按三种处理冲突的方法 将它填入表中 1 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 2 MOD11 7冲突H3 5 3 MOD11 8不冲突 38 2 H 38 38MOD11 5冲突H1 5 1 MOD11 6冲突H2 5 1 MOD11 4不冲突 38 3 H 38 38MOD11 5冲突设伪随机数序列为9 则 H1 5 9 MOD11 3不冲突 38 处理冲突的方法 开放定址法 113 处理冲突的方法 开放定址法双哈希函数探测法方法 Hi Hash key i ReHash key modm i 1 2 m 1 其中 Hash key ReHash key 是两个哈希函数 m为哈希表长度先用第一个函数Hash key 对关键字计算哈希地址 一旦产生地址冲突 再用第二个函数ReHash key 确定移动的步长因子 最后 通过步长因子序列由探测函数寻找空的哈希地址 比如 Hash key a时产生地址冲突 就计算ReHash key b 则探测的地址序列为 H1 a b modmH2 a 2b modm Hm 1 a m 1 b modm特点 计算时间增加 114 链地址法方法 将所有关键字为同义词的记录存储在一个单链表中 并用一维数组存放头指针 处理冲突的方法 115 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key keyMOD13 用链地址法处理冲突 链地址法处理冲突 116 建立一个公共溢出区设哈希函数产生的哈希地址集为 0 m 1 则分配两个表 一个基本表ElemTypebase tbl m 每个单元只能存放一个元素 一个溢出表ElemTypeover tbl k 只要关键字对应的哈希地址在基本表上产生冲突 则所有这样的元素一律存入该表中 查找时 对给定值kx通过哈希函数计算出哈希地址i 先与基本表的base tbl i 单元比较 若相等 查找成功 否则 再到溢出表中进行查找 处理冲突的方法 117 哈希查找过程及分析哈希查找过程 118 哈希查找分析哈希查找过程仍是一个给定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程 给定值与关键字进行比较的的次数取决于 哈希函数处理冲突的方法哈希表的填满因子 表中填入的记录数 哈希表长度 119 哈希查找分析性能分析1 ASL 总比较次数 记录个数 采用不同的解决冲突方法 平均查找长度也可能不同 2 与线性查找 对分查找相比 ASL较小 3 平均查找长度是装填系数 的函数 适当选择 的值是很关键的 120 例已知一组关键字 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 MOD13 4冲突 H2 3 2 MOD13 5 H 79 1冲突 H1 1 1 MOD13 2冲突 H2 1 2 MOD13 3冲突 H3 1 3 MOD13 4冲突 H4 1 4 MOD13 5冲突 H5 1 5 MOD13 6冲突 H6 1 6 MOD13 7冲突 H7 1 7 MOD13 8冲突 H8 1 8 MOD13 9 ASL 1 6 2 3 3 4 9 12 2 5 14 1 68 27 55 19 20 84 79 23 11 10 H 19 6 H 14 1 H 23 10 H 1 1冲突 H1 1 1 MOD13 2 H 68 3 H 20 7 H 84 6冲突 H1 6 1 MOD13 7冲突 H2 6 2 MOD13 8 H 27 1冲突 H1 1 1 MOD13 2冲突 H2 1 2 MOD13 3冲突 H3 1 3 MOD13 4 H 11 11 H 10 10冲突 H1 10 1 MOD13 11冲突 H2 10 2 MOD13 12 121 2 用链地址法处理冲突 ASL 1 6 2 4 3 4 12 1 75 关键字 19 14 23 1 68 20 84 27 55 11 10 79 122 一 哈希表是什么 二 哈希函数的构造方法 三 处理冲突的方法 四 哈希表的查找 9 3哈希表 123 以上两节讨论 一 哈希表是什么 查找的过程为给定值依次和关键字集合中各个关键字进行比较 查找的效率取决于和给定值进行比较的关键字个数 用这类方法表示的查找表 其平均查找长度都不为零 124 只有一个办法 预先知道所查关键字在表中的位置 对于频繁使用的查找表 希望ASL 0 即 要求 记录在表中位置和其关键字之间存在一种确定的关系 125 若以下标为000 999的顺序表表示之 例如 为每年招收的1000名新生建立一张查找表 其关键字为学号 其值的范围为xx000 xx999 前两位为年份 则查找过程可以简单进行 取给定值 学号 的后三位 不需要经过比较便可直接从顺序表中找到待查关键字 126 上例在关键字与记录在表中的存储位置之间建立了一个函数关系 以f key 作为关键字为key的记录在表中的位置 通常称这个函数f key 为哈希函数 127 Zhao Qian Sun Li Wu Chen Han Ye Dei 例如 对于如下9个关键字 设哈希函数f key Ord 第一个字母 Ord A 1 2 Chen Zhao Qian Sun Li Wu Han Ye Dei 问题 若添加关键字Zhou 怎么办 能否找到另一个哈希函数 128 1 哈希函数是一个映象 即 将关键字的集合映射到某个地址集合上 它的设置很灵活 只要这个地址集合的大小不超出允许范围即可 从这个例子可见 2 在一般情况下 很容易产生 冲突 现象 即 key1 key2 而f key1 f key2 129 3 很难找到一个不产生冲突的哈希函数 一般情况下 只能选择恰当的哈希函数 使冲突尽可能少地产生 因此 在构造这种特殊的 查找表 时 除了需要选择一个 好 尽可能少产生冲突 的哈希函数之外 还需要找到一种 处理冲突 的方法 130 哈希表的定义 根据设定的哈希函数H key 和所选中的处理冲突的方法 将一组关键字映象到一个有限的 地址连续的地址集 区间 上 并以关键字在地址集中的 象 作为相应记录在表中的存储位置 如此构造所得的查找表称之为 哈希表 131 二 构造哈希函数的方法 对数字的关键字可有下列构造方法 若是非数字关键字 则需先对其进行数字化处理 1 直接定址法 3 平方取中法 5 除留余数法 4 折叠法 6 随机数法 2 数字分析法 132 哈希函数为关键字的线性函数H key key或者H key a key b 1 直接定址法 此法仅适合于 地址集合的大小 关键字集合的大小 133 此方法仅适合于 能预先估计出全体关键字的每一位上各种数字出现的频度 2 数字分析法 假设关键字集合中的每个关键字都是由s位数字组成 u1 u2 us 分析关键字集中的全体 并从中提取分布均匀的若干位或它们的组合作为地址 134 以关键字的平方值的中间几位作为存储地址 求 关键字的平方值 的目的是 扩大差别 同时平方值的中间各位又能受到整个关键字中各位的影响 3 平方取中法 此方法适合于 关键字中的每一位都有某