=2-6 2-26 (7) 公式(7)告诉我们，对开放定址而言，只要6=”为一固定的小于1的常数，那么 m 不论表长m为多大，其平均查找长度A1(m,n)总小于一个定值：？226。 例如，取6=0.8时， A:m,08m)<222408=6号=3 (8) 所以，人们在使用开放定址HASH技术时，通常取6=0.8，其理论根据也就在公式(7) 和(8)：。这是一个重要的结论：不管表有几千几万项，只要充满程度6=0.8，用开放龙 址法查找表中一项，平均说来，查找3次即可成功。 当6=1时，由公式(4) A1(m,m)+∞（当m→∞) (9) 但是，对链溢出HASH表来说，即使6=-”=1由公式(6)，即得： m A2(m,m)=1+m,1<1.5 (10) 2m 对于公式(8)，(9)，计算机模拟试验的结果也作了有力的支持。由于链溢出HASH表 的平均查找长度理论公式简洁，模拟试验结果也较单调划一，前人已做过，故在此不予列 出。 作者感谢北京钢铁学院计算机中心所给予的方便和支持。 参考文献 (1 F.R.A.Hopgood,Compiling Techniques,1970. (2]D.E.Knuth:The Art of Computer programming.Volu:ne 3/Sorting and Searching.1973 (3)E.Horowitz and S.Sahni; Fundamentals oq Data Structures.1976. 〔4〕姚诗斌：数据库系统基础。计算机工程与应用，1981年第8,9.10、 〔5〕冯克清：数据结构，北京钢铁学院内部讲义。 188么一 已 一 公式 ‘ ， 告诉我 们 ， 对开放定址而 言 ， 只要‘ 盒 为一 固定的小于 的 常 数 ， 那 么 不论表长 为多大 ， 其平均查找长度 ， 总小于 一 个定 值 一 一 例如 ， 取 。 时 ， ， 。 一 。 一 关 。 昭 二 一 所 以 ， 人们在使用开放定址 技术时 ， 通常取 ， 其理论 根据也 就在 公 式 和 。 这是一 个重要 的结论 不管表有几 千几万 项 ， 只 要充满程度 ， 用 开 放 定 址法查找表中一项 ， 平均说来 ， 查找 次即可成功 。 当 时 ， 由公式 ， ， ， 当 ， 但是 ， 对链滋出 表来说 ， 即使 ‘ 一 盘 ‘ 由公 式 ， ， 即 得 ， 二 一 。 对于 公式 ， ， 计算机模拟试验的结果也作 了有力的支持 。 由于链 溢出 表 的平均查找长度理 论 公式简洁 ， 模拟试 验 结果也较单调 划一 ， 前人 已做过 ， 故在此不 予 列 出 。 作者感谢北京钢铁学院计算机 中心所给予的方便和支持 。 参 考 文 献 〔 〕 。 。 ， 〔 〕 。 。 〔 〕 “ 〔 〕 姚诗斌 数据库系统基础 。 计算机工程 与应 用 ， 年第 期 ， 〔 〕 冯克清 数据结构 ， 北京钢铁 学 院内部讲 义 。 甸 吕