探查序列 几种常见的闭散列方法 插入和检索函数都假定每个关键码 令1.线性探查 的探查序列中至少有一个存储位置 令2.二次探查 是空的 令3.伪随机数序列探查 否则可能会进入一个无限循环中 ■也可以限制探查序列长度 令4.双散列探查法 叔新有,盘 张 1.线性探查 可能产生的问题—一聚集 基本思想: “聚集 a(clustering 或称为 a表军{到接劉位下整存也垩么 “堆积”) 探查下述地址单 散列地址不同的结点,争夺同 用于简单线性探查的探查函数是 后继散列地址 线性探查的优点 ■小的聚集可能汇合成大的聚集 表中所有的存储位置都可以作为插入新记录 导致很长的探查序列 订恤 张铭趣 张帖 散列表示例 改进线性探查 M=15, h(key= key%o13 在理想情况下,表中的每个空槽都应该有 ■每次跳过常数C个而不是1个槽 同的机会接收下一个要插入的记录 ■探查序列中的第玠槽是h(+ 下一条记录放在第11个植中的概率是2/15 ic mod M 放到第7个着中的概率是11/15 基位置相邻的记录就不会进入同 一个探查序列了 探查函数是p(K,)=f 2625 华须使常数c与M互素 学恤息 权新有,种 张帖15 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 85 探查序列 „ 插入和检索函数都假定每个关键码 的探查序列中至少有一个存储位置 是空的 „ 否则可能会进入一个无限循环中 „ 也可以限制探查序列长度 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 86 几种常见的闭散列方法 „ 1. 线性探查 „ 2. 二次探查 „ 3. 伪随机数序列探查 „ 4. 双散列探查法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 87 1. 线性探查 „ 基本思想： „ 如果记录的基位置存储位置被占用，那么就 在表中下移，直到找到一个空存储位置。 „ 依次探查下述地址单元：d+1，d+2，......， M-1，0，1，......，d-1 „ 用于简单线性探查的探查函数是： p(K，i) = i „ 线性探查的优点 „ 表中所有的存储位置都可以作为插入新记录 的候选位置 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 88 可能产生的问题——聚集 „ “聚集”（clustering，或称为 “堆积”） „ 散列地址不同的结点，争夺同一 后继散列地址 „ 小的聚集可能汇合成大的聚集 „ 导致很长的探查序列 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 89 散列表示例 „ M = 15, h(key) = key%13 „ 在理想情况下，表中的每个空槽都应该有 相同的机会接收下一个要插入的记录 „ 下一条记录放在第11个槽中的概率是2/15 „ 放到第7个槽中的概率是11/15 0 1 2 3 4 5 6 7 8 9 10 12 13 14 26 25 41 15 68 44 6 36 38 12 51 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 90 改进线性探查 „ 每次跳过常数c个而不是1个槽 „ 探查序列中的第i个槽是(h(K) + ic) mod M „ 基位置相邻的记录就不会进入同 一个探查序列了 „ 探查函数是p(K，i) = i*c „ 必须使常数c与M互素