字典的散列表示.pptVIP

缓冲区与访外 读外存上的数据: 1,把外存上一个或者多个物理记录读到内存的指定的区域（缓冲区）。 2,在缓冲区中找到需要的逻辑记录进行处理。 写的过程则相反，先写到缓冲区中，然后通过主机与外存的接口，把缓冲区中的数据写到外存储器的物理记录中。 一次读写过程，通常称为一次访外。 提高外存的存取时间的关键在于减少访外的次数。 * 文件与逻辑记录 文件通常指存储在外存的数据，是逻辑记录的集合。 逻辑记录（简称记录）是应用程序需要进行内外存交换的逻辑单位。 每个记录可以包含若干数据项， 其中能够唯一标识该记录的数据项称为关键码。 逻辑记录在外存储器上的地址由两部分组成： 逻辑记录所在物理记录的地址； 逻辑记录在物理记录内的相对位置。 由于缓冲区的大小受到内存容量的限制，所以减少访外次数的有效方法是精心设计文件的结构，使外存中存放的记录，相互关联，以便于成批处理。 * * 按桶散列的文件 桶: 拉链法中存放同义词的表. 这里桶是由0个或多个外存的页块通过指针的链接而构成. 实现散列文件的常见方法就是按桶散列: 只是这里存储桶里的一个链表结点对应于外存的一个页块,各种链接都直接采用外存的页块地址. 检索和插入、删除操作中涉及到访问外存. 桶目录表是一些指针的序列, 通常存储在内存中,每个指针指向一个桶的首页块. ? ? ? ? ? ? ? ? ? ? 桶目录表 桶的页块 按桶散列的文件 * 首先计算ｈ（key）； 设ｈ（key）＝ｉ，查阅桶目录表的第ｉ项，得到第ｉ个桶的首页块地址，读入首页块，在块上进行顺序查找； 找到关键码为key的记录则结束，否则根据块之间的链指针读入下一块，继续查找； 直到找到或者找遍全桶时结束。 检索：查找关键码值为key的记录 * 先按上述方法进行查找； 找到时，说明本次插入是错误的或多余的； 若找不到(则此时读到内存中的页块恰好是新记录应插入的桶的最后一块),在这个页块的空位置上填入新记录，并写回外存； 如果此页块已满，则申请一个新页块，其地址填入前一块的指针位置; 在新页块上填入新记录并把指针置空；最后把两个页块都写回外存。 插入：插入关键码为key的记录 * 桶数的选择* 桶数的选择: 桶数太少会使得桶中的页块较多, 增大访外次数. 桶数太多,造成空间浪费. 桶目录表本身的增大所带来的浪费不严重. 主要的空间浪费: 不空但只存放很少几个记录的桶. 确定桶的数目: 经验规则:桶数与文件所能填满的页块数大致相等, 即 B?n/b, 其中B为桶数, n为文件记录数, b为每个页块能容纳的记录数. 按照上面取法,如果散列函数不太糟, 大多数桶中不超过２个页块, 检索时平均只需要１－２次访外， 每个页块中平均放入的记录数能使空间利用率达到半满的程度. * 桶数的扩充* 随着文件增大,桶的页块数目增大,检索效率下降. 解决方法:扩充桶的数目, 定义新的散列函数. 成倍扩充方法: 减少访外次数. 散列函数采用除余法, 桶数(B)与模相等. 把模扩大一倍(2B), 则 原来第i号桶的所有记录要么留在第i号桶, 要么存入新形成的第B+i号桶. 第B+i号桶的全部记录只能来自第i号桶. 总访外次数N1+N2, 其中N1是扩充前文件占用的页块数, N2是扩充后的页块数. * 本讲重点： 介绍了散列法，包括基本思想和一些常用的散列函数，以及，解决碰撞问题的两种方法：开地址法和拉链法。 在散列表示的字典中执行元素的检索运算平均可能达到常数的时间。 散列表示主要用于表示静态的字典 散列文件把散列表的思想用于外存文件之上。 张乃孝精讲：“数据结构”第十讲 字典的散列表示 张乃孝精讲：“数据结构”第十讲 字典的散列表示 * *   第十讲　字典的散列表示 * * * 教材与参考资料 普通高等教育“十一五”国家级规划教材 　普通高等教育精品教材 《算法与数据结构— C语言描述》（第2版） 张乃孝 编著, 高等教育出版社 2008. 第6章 集合与字典（6.5） 参考１.３.４（外存数据的组织） 普通高等教育“十一五”国家级规划教材配套参考书 《算法与数据结构》（第2版）学习指导与习题解析 　张乃孝 编著, 高等教育出版社 2009. * 6.5 字典的散列表示 动机: 如果关键码是存储字典元素的数组下标, 则可以直接找到字典元素! 关键码未必总是整数! Windows 序列号 关键码即使是整数,也未必适合做数组下标! 北大学生学号 如何建立从关键码集合到适当整数集合的映射, 把数据存放在映射值对应的位置. 散列表示! * 6.5.1基本概念 散列法(Hashing), 也称