拉链法性能分析 拉链法不适于外存检索 给定一个大小为M存储n个记录的表 教列函数(在理想情祝下将把记录在 勿类琵较蓉劲类储在内存中,开散列 知 列表存储在磁盘中,用开散列不 链表中有nM个记录 Dn时,散列方法的平均代价就是 盘介氧义词表中的元素可能存储在不同的磁 接金爱而增检繁刪{时 桶式散列 叔新有,盘 张 溢出区—静态链 2.桶式散列 ■适合存储于磁盘的散列表 Ia peary 基本思想: n把一个文件的记录分为若干存储桶, (ii 每个存储桶包含一个或多个页块 个存储桶内的各页块用指针连接起 块包含若干记录 散列函数h(K表示具有关键码值K的 记录所在的存储桶号 订恤 张铭趣 张陪 桶式散列文件组织 桶式散列的磁盘访问性能分析 右图表示了一个具有B 个查找平均访外次数等于桶内页块数k 个存储桶的散列文件 口[ 存储桶目录表进入内存(假定目录表不在 组织 如果B很小,存储桶目 贡蝨找求的记录必须逐个检查个桶内 录表可放在内存 实际上是(k+1)/2 ■如果B较大,要存放好 陕诱禁改用莩金驾 算尚需另一 录表就放到外存上 创键法表 学恤息 权新有,种 耍13 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 73 拉链法性能分析 „ 给定一个大小为M存储n个记录的表 „ 散列函数(在理想情况下)将把记录在 表中M个位置平均放置，使得平均每一 个链表中有n/M个记录 „ M>n 时，散列方法的平均代价就是 Θ(1) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 74 拉链法不适于外存检索 „ 如果整个散列表存储在内存中，开散列 方法比较容易实现 „ 如果散列表存储在磁盘中，用开散列不 太合适 „ 一个同义词表中的元素可能存储在不同的磁 盘页中 „ 这就会导致在检索一个特定关键码值时引起 多次磁盘访问，从而增加了检索时间 „ 桶式散列 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 75 溢出区——静态链 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 76 2. 桶式散列 „ 适合存储于磁盘的散列表 „ 基本思想: „ 把一个文件的记录分为若干存储桶， 每个存储桶包含一个或多个页块 „ 一个存储桶内的各页块用指针连接起 来，每个页块包含若干记录 „ 散列函数h(K)表示具有关键码值K的 记录所在的存储桶号 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 77 桶式散列文件组织 0 1 B-1 … … b1 ∧ b2 b4 b5 ∧ b6 ∧ b3 存储桶目录表 „ 右图表示了一个具有B 个存储桶的散列文件 组织 „ 如果B很小，存储桶目 录表可放在内存 „ 如果B较大，要存放好 多页块，则存储桶目 录表就放到外存上 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 78 桶式散列的磁盘访问性能分析 „ 一个查找平均访外次数等于桶内页块数k 的一半 „ 调存储桶目录表进入内存(假定目录表不在 内存) „ 为了寻找要求的记录必须逐个检查一个桶内 各页块 „ 实际上是(k+1)/2 „ 对于修改、插入、删除等运算尚需另一 次访外，用于重新写回外存