HASH表查找效率的讨论和验证

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

ELSE{i=i+1(modm),GOTO②}/*P(i)为表的第i个位置*/ 重复执行上述算法n次，即可将n项数据登入表内。 B)查表算法： ①i=H(K),/K为欲从HASH表中查找的项T的关键字*/ ②IFP(i)=empty THEN Print failure,RETURN ELSE IF P(i)=T(K) THEN (GET P(i);RETURN) ELSE {i=i+1(modm):GOTO} /查表时，要求n<m*/ 2.链溢出HASH方法 表项格式设计为，DATA NEXT POINTER. 除了准备有1到m的m个连续编址的 存贮单位外，还需另辟一个供溢出拉链用的区域，并组织成单向链表的形式，其链头以指 针FREE指示。首先将l到m个存贮位置全部清零，各NEXT域置nuI1'。 A)造表算法： ①i=H(K)/K为欲登入项T的关键字，i为一指针/ ②IFi-→NEXT=nuII'THEN .(i-DATA=T(K); i-+NEXT=full',/*ful'为链的结束标志◆/ RETURN}/i+NEXT为i指针所指项的NEXT域，i+DATA一 DATA域/ ③1)FREE+DATA=T(K), 2)TEMP=FREE,/TEMP为一工作指针*/ 3)FREE-FREE→NEXT, 4)TEMP-NEXT=i-NEXT 5)i-NEXT=TEMP; 6)RETURN/*③完成在溢出链上扦入一项的工作/ 以上过程执行n次即造好了一张“外链滥出”HASH表。当n≤m时，显然，造完表时， HASH表的1到m个连续位置上将有若干空白，故可将拉链到滥出区的项，组织到这些空 白位置。这样鉴理后的表叫“内链褴出”HASH表。很明显，内链溢出HASH表较外链 溢出HASH表节约存贮。 B)查表算法， ①i=H(K)/K为欲查项的关键字/ ②IFi-→NEXT='nulI'THEN Print failure;RETURN ③IFi+DATA=T(K)THEN {GETi→DATA,RETURN} ELSE (i=i-NEXT; 184

一 ② 为表的第 个位置 重 复执行上述算法 次 ， 即可将 项数据登入表内 。 查表算法 ① ， 为欲从 表中查找的项 的关键字 ② 二 ， ， ， ② 查表时 ， 要求 。 链 溢出 方法 表项 格式设计为 ， ” 叫 “ ‘“ “ 卜除了准备有‘到 的 个连续编址 的 存贮单位外 ， 还需另辟一 个供溢 出拉链用 的区域 ， 并组织成单 向链表的形式 ， 其链头 以指 针 指示 。 首先将 到 个存贮位置全部清零 ， 各 域置 、 尹 。 造表算法 ① ， 为欲登入项 的关键字 ， 为一 指针 ② ， ‘ 尹 ， 多 ， 、 ‘ ， 、 ‘ 为链的结束标志 ， 为 指针所指项的 域， ， 一 域 ③ ‘ ， ， 为一 工作指针 ， ， ， ， ， ， ⑧完成在溢 出链上扦入一项 的工作 以上 过程执行 次即造好 了一张 “ 外链溢 出” 表 。 当 时 ， 显然 ， 造 完 表 时 ， 表的 到 个连续位置上将有若千 空 白 ， 故可将拉链到溢 出区 的项 ， 组织到这 些 空 白位置 。 这样整 理后 的表 叫 “ 内链滋 出” 表 。 很 明显 ， 内链溢 出 表较 外 链 溢 出 表节约存贮 。 查 表算法 ， ① 为欲查项的关键字 ② ， “ ， 、 ， ， ③ ， ， ，

IF i=full/THEN {Print failure';RETURN ELSE GOTO③} 二、HASH表查找效率讨论 定义1. 为要在表中找到一特定表项T(K)而需要访问表中的项的次数称为查找T(K)项的查 找长度，记为S。 显然某项的查找长度S与表的组织方式、查找方法及该项在表中的位置有关。 定义2. 为要查找表中的任意一项，平均说来，需要访问表项的次数称为平均查找长度，记 为A。 显然，平均查找长度A与表的组织方式、表的长度、查找方法以及表中各项被查找的 频率有关。可见，平均查找长度A是衡量查找方法的查找效率高低的尺度。按定义知， A=∑P*S (1) i=1 其中：n为实际表中的项数 P:为T项被查找的概率，自然∑P=1 i=1 S为查找T项的查找长度。 今假定，表中各项被查找的概率相同（即均为），则(《1)式将变成： 11 A=1∑S (2) n i=1 1.开放定址HASH法平均查找长度的讨论 按开放定址法造表的算法，在假定了映象函数H(K)能将T(K)均匀地映象到1到m个 位置上后，对于第一个登入HASH表的项，有： S1=1 对于第二个登入HASH表的项，考虑到可能的冲突和引起表项的下移后，有： S2=1+1 m 对于第三个、第四个…登入HASH表的项，有： Sg=1+2+3 m 5=1*品+品+将 m 185

、 ， 毛 、 ， ， ⑧ 二 、 表查找效率讨论 定 义 为要在表 中找 到一特定表项 而需要访 间表中的项 的次数称为查找 项 的 查 找长度 ， 记 为 。 显 然某项 的查找 长度 与表的组织 方式 、 查找方法及该项在表中的位置有关 。 定义 。 为要查 找表 中的任意一 项 ， 平均说来 ， 需要访问表项 的次数称为平均 查 找 长 度 ， 记 为 。 显 然 ， 平均查找长度 与表的组织 方式 、 表 的长度 、 查找方法 以及表中各项被查找 的 频率有关 。 可见 ， 平均查找长度 是衡量 查找方法的查找效率高低 的尺度 。 按定义知 茗 一 ‘ 其中 为实际表中的项数 为 ‘项被查找的概率 ， 自然 刃 。 伪查找 项的查找长度 。 今假定 ， 表 中各项被查找 的概率相同 ‘即 均 为 十 ， 则 ‘ ， 式 将变成 二 刃 。 开 放定址 法平均查找长度 的讨论 按开 放定址法 造表的算法 ， 在假定 了映象函数 能将 均 匀地映象到 到 个 位置上后 ， 对 于第一 个登入 表的项 ， 有 一 对于第二个 登入 表的项 ， 考虑到可能 的冲 突和引起表项 的下 移后 ， 有 二 对于第三个 、 第 四 个 … 登入 表的项 ， 有 上 自 ﹄月 ︸ 口一 一切 。 ‘ 宁 － 十 二 」十 －

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

宁 一 一 一 一 一 一 一 ， ， … 使用数学归纳法 ， 易于证明 刃 ， 一 一 一 二 。 一 成立 。 由 为 式得知 ， 对开放定址法而言 ， 其平均查找长度 ，的 理 论 计 算 公 式 一 ， 丝二卫 一 一 。 。 。 一 一 链滋出 法平均查找长度的讨论 按链 溢 出 法的造表算法 ， 对于第一 个登入 表的项 ， 有 一 对第二个登入表的项 ， 考虑到可能引起冲突和 拉链 ， 将有 一 常 十 － 常 ‘ 对于第三 、 第四 … 登入 表的项 ， 将依次有 八 来 一 一 带 ， 卜 一 卜 一 带 卜 一 卜 ，一 来 … 十 卜 ’ 一 “ 一 ， ， … 对于 ， 我们不难用数学归纳法证明下式成立 一 ， ， … 由 和 式 ， 得链滋出 法 的平均查找 长度 的理论公式为 工 一 ‘了、， ， 二 二 万 一 了‘、 占 一竺二

三、统计试验结果的支持 为了验证开放定址法和链溢出HASH的平均查找长度理论计算公式(4)和(6)的 正确性，作者曾在计算机上多次模拟这两种HASH法的造表、查表过程，并统计计算其 平均查找长度，获得了一批试验结果。下表即是多次试验结果中的一组，它指明了开放定 址法在各种情况下的理论平均查找长度A1(m,n)和模拟统计平均查找长度A1(m,n)的 对照。 表1 开放定址HASH法 6= n 0,1 0.2 0,3 0.4 0.5 0.6 0.7 0.8 0,9 :1.00 1.04250 1.10668 1,18752 1.292161.432301.62821 1.917602.377073.17968 4.77155 50 Ar 1.028001.10400 1,17133 1.27199 1.3967911.55833 1,77056 2.146992.801544.04135 Ar 1.04886 1,115551.20034 1.311581.46345 1.682042.02001 2.598363.747066.60495 100 Al 1.04900 1.099991.17633 1,27849 1.41279 1.58683 1.854142.30549 3.148645.59984 1.054191.1230611.21139 1.328761,49214 1,734852,131642.889354.8204914.34804 500 A: 1.056791.12059 1.21033 1.330391.50147 1,74529 2.138282.80270 4.2189712.97143 A 1,054871.12402 1.212831.33103 1,49603 1.74229 2,148662.941415.1013620.15067 1000 1.053691.12574 1.22329 1.342021,50215 1.741362,152482.897564.6585219,17783 Al 1.055421.124801.21399 1.332851.49919i1.74843 2.162962.987645,4052444.64273 5000 1.054571.123751,211551.327741.491401.72961 2,13004 2.91936;5.2952245,19316 表1的结果充分地支持了理论计算公式(4)是正确的。理论公式(4)和(6)在国外 文献中均已见过，在这里我们只是给出了理论上的初等证明。 关于开放定址法的平均查找长度A1(m,n)计算公式还可以得到一个上界。例如， 令6=D,称6为HASH表的充满程度，则我们有： m A1(m,n)=1+.-1.+(n-1)(-2)++_（-1)1 2m 2m2 2m-1 <1+”+, 2m 2m2+…+n-1 2m-+ 2+、62 =1+6 2+…+61 2 187

三 、 统计试验结果的支持 为 了验证开放定址法和链溢出 的平均查找长度理论计 算 公 式 和 的 正确性 ， 作者曾在计算机上多次模拟这两种 法的造表 、 查 表过程 ， 并统计 计 算 其 平均查 找长度 ， 获得了一 批试验结果 。 下 表 即是多次试验结果中的一 组 ， 它指 明 了开 放定 址法在各种情况下 的理论 平均查 找长度 ， 和模拟统计平均查找长度 ， 的 对照 。 表 开放定址 人 法 气 一 一， 一 … … … 、 、 一 皿 ” · …” · …“ · “ · ” · “ ” · “ 。 · 了 。 · 。 · “ ’ · 一 、 ︸﹄ 了，口 山己三 曰七 一﹄勺︸ …二 人 …暨…些色 · “ 了 · “ “ 了 … 王坐· ‘ …哩· ‘ 、 · · ‘ 。 。 丽而而万 缨 少竺 、 ， · ‘ 。 · 。 。 。 二 一 。 。 · ” · ‘ 爪石石 孟 · 竺吧 二卫 一 … ’ 。 ‘ ” · ” “ ， · “ “ · “ 。 · · 。 ‘ ，‘ … 。 · 。 右心一注一一魂 ︸ 一仲了召 ﹄加一︸众马孟︷月 刁石︷一 一山，臼，山，，‘，二 一职。， 卜 。 · 魂 · · 。 。 。 全生 ‘ · 。 ” ‘ 毛些竺竺 ， … · “ ‘ ” … ， · “ 了 。 。 。 · · · 」 · ‘ · “ ‘ · ‘ · ‘ ‘ … ‘ · 了 ‘ 。 。 。 … “ · ’ ‘ 表 的结果充分地支持 了理论计算公式 是正确的 。 理论 公式 和 文 献中均 已见 过 ， 在这里我们只是 给出 了理论上的初等证明 。 关于 开放定址法 的平均查找 长度 ，幻 计算公式还可 以 得到一 个上 界 。 在国外 例 如 ， ‘尸叮 令 不 一， 称 为 表的充满程度 ， 则我们 有 一 ， 一卫二， ， 一 一 一 勺 一 一 乒乙】 十 一 一 一 。 · 。 十 － 十 一 。 。 一 。 。

=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

么一 已 一 公式 ‘ ， 告诉我 们 ， 对开放定址而 言 ， 只要‘ 盒 为一 固定的小于 的 常 数 ， 那 么 不论表长 为多大 ， 其平均查找长度 ， 总小于 一 个定 值 一 一 例如 ， 取 。 时 ， ， 。 一 。 一 关 。 昭 二 一 所 以 ， 人们在使用开放定址 技术时 ， 通常取 ， 其理论 根据也 就在 公 式 和 。 这是一 个重要 的结论 不管表有几 千几万 项 ， 只 要充满程度 ， 用 开 放 定 址法查找表中一项 ， 平均说来 ， 查找 次即可成功 。 当 时 ， 由公式 ， ， ， 当 ， 但是 ， 对链滋出 表来说 ， 即使 ‘ 一 盘 ‘ 由公 式 ， ， 即 得 ， 二 一 。 对于 公式 ， ， 计算机模拟试验的结果也作 了有力的支持 。 由于链 溢出 表 的平均查找长度理 论 公式简洁 ， 模拟试 验 结果也较单调 划一 ， 前人 已做过 ， 故在此不 予 列 出 。 作者感谢北京钢铁学院计算机 中心所给予的方便和支持 。 参 考 文 献 〔 〕 。 。 ， 〔 〕 。 。 〔 〕 “ 〔 〕 姚诗斌 数据库系统基础 。 计算机工程 与应 用 ， 年第 期 ， 〔 〕 冯克清 数据结构 ， 北京钢铁 学 院内部讲 义 。 甸 吕

DISCUSSION ABOUT SEARCHING EFFICENCY ON HASH TABLE Feng Ke qing,Zeng Shao liang BRIEF HASH TABLES are widely and efficentey used for designing a variety of software in Computers,and in special for data processing and data base system. The efficency of the advenced Searching technology-the average Searc- hing time on the table,A is discussed in theory in this paper.Two theore- tic formulas is given and a random on-line test is done using the Computer M-150.The theoretic correctenss is proved by a lot of result obtained. 189

， ， 一 。 一 ， 。 一 一 。 丁 。 瓦、 盯 价 夕