桶式散列的磁盘访问性能分析(续) 桶式散列面临的问题 最理想状况 ■理想状况很难实现 每个桶仅由一个页块组成,假设目录在外存 尤其当文件不断增长时,桶内的页块数也随 ■这样只需访外二次(对检索)或三次(对其他 之增多 运算 ■由于分布不均匀,有些桶内页块数可能过 要求 多,严重影响检索效率 存储桶的个数大致等于记录存放所需的页块 ■必要时需对文件进行重新组织 改变散列函数 散列函数值分布均匀 增加存储桶目录表的大小 叔新有,盘 张幽 93.3闭散列方法 闭散列表解决冲突的基本思想 把所有记录直接存储在散列表中。 当冲突发生时,使用某种方法为关 每个记录关键码有一个基位置即 键码K生成一个散列地址序列 hkey),即由散列函数计算出来的地址 d2,…di 如果要插入一个关键码,而另一个记 录已经占据了R的基位置(发生碰撞), a其中dh(K)称为K的基地址地置 那么就把R存储在表中的其它地址内,由 所有d(0<m)是后继散列地址 冲突解决策略确定是哪个地址 形成探查的方法不同,所得到的解决冲 突的方法也不同 订恤 张铭趣 张帖 闭散列表解决冲突的基本思想(续 检索过程 当插入K时,若基地址上的结点 检索时也要像插入时一样遵循同样 已被别的数据元素占用 的策略 ■则按上述地址序列依次探查,将 重复冲突解决过程 找到的第一个开放的空闲位置d作 找出在基位置没有找到的记录 为K的存储位置 若所有后继散列地址都不空闲 说明该闭散列表已满,报告溢出 学恤息 权新有,种 1414 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 79 桶式散列的磁盘访问性能分析(续) „ 最理想状况: „ 每个桶仅由一个页块组成，假设目录在外存 „ 这样只需访外二次(对检索)或三次(对其他 运算) „ 要求 „ 存储桶的个数大致等于记录存放所需的页块 数 „ 散列函数值分布均匀 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 80 桶式散列面临的问题 „ 理想状况很难实现 „ 尤其当文件不断增长时，桶内的页块数也随 之增多 „ 由于分布不均匀，有些桶内页块数可能过 多，严重影响检索效率 „ 必要时需对文件进行重新组织 „ 改变散列函数 „ 增加存储桶目录表的大小 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 81 9.3.3 闭散列方法 „ 把所有记录直接存储在散列表中。 „ 每个记录关键码有一个基位置即 h(key)，即由散列函数计算出来的地址 „ 如果要插入一个关键码，而另一个记 录已经占据了R的基位置(发生碰撞)， „ 那么就把R存储在表中的其它地址内，由 冲突解决策略确定是哪个地址 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 82 闭散列表解决冲突的基本思想 „ 当冲突发生时，使用某种方法为关 键码K生成一个散列地址序列 d0，d1，d2，... di，...dm-1 „ 其中d0=h（K）称为K的基地址地置 „ 所有di (0<i<m)是后继散列地址 „ 形成探查的方法不同，所得到的解决冲 突的方法也不同 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 83 闭散列表解决冲突的基本思想（续） „ 当插入K时，若基地址上的结点 已被别的数据元素占用 „ 则按上述地址序列依次探查，将 找到的第一个开放的空闲位置di 作 为K的存储位置 „ 若所有后继散列地址都不空闲， 说明该闭散列表已满，报告溢出 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 84 检索过程 „ 检索时也要像插入时一样遵循同样 的策略 „ 重复冲突解决过程 „ 找出在基位置没有找到的记录