PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

记伍
6 years ago
Views:

数据结构与算法 ( 十 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008.

1 数据结构与算法 ( 十 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社, ( 十一五国家级规划教材 )

2 10.1 线性表的检索第十章检索 10.1 线性表的检索 10.2 集合的检索 10.3 散列表的检索总结 2

3 散列检索散列中的基本问题散列函数碰撞的处理开散列方法闭散列方法闭散列表的算法实现散列方法的效率分析 3

4 闭散列表的算法实现字典 (dictionary) 一种特殊的集合, 其元素是 ( 关键码, 属性值 ) 二元组关键码必须是互不相同的 ( 在同一个字典之内 ) 主要操作是依据关键码来插入和查找 bool hashinsert(const Elem&); // insert(key, value) bool hashsearch(const Key&,Elem&) const; // lookup(key) 4

5 散列字典 ADT( 属性 ) template <class Key,class Elem,class KEComp,class EEComp> class hashdict { private: Elem* HT; // 散列表 int M; // 散列表大小 int currcnt; // 现有元素数目 Elem EMPTY; // 空槽 int h(int x) const ; // 散列函数 int h(char* x)const ; // 字符串散列函数 int p(key K,int i) // 探查函数 5

6 散列字典 ADT( 方法 ) public: hashdict(int sz,elem e) { // 构造函数 M=sz; EMPTY=e; currcnt=0; HT=new Elem[sz]; for (int i=0; i<m; i++) HT[i]=EMPTY; } ~hashdict() { delete [] HT; } bool hashsearch(const Key&,Elem&) const; bool hashinsert(const Elem&); Elem hashdelete(const Key& K); int size() { return currcnt; } // 元素数目 }; 6

7 插入算法散列函数 h, 假设给定的值为 K 若表中该地址对应的空间未被占用, 则把待插入记录填入该地址如果该地址中的值与 K 相等, 则报告散列表中已有此记录否则, 按设定的处理冲突方法查找探查序列的下一个地址, 如此反复下去直到某个地址空间未被占用 ( 可以插入 ) 或者关键码比较相等 ( 不需要插入 ) 为止 7

8 散列表插入算法代码 // 将数据元素 e 插入到散列表 HT template <class Key, class Elem, class KEComp, class EEComp> bool hashdict<key, Elem, KEComp, EEComp>::hashInsert(const Elem& e) { int home= h(getkey(e)); // home 存储基位置 int i=0; } int pos = home; while (!EEComp::eq(EMPTY, HT[pos])) { if (EEComp::eq(e, HT[pos])) return false; i++; pos = (home+p(getkey(e), i)) % M; } HT[pos] = e; return true; // 探查序列的初始位置 // 探查 // 插入元素 e 8

9 与插入过程类似检索算法采用的探查序列也相同假设散列函数 h, 给定的值为 K 若表中该地址对应的空间未被占用, 则检索失败否则将该地址中的值与 K 比较, 若相等则检索成功否则, 按建表时设定的处理冲突方法查找探查序列的下一个地址, 如此反复下去关键码比较相等, 检索成功走到探测序列尾部还没找到, 检索失败 9

10 template <class Key, class Elem, class KEComp, class EEComp> bool hashdict<key, Elem, KEComp, EEComp>:: hashsearch(const Key& K, Elem& e) const { int i=0, pos= home= h(k); // 初始位置 while (!EEComp::eq(EMPTY, HT[pos])) { } if (KEComp::eq(K, HT[pos])) { e = HT[pos]; return true; } i++; pos = (home + p(k, i)) % M; } // while return false; // 找到 10

11 删除删除记录的时候, 有两点需要重点考虑 : (1) 删除一个记录一定不能影响后面的检索 (2) 释放的存储位置应该能够为将来插入使用只有开散列方法 ( 分离的同义词子表 ) 可以真正删除闭散列方法都只能作标记 ( 墓碑 ), 不能真正删除若真正删除了探查序列将断掉检索算法直到某个地址空间未被占用 ( 检索失败 ) 墓碑标记增加了平均检索长度 11

12 删除带来的问题 K1K2K1 K2K2K2 K2 例, 长度 M = 13 的散列表, 假定关键码 k1 和 k2, h(k1) = 2,h(k2) = 6 二次探查序列 k1 的二次探查序列是 k2 的二次探查序列是删除位置 6, 用 k2 序列的最后位置 2 的元素替换之, 位置 2 设为空检索 k1, 查不到 ( 事实上还可能存放在位置 3 和 1 上! ) 12

13 墓碑设置一个特殊的标记位, 来记录散列表中的单元状态单元被占用空单元已删除被删除标记值称为墓碑 ( tombstone ) 标志一个记录曾经占用这个槽但是现在已经不再占用了 13

14 带墓碑的删除算法 template <class Key, class Elem, class KEComp, class EEComp>Elem hashdict<key,elem,kecomp,eecomp>::hashdelete(const Key& K) { int i=0, pos = home= h(k); // 初始位置 while (!EEComp::eq(EMPTY, HT[pos])) { if (KEComp::eq(K, HT[pos])){ temp = HT[pos]; HT[pos] = TOMB; // 设置墓碑 return temp; // 返回目标 } i++; pos = (home + p(k, i)) % M; } return EMPTY; } 14

15 带墓碑的插入操作在插入时, 如果遇到标志为墓碑的槽, 可以把新记录存储在该槽中吗? 避免插入两个相同的关键码检索过程仍然需要沿着探查序列下去, 直到找到一个真正的空位置 15

16 带墓碑的插入操作改进版 template <class Key, class Elem, class KEComp, class EEComp> bool hashdict<key, Elem, KEComp, EEComp>::hashInsert(const Elem &e) { int insplace, i = 0, pos = home = h(getkey(e)); bool tomb_pos = false; while (!EEComp::eq(EMPTY, HT[pos])) { if (EEComp::eq(e, HT[pos])) return false; if (EEComp::eq(TOMB, HT[pos]) &&!tomb_pos) {insplace = pos; tomb_pos = true;} // 第一 pos = (home + p(getkey(e), ++ i)) % M; } if (!tomb_pos) insplace=pos; // 没有墓碑 HT[insplace] = e; return true; } 16

17 散列方法的效率分析衡量标准 : 插入删除和检索操作所需要的记录访问次数散列表的插入和删除操作都基于检索进行删除 : 必须先找到该记录插入 : 必须找到探查序列的尾部, 即对这条记录进行一次不成功的检索对于不考虑删除的情况, 是尾部的空槽对于考虑删除的情况, 也要找到尾部, 才能确定是否有重复记录 17

18 影响检索的效率的重要因素散列方法预期的代价与负载因子 α= N/M 有关 α 较小时, 散列表比较空, 所插入的记录比较容易插入到其空闲的基地址 α 较大时, 插入记录很可能要靠冲突解决策略来寻找探查序列中合适的另一个槽随着 α 增加, 越来越多的记录有可能放到离其基地址更远的地方 18

19 散列表算法分析 (1) 基地址被占用的可能性是 α 发生第 i 次冲突的可能性是 N( N 1) ( N i 1) M ( M 1) ( M i 1) 如果 N 和 M 都很大, 那么可以近似地表达为 ( N/M ) i 探查次数的期望值是 1 加上每个第 i 次 (i 1) 冲突的概率之和, 即插入代价 : i 1 ( N / M ) 1/(1 a) i1 19

20 散列表算法分析 (2) 一次成功检索 ( 或者一次删除 ) 的代价与当时插入的代价相同由于随着散列表中记录的不断增加,α 值也不断增大我们可以根据从 0 到 α 的当前值的积分推导出插入操作的平均代价 ( 实质上是所有插入代价的一个平均值 ): 1 a dx ln a 0 1x a 1a 20

21 散列表算法分析 ( 表 ) 编号冲突解决策略 1 开散列法 2 双散列探查法 3 线性探查法 1 成功检索 ( 删除 ) 2 不成功检索 ( 插入 ) ln e (1 ) 2 21

22 散列表算法分析 ( 图 ) 用几种不同方法解决碰撞时散列表的平均检索长度 3. 线性探测插入 2 双散列插入 3 线性 2. 双散列探测删除删除编号冲突解决策略 1 开散列法 2 双散列探查法 3 线性探查法 1 成功检索 ( 删除 ) 2 不成功检索 ( 插入 ) e 1 1 ln (1 ) 2 1. 开散列删除 1 开散列法插入 22

23 散列表算法分析结论 (1) 散列方法的代价一般接近于访问一个记录的时间, 效率非常高, 比需要 log n 次记录访问的二分检索好得多不依赖于 n, 只依赖于负载因子 α=n/m 随着 α 增加, 预期的代价也会增加 α 0.5 时, 大部分操作的分析预期代价都小于 2 ( 也有人说 1.5) 实际经验也表明散列表负载因子的临界值是 0.5( 将近半满 ) 大于这个临界值, 性能就会急剧下降 23

24 散列表算法分析结论 (2) 散列表的插入和删除操作如果很频繁, 将降低散列表的检索效率大量的插入操作, 将使得负载因子增加从而增加了同义词子表的长度, 即增加了平均检索长度大量的删除操作, 也将增加墓碑的数量这将增加记录本身到其基地址的平均长度实际应用中, 对于插入和删除操作比较频繁的散列表, 可以定期对表进行重新散列把所有记录重新插入到一个新的表中清除墓碑把最频繁访问的记录放到其基地址 24

25 思考是否可以把空单元已删除这两种状态, 用特殊的值标记, 以区别于单元被占用状态? 调研除散列以外字典的其他实现方法 25

26 数据结构与算法谢谢聆听国家精品课数据结构与算法张铭, 王腾蛟, 赵海燕高等教育出版社, 十一五国家级规划教材

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用