m3+60 5=1+是+品+ m 如 51=1+2=1D+3--2》-+…+.i!i=12,…n) 2m 2m2 2mi-1 使用数学归纳法，易于证明： ◇ S1=n+ a-)+n(a-a-2》-+…+ n! 2m2 2m4-i (3) i=1 2m 成立。 由(2)，(3)式得知，对开放定址法而言，其平均查找长度A,的理论计算公式 为： A1(m,)=1+(a-1)+(a-1D(a-2》+…+-（n-)1 (4) 2m 2m2 2ma-1 2,链溢出HASH法平均查找长度的讨论 按链溢出HASH法的造表算法，对于第一个登入HASH表的项，有： S1=1 对第二个登入表的项，考虑到可能引起冲突和拉链，将有： S2=mm1*1+品*2 m 对于第三、第四…登入HASH表的项，将依次有： 5,=(m=*1+2(m2D*2+日2*3 m2 m*1+C%1(m-1)-2 S1=C:.1（m-1)i-」 mi产 米2+…+C-1-1 (m-1)0 mi-i 米i (i=1,2,…n) 对于S:,我们不难用数学归纳法证明下式成立： S1=1+i-1(i=1,2,…n) (5) m 由(2)和(5)式，得链溢出HASH法的平均查找长度A2的理论公式为： (1+）1* A2(m,)=是 (6) 186宁 一 一 一 一 一 一 一 ， ， … 使用数学归纳法 ， 易于证明 刃 ， 一 一 一 二 。 一 成立 。 由 为 式得知 ， 对开放定址法而言 ， 其平均查找长度 ，的 理 论 计 算 公 式 一 ， 丝二卫 一 一 。 。 。 一 一 链滋出 法平均查找长度的讨论 按链 溢 出 法的造表算法 ， 对于第一 个登入 表的项 ， 有 一 对第二个登入表的项 ， 考虑到可能引起冲突和 拉链 ， 将有 一 常 十 － 常 ‘ 对于第三 、 第四 … 登入 表的项 ， 将依次有 八 来 一 一 带 ， 卜 一 卜 一 带 卜 一 卜 ，一 来 … 十 卜 ’ 一 “ 一 ， ， … 对于 ， 我们不难用数学归纳法证明下式成立 一 ， ， … 由 和 式 ， 得链滋出 法 的平均查找 长度 的理论公式为 工 一 ‘了、， ， 二 二 万 一 了‘、 占 一竺二