数据结构 -Maple Related- 牟克典 数学科学学院信息科学系 2012秋季 1/16/2019

第六讲 数据和检索(1) 数据检索和字典 基于线性表实现字典和检索 散列的概念 散列表 有序表和二分检索 2012年12月12日 第六讲　数据和检索(1) 数据检索和字典 基于线性表实现字典和检索 有序表和二分检索 散列的概念 散列表 2012年12月12日 10:10-12:00 三教303 1/16/2019

数据存储、检索和字典 存储和检索是计算过程中最重要最基本的工作，也是各种计算 机应用和信息处理的基础。数据需要存储和使用，因此需要检 索 本讲研究的问题就是数据的存储和检索（查询），实际中的例 子： 电子字典，基本概念就是基于算法的数据检索 图书馆编目和目录系统，读者检索书籍资料 多项式乘法，做出一个因子乘积后要合并同类项，需要检索 本讲讨论的是基于关键码的数据存储和检索 关键码指数据项的某种（可能具有唯一性的）特征，可以是数据内 容的组成部分，也可以是专门为数据检索建立的标签 支持这种操作的数据结构，通常称为字典或查找表 1/16/2019

字典 字典就是实现存储和检索的结构。需要存储和检索的信息有许多 具体情况，因此要考虑各种不同的字典实现技术 字典的实现将用到前面讨论过的许多想法和结构。包括 各种线性结构、树性结构及其各种组合 涉及到在这些结构上操作的许多算法 组织方法很多，下面讨论顺序，散列，二叉树和其他树形结构等 这里的基本问题是空间利用率和操作效率 字典的最主要也是使用最频繁的操作是检索（search，也称查找） 检索效率是字典实现中最重要的考虑因素 由于规模不同，对效率方面的重视程度也可能不同 更一般的问题是需要根据某些线索找出相关数据，可能需要做更 复杂的匹配，或者“模糊”的匹配，基于内容的匹配。例如网络 上的检索。这些都是字典概念的发展 1/16/2019

字典 字典可以分为两类： 静态字典：建立后保持不变，只做检索，实现只需考虑检索效率 动态字典：内容经常动态变动的字典。基本操作除检索外还有插入和 删除，实现中还需要考虑插入删除操作的效率 动态字典的插入删除操作可能导致字典的结构变化。要支持长期使用， 还需要考虑字典在动态变化中能否保持良好的结构，能否保证良好的 检索效率？（字典性能不应该随操作的进行而逐渐恶化） 检索效率的评价标准是检索过程中关键码的平均比较次数，称为平均检索长度ASL（Average Search Length），定义为： 其中 ci 和 pi 分别为元素 i 的检索长度和概率。如果各元素检索概率相等， 就有 pi=1/n，ASL = 1/n ∑ ci。还可能需要考虑找不到的情况 1/16/2019

字典：抽象模型 设有关键码集合 和值（或称属性）集合 关联 (Association) 是二元组 字典：以关联 为元素的有穷集合 设有关键码集合 和值（或称属性）集合 字典：以关联 为元素的有穷集合 关键码到值的有穷函数： 所有字典的集合： 主要字典操作： 检索 插入元素 删除元素 1/16/2019

线性表表示 线性表可以保存信息，因此可以作为字典的实现基础 顺序表在 Maple可用 Array 表示，容量和长度。定义一个模块生成器： 关联在线性表里顺序排列，形成关联的序列 检索就是在线性表里查找关键码合适的元素，数据元素的插入删除都是普通的 线性表操作 顺序表在 Maple可用 Array 表示，容量和长度。定义一个模块生成器： ListDicGenerator := proc(nmax :: posint) module () export empty,init,size,volumn,insert,delete,search; local elems, num := 0, nvolumn := nmax; elems := Array(1..nmax); empty := () -> evalb(num = 0): init := proc() num := 0 end: size := () -> num: volumn := () -> nvolumn: ... ... end end: 1/16/2019

简单线性表和顺序检索 字典的元素用二元表 [key, datum] 表示。下面考虑操作的实现 如果字典里的元素没有任何关系，要检索只能顺序地一项项比较 遇到关键码相等的项就是找到了，返回对应的 datum 检索了所有元素没遇到要找的关键码就是没找到，返回特殊信息 检索操作的定义很简单： search := proc(key) local i; for i from 1 to num do if evalb(elems[i][1] = key) then return elems[i][2] fi od; false end: 1/16/2019

简单线性表和顺序检索 线性表实现的字典的性质： 优点：数据结构和算法简单，对任何关键码集合都可使用 插入的元素可以放在最后，O(1) 时间复杂性 删除元素时也需要先检索，找到后可以把最后一个元素拷贝过来 主要操作是检索（删除依赖于检索），分析其复杂性，考虑比较次数： 线性表实现的字典的性质： 优点：数据结构和算法简单，对任何关键码集合都可使用 缺点：平均检索长度大，表长度 n 很大时检索耗时太多 删除的效率也比较低，因此不太适合频繁变动的字典 在字典的动态变化中，各种操作的效率不变（因为已经是效率很低的操作了） 1/16/2019

有序线性表和二分检索 要想提高字典的操作效率，就需要更好地把字典元素组织好，使之具有可利用的规 律，就有可能利用它加快检索速度 有更复杂的内部结构的字典，可能支持更有效的检索 如果关键码取自一个有序集（关键码集合有某种序关系，例如整数和小于，字符串 和字典序），就可以将字典元素按关键码排列（从小到大或从大到小）。利用元素 排列顺序，可以采用二分法快速检索 二分法检索通过按比例缩小检索范围的方式，快速逼近要检索的数据。其基本过程 是（假设元素按关键码的升序排列）： 初始时，所考虑的范围是整个字典（顺序表） 取所考虑范围里位于中间位置的元素，比较该元素的关键码与检索关键码。如果它们相 等则检索结束；否则 如果检索关键码较大，把检索范围改为中间元素之后的一半；如果检索关键码较小，把 检索范围改为中间元素之前的一半 如果范围里已经无元素，则检索失败结束，否则回到 2 继续 1/16/2019

有序线性表和二分检索 # 二分检索算法 search := proc(key) local low, high, mid; low := 1; high := num; while low <= high do #范围内还有元素 mid := iquo(low + high, 2); if evalb(elems[mid][1] = key) then return elems[mid][2] fi; if evalb(elems[mid][1] > key) then high := mid - 1 #在低半区继续 else low := mid + 1 #在高半区继续 fi od; false end: 1/16/2019

有序线性表和二分检索 6 3 9 1 4 7 10 2 5 8 11 检索过程可用二叉树表示。树结点所标数字是数据的位置 性能分析示例： 以下面11个数的检索为例： 关键码： 5 13 19 21 37 56 64 75 80 88 92 位置： 1 2 3 4 5 6 7 8 9 10 11 用二分法检索：找到第6个数需比较1次，找到第3, 9个数需2次，找到第1, 4, 7, 10个数需3次，找到第2, 5, 8, 11个数需4次 6 3 9 1 4 7 10 2 5 8 11 检索过程可用二叉树表示。树结点所标数字是数据的位置 检索找到某结点的比较次数等于该结点的层数加1 检索结点的过程在从根结点到要检索的结点的路径上的各个位置做了比较 1/16/2019

有序线性表和二分检索 由此可见，检索不成功时，最大比较次数也是 log2n+1 这是基于检索中的判定操作形成的判定树的分析 6 3 9 检索成功时，所做比较次数不超过树的深度。n 结点判定树深度至多为 log2 n 。二分法检索成功时的比较次数最多为 log2n +1 检索不成功时的判定树如下。方框表示检索不成功情况（是扩充二叉树 的外部结点），例如图中 3-4 表示被检索关键码值在 3 和 4 两个位置 的关键码的值之间。检索到达方框就知道失败 由此可见，检索不成功时，最大比较次数也是 log2n+1 这是基于检索中的判定操作形成的判定树的分析 6 3 9 1 4 7 10 2 5 8 11 -1 3-4 6-7 9-10 1-2 4-5 5-6 7-8 8-9 10-11 11- 1/16/2019

有序线性表和二分检索 每次比较范围缩小一半，第 i 次 可能比较的元素个数如下表 1 1=20 2 2=21 k 2k-1 比较次数 可能比较的元素个数 1 1=20 2 2=21 ┇ ┇ k 2k-1 若元素个数 n 刚好为 20 + 21 +… + 2k-1 = 2k-1 则最大检索长度为 k；对一般 的 2k-1 < n ≤ 2k+1-1，最大检索 长度为 k+1 所以，n 元字典的二分法检索， 最大检索长度为 平均检索长度（设 n = 2j – 1，j 是搜索的“深度” ）： 1/16/2019

用有序线性表和链接表实现字典 有序线性表和二分法检索（排序顺序字典）： 考虑用单链表或双链表实现字典的情况： 优点：检索速度快，O(log n) 插入删除时需要维护元素顺序，O(n) 操作（检索插入或删除元素的 位置可以用二分法，O(log n)） 只能用于元素按关键码排序的字典，只适合顺序存储结构；不适合用 于实现大的动态字典 考虑用单链表或双链表实现字典的情况： 若元素任意排列方式：插入元素可插入在表头，O(1) 操作；检索和 删除需要顺序扫描检查，O(n) 操作 若元素按关键码升序或降序排列，插入要检索位置，O(n) 操作；检 索和删除需要顺序扫描检查，平均查半个表，O(n) 操作 实现情况很简单，不再深入讨论了 1/16/2019

字典和检索：问题 采用线性表的方式表示字典，常常不能满足实际的需要 实际需要存储和检索的数据集里的数据量越来越大，可能达到 GB 或者 TB，或者更大（大型信息系统，一个大型企业的业务数据很可能达到 TB 级）。要支持这种数据集里的检索，必须考虑其他组织结构 采用简单连续表或邻接表检索效率太低，不能满足存储和检索大规模的 数据集合的需要 采用排序连续表和二分检索，检索速度大大提高，但仍有两个大问题 不能很好支持数据的变化（数据插入和删除） 必须采用连续方式表示。如果数据集很大（例如几百 M 或者几 G 或更 大的数据集，这种实现方式本身就无法接受了 实际中人们考虑了另一些结构，主要分为两类： 基于散列（Hash）的思想开发的散列表（哈希表） 基于树形结构的各种数据存储和检索技术（可能达到对数时间） 1/16/2019

散列表（Hash Table，哈希表，杂凑表） 什么情况下检索元素的速度最快？ 如果关键码是数组下标，就可以直接找到元素！（只需常量时间） 一般说，关键码可能不是整数 即使是整数，也可能取值范围太大，不好直接作为数组下标 例如北大学生学号：8位数，取值范围 0～1亿（研究生 10 位数） 散列表背后的思想：把基于关键码的检索变为基于整数下标的访问 方法：找一个从关键码集合到选定整数范围的适当映射 h 存数据时，将其存入数组的第 h(key) 个元素 以 key 为关键码检索数据时，直接去检查数组的第 h(key) 个元素 散列函数，又称哈希（Hash）函数或杂凑函数，是一个映射，它把可 能的关键码映射到一段整数（数组下标，整数区间）。其类型是： 1/16/2019

散列技术（Hashing） 散列的思想是计算机领域中逐渐发展起来的一种极其重要的思想 一般而言，所谓散列，就是以某种精心设计的方式从一个很长的信息体 生成出一段较短（很短，通常采用固定长度）的信息串（整数或字符串， 最后都是二进制序列） 散列技术在计算机和信息领域很有价值，应用极广，可能用在各种数据 处理、存储、检索工作中。例如： 文件完整性检查（定义一个映射，把一个任意大的文件映射到一个数或 者一个不长的字符串） 软件安装时说的“检查文件的完整性”，就是做这件事 显然是一种概率性的检查，但出错的概率极低 互联网技术，到处都依靠散列函数 计算机安全领域中大量使用散列技术，例如各种安全协议 1/16/2019

key1 ≠ key2 但 h(key1) ＝ h(key2) 散列技术：设计和性质 将散列技术用于存储和检索，就得到了散列表。基本做法是： 用一个连续数组（线性表）作为基本存储区（也称散列表） 散列函数的值域应属于其存储区的地址（下标）范围 散列函数 h 作用于关键码，得到的值 h(key) 称为散列值 要实现散列表，就需要考虑合适的关键码映射，还需要考虑由 于使用了这种映射确定存储和检索位置带来的问题 对于散列表，通常都有 h 把大集合的元素都对应到小集合，它不可能是单射，必然会出现多个关键码对应到同一个位置的情况，即出现 key1 ≠ key2 但 h(key1) ＝ h(key2) 此时说出现冲突（碰撞），称 key1 和 key2 为同义词 冲突是必然会出现的情况，散列表实现必须考虑和解决冲突问题 1/16/2019

散列表 显然，对于规模确定的散列表，一般而言，表里的元素越多，出现冲突的可能性也就越大，人们提出“负载因子”作为一种有用的度量 负载因子  是考察散列表性质的一个重要参数。定义是： 散列表中实际结点数 基本区域能容纳的结点数  = 这样定义的负载因子总小于等于 1。其大小与冲突出现的概率密切相关：负载因子越大，出现冲突的可能性也越大 注意：增大存储空间（增加可能的存储位置）可以减小负载因子，也会减小出现冲突的概率 但负载因子小，空闲的空间比例就大。这里有权衡问题 人们在散列表的设计中提出了许多冲突处理技术。不同的处理方式形成的大不相同的散列表实现 1/16/2019

散列函数 现在考虑散列函数的设计问题 在关键码和位置区间确定的情况下，散列函数有许多选择（两个有限集 之间的函数），其选择可能影响出现冲突的概率（显然） 应尽可能把关键码映射到不同的值 关键码的散列值在地址区间分布比较均匀，可能减少冲突。实际中，还与实际 使用中不同关键码值出现的分布有关 计算比较简单 人们提出了许多设计散列函数的方法 一些方法依赖于对实际数据集的分析，实际中很难使用 另一些方法是通用的，基于对数据集的均匀分布假设 下面只介绍两种散列函数 除余法，用于整数关键码的散列 基数转换法，用于整数或字符串关键码的散列 1/16/2019

散列函数 设计散列函数的最基本想法是使得到的结果尽可能没有规律 除余法：关键码是整数。以关键码除以一个不大于散列表长度 m 的整数 p 得到的余数（或者余数加 1）作为散列地址 m 经常取 2 的某个幂值，此时 p 可以取小于 m 的最大素数。如果数组下标从 1 开始，可以用 key mod p + 1 例如，当 m 取 128，256，512，1024 时，p 可以分别取 127，251，503，1023 除余法使用最广，还常被用于将其他散列函数的结果归入所需区间 设计散列函数的最基本想法是使得到的结果尽可能没有规律 采用除余法法时，如果用偶数作为除数，就会出现偶数关键码得到偶数散列值，奇数关键码得到奇数散列值的情况 如果关键码集合数字位数较多，可考虑采用较大的除数，然后去掉最低位（或去掉最低的一个或几个二进制位），排除最低位的规律性。还可以考虑其他方法，目标是去掉规律性 1/16/2019

散列函数 基数转换法：针对整数关键码，取正整数 r，把关键码看作基数是 r 的数，将其转换为十进制（或二进制）数。通常 r 取一个素数 (335647)13 = 3 * 135 + 3 * 134 + 5 * 133 + 6 * 132 + 4 * 13 + 7 = (6758172)10 可以考虑用除余法或删除几位数字的方法将其归入所需范围 对非整数关键码，常用的是先设计一种方法把它转换到整数，而后再用 整数散列的方法。常在最后用除余法把关键码归结到所需范围 字符串也常作为关键码。常见方法是把一个字符看作一个整数（它的编 码），把一个字符串看作以某个整数为基数的“数” 常以 29 或 31 为基数，用基数转换法把字符串转换为整数 再用整数散列法（如除余法），把结果归入散列表的下标范围内 1/16/2019

设计散列表的考虑 采用散列表技术实现字典，检索时间包括 根据实际情况设计虑散列表时，需要考虑的因素通常包括： 计算散列函数的时间和实际检索时间 由此，散列函数的计算不应太复杂 根据实际情况设计虑散列表时，需要考虑的因素通常包括： 保存字典内容的数组的大小（根据实际需要确定） 关键码的类型和长度 关键码的分布情况（不同记录的检索频率） 散列函数的设计和散列函数的计算代价 人们已经积累了许多设计散列表和散列函数的经验 许多程序设计语言或语言的标准库提供了散列表功能。这种功能常称为 map，或者 table，或者 dictionary Maple 的实现中大量使用散列表，后面简单介绍 1/16/2019

散列表的设计和实现 下面逐一讨论散列表设计的各方面问题： 散列表的基本部分是个数组，应根据实际需要确定其大小 数组有连续的一段下标范围（例如从 1 到某个正整数） 散列表里存储的是字典元素（元素是关键码和值的关联） 需要根据关键码和其他因素的情况设计一个散列函数 h，其值域必须完 全落在合法的数组下标范围中 冲突是必然会出现的事件（大集合到小集合的全函数，必然会出现两个 元素的函数值相同的情况），设计散列表，必须同时设计一种冲突消解 方案，处理元素冲突问题 人们提出了一些冲突消解方法，主要分为 内消解方法（在基本存储区内解决元素冲突） 外消解方法（在基本存储区之外解决元素冲突） 1/16/2019

散列表：开地址法 通过散列函数为数据安排存储位置，但发现那里已经有元素，这就是 出现了冲突，必须处理 开地址法（内消解法）的基本想法：出现冲突时元素无法保存在散列 函数确定的位置，那么就设法在数组里另外为它安排一个位置 为此要设计一种系统化的位置安排方式（探查方式） 这里采用的方法是生成存储范围中的一个位置探查序列 Hi = (h(key) + di) mod m + 1 其中 m 为不超过表长的数，di 为一个增量序列 逐个试探位置 Hi，直至找到一个空闲位置将元素存入 增量序列有许多可能取法，例如 取 di = 0, 1, 2, 3, 4, …，称为线性探索 设计另一散列函数 h2，令 di = i * h2(key)，称为双散列探查 1/16/2019

散列表：开地址法 确定了探查序列后如果发现冲突，就根据探查序列进一步检索 插入元素时发现冲突（要保存元素的位置已被占），就按照探查序列逐个向下 检查，直至找到一个空位 检索是找到位置后还需要比较关键码。若关键码不对就按探查序列去检查下一 位置的元素，直至找到（成功）或确定找不到为止。为确定“找不到”，还需 确定一种方式表示“没有值” 例：设 key 为整数，取 h(key) = key mod 13 + 1。设有关键码集合 KEY = {18, 73, 10, 5, 68, 99, 22, 32, 46, 58, 25} h(key) = { 6, 9, 11, 6, 4, 9, 10, 7, 8, 7, 13}，用线性探 查 位置 关键码 1 6 2 3 4 5 13 8 7 9 12 11 10 58 25 68 18 5 32 73 99 10 22 46 线性探查很容易出现元素堆积的现象，就是在处理同义词时又引进了非同义词之间的冲突。其他探查法也可能出现这种情况 1/16/2019

散列表：开地址法 例，同样实例，采用双散列探查法 位置 关键码 1 6 2 3 4 5 13 8 7 9 12 11 10 99 58 25 KEY = {18, 73, 10, 5, 68, 99, 22, 32, 46, 58, 25} h1(key) = { 6, 9, 11, 6, 4, 9, 10, 7, 8, 7, 13} h1(key) = key mod 13 + 1；h2(key) = key mod 5 + 1 位置 关键码 1 6 2 3 4 5 13 8 7 9 12 11 10 99 58 25 68 18 5 46 73 22 10 32 开地址法散列表上的检索很像插入操作。对给定key值： 根据散列函数求出散列地址 若该位置无记录，则检索失败结束 否则比较元素关键码，若与 key 相等则检索成功结束 否则根据散列表设计的冲突处理方法找“下一地址”并回到步骤 2 1/16/2019

散列表：开地址法 无论采用哪种探查方法，随着元素增加、负载因子的值增大，出现冲突 的可能性（概率）也明显地增大了 采用开地址法的一个问题是元素删除。当要求删除一个元素时，如果找 到元素就将其直接删掉，可能破坏后序的检索操作 如果被删除元素位于同一散列值或不同散列值的检索链上，直接删除就 会导致检索链的破坏 解决办法：在被删除元素处放一个（与空位标记不同的）特殊标记。检 索操作将这个标记看作有元素，还将继续进行探查；而插入操作遇到这 一标记则将其看作空位 可以考虑在负载因子达到一定程度的情况下，扩大元素存储区 人们提出的一种方法是将存储区扩大一倍 而后将原存储的所有元素重新散列到新的存储区里 1/16/2019

散列表：溢出区 公共溢出区是一种在基本存储区之外消解冲突的方法，基本想法就是另 外设立一个溢出表，把所有关键码冲突的记录都填入溢出表 用一个线性表作为公共溢出区 如果插入元素时遇到冲突，就将元素放入公共溢出区里下一空位 检索元素时先通过散列函数找到对应位置 - 如果关键码匹配就返回 - 如果关键码不匹配，就转到公共溢出区中顺序检索 很容易看出 如果散列表的元素很多，溢出区就可能变得很大 随着元素增加，元素插入和检索的工作量都会趋于线性 对采用公共溢出区的散列表，负载因子也可能超过 1 1/16/2019

散列表：拉链法 如果不把元素放在散列表里面，而是通过散列表找到元素的引用，可以得 到许多可能的设计 这方面最简单的技术是“拉链法” 基本思想：元素存在基本数组之外，为每个关键码建立一个链接表，所有 关键字为同义词的记录存储在同一个链表中 所有元素可以统一处理（无论是否冲突） 允许任意的负载因子 最简单的方法是把新元素插在链接表头 如果要防止出现重复关键码，就需要检查整个链表 例：{18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25}， h(key)=key mod 13 算出的位置：{ 5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12} 把同一个散列值的元素收集到一起：{ { }, {{27}, {41}, {68}, { }, {05, 18}, {32}, { }, {99, 73}, { }, {10}, { }, {25, 51} } 1/16/2019

散列表：拉链法  27  41  18 5  32  73 99  10  51 25  K = {18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25} h(key) = key mod 13 + 1 拉链法散列表 1/16/2019

散列表 在实际应用中上述方法可以推广，同义词表可以采用顺序表或散列表，还 可以采用其他数据结构 下面考虑散列表的效率 人们有时把存放同义词的表称为“桶”，这种结构也称为“桶散列”。这种结构 可以用于存储大型字典，用于组织文件 下面考虑散列表的效率 采用内部消解时的一般情况 负载因子  ≤ 0.5 ~ 0.75 时，平均检索长度几乎为常数 采用桶散列，负载因子就是桶的平均大小（平均长度） 因此可以容忍任意大的负载因子 随着负载因子变大，检索时间趋于线性（桶长 ＝ 元素个数/桶数） 如果效率不能满足需要，可扩大散列桶的个数 这是明显的时间与空间交换。计算机科学中的一条基本原理 1/16/2019

Maple 里使用的散列表 Maple 系统里有直接使用散列表的数据结构 table 和 array 数据结构的内部实现都是基于散列表 注：Array 的实现不是基于散列表，而是下标访问的连续存储块 此外，在 Maple 系统实现中，散列表扮演了重要角色。Advanced Prog. Guide 的附录 A.3 专门讨论了这一问题。主要情况： Maple 里的许多关键功能大量采用了基于散列表的算法，这种设计是整个 Maple 的效率的基础。在化简和求值中都使用散列表，还有许多不那么重要的函数理也 用了散列表 过程可以有 remember 选项，要求将计算结果记录下来。这样就可以避免大量的 重复计算。这种记忆表也用散列表实现 Maple 核心的名字表也是一个散列表，所有全局名字（定义的过程名、变量名） 和它们的定义都保存在一个名字表里，计算中使用时，到这个表里查找 可以说，散列表是 Maple 实现的最基本的技术 1/16/2019

Maple 里使用的散列表 Maple 里的散列表采用了两种技术 基本散列表（Basic Hash Table），采用两层结构 Maple 还使用了一种 Dynamic Hash Table，用于支持更加大型和灵活变化的字典。 其实现细节没有给出，是结合了树形结构和散列技术的一种数据结构 Maple 里散列表的最重要使用是化简表，其中保存着一次工作期里生成的所有最简 表达式，这些表达式在系统里唯一存在 这样可以支持在成千上万的表达式里确定等价表达式 这里有一个计算出任意表达式的“签名”的技术，也就是把任意复杂的表达式映射到一个固 定长度的二进制串 1/16/2019

问题与讨论 1/16/2019