D0I:10.13374/j.issn1001053x.198M.01.031 北京钢铁学院学报 1984年第1期 HASH表查找效率的讨论和验证 2 软件工程教研室 冯克清曾绍良 摘 要 HAS造表、查表方法广泛而有效地应.用于计算机基本软件和应用软件的 设计中，尤其在计算机的数据处理和数据库技术中，更为如此。本文使用初等的 数学方法对这种先进的查找技术的效率一表平均查找长度A进行了理论上的讨 论，同样得到了前人已经得到的两个理论计算公式。此外，我们还在M-150计算 机上做了随机模拟试验，得到了一系列试验结果，支持和验证了理论的正确性。 一、两种HASH造表、查表方法 设有个表项T(K),其中K为表项T中的一个栏目，由它可唯一地标别出一个表项T, 我们称K为表项T的关键字(KEY)。例如，某班学生成绩表的一个表项可以是如下格式： 学 学生姓名 政 治 程序设计 数据结构 数据岸 那末，其中的栏目：“姓名”，如果无重名时，可为该表项的关键字。当然， “学号”也 可以为关键字。 今欲将个表项组织到m个位置编号为1到m的连续存贮单位中去，这就是造表。 设n≤m。并且假定已找到了一个定义于 2,{K}上的映象函数H(K),满足： ①H(K)为整函数，且1≤H(K)≤m,当K∈2时。 ②对于任何的K∈2，H()均匀地分布于〔1，m)之中。 于是，任取-一项T(K*),通过映象函数H(K),均可得到一个介于1和m之间的位置 H(K),自然，我们可以将T(K*)存放在H(K◆)位置上。但是，尽管有n≤m,但由于 H(K)的随机性，完全有可能对于T(K),K+K*,而H(《)=H(*衣)。这样将有两个（或 两个以上)互不相同的项T映象到同一个位置，这就称之为“冲突”。为解决“冲突”， 可以采用以下两种HASH造查表方法： 1.开放定址HASH方法。 ∧)造表算法： ①i=H(K),/*K为欲登入的项T的关键字/. ②IFP(i)=empty THEN {enter T(K)in P(i);RETURN} 183北 京 钢 铁 学 院 学 报 年 筑 翔 表查找效率的讨论和验证 软 件工 程教研室 冯 克 清 曾绍 良 摘 要 造 表 、 查 表方法广泛 而有效地应 用 于计算机基本软件和应 用软件 的 设 计 中 ， 尤 其在计算机 的数据处 理和 数据库 技 术 中 ， 更 为如此 。 本文使用初等的 数学 方法 对 这 种先进 的查找 技术 的效率一 表平均查找 长度 进行 了理 论 上 的 讨 论 ， 同样得 到 了前人 已 经得到 的两个理 论计算公式 。 此 外 ， 我们 还在 一 计算 机上做 了随 机模拟试验 ， 得 到 了一 系 列试验 结果 ， 支持和验证 了理论 的正 确性 。 一 、 两种 造表 、 查表方法 设有 个表项 ， 其中 为 表项 中的一 个栏 目 ， 由它可唯一 地标别 出一 个表项 ， 我们称 为表项 的关键字 。 例如 ， 某 班学生 成绩表的一个表项可 以是如下格式 学 号 学生 姓 名 政 治 程序设计 数据结构 数 据 库 那 末 ， 其中的栏 目 “ 姓名” ， 如果 无重名 时 ， 可 为该表项的关键字 。 当然 ， “ 学号 ” 也 可 以为关键字 。 今欲将 个表项组织 到 个位置 编号 为 到 的连续存贮单位 中去 ， 这就是 造表 。 设 《 。 并且 假定 已找到 了一 个定 义 于 的映 象函 数 ，满足 ① 为整 函 数 ， 且 镇 ， 当 〔 时 。 ② 对 于任何的 任 ， 二 均匀地 分布于 〔 ， 〕 之 中 。 于是 ， 任 取一 项 ， 通 过 映象函数 ， 均可得到一 个 介于 和 之 间 的 位 置 中 ， 自然 ， 我 们可 以将 存放在 位置上 。 但是 ， 尽管 有 ， 但 由 于 的随机性 ， 完全有 可能对 于 ， 钾 ， 而 又 又 。 这 样将有两个 或 两个 以上 互不 相 同的项 映象到 同一 个位置 ， 这就称 之 为 “ 冲 突” 。 为解 决 “ 冲突” ， 可 以采用 以下两种 造查表方法 开放定址 方法 。 造表算法 ① ， 为欲登入的项 的关键字 ， ② ， DOI ：10．13374／j ．issn1001－053x．1984．01．031