先给结论2010年这道408的第一道数据结构大题考的是散列表中最经典的计算题——给定一串关键字、一个散列函数、一张固定长度的散列表再用线性探测法解决冲突最后求等概率成功查找时的平均查找长度ASL。题目本身不难但它把散列函数、冲突处理、平均查找长度这三个核心考点全串起来了是408里少见的高性价比“送分题”也是很多人口算失误的重灾区。这篇就来把这道题从原理到步骤完整拆开再顺手解决掉一堆容易踩的坑。在我刷408真题的经历里散列表的题每年都会以各种形态反复出现而2010年这题之所以值得单独拿出来讲是因为它考得特别“干净”不涉及高阶设计不需要写代码就是纯粹的计算与理解。但如果对线性探测法的探测过程理解不到位或者对ASL的统计口径不熟悉这题很容易算出一个看起来“很有道理”的错误答案。下面就把这道题从头到尾过一遍顺便把散列表相关的复习要点也带出来。1. 这道题为什么值得反复琢磨1.1 一道统考元年的数据结构大题2010年是全国计算机学科专业基础综合408第一次正式统考这一年的题目对整个考研群体的复习方向影响很大。第41题作为数据结构部分的经典大题考的不是复杂的算法设计而是散列表的基本计算。很多同学第一次做这道题时会觉得“内容这么少能算个啥”结果一对答案才发现自己算出来的ASL和标准答案差着十万八千里。这道题在当年其实起到了“定调”的作用408的数据结构大题不一定要写很长的代码它是可以回归基础概念用计算题的形式来考察的。散列表题目也正是从这一年开始在之后的历年真题里频繁出现并且反复变着法子考一会儿让你算查找成功一会儿让你算查找失败一会儿换成链地址法一会儿又和其他知识点结合起来。所以把2010年这题吃透对后面复习散列表相关真题有很大帮助。1.2 题目到底在问什么先把题目完整梳理一遍。已知线性表382574635248采用散列函数 h(key) key % 7 计算散列地址并将这些关键字依次存入散列表 A[0..6] 中若采用线性探测法解决冲突则在该散列表上进行等概率成功查找的平均查找长度为多少。乍一看这题只有三句话但里面包含的信息量绝对不少。首先关键字有6个散列表长度是7装填因子是6/7已经是一个负载比较高的表了。其次散列函数用的是除留余数法模数是7正好和表长相等。最后冲突处理的方法是线性探测法也就是当位置被占用时逐个向后找空位一直到表尾再从头开始继续找。题目要求的结果是“等概率成功查找的平均查找长度”也就是ASL。这个指标衡量的是当我们知道某个关键字一定在表里然后从它的散列地址出发去查找平均要比较多少次才能找到。理解了这一点后面的计算才有方向。很多人容易把“成功查找”和“失败查找”混在一起这是第一个容易出错的地方后面我会专门讲。2. 散列表核心原理从“为什么需要”说起2.1 散列表的本质用空间换时间散列表也叫哈希表它的核心思想是建立一个从关键字到存储位置的映射关系让我们能够通过关键字直接计算地址而不需要像顺序查找那样一个个比较也不需要像有序表查找那样每次都折半。理想情况下散列表的查找时间复杂度可以做到O(1)这是其他查找结构很难做到的。打个比方你去一个巨大的图书馆找一本书如果图书馆没有任何索引系统你就只能一排一排地找但如果每本书都有一个唯一的索书号而索书号又能直接对应到书架位置那么你拿到书名的瞬间就能知道它大概在哪个区域。散列表做的事就是给每个关键字算出一个“索书号”散列地址然后直接去这个地址找。但问题在于不同的关键字经过散列函数计算后可能会得到相同的地址。比如这题里的25和7425 % 7 474 % 7 4它们俩都指向位置4。这就是“冲突”冲突是散列表无法避免的问题我们只能想办法“解决冲突”让两个原本想去同一个位置的关键字都能顺利地存进表里。2.2 除留余数法散列函数的选择有讲究散列函数有很多种比如直接定址法、数字分析法、平方取中法以及最常用的除留余数法。除留余数法的公式是 h(key) key % p其中p是一个小于或等于表长的正整数。理论上p的选取非常关键选得好能让关键字分布得更均匀减少冲突选得不好则可能导致大量关键字挤在一起散列表性能急剧下降。实际中p通常取不大于表长的最大质数或者直接取表长。这题里表长是7p也正好是7所以地址范围就是0到6和数组下标完美对应。我用这题的6个关键字算一遍38 % 7 325 % 7 474 % 7 463 % 7 052 % 7 348 % 7 6。可以看到38和52都落在3号地址25和74都落在4号地址冲突相当密集。为什么会出现这种情况因为7这个模数比较小而6个关键字在0到6的地址空间里必然存在重复。如果题目把表长设计成13或者更大的值冲突概率会明显下降。不过考试不会故意为难你表长7是为了让“手工模拟计算”成为可能所有位置都能人工推演。2.3 冲突处理线性探测法为什么是“依次找空位”线性探测法是最简单的开放定址法。当h(key)对应的位置已经被占用时就依次检查下一个位置也就是对地址序列 h(key), h(key)1, h(key)2, ... 进行探测每个地址都要对表长取模绕回表头继续找直到找到一个空位。用生活化的话说就像你去地下车库停车指定车位被人占了那就往前开一个车位看有没有空位如果一直开到出口还没停成再绕回入口继续找。这题里48号的关键字就碰到了这种“绕一圈”的情况我在后面会详细展开。线性探测法的优点是实现简单、容易理解缺点是容易产生“堆积现象”也就是冲突的关键字会抱成一团导致后续关键字的查找次数不断增加。3. 核心细节解析与实操要点3.1 逐个插入过程全推演这是整道题最核心的部分我必须把6个关键字的插入过程一步步写清楚每个关键字的查找次数也会在插入过程中顺便确定。第一个关键字是38。h(38) 38 % 7 3检查A[3]发现是空的直接放进去。查找次数记为1。第二个关键字是25。h(25) 25 % 7 4检查A[4]空的直接放进去。查找次数记为1。第三个关键字是74。h(74) 74 % 7 4检查A[4]发现25已经占了。冲突于是线性探测到下一个位置A[5]A[5]是空的把74放进去。74的查找次数记为2因为它比较了A[4]和A[5]两个位置才在第二个位置找到自己。第四个关键字是63。h(63) 63 % 7 0A[0]是空的直接放入。查找次数记为1。第五个关键字是52。h(52) 52 % 7 3检查A[3]已经被38占用了。冲突线性探测到A[4]又被25占用了再探测到A[5]被74占用继续探测到A[6]发现是空的把52放进去。所以52的查找次数是4它一路经历了3次冲突最终在第4次比较时才找到空位。第六个关键字是48。h(48) 48 % 7 6检查A[6]发现已经被52占了。冲突。按照线性探测法继续检查A[0]又被63占了再检查A[1]终于空出来了把48放进去。48的查找次数是3。到这里最终的散列表状态是A[0]63A[1]48A[2]空A[3]38A[4]25A[5]74A[6]52。整个过程如果我整理成一个表看起来会更清楚。插入顺序关键字h(key)冲突探测过程最终位置查找次数1383A[3]空直接放入A[3]12254A[4]空直接放入A[4]13744A[4]冲突探测A[5]A[5]24630A[0]空直接放入A[0]15523A[3]冲突探测A[4]冲突A[5]冲突A[6]空A[6]46486A[6]冲突探测A[0]冲突A[1]空A[1]33.2 线性探测的循环边界最容易算错的地方我再把线性探测法的边界问题单独拿出来讲一下。因为散列表是循环使用的所以当探测到表尾A[6]时下一个要探测的位置不是A[7]不存在而是回到表头A[0]。这在48的插入过程中体现得特别明显48的散列地址是6但A[6]被52占了于是它去探测(61)%70也就是A[0]结果也被63占了继续探测(62)%71也就是A[1]发现空位这才放进去。很多同学在手工模拟时只往后找忘了“绕回开头”于是48跑到了“想象中”的A[7]或者A[8]整个表就乱套了。这个循环取模的逻辑是线性探测法的基础一定要刻在脑子里。3.3 常见错误为什么很多人算成1.83或2.33这道题我在不同场合看到过很多种错误答案最常见的两种是1.83和2.33。先说2.33是怎么来的有人把48的查找次数算成了4次也就是认为48在A[6]冲突后依次探测A[0]、A[1]都冲突直到A[2]才放下于是查找次数变成4。但实际A[2]没有被占A[1]就已经是空位了所以正确查找次数应该是3次。把48的3次改成了4次其他不变ASL就会变成13/6约等于2.17如果把52也算错成5次那就更不对了。再说1.83是怎么来的有人把74、52这种发生冲突的关键字查找次数理解成了“冲突次数”而不是“比较次数”。74经历了1次冲突就记成152经历了3次冲突也记成348经历了2次冲突记成2。这样6个关键字的次数变成1111329ASL9/61.5也不是1.83。还有人会把“探测到的空位次数”也算上导致结果五花八门。出现这些错误的根本原因只有一个没有明确“比较次数”到底数的是什么。查找成功时比较次数是指从散列地址开始到最终找到该关键字所在位置为止一共检查了多少个表项。如果第一次就在散列地址找到了次数是1如果中间经历了k次冲突最后在一个空位放下了次数是k1。所有的空位探测、冲突位置只要被检查过都要算进比较次数里。4. 平均查找长度ASL从公式到考场步骤4.1 ASL成功的标准计算方法平均查找长度的定义是所有关键字的查找次数之和除以关键字个数。对于这道题成功查找的ASL就是(112143) / 6 12 / 6 2。也就是说在等概率情况下查找任意一个在表中的关键字平均需要比较2次。这里的除数为什么是6因为表里一共有6个关键字我们只统计“成功查找”的情况也就是只关心那些确定存在的关键字。一个常见的低级错误是拿总次数除以表长7这会把ASL变成12/7约等于1.71但这道题问的是成功查找所以必须以实际关键字个数6为分母不能用表长。计算ASL的标准流程我建议平时做题时严格按以下步骤来对每个关键字计算散列地址。按照插入顺序模拟一次完整的冲突解决过程确定每个关键字的最终存储位置。记录每个关键字查找成功需要比较的次数。把所有关键字的比较次数相加再除以关键字总数。这个流程看起来简单但步骤2是真正的难点特别是当装载因子很高、冲突很多的时候画一张表出来会有助于理清思路。4.2 ASL失败同为高频考点的扩展计算虽然2010年这题只问了成功查找但在之后的408真题里查找失败的平均查找长度也出现过。这里我把失败查找怎么算也一并讲清楚以备不时之需。查找失败的情况是给定的关键字不在表里我们从头开始探测直到遇到一个空位才确认“这个关键字不存在”。按照这个逻辑需要从每个散列地址出发模拟一次“找不到”的完整过程统计需要比较的次数。对于本表A[0]63A[1]48A[2]空A[3]38A[4]25A[5]74A[6]52从地址0开始查找失败先比较A[0]63不匹配继续A[1]48不匹配A[2]为空停止。一共比较了3次。从地址1开始A[1]48A[2]为空比较2次。从地址2开始A[2]为空比较1次。从地址3开始A[3]38A[4]25A[5]74A[6]52A[0]63A[1]48A[2]为空比较7次。从地址4开始A[4]25A[5]74A[6]52A[0]63A[1]48A[2]为空比较6次。从地址5开始比较5次。从地址6开始比较4次。把它们全部加起来321765428再除以7得到失败查找的ASL为4。这里要特别说明一个统计口径的问题不同教材对“失败查找分母”的处理不完全一样。有的按表长m做分母有的按散列函数中模数p做分母。当m和p相等时两种口径结果一样当m和p不相等时结果会有差异。在408考场上一般按主流复习资料和历年真题答案的口径来遇到这类题时不妨先看清题目给的表长和模数再决定分母用哪个。更稳妥的做法是平时做题时就把两种口径的差异记录下来别到考场上才纠结。4.3 考场上的标准书写格式很多同学会问这种计算题考场上要不要写很多文字我的建议是关键过程必须展示但不需要写小作文。标准写法大致如下先列出散列函数和冲突处理方法。逐个写出关键字的散列地址和最终位置。列出每个关键字的查找次数。写出ASL的公式并代入计算得到最终结果。比如可以写成h(38)3A[3]空查找长度1 h(25)4A[4]空查找长度1 h(74)4冲突线性探测到A[5]查找长度2 h(63)0A[0]空查找长度1 h(52)3冲突探测A[4]、A[5]均冲突放入A[6]查找长度4 h(48)6冲突探测A[0]冲突放入A[1]查找长度3。ASL成功 (112143)/6 2。这样阅卷老师一眼就能看到你的计算逻辑就算最终结果不小心算错了也给分步骤提供了依据。写清楚“为什么是4次”比只写一个“4”要稳妥得多。5. 常见问题与排查技巧实录5.1 一错一大片计算表比口算可靠得多实话实说这种6个关键字的散列表题目口算确实容易出现混乱。我在复习初期也喜欢心算觉得就6个数算什么算结果经常算着算着就乱了。后来我总结出来一个很笨但很管用的方法做题时先画一张六列的表格分别是“插入顺序、关键字、h(key)、冲突探测过程、最终位置、查找次数”每插入一个关键字就往表格里填一行。这样做有三个好处。第一每一行的“冲突探测过程”逼着我把线性探测的每一步都写出来减少跳步导致的错误。第二表格填完后整张表的状态一目了然最终的ASL计算只需要看查找次数那一列。第三后面检查答案时我可以快速定位到某个关键字验证它的位置和查找次数是否合理。这个方法适用于所有散列表计算题无论是408还是期末考都建议养成习惯。5.2 换一种冲突处理方法链地址法怎么算线性探测法的计算学会了并不意味着所有冲突处理方法都会了。408很喜欢把同一种数据换成不同处理方式来考。我又把2010年这题改成链地址法重新算了一遍这里把结果也放出来大家可以对照参考。链地址法的思路是散列表的每个位置变成一个链表的头节点冲突的关键字直接挂在对应地址的链表后面不需要在表内找空位。按这个规则6个关键字的存放情况是地址063地址1空地址2空地址338 - 52地址425 - 74地址5空地址648每个关键字的查找次数为38是1次25是1次74是2次先找到25再找到7463是1次52是2次在38后面48是1次。所以成功查找的ASL (112121)/6 8/6约等于1.33。从这组数字就能看出链地址法在同样的数据、同样的散列函数之下平均查找长度比线性探测法要小。这是因为链地址法的冲突关键字是纵向挂在链表里不会像线性探测法那样在表内产生“堆积”查找次数自然更少。5.3 换二次探测呢留一道思考题如果题目要求改用二次探测法也就是探测序列为1的平方、负1的平方、2的平方、负2的平方……那么结果会完全不同。这里我不逐字推演了但可以告诉大家一个大概结论52在地址3冲突后依次探测A[4]、A[2]最后会落在A[2]48在地址6冲突后会经历一串较长的探测过程最终落到A[1]。在这种处理方式下成功查找的ASL会比线性探测法还要大一些。建议有兴趣的同学自己把表重新推一遍这是检验自己是否真正理解“探测序列”概念的绝佳练习。6. 408散列表考点全景与备考建议6.1 散列表在408中的考察方式看完2010年这题再把视野放宽一点。408对散列表的考察基本围绕这样几个方向反复出现一是给定关键字序列和散列函数求装填因子和平均查找长度二是给定散列表和冲突处理方法反推散列函数或插入顺序三是把散列表和“查找”章节的其他知识点结合起来比如比较散列查找和折半查找、二叉排序树查找的性能差异。这些题目都不会要求你写一个完整的散列表实现代码但要求你对手工模拟的流程非常熟悉。很多同学有一种误区觉得散列表代码写过一遍考试就不会丢分。实际上408考的是你在纸上一步步推演的能力代码能力反而退居其次。所以在复习时一定要把“手工模拟”作为练习重点把模拟过程当作考试的标准动作来反复训练。6.2 散列表复习需要注意的五个清单根据我刷真题和辅导别人时的经验散列表专题复习时至少要把下面五件事做到位第一几种常见的散列函数都要会算尤其要理解除留余数法中p的选取原则。第二开放定址法里的线性探测法、二次探测法、再散列法都要动手模拟一遍不能只看书。第三链地址法一定要掌握它是408高频选项和高频大题常客。第四查找成功和查找失败两种ASL都必须会算统计口径要清楚。第五装填因子对查找性能的影响要能定性分析知道为什么装填因子越大冲突概率越高查找效率越低。6.3 时间安排这题适合放在复习的哪个阶段我个人的看法是像这种基础计算题应该在数据结构第一轮复习结束时就能独立做出来。也就是说当你学完查找章节并且刚接触散列表时就可以拿2010年这题来检验自己对“散列函数-冲突处理-ASL”整条链路是否理解。如果第一遍就能准确算对说明基础不错如果第一遍算错了也不用慌这题的价值就在于帮你定位哪一环出了问题。等到第二轮、第三轮复习时这题已经不需要再完整做一遍了你可以把它当成一个“母题”在脑海里快速把变体过一遍换链地址法会怎样换二次探测会怎样题目问失败查找又应该怎么算。能把变体都想清楚这题才算真正吃透了。7. 实用技巧10分钟吃透这道题的复盘模板7.1 复盘模板对着自己的解题过程提问每次做完一道散列表真题我都建议用一个固定的复盘模板来检查。模板长这样第一问自己散列函数算对了吗有没有把取模结果算错这类低级错误经常出现在时间紧张的时候。第二问自己每个关键字的最终位置是通过完整的冲突探测得出来的吗有没有跳步比如52为什么会到A[6]48为什么会到A[1]能不能立刻说出来。第三问自己查找次数的计数口径正确吗查找成功时第一次比较就算1次失败了遇到空位才停止。第四问自己分母用的是关键字个数还是表长题目问的是成功还是失败一定要看清楚了再选分母。第五问自己最终结果有没有检查过合理性比如成功查找的ASL不可能小于1也不可能超过表长如果算出来明显不合理很可能中间某个步骤出了问题。7.2 把“母题”变成“一题十练”这题的扩展空间其实非常大。我每次带人复习都鼓励他们拿同一组数据玩出多种问法这题如果问你装填因子是不是一眼就能报出6/7这题如果把查找成功改成查找失败结果会从2变成4你会算吗这题如果把线性探测换成链地址法结果约等于1.33你能很快推出来吗这题如果给定的是散列表的最终状态反过来问你关键字的插入顺序你有思路吗这几种问法在历年真题和各大复习资料里都有出现过。与其盲目刷很多道新题不如把这样一道母题反复咀嚼透。7.3 考场上遇到散列表题怎么避免慌乱到了考场上时间紧张很多人容易因为一个数字算岔了就乱了阵脚。我的经验是碰到散列表的计算题不管多简单都先在草稿纸上把那张六列表格规规矩矩地画出来然后一步一步填。越是看着简单的题越要写清楚过程。一方面是为了防止自己思路飘了另一方面是就算最后结果有问题阅卷老师也能看到你的思路可能还会给步骤分。再有一个实战技巧算完ASL之后立刻看一遍结果是否符合常识。对于成功查找ASL一般在1到装填因子倒数之间波动对于失败查找一般会大于成功查找。如果你算出失败查找反而比成功查找小那大概率是某个环节算错了回头检查的时候优先复查计数过程。关于这题我心里还有个很深的印象。我第一次做的时候把48的查找次数算成了4次因为总觉得从A[6]绕到A[0]再绕到A[1]应该算4次才够。后来才发现所谓“检测次数”应该是“检查到空位并放下”的次数A[1]是第三个被检查的位置所以是3次。从那之后我再也没在单次比较计数上犯过同样的错。希望这篇拆解也能帮你把这类题彻底盘顺。