DS09散列查找b.pptVIP

* 第5章 散列查找 §5.4 处理冲突的方法 ? 开放定址法（Open Addressing） 【定义】所谓开放定址法，就是一旦产生了冲突，即该地址已经存放了其它数据元素，就去寻找另一个空的散列地址。 ? 若发生了第 i 次冲突，试探的下一个地址将增加di，基本公式是： hi(key) = (h(key)+di) mod TableSize ( 1≤ i TableSize ) （公式5.10） ? di 决定了不同的解决冲突方案：线性探测、二次探测、双散列。 ? 处理冲突的方法 常用的处理冲突的方法有两种：开放定址法和链地址法。 在没有装满的散列表中， 空的散列地址是否总能找到？ di = i di = ± i2 di = i*h2(key) 1. 线性探测法（Linear Probing） 第5章 散列查找 §5.4.1 开放地址法 ? 即线性探测法以增量序列 1，2，……，（TableSize -1）循环试探下一个存储地址。 [例5.6] 设关键词序列为 {47，7，29，11，9，84，54，20，30}， ? 散列表表长TableSize =13， ? 装填因子 α = 9/13 ≈ 0.69； ? 散列函数为：h(key) = key mod 11。 ?用线性探测法处理冲突，列出依次插入后的散列表， ? 并估算查找性能。 关键词 (key) 47 7 29 11 9 84 54 20 30 散列地址 h(key) 3 7 7 0 9 7 10 9 8 第5章 散列查找 地址 操作 0 1 2 3 4 5 6 7 8 9 10 11 12 说 明 插入47 47 无冲突 插入7 47 7 无冲突 插入29 47 7 29 d1 = 1 插入11 11 47 7 29 无冲突 插入9 11 47 7 29 9 无冲突 插入84 11 47 7 29 9 84 d3 = 3 插入54 11 47 7 29 9 84 54 d1 = 1 插入20 11 47 7 29 9 84 54 20 d3 = 3 插入30 11 30 47 7 29 9 84 54 20 d6 = 6 “一次聚集（Primary Clustering）”现象：需要经过很多次冲突才找到空位置。 表5.9　线性探测法构建散列表的过程 关键词 (key) 47 7 29 11 9 84 54 20 30 散列地址 h(key) 3 7 7 0 9 7 10 9 8 冲突次数 0 0 1 0 0 3 1 3 6 §5.4.1 开放地址法 问题：如何删除关键字 “7”？ ? 在散列表中查找数据对象的平均查找长度（ASL）。分成成功查找的ASL(ASLs)和不成功查找的ASL (ASLu) 。 第5章 散列查找 【分析】ASLs：假设要查找的关键词一定在散列表中存在。只要对查找表中的每个关键词的比较次数加起来，除以关键词的个数，就得到平均每个关键词的查找长度。而每个关键词的比较次数是其冲突次数加1。 ASL s= （1+7+1+1+2+1+4+2+4）/ 9 = 23/9 ≈ 2.56 H(key) 0 1 2 3 4 5 6 7 8 9 10 11 12 key 11 30 47 7 29 9 84 54 20 冲突次数 0 6 0 0 1 0 3 1 3 【分析】ASLu：假设要查找的关键词一定不在散列表中，并且所有关键词对应的散列地址均匀分布在地址空间上。每个地址的探测次数加和/地址空间大小就是ASL u（插入元素的ASL） ： ASL u= （3+2+1+2+1+1+1+9+8+7+6+5+4）/ 13 = 50/13 ≈ 3.85 散列表： §5.4.1 开放地址法 2. 平方探测法（Quadratic Probing） ? 即平方探测法以增量序列12，-12，22，-22，……，q2，-q2且q ≤ ?TableSize/2? 循环试探下一个存储地址。 第5章 散列查找 [例5.7] 设关键词序列为 {47，7，29，11，9，84，54，20，30}， ? 散列表表长TableSize = 11（即满足4×2+3形式的素数）， ?装填因子 α = 9/11 ≈ 0.82； ? 散列函数为：h(key) = key mod 11。 ? 用平方探测法处理冲突，列出依次插入后的散列表， ? 并估算ASLs。 有定理显示：如果散列表长度TableSize是某个4k+3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间。 关键词 key 47 7 29 11 9 84 54 20 30 散列地址h(key) 3 7 7 0 9 7 10 9 8 §5.4.1