14

Size: px

Start display at page:

Download "14"

铺艺乔
5 years ago
Views:

1 孙猛年 11 月 27 日 1

2 字典的散列列表示 2

3 动机 : 如果关键码是存储字典元素的数组下标, 则可以直接找到字典元素! 关键码未必总是整数! Windows 序列列号关键码即使是整数, 也未必适合做数组下标! 北北大学生学号 10 位数字, 取值范围 100 亿如何建立从关键码集合到适当整数集合的映射, 把数据存放在映射值对应的位置散列列表示! 3

4 4

5 散列列法 (Hashing), 也称为杂凑法或关键码 - 地址转换法散列列函数 h 关键码 key 散列列地址 h(key) 这个 h 就称为散列列函数, 又称哈希 (hash) 函数或杂凑函数, 是从可能的关键码到一个整数区间里里 ( 下标 ) 的映射存入关键码为 key 的数据时, 将其存入表中第 h(key) 个位置以 key 为关键码检索数据时, 直接查第 h(key) 个位置的元素散列列函数 h 的值域应该是可以使用的整个地址空间, 称为基本区域 5

6 散列列法 (Hashing), 也称为杂凑法或关键码 - 地址转换法散列列函数 h 关键码 key 散列列地址 h(key) 这个 h 就称为散列列函数, 又称哈希 (hash) 函数或杂凑函数, 是从可能的关键码到一个整数区间里里 ( 下标 ) 的映射负载因子 :α = 字典中结点数 / 基本区域能容纳的结点数碰撞 : 如果 key1 key2, 而 h(key1) = h(key2) 发生碰撞的关键码称为同义词散列列表 : 采用散列列法表示的字典 6

7 主要关注两个问题 : 散列列函数的选择使得散列列地址的分布尽可能均匀 ; 理理想的负载因子α>0.5 碰撞的处理理依据存储条件, 同义词可以存放在基本区域中未被占用的单元 ; 也可以在基本区域以外另开辟区域, 例例如 α>1 时 7

8 不不存在一种普遍适用的最佳的散列列函数! 具体问题具体设计! 常用设计方法数字分析法折叠法中平方法基数转换法除余法对于非整数关键码, 常见的方式是先设计一种方式把它转换到整数, 而后再用整数散列列的方法 8

9 如果关键码位数比基本区的地址码位数多, 丢掉分布不不均匀的位留留下均匀的位作为地址例例如 : key h(key) 136xxxx xxxx xxxx xxxx 过分依赖于关键码集合, 通常适合静态的字典 9

10 如果关键码位数比地址码位数多, 且分布比较均匀, 则将关键码从某些地方断开, 分为几部分, 以几部分的叠加和 ( 舍弃进位 ) 作为地址. 例例如 : key = 移位折叠相加移位相加

11 先求出关键码的平方, 然后取中间几位作为地址例例如 : key = 4731, = , h(4731)=

12 把关键码看成基数为 r1 的数, 将它转换成基数为 r2 的数, 用数字分析法取中间几位作为散列列地址 r1 和 r2 互素 key =236075, r1=13, r2=10, (236075) 13 = = (841547) 10 h(key) =

13 关键码除以某个不不大于基本区域大小 (m) 的数 p 后的余数为散列列地址, 即 h(key)=(int)key%p; 数 p 一般选素数常用素数 : m = 128, 256, 512, 1024, p 选择 127, 251, 503, 1019 除余法使用最广, 常用于动态字典和关键码没有规律律出现的情况也可以用于将其他散列列函数得到值归缩到所需基本区域 13

14 一般而言, 散列列函数的选取应根据具体问题具体分析的原则, 针对具体字典元素关键码集合的特性, 加上空间时间的条件, 去构造相对理理想的散列列函数散列列函数计算出的地址应该尽可能均匀地分布在希望的地址空间中散列列函数应该尽可能简单, 以提高关键码到地址的转换速度 14

15 散列列表的插入和检索都要考虑对碰撞的处理理如果以 h(key) 为地址的空间未被占用 : 执行行检索, 检索失败 ; 执行行插入, 将元素存入该存储空间如果以 h(key) 为地址的空间已被占用 : 执行行检索, 则需要检查已经存放的元素 ( 甚至同义词 ) 是否是需要检索的元素 ; 检查同义词需要知道处理理碰撞的方法如果执行行插入, 发生碰撞涉及对同义词的处理理碰撞处理理方法 : 开地址法拉链法 15

16 基本想法 : 出现冲突时元素无法保存在散列列函数确定的位置, 需设法为它在基本区域内另外安排一个位置采用探查方式作为系统化的位置安排方式开地址法解决碰撞 : 在基本区域内形成一个同义词的探测序列列, 沿着探测序列列逐个查找, 直到满足下列列条件为止 : 找到查找的元素 ( 检索成功 ), 或者碰到一个未被占用的地址 ( 可以插入同义词或者检索失败 ) 显然基本区域的负载因子必须小于 1 16

17 基本区域内的一个探查序列列 : H i = (h(key)+d i )%m, 其中 :m 为表长, d i 为增量量序列列, i=1,2,,k (k m-1) 如果增量量序列列满足 : d i =i, 则为线性探查序列列如果增量量序列列满足 : d i =i h 2 (key) 则为双散列列探查序列列 17

18 对关键码集合 K={18,73,10,5,68,99,22,32,46,58,25}, 我们取 h(key)=key%13, 则 h(18)=5, h(73)=8, h(10)=10, h(5)=5, h(68)=3, h(99)=8, h(22)=9, h(32)=6, h(46)=7, h(58)=6, h(25)=12 散列列地址关键码从例例子中看到线性探测容易易出现堆积现象, 即在处理理同义词的过程中又添加了了非同义词冲突 ( 其他探查法也可能有类似情况 ) 58 18

19 对关键码集合 K={18,10,73,7}, 我们取 h(key)=key%5,h 2 (key) =key%3+1, 则 h(18)=3,h(10)=0,h(73)=3,h(7)=2; h 2 (18)=1,h 2 (10)=2,h 2 (73)=2,h 2 (7)=2 散列列地址关键码

20 对给定 key 值 : 1. 根据散列列函数求出散列列地址 ; 2. 若该位置无记录, 则检索失败结束 ; 3. 否则比较元素关键码, 若与 key 相等则检索成功结束 ; 4. 否则根据本散列列表设计的冲突处理理方法找出下一地址, 回到步骤 2 用这个位置检查对关键码集合 K={18,10,73,7}, 我们取 h(key)=key%5, h 2 (key) =key%3+1, 则 h(18)=3,h(10)=0,h(73)=3,h(7)=2; h 2 (18)=1,h 2 (10)=2,h 2 (73)=2,h 2 (7)=2. 检索关键码 73 散列列地址关键码

21 存储结构实现算法创建空散列列表与顺序表的创建算法类似 ; 假定有效的关键码值都大于 0, 因此创建空字典的时候都用 0 初始化关键码散列列表的检索算法用线性探查法解决碰撞 ; 散列列表的插入算法用线性探查法解决碰撞 21

22 typedef int KeyType; typedef int DataType; typedef struct { KeyType key; /* 字典元素的关键码字段 */ DataType value; /* 字典元素的属性字段 */ } DicElement; typedef struct { int m; /* m 为基本区域长度 */ DicElement *elements; } HashDictionary; typedef HashDictionary *PHashDictionary; 22

23 int linearsearch(hashdictionary *phash, KeyType key, int *position) { int d = h(key), inc; /* 设 h 为散列列函数 */ for (inc = 0; inc < phash->m; inc++) { if (phash->elements[d].key == key) { *position = d; return 1; /* 检索成功 */ } else if (phash->elements[d].key == 0) { *position = d; return 0; /* 检索失败, 找到空位置 */ } d = (d+1) % phash->m; } *position = -1; /* 散列列表溢出 */ return 0; } 23

24 首先调用检索算法, 如果检索失败, 再根据提供的位置信息将元素 ele 插入 int linearinsert(hashdictionary *phash, DicElement ele) { int position; if (linearsearch(phash, key, &position) ==1) printf("key exists \n"); /* 已有关键码为 key 的结点 */ else if (position!= -1) /* 插入结点 */ phash->elements[position] =ele ; else return 0; /* 散列列表溢出 */ return 1; } 24

25 对于用开地址法构造的散列列表, 删除结点时不不能简单地将要删除的结点空间置为 0; 这会引起检索方面的问题怎么处理理?! 散列列地址关键码散列列地址关键码检索 73 失败 25

26 基本思想 : 元素存在基本区域之外 ; 为每个关键码建立一个链接表, 所有关键字为同义词的记录存储在同一个链表中所有元素可以统一处理理 ( 无论是否冲突 ) 允许任意的负载因子最简单的方法是把新元素插在链接表头如果要防止出现重复关键码, 就需要检查整个链表 26

27 对关键码集合 K={18,10,73,7}, 取 h(key)=key%5, 则 h(18)=3,h(10)=0,h(73)=3,h(7)=2 用拉链法解决碰撞 :

28 拉链法的实现比较清楚 : 在单链表上检索插入删除每个同义词子表的平均长度为 n/m, 其中 n 为关键码个数, m 为基本区域长度 n<m, 则一定存在若干空表 ; 一般设计为 1<n/m<10 各链接表上的结点动态申请, 适合构造散列列表前无法确定表长的情况 ; 不不会造成堆积现象, 结点的删除比较方便便 28

29 散列列文件是存在外存的大型字典结构, 把散列列的思想用于文件 : 将散列列函数作用到记录的关键码, 确定记录在外存的存储地址 ; 处理理冲突常用适合外存分块存取的拉链法 29

30 30

31 磁盘类似于多碟的 CD, 若干盘片 ( 比如 4 片 ) 串串在一根主轴上形成一个盘组, 当主轴旋转时带动各个盘片旋转每个盘面上包含大小不不同的许多同心圆每个圆圈称为一个磁道, 各个盘面的半径相同的磁道合在一起构成一个柱面一个磁道又可分为若干段, 每段是一个页块 ( 物理理记录 ) 一个盘组上从大到小的存储地址为 : 柱面磁道和页块 31

32 1. 选定柱面, 这是机械动作, 所以比较慢 2. 选定磁道, 由电子线路路实现, 所以比较快 3. 找物理理记录, 这是机械动作, 较慢实际读写信息的时间比定位时间少得多, 访问磁盘中的数据比访问内存慢 5-6 个数量量级主机对外存储器器上的数据必须按页块存取 ( 不不能直接按字或者字节存取 ) 页块是内存与外存进行行交换的物理理单位 32

33 读外存上的数据 : 1, 把外存上一个或者多个物理理记录读到内存的指定的区域 ( 缓冲区 ) 2, 在缓冲区中找到需要的逻辑记录进行行处理理写的过程则相反, 先写到缓冲区中, 然后通过主机与外存的接口, 把缓冲区中的数据写到外存储器器的物理理记录中一次读写过程, 通常称为一次访外提高外存的存取效率的关键在于减少访外的次数 33

34 文件通常指存储在外存的数据, 是逻辑记录的集合逻辑记录 ( 简称记录 ) 是应用程序需要进行行内外存交换的逻辑单位每个记录可以包含若干数据项, 其中能够唯一标识该记录的数据项称为关键码逻辑记录在外存储器器上的地址由两部分组成 : 逻辑记录所在物理理记录的地址 ; 逻辑记录在物理理记录内的相对位置由于缓冲区的大小受到内存容量量的限制, 所以减少访外次数的有效方法是精心设计文件的结构, 使外存中存放的记录, 相互关联, 以便便于成批处理理 34

35 散列列文件是存放在外存的大型字典结构, 把散列列的思想用于文件 : 将散列列函数作用到记录的关键码, 确定记录在外存的存取地址处理理冲突常用适合外存分块存取的拉链法 35

36 桶 : 拉链法中存放同义词的表. 桶目录表桶的页块这里里桶是由 0 个或多个外存的页块通过链接而构成. 实现散列列文件的常见方法就是按桶散列列 : 只是这里里存储桶里里的一个链表结点对应于外存的一个页块, 各种链接都直接采用外存的页块地址. 检索和插入删除操作中涉及到访问外存. 桶目录表是一些链接的序列列, 通常存储在内存中, 每个链接指向一个桶的首页块. 按桶散列列的文件 36

37 key 首先计算 h(key); 设 h(key)=i, 查阅桶目录表的第 i 项, 得到第 i 个桶的首页块地址, 读入首页块, 在块上进行行顺序查找 ; 找到关键码为 key 的记录则结束, 否则根据块之间的链接读入下一块, 继续查找 ; 直到找到或者找遍全桶时结束 37

38 key 先按上述方法进行行查找 ; 找到时, 说明本次插入是错误的或多余的 ; 若找不不到 ( 则此时读到内存中的页块恰好是新记录应插入的桶的最后一块 ), 在这个页块的空位置上填入新记录, 并写回外存 ; 如果此页块已满, 则申请一个新页块, 其地址填入前一块的链接位置 ; 在新页块上填入新记录并把链接置空 ; 最后把两个页块都写回外存 38

39 桶数的选择 : 桶数太少会使得桶中的页块较多, 增大访外次数桶数太多, 造成空间浪费桶目录表本身的增大所带来的浪费不不严重主要的空间浪费 : 不不空但只存放很少几个记录的桶确定桶的数目 : 经验规则 : 桶数与文件所能填满的页块数大致相等, 即 B n/b, 其中 B 为桶数, n 为文件记录数, b 为每个页块能容纳的记录数按照上面取法, 如果散列列函数不不太糟, 大多数桶中不不超过 2 个页块, 检索时平均只需要 1-2 次访外, 每个页块中平均放入的记录数能使空间利利用率达到半满的程度 39

13

孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 11 月 23 日 1 字典及其抽象数据类型字典的线性表实现二分法与插值法 (interpolation) 检索集合的抽象数据类型及实现 2 数据的存储和访问是计算中最重要最基本的工作, 也是各种计算机应用和信息处理理的基础在许多情况下, 计算过程并不不知道数据的存储位置, 但需要使用数据,