数据结构与算法分析第9章.ppt

数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星第9章检索9.1检索已排序的数组9.3集合的检索9.4散列方法散列方法对按关键码进行检索，效率非常高。
但不适用于：
允许多条记录有相同关键码的应用程序。
不适用于范围检索。
检索最大或最小的关键码。
按关键码的顺序访问记录。
散列允许关键码范围中的值比散列表中的槽多。
冲突：两个或多个不同关键码通过散列函数映射到散列表的
同一个槽。
对于一个散列函数h和两个关键码值k1,k2,如果
h(k1)=β=h(k2)，其中β是表中的一个槽。
采用散列方法检索关键码值K的步骤：
根据散列函数h计算在散列表中的位置h(K)。
使用冲突解决策略找到包含关键码值K的记录。
散列函数例9.8用于字符串的散列函数
inth(char*x){
inti,sum;
for(sum=0,i=0;x[i]!='\0';i++)
sum+=(int)x[i];
return(sum%M);
}
原理：折叠法。累加字符串中所有字母的ASCII值，再对M（槽的数量）取余数。
分析：散列函数值与关键码值的每一位都有关系。如果M较小，随机性较大，如果M较大，则随机性不足，可能会产生一个差的分布。9.4.2开散列方法9.4.3闭散列方法线性探查
“经典”形式的散列方法：
原理：如果某记录的基位置已被占用（发生冲突），由冲突解决策略在散列表中产生下一个存放记录的槽。如果下一个槽仍被占用，则由冲突解决策略产生再下一个槽，直到有空槽为止。
由冲突解决策略产生的一组槽称为探查序列，由探查函数P(K,i)产生。
例如：关键码K对应的基位置为home，如果home已被占用，则该记录移动到home+P(K,1),如果仍被占用，则移动到home+P(K,2)…..，直到找到一个空槽为止。线性探查
简单线性探查：P(K,i)=mod(i,M)
如果基位置已被占用，则从基位置出发向后依次寻找空槽。
线性探查可能出现基本聚集现象，即关键码探查序列的某些段重叠在一起。
改进的冲突解决方法（为避免基本聚集）
仍线性探查，但跳过多个槽。即
P(K,i)=mod(i＋C,M)
C与M互素，以便可以走遍所有的槽。
随机地选择下一个槽。即
P(K,i)=mod(Random（i）＋C,M)
Random(i)为一个伪随机序列。二次探测
不同基位置的两个关键码具有叉开的探查序列
例：P(K,i)=mod(i2,M)
伪随机探查和二次探查能消除基本聚集，但存在二次聚集。
概念：两个关键码散列在同一个基位置，则它们会有相同的探查序列。
解决方法：探查序列是关键码值的函数，而不是基位置的函数。
如仍采用线性探查，P(K,i)=i*h(K)
又称为双散列方法设散列表容量为7（散列地址空间0~6），给定表（30，36，47，52，34），散列函数H(k)=kmod6。(1)请采用线性探测法来构造散列表；(2)求查找数34所需要的比较次数。设散列表容量为7（散列地址空间0~6），给定表（30，36，47，52，34），散列函数H(k)=kmod6。(1)请采用线性探测法来构造散列表；(2)求查找数34所需要的比较次数。闭散列方法分析
成功检索和删除的时间代价一样，而不成功检索和插入的时间代价一样。前者时间代价低于后者。
如果不存在冲突（所有记录都存储在它的基位置），则检索、插入和删除操作都只需一次记录访问。
冲突越多，操作所需的访问次数越多。
冲突发生的概率同表填充程序成正例，由负载因子a=N/M表示，其中N为记录数，M为表中槽数。
在散列表中槽随机排列（不存在聚集）条件下，线性探查的
插入和不成功检索的平均代价：
删除和成功检索的平均代价：填充因子a<0.5，散列方法的代价好于二分法检索(logn)。
当a>0.5后，散列方法的时间代价随a增大而急剧恶化。
为减小访问代价，可以对记录沿着探查序列按访问频率排序，即访问频率最高的记录放在基位置。删除
从散列表中删除记录应考虑：
不能影响后面的检索。
删除的位置可再利用。
解决方法：在被删除记录的位置上置一个特殊标记（墓碑）。
为减少墓碑：
删除时进行一次局部重组。
定期重新散列整个表。