北京大学：《数据结构与算法》课程教学资源（实验班讲义）第九章 检索

数据结构与算法4第九章检索 第九章检索 令基本概念 任课教员:张铭 9.1线性表的检索 http://db.pku.edu.cn/mzhang/ds 令92集合的检索 zhang@db.pku.edu.cn 北京大学信息科学与技术学院 令93散列表的检索 网络与信息系统研究所 9.4总结 ⊙版权所有,转载或翻印必究 张铭 叔省。斩就即究 基本概念 基本概念(续) 检索:在一组记录集合中找到关键码 预排序 值等于给定值的某个 或者找到 关键码值符合特定条件的某些记录的 排序算法本身比较费时 过程 ■只是预处理(在检索之前已经完成) ■建立索引 检索的效率非常重要 检索时充分利用辅助索引信息 牺牲一定的空间 尤其对于大数据量 从而提高检索效率 需要对数据进行特殊的存储处理 气斯有 京大富息美 张铭 基本概念(续) 平均检索长度(AsL) 散列技术 关键码的比较:检索运算的主要操作 把数据组织到一个表中 均检索长度( Average Search Length) 根据关健码的值来确定表中每个记录的位置 ∷靈被衡法关的的你较次数 缺点: ·一般也不允许出现重复关键码 ASL= PC 散列方法不适合于基于磁盘的应用程 序时,我们可以选择B树方法 P为检索第个元素的概率 c为找到第个元素所需的关键码值与 给定值的比较次数 真大_息单 张铭 回

1 数据结构与算法 第九章 检索 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 第九章 检索 „ 基本概念 „ 9.1 线性表的检索 „ 9.2 集合的检索 „ 9.3 散列表的检索 „ 9.4 总结 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 基本概念 „ 检索：在一组记录集合中找到关键码 值等于给定值的某个记录，或者找到 关键码值符合特定条件的某些记录的 过程 „ 检索的效率非常重要 „ 尤其对于大数据量 „ 需要对数据进行特殊的存储处理 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 基本概念（续） „ 预排序 „ 排序算法本身比较费时 „ 只是预处理（在检索之前已经完成） „ 建立索引 „ 检索时充分利用辅助索引信息 „ 牺牲一定的空间 „ 从而提高检索效率 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 基本概念（续） „ 散列技术 „ 把数据组织到一个表中 „ 根据关键码的值来确定表中每个记录的位置 „ 缺点： „ 不适合进行范围查询 „ 一般也不允许出现重复关键码 „ 当散列方法不适合于基于磁盘的应用程 序时，我们可以选择B树方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 平均检索长度（ASL） „ 关键码的比较：检索运算的主要操作 „ 平均检索长度(Average Search Length) „ 检索过程中对关键码的平均比较次数 „ 衡量检索算法优劣的时间标准 1 n i i i A SL P C = = ∑ Pi 为检索第i个元素的概率 Ci 为找到第i个元素所需的关键码值与 给定值的比较次数

平均检索长度的例子 检索算法评估的几个问题 ■假设线性表为(a,bc)检索a、 衡量一个检索算法还需要考虑 b、c的概率分别为04、01、05 算法所需的存储量 顺序检索算法的平均检索长度为 n算法的复杂性 04×1+01×2+05×3=2.1 即平均需要21次给定值与表中关键 码值的比较才能找到待查元素 攻大_息单 有,命叠 张铭 叔省。斩就即究 9.1基于线性表的检索 9.1.1顺序检索 1.1顺序检索 ■针对线性表里的所有记录,逐个进 令9.1.2二分检索 行关键码和给定值的比较。 若某个记录的关键码和给定值比较相 9.1.3分块检索 等,则检索成功; 否则检索失败(找遍了仍找不到)。 ■存储:可以顺序、链接 排序要求:无 张帖 顺序检索算法 监视哨”顺序检索算法 template class Item i 索成功返回元位量,检索失败统一返回0 template int Item(Type value): key value)& ector setKey(k//设监视哨 string other; /其它域 while(dataList[]->getKeyol=k)i--' /返回元素位置 vector*> dataList 学恤息 权新有,种

2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 平均检索长度的例子 „ 假设线性表为（a, b, c）检索a、 b、c的概率分别为0.4、0.1、0.5 „ 顺序检索算法的平均检索长度为 0.4×1+0.1×2+0.5×3 = 2.1 „ 即平均需要2.1次给定值与表中关键 码值的比较才能找到待查元素 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 检索算法评估的几个问题 „ 衡量一个检索算法还需要考虑 „ 算法所需的存储量 „ 算法的复杂性 „ ... 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 9.1 基于线性表的检索 „ 9.1.1 顺序检索 „ 9.1.2 二分检索 „ 9.1.3 分块检索 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 9.1.1 顺序检索 „ 针对线性表里的所有记录，逐个进 行关键码和给定值的比较 。 „ 若某个记录的关键码和给定值比较相 等，则检索成功 ； „ 否则检索失败(找遍了仍找不到)。 „ 存储：可以顺序、链接 „ 排序要求：无 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 顺序检索算法 template class Item { public: Item(Type value):key(value) {} Type getKey() {return key;} //取关键码值; void setKey(Type k){ key=k;} //置关键码 private: Type key; //关键码域 string other; //其它域 }; vector*> dataList; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 “监视哨”顺序检索算法 „ 检索成功返回元素位置，检索失败统一返回0; template int SeqSearch(vector*>& dataList,int length, Type k) { int i=length; //将第0个元素设为待检索值 dataList[0]->setKey (k); //设监视哨 while(dataList[i]->getKey()!=k) i--; return i; //返回元素位置 }

顺序检索性能分析 顺序检索平均检索长度 每个关键码是等概率的,Pi=1/n 设检索成功的概率为p,检索失败的概率 q=(1-p ASL +1 +(1-p)(n+1) ∑i (n+1)(1-P/2) 失败时都需要比较n+1次(设置了一个 (n+1)/2K,若有则一定排在 dataList[Ol前 (3)Key int Bin Search 17|82235|516088 ector*>& dataList,int length, Type k) while(lowgetKeyo) 检索关键码181ow=1high=9K=18 区间 else if (k>dat low mid+1 else return mid;//成功返回位置 第二次:mid=2;aray[2]=17(18 turn0;//检紫失败,返回0 =1818 张帖兽

3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 顺序检索性能分析 „ 检索成功 假设检索每个关键码是等概率的，Pi = 1/n „ 检索失败 假设检索失败时都需要比较n+1次（设置了一个 监视哨） Pi n i i n n n i i n i n i n ·() () − = − ∑ = − = − ∑ = = + = ∑ 0 1 1 0 1 1 2 1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 顺序检索平均检索长度 „ 假设检索成功的概率为p，检索失败的概率 为q=(1-p) „ （n+1)/2 K，若有则一定排在dataList[i]]前 （3）Key int BinSearch (vector*>& dataList,int length,Type k){ int low=1, high=length, mid; while (lowgetKey()) high = mid-1; //右缩检索区间 else if (k>dataList[mid]->getKey()) low = mid+1; //左缩检索区间 else return mid; //成功返回位置 } return 0; //检索失败，返回0 } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 检索关键码18 low=1 high=9 K=18 第一次：mid=5; array[5]=35>18 high=4; (low=1) 第二次：mid=2; array[2]=17<18 low=3; (high=4) 第三次：mid=3; array[3]=18=18 mid=3；return 8 二分法检索图示 35 1 2 3 45 6 7 8 9 15 22 51 60 88 93 low mid high 17 18

二分法检索性能分析 二分法检索性能分析(续) ■最大检索长度为 成功的平均检索长度为: ■失败的检索长度是 停止在内部叶结点 nt-log,(n+l)-I 优缺点 (n+1) 优点:平均与最大检索长度相近,检索速度快 停止在外部空结点,则加 缺点:要排序、顺序存储,不易更新(插/删 叔新有,盘 张 9.1.3分块检索 分块检索思想 顺序与二分法的折衷 ■“按块有序” 既有较快的检索 a设线性表中共有n个数据元素,将表分 又有较灵活的更改 不需要均匀 ■每一块中的关键码不一定有序 但前一块中的量大关键码必须小于后 订恤 张铭趣 张帖 索引表 分块检索分两个阶段 索引表 (1)确定待查元素所在的块 各块中的最大关键码 (2)在块内检索待查的元素 及各块起始位置 可能还需要块中元素个数(每一块可 分块检索——索引顺序结构 ■索引表是一个递增有序表 由于表是分块有序的 权新有,种 耍

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 二分法检索性能分析 „ 最大检索长度为 „ 失败的检索长度是 „ 停止在内部叶结点 或 „ 停止在外部空结点，则加1 ⎣ ⎦ log（2 n + 1） ⎡ ⎤ log（2 n + 1） 15 18 22 51 7 8 9 2 1 3 4 88 60 93 35 17 5 ⎡ ⎤ log（2 n +1） 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 二分法检索性能分析（续） „ 成功的平均检索长度为： (n > 50) „ 优缺点 „ 优点：平均与最大检索长度相近，检索速度快 „ 缺点：要排序、顺序存储，不易更新(插/删) 1 1 ASL ( 2 ) 1 1 log ( 1) 1 2 log ( 1) 1 2 j i i n i n n n n − = ⋅ ∑ = + = + − ≈ +− 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 9.1.3 分块检索 „ 顺序与二分法的折衷 „ 既有较快的检索 „ 又有较灵活的更改 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 分块检索思想 „ “按块有序” „ 设线性表中共有n个数据元素，将表分 成b块 „ 不需要均匀 „ 每一块可能不满 „ 每一块中的关键码不一定有序 „ 但前一块中的最大关键码必须小于后 一块中的最小关键码 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 索引表 „ 索引表 „ 各块中的最大关键码 „ 及各块起始位置 „ 可能还需要块中元素个数（每一块可 能不满） „ 索引表是一个递增有序表 „ 由于表是分块有序的 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 分块检索分两个阶段 „ （1）确定待查元素所在的块 „ （2）在块内检索待查的元素 分块检索——索引顺序结构

分块检索——索引顺序结构 分块检索性能分析 2345678910ll12131151617 分块检索为两级检索 先在索引表中确定待查元素所在 设在索引表中确定块号的时间开销是 ae H ■块内最大关键码 ■块起始位置 ■块内有效元素个数 然后在块内检索待查的元素。 在块中查找记录的时间开销为A ASL (n) 叔新有,盘 张幽 分块检索性能分析(续1) 分块检索性能分析(续2) 索引表是按块内最大关键码有序 假设在索引表中用顺序检索,在块内 的,且长度也不大,可以二分检 索,也可以顺序检索 ASL ASL:6+l+5+I=b+s ■各子表内各个记录不是按记录关键 码有序,只能顺序检索 当s=√n时,ASL取最小值 订恤 张铭趣 张帖 分块检索性能分析(续3) 分块检索性能分析(续4) ■当n=10,000时 若采用二分法检索确定记录所在 顺序检索5,000次 二分法检索14次 的子表,则检索成功时的平均检 分块检索100次 索长度为 ■如果数据块(子表)存放在外存时,还 ASL=ASL,+ ASLw 会受到页块大小的制约 此时往往以外存一个I/O读取的数据(一 ≈log2(b+1)-1+(s+1)/2 页)作为 ≈log2(1+n/s)+s2 学恤息 权新有,种 耍

5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 link: Key: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 22 12 13 33 42 44 38 24 48 60 80 74 49 86 22 48 86 0 6 12 分块检索——索引顺序结构 „ 块内最大关键码 „ 块起始位置 Size: 3 6 5 „ 块内有效元素个数 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 分块检索性能分析 „ 分块检索为两级检索 „ 先在索引表中确定待查元素所在 的块； „ 设在索引表中确定块号的时间开销是 ASLb „ 然后在块内检索待查的元素。 „ 在块中查找记录的时间开销为ASLw „ ASL(n) = ASLb + ASLw 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 分块检索性能分析(续1) „ 索引表是按块内最大关键码有序 的，且长度也不大，可以二分检 索，也可以顺序检索 „ 各子表内各个记录不是按记录关键 码有序，只能顺序检索 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 分块检索性能分析(续2) „ 假设在索引表中用顺序检索，在块内 也用顺序检索 „ 当s= 时，ASL取最小值， ASL = +1 ≈ 1 ASL 2 b b + = n n n 1 ASL 2 s w + = 2 1 1 ASL 1 22 2 1 2 b s bs n s s + + + = += + + = + 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 分块检索性能分析(续3) „ 当n=10,000时 „ 顺序检索5,000次 „ 二分法检索14次 „ 分块检索100次 „ 如果数据块（子表）存放在外存时，还 会受到页块大小的制约 „ 此时往往以外存一个Ｉ/Ｏ读取的数据（一 页）作为一块 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 分块检索性能分析(续4) „ 若采用二分法检索确定记录所在 的子表，则检索成功时的平均检 索长度为 ASL= ASLb + ASLw ≈ log2 (b+1)-1 + (s+1)/2 ≈ log2(1+n / s ) + s/2

分块检索的优缺点 92集合的检索 优点: 用位向量来表示集合 插入、删除相对较易 对于密集型集合(数据范围小,而 没有大量记录移动 集合中有效元素个数比较多) ■缺点: 增加一个辅助数组的存储空间 初始线性表分块排序 00110100001 当大量插入/删除时,或结点分布不均 匀时,速度下降 叔新有,盘 张 例:计算0到15之间所有的奇素数 实际实现用无符合长整数数组 奇数:012345678910112131415 全集元素个数N=40的集合,集 010f0d10101o1o 合{359753,1}表示为 000000000000000000000000 00 000 o00000000000000000000010 奇素数: 不够一个 signed long,左补0 订恤 张铝 权新有,种 张帖 93散列检索 9.3.0散列中的基本问题 9.3.0散列中的基本问题 基于关键码比较的检索 9.31散列函数 二分法、树型 令碰撞的处理 检索是直接面向用户的操作 上述检索的时间效率可 △9.32开散列方法 能使得用户无法 .33闭散列方法 最理想的情况 Q9.34闭散列表的算法实现 根据关健码值,直接找到记录的存储地址 待查关键码与候选记录集合的某些记录进 △935散列方法的效率分析 学恤息 权新有,种

6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 分块检索的优缺点 „ 优点： „ 插入、删除相对较易 „ 没有大量记录移动 „ 缺点： „ 增加一个辅助数组的存储空间 „ 初始线性表分块排序 „ 当大量插入/删除时，或结点分布不均 匀时，速度下降 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 9.2 集合的检索 „ 用位向量来表示集合 „ 对于密集型集合（数据范围小，而 集合中有效元素个数比较多） 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 例：计算0到15之间所有的奇素数 奇数： 素数： 奇素数： 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15 0 4 6 8 10 12 14 1 9 15 2 3 5 7 11 13 0 2 4 6 8 10 12 14 1 9 15 3 5 7 11 13 1 3 5 7 9 11 13 15 2 3 5 7 11 13 3 5 7 11 13 & = 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 实际实现用无符合长整数数组 „ 全集元素个数N=40的集合，集 合{35, 9, 7, 5, 3, 1}表示为 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0010 1010 1010 不够一个usigned long, 左补0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 9.3 散列检索 „ 9.3.0 散列中的基本问题 „ 9.3.1 散列函数 „ 碰撞的处理 „ 9.3.2 开散列方法 „ 9.3.3 闭散列方法 „ 9.3.4 闭散列表的算法实现 „ 9.3.5 散列方法的效率分析 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 9.3.0 散列中的基本问题 „ 基于关键码比较的检索 „ 顺序检索，==, != „ 二分法、树型 >, == , < „ 检索是直接面向用户的操作 „ 当问题规模n很大时，上述检索的时间效率可 能使得用户无法忍受 „ 最理想的情况 „ 根据关键码值，直接找到记录的存储地址 „ 不需要把待查关键码与候选记录集合的某些记录进 行逐个比较

由数组的直接寻址想到的 散列基本思想 例如,读取指定下标的数组元 一个确定的函数关系h 以结点的关键码K为自变量 函数值h(K作为结点的存储地址 与数组元囊个数的规模n无关 ■检索时也是根据这个函数计算其存储位 猫经楼 通常散列表的存储空间是一个一维数组 种重要的存储方法 散列地址是数组的下标 也是一种常见的检索方法 叔新有,盘 张 列盐类膏 散列地她类萄码 例子1 例91:已知线性表关健码集合为 S=iand, begin, do, end, for, go, if, repeat, then, until, while 可设散列表为 char HT2 26I8I 散列函数H(key)的值,取为关健码key中的 个字母在字母表{a,b,c,….x}中的序 订恤 张铝 张帖 歡列地址关健码 歐列地址关管码 例子2 例92:在集合S中增加4个关健码,集合S1=S+ 要修改散列函数:散列函数的值为key中首尾字 母表中序号的平均值,即 学恤息 权新有,种

7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 由数组的直接寻址想到的 „ 例如，读取指定下标的数组元 素 „ 根据数组的起始存储地址、以及 数组下标值而直接计算出来的， 所花费的时间是O(1) „ 与数组元素个数的规模n无关 „ 受此启发，计算机科学家发明 了散列方法（Hash, 有人称“哈 希”，还有称“杂凑”）散列是一 种重要的存储方法 „ 也是一种常见的检索方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 散列基本思想 „ 一个确定的函数关系h „ 以结点的关键码K为自变量 „ 函数值h(K)作为结点的存储地址 „ 检索时也是根据这个函数计算其存储位 置 „ 通常散列表的存储空间是一个一维数组 „ 散列地址是数组的下标 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 例子1 例9.1：已知线性表关键码集合为： S = { and, begin, do, end, for, go, if, repeat, then, until, while} 可设散列表为： char HT2[26][8]; 散列函数H(key)的值，取为关键码key中的第一 个字母在字母表{a, b, c, ..., z}中的序号，即： H(key)=key[0] – ‘a’ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 例 子 1表 散列地址 关键码 散列地址 关键码 0 and (array) 13 1 begin 14 2 15 3 do 16 4 end (else) 17 repeat 5 for 18 6 go 19 then 7 20 u ntil 8 if 21 9 22 w hile (w ith) 10 23 11 24 1 2 2 5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 例子2 例9.2：在集合S中增加4个关键码，集合S1 = S + { else, array, with, up} 要修改散列函数：散列函数的值为key中首尾字 母在字母表中序号的平均值，即： int H3(key) char key[]; int i; { i = 0; while ((i<8) && (key[i]!=‘\0’)) i++; return((key[0] + key(i-1) – 2*’a’) /2 ) } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 例 子 2表 散列地址 关键码 散列地址 关键码 0 13 w hile 1 and 14 w ith 2 15 until 3 end 16 then 4 else 17 5 18 repeat 6 if 19 7 begin 20 8 do 21 9 22 10 go 23 11 for 24 1 2 arra y 2 5

几个重要概念 散列技术的两个重要问题 负载因子a=n/ 散列表的空间大小为m 用散列技术时需要考虑的两个首 填入表中的结点数为 要问题是: 冲突 )如何构造选择)使结点“分布均 某个散列函数对于不相等的关健码计算出了相同的 匀”的散列函数? 在实际应用中,不产生冲突的散列函数极少存在 (2)一旦发生冲突,用什么方法来解 同义词 决 发生冲突的两个关健 还需考虑散列表本身的组织方法 叔新有,盘 张 9.3.1散列函数 散列函数的选取原则 散列函数:把关键码值映射到 ■运算尽可能简单 存储位置的函数,通常用h来表 ■函数的值域必须在表长的范围内 ■尽可能使得关键码不同时,其散列 Address Hash( key 函数值亦不相同 订恤 张铭趣 张帖 需要考虑各种因素 常用散列函数选取方法 关键码长度 令1.除余法 散列表大小 令2.乘余取整法 关键码分布情况 令3.平方取中法 记录的检索频率 Q4.数字分析法 5.基数转换法 6.折叠法 Q7. ELFhash字符串散列函数 权新有,种

8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 几个重要概念 „ 负载因子α=n/m „ 散列表的空间大小为m „ 填入表中的结点数为n „ 冲突 „ 某个散列函数对于不相等的关键码计算出了相同的 散列地址 „ 在实际应用中，不产生冲突的散列函数极少存在 „ 同义词 „ 发生冲突的两个关键码 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 44 散列技术的两个重要问题 „ 采用散列技术时需要考虑的两个首 要问题是： „ （1）如何构造(选择)使结点“分布均 匀”的散列函数？ „ （2）一旦发生冲突，用什么方法来解 决？ „ 还需考虑散列表本身的组织方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 9.3.1 散列函数 „ 散列函数：把关键码值映射到 存储位置的函数，通常用h来表 示 Address ＝ Hash ( key ) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 散列函数的选取原则 „ 运算尽可能简单 „ 函数的值域必须在表长的范围内 „ 尽可能使得关键码不同时，其散列 函数值亦不相同 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 需要考虑各种因素 „ 关键码长度 „ 散列表大小 „ 关键码分布情况 „ 记录的检索频率 „ … 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 常用散列函数选取方法 „ 1. 除余法 „ 2. 乘余取整法 „ 3. 平方取中法 „ 4. 数字分析法 „ 5. 基数转换法 „ 6. 折叠法 „ 7. ELFhash字符串散列函数

1.除余法 M为什么不用偶数 若把M设置为偶数 x是偶数,h(Xx)也是偶数 h(x= x mod M x是奇数,h(Xx)也是奇数 ■通常选择一个质数作为M值 函数值依赖于自变量x的所有位,而不仅仅 是最右边k个低位 缺点:分布不均匀 增大了均匀分布的可能性 卖哭级釜嵌态考现的概率 例如,4093 反之亦然 叔新有,盘 张 M不用幂 mdy选择最右边8位 除余法面临的问题 0110010111000011010 若把M设置为2的幂 除余法的潜在缺点 那么,h(x)=xmod2k仅仅是x(用二进制 连续的关键码映射成连续的散列值 表示)最右边的k个位(bt 若把M设置为10的幂 ■虽然能保证连续的关键码不发生冲突 那么,h(x)=xmod10仅仅是x(用十进 但也意味着要占据连续的数组单元 制表示)最右边的k个十进制位( digita) 可能导致散列性能的降低 ■缺点:散列值不依赖于x的全部比特位 订恤 张铭趣 张帖 2.乘余取整法 乘余取整法示例 统让美最积的要放都分 上一个常数A(0<A< 设关键码key=123456,n=10000 然后,哥用警数n乘以这个值,对结果 且取A=(√5-1)/2=06180339, 因此有 ■散列函数为 ah(123456)= hash(key)=Ln*(A* key%1)J =L10000(0.6180339*123456 “A*key%1”表示取A*key小数部分: A*key %1=A*key-LA*key J =L1000(76300.004151 为助 =L10000*0.04151.J=41 学恤息 权新有,种

9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 1. 除余法 „ 除余法：用关键码x除以M(往往取散列表长 度)，并取余数作为散列地址。散列函数为： h(x) ＝ x mod M „ 通常选择一个质数作为M值 „ 函数值依赖于自变量x的所有位，而不仅仅 是最右边k个低位 „ 增大了均匀分布的可能性 „ 例如，4093 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 M为什么不用偶数 „ 若把M设置为偶数 „ x是偶数，h(x)也是偶数 „ x是奇数，h(x)也是奇数 „ 缺点：分布不均匀 „ 如果偶数关键码比奇数关键码出现的概率 大，那么函数值就不能均匀分布 „ 反之亦然 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 M不用幂 „ 若把M设置为2的幂 „ 那么，h(x)＝x mod 2k 仅仅是x(用二进制 表示)最右边的k个位(bit) „ 若把M设置为10的幂 „ 那么，h(x)＝x mod 10k 仅仅是x(用十进 制表示)最右边的k个十进制位(digital) „ 缺点：散列值不依赖于x的全部比特位 0110010111000011010 x mod 28 选择最右边8位 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 除余法面临的问题 „ 除余法的潜在缺点 „ 连续的关键码映射成连续的散列值 „ 虽然能保证连续的关键码不发生冲突 „ 但也意味着要占据连续的数组单元 „ 可能导致散列性能的降低 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 2. 乘余取整法 „ 先让关键码 key 乘上一个常数A (0<A < 1)，提取乘积的小数部分 „ 然后，再用整数 n 乘以这个值，对结果 向下取整，把它作为散列地址 „ 散列函数为： hash ( key ) = ⎣ n * ( A * key % 1 ) ⎦ „ “A * key % 1”表示取 A * key 小数部分: A * key % 1 = A * key - ⎣ A * key ⎦ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 乘余取整法示例 „ 设关键码 key = 123456, n = 10000 且取 A = = 0.6180339， „ 因此有 hash(123456) = = ⎣10000*(0.6180339*123456 % 1)⎦ = = ⎣10000 * (76300.0041151… % 1)⎦ = = ⎣10000 * 0.0041151…⎦ = 41 ( 5 1) / 2 −

乘余取整法参数取值的考虑 3.平方取中法 ■若地址空间为p位,就取n=2P 所求出的散列地址正好是计算出来的 A* key %1=A* key-LA* key J 值的小数点后最左p位(bi)值 00110 此方法的优点:对n的选择无关紧要 ■ Knuth认为:A可以取任何值,与待 排序的数据特征有关。一般情况下 6,进8位10可:同倍作为散列 取黄金分割 1)/2最理想 叔新有,盘 张 4.数字分析法 数字分析法(续1) 设有n个d位数,每一位可能有r种不同的 计算各位数字中符号分布的均匀度A2的公 这r种不同的符号在各位上出现的频率不一定 λ=∑(a24-n/r)2 可鲣在某些位上分布均匀些,每种符号出现的几率 其中,a冫表示第i个符号在第k位上出 现的次数, 在某些位上分布不均匀,只有某几种符号经常出现 题想翻警夯霰列 取其中各种符号分布 m/r表示各种符号在个数中均匀出现的 计算出的λ值越小,表明在该位(第k位) 各种符号分布得越均匀 订恤 张铭趣 张帖 数字分析法(续2) 991269 ②位,λ2=57.60 数字分析法(续3) ③位,λ;=1760 991630 ④位,λ,=5.60 ①位,仅9出现8次 9 805 位,λs=5.60 =(8-810)2x1+(08/10)2x9=57.6 ⑥位,λ6=5.60 ②位,仅9出现8次 992047 λ2=(8-8/10)2x1+(0-8/10)2x957.6 990001 ■③位,0和2各出现两次,1出现4次 ①②③④@⑥ λ3=(28/10)2x2+(48/10)2x1+(08/10)2 若散列表地址范国有3位数字,取各关健码的④⑤⑥位做为 ■位,0和4各出现两次,2、3、5、6各出现1次 癥可与合来推假拥加址含素进份用我方 ■⑥位,7和8各出现两次,0、1、5、9各出现1次 -8/10)2x2+〔1-8/10) 学恤息 权新有,种 张帖兽

10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 乘余取整法参数取值的考虑 „ 若地址空间为p位，就取n=2p „ 所求出的散列地址正好是计算出来的 A * key % 1 = A * key - ⎣ A * key ⎦ 值的小数点后最左p位（bit）值 „ 此方法的优点:对 n 的选择无关紧要 „ Knuth认为：A可以取任何值，与待 排序的数据特征有关。一般情况下 取黄金分割 最理想 ( 5 −1) 2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 3. 平方取中法 „ 此时可采用平方取中法：先通过求关键码的平 方来扩大差别，再取其中的几位或其组合作为 散列地址 „ 例如， „ 一组二进制关键码：(00000100，00000110， 000001010，000001001，000000111) „ 平方结果为：(00010000，00100100，01100010， 01010001，00110001) „ 若表长为4个二进制位，则可取中间四位作为散列 地址：(0100，1001，1000，0100，1100) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 4. 数字分析法 „ 设有 n 个 d 位数，每一位可能有 r 种不同的 符号 „ 这 r 种不同的符号在各位上出现的频率不一定 相同 „ 可能在某些位上分布均匀些，每种符号出现的几率 均等 „ 在某些位上分布不均匀，只有某几种符号经常出现 „ 可根据散列表的大小，选取其中各种符号分布 均匀的若干位作为散列地址 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 数字分析法（续1） „ 计算各位数字中符号分布的均匀度 λk 的公 式： „ 其中， 表示第 i 个符号在第 k 位上出 现的次数， „ n/r 表示各种符号在 n 个数中均匀出现的 期望值。 „ 计算出的 λk 值越小，表明在该位 (第k 位) 各种符号分布得越均匀 ∑= = − r i k k i n r 1 2 λ (α / ) k αi 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 数字分析法（续2） 9 9 2 1 4 8 ①位， λ 1 = 57.60 9 9 1 2 6 9 ②位， λ 2 = 57.60 9 9 0 5 2 7 ③位， λ 3 = 17.60 9 9 1 6 3 0 ④位， λ 4 = 5.60 9 9 1 8 0 5 ⑤位， λ 5 = 5.60 9 9 1 5 5 8 ⑥位， λ 6 = 5.60 9 9 2 0 4 7 9 9 0 0 0 1 ①②③④⑤⑥ „ 若散列表地址范围有 3 位数字, 取各关键码的④⑤⑥位做为 记录的散列地址 „ 也可以把第①，②，③和第⑤位相加，舍去进位，变成一位 数，与第④，⑥位合起来作为散列地址。还可以用其它方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 数字分析法（续3） „ ①位，仅9出现8次， „ λ 1 =（8-8/10）2×1+（0-8/10） 2 ×9=57.6 „ ②位，仅9出现8次， „ λ 2 =（8-8/10）2×1+（0-8/10） 2 ×9=57.6 „ ③ 位，0和2各出现两次，1出现4次 „ λ 3 =（2-8/10）2×2+（4-8/10） 2 ×1+ （0-8/10） 2 ×7 =17.6 „ ④位，0和5各出现两次，1、2、6、8各出现1次 „ ⑤位，0和4各出现两次，2、3、5、6各出现1次 „ ⑥位，7和8各出现两次，0、1、5、9各出现1次 „ λ 4 = λ 5 = λ 6 = （2-8/10）2×2+（1-8/10） 2 ×4+ （0-8/10） 2 ×4 =5.6