1. 项目概述：为什么期末复习必须死磕哈希表？
又到期末了，数据结构这门课，哈希表绝对是老师最爱考、学生最容易懵的章节之一。我当年复习的时候，就发现教材上关于哈希表的构造和冲突解决，往往就是干巴巴地列几个公式、画几个图，看完感觉懂了，合上书啥也记不住。直到后来自己刷题、做项目，才真正把这块骨头啃下来。今天，我就以一个过来人的身份，把哈希表这块的复习要点掰开揉碎了讲，尤其是那6种构造方法和4种解决冲突方法，这不仅是应付考试的选择题、简答题、算法设计题的核心，更是你未来面试、写代码时绕不开的实用技能。
哈希表（Hash Table）的本质，就是一个“超级索引”。它通过一个函数（哈希函数），把任意长度的输入（比如一个字符串“John Doe”），映射到一个固定范围的索引值（比如数组下标5），然后直接在这个位置存取数据。理想情况下，这个操作的时间复杂度是O(1)，快得飞起。但现实很骨感，不同的输入可能会被映射到同一个索引，这就是“冲突”。所以，整个哈希表技术的核心就两块：怎么设计这个映射函数（构造方法），以及映射撞车了怎么办（解决冲突方法）。期末考试，翻来覆去就是考你对这两块的理解深度和灵活应用。
2. 哈希表核心：构造方法与冲突解决的逻辑框架
在深入细节之前，我们必须建立一个顶层的认知框架。你可以把哈希表想象成一个有固定数量停车位（哈希地址）的停车场。现在有两件关键事要做：
- 分配车位（构造方法）：给定一辆车（关键字Key），用一套规则决定它应该停进哪个编号的车位。这个规则就是哈希函数。好的规则应该让车辆尽可能均匀地分散在所有车位上，避免某些车位挤爆，另一些却空着。
- 处理占位（解决冲突方法）：当你按照规则找到车位时，发现已经有一辆车（另一个Key）停在那里了。这时候怎么办？是让后到的车另寻他处（开放定址），还是在原车位上搭建一个立体车库停放多辆车（链地址法）？
期末考题，无论是让你计算某个关键字的哈希地址，还是分析平均查找长度（ASL），或是比较不同方法的优劣，都是基于这个框架展开的。接下来，我们就逐一拆解这6种构造方法和4种解决冲突方法，我会结合具体例子和计算过程，让你不仅记住“是什么”，更明白“为什么”和“怎么算”。
3. 六种哈希函数构造方法详解与实战对比
哈希函数的设计目标很明确：计算简单、散列均匀、冲突概率低。下面这六种方法是教材里的常客，也是考试重点。
3.1 直接定址法
这是最简单粗暴的一种。取关键字本身或者关键字的某个线性函数值作为哈希地址。公式一般是：Hash(key) = a * key + b（其中a、b为常数）。
实战场景与计算： 假设我们要存储某公司员工信息，以员工工号（从2024001开始连续编号）为关键字。我们可以直接定义Hash(工号) = 工号 - 2024000。那么工号2024001就存到地址1，2024002存到地址2，以此类推。
为什么用它？
- 优点：绝对没有冲突，是理想的“一对一”映射，查找速度是严格的O(1)。
- 缺点：适用范围极窄。它要求关键字的分布必须连续，或者是非常密集。如果工号是2024001, 2024010, 2024300这样跳跃的，那么哈希表空间（数组）的绝大部分都会是空的，造成巨大的空间浪费。
注意：直接定址法在考试中常作为“特例”出现，用于对比其他会产生冲突的方法。你需要迅速识别出关键字是否具备“连续或近乎连续”的特性。
3.2 数字分析法
这种方法适用于关键字是位数较多的数字（如手机号、身份证号），并且已知这些数字的某些位上分布不均匀（某些位上的数字重复多），而某些位分布均匀。我们抽取其中分布均匀的若干位组合起来作为哈希地址。
实战场景与计算： 假设有一批关键字是某地的8位电话号码，如 88234567, 88235123, 88239876... 我们发现前三位“882”都是区号，所有号码都相同，肯定不能用来做哈希（否则全冲突）。中间两位“34”、“35”、“39”分布比较随机，后三位“567”、“123”、“876”分布也比较均匀。我们可以抽取中间两位+后两位，组成一个4位的哈希地址。例如：Hash(88234567) = 3456Hash(88235123) = 3512
为什么用它？
- 优点：基于已知的数据集特征进行设计，如果位选取恰当，能有效减少冲突。
- 缺点：严重依赖数据集！你必须事先分析所有关键字的构成。如果来了一个新的、不符合原分布规律的关键字，冲突率可能会急剧上升。因此，它适用于关键字集合已知且静态，或变化不大的情况。
3.3 平方取中法
先求出关键字的平方值，然后取平方值的中间几位作为哈希地址。具体取多少位，取决于哈希表的大小（表长）。
实战场景与计算： 假设关键字是1234，哈希表长度为1000（即地址范围0~999，需要3位数）。
- 计算平方：1234² = 1522756。
- 取中间3位：从中间开始取，1522756，我们可以取第3到第5位（227），或者第2到第4位（522）。通常约定一种规则即可，比如取右起第4位开始的3位（从右往左数，个位是第1位）。这里1522756，右起第4、3、2位是7, 5, 2？等等，这样取容易乱。更通用的方法是：将平方数视为固定位数的字符串（不足补零），然后取中间部分。假设我们总取中间3位，1522756是7位数，中间3位就是第3、4、5位：2, 2, 7，即227。 所以
Hash(1234) = 227。
为什么用它？
- 优点：平方操作能使关键字的每一位都参与到最终的地址计算中，特别是中间几位，受到了关键字所有位的影响。因此，即使关键字只有少量变化（如1234和1235），平方后的中间几位通常也会有很大不同，有助于分散冲突。
- 缺点：计算量相对稍大（需要做乘法）。对于非常庞大的数据集，性能开销需要考虑。
3.4 折叠法
将关键字分割成位数相等的几部分（最后一部分位数可以略少），然后将这几部分叠加求和，根据哈希表大小，取后几位作为哈希地址。
实战场景与计算： 关键字 123456789，哈希表长度1000（地址3位数）。
- 分割：每3位一段，分成123， 456， 789。
- 叠加求和：123 + 456 + 789 = 1368。
- 取后三位：
Hash(123456789) = 368。
还有一种“移位折叠”，在叠加前将偶数段（或奇数段）反转后再加。例如，反转偶数段456->654，那么求和为123 + 654 + 789 = 1566，取后三位566。这种方法能更好地打乱模式。
为什么用它？
- 优点：适用于关键字位数很多，且每一位上的数字分布可能不均匀的情况。通过折叠和求和，将长关键字压缩成短地址，同时混合了所有部分的信息。
- 缺点：可能存在一定的“信息损失”，求和后高位被截断。但哈希函数本身不要求可逆，所以问题不大。
3.5 除留余数法（最常用！）
这是实践中最常用、最核心的方法。取关键字被某个数p除后的余数作为哈希地址。公式：Hash(key) = key MOD p。 这里的p的选择是成败关键。
实战场景与计算： 关键字集合为 {12, 25, 36, 48, 60}，哈希表长度（表长）m=10。 如果我们随意取p=10，则： Hash(12)=2, Hash(25)=5, Hash(36)=6, Hash(48)=8, Hash(60)=0。分布均匀，无冲突。 但如果关键字集合是 {12, 22, 32, 42, 52}，p仍取10，则所有关键字的哈希地址都是2，冲突极其严重。
为什么p的选择至关重要？理论证明，p应选取一个不大于表长m，但最接近或等于m的质数。为什么？
- 减少模运算的规律性：如果p是一个合数，比如p=10，它的因子有2和5。那么所有关键字中，能被2整除的数（偶数）将只会映射到偶数地址，奇数关键字映射到奇数地址，分布不均。质数只有1和它本身两个因子，能最大程度地打破关键字可能存在的周期性规律，使得余数分布更均匀。
- 考试必考计算：给你一个表长m，让你选p。例如m=15，那么不大于15的质数有13, 11, 7, 5, 3, 2。应选择最接近15的质数，即p=13。
实操心得：在期末试卷和面试中，除留余数法是出现概率最高的。你必须熟练掌握给定一组关键字和表长m，计算哈希地址并填入哈希表的全过程，同时能分析冲突情况。这是大题的基础。
3.6 随机数法
取关键字的随机函数值作为哈希地址：Hash(key) = random(key)。这里random是一个伪随机数生成器，当种子（key）相同时，生成的随机数序列是固定的。
为什么用它？
- 优点：当关键字长度不等，且分布不明时，随机数法通常能得到较好的散列效果，冲突概率取决于随机数生成器的质量。
- 缺点：“随机”意味着每次计算结果相同，这很重要！哈希函数必须是确定的（Deterministic），同一个key必须每次都能得到同一个地址，否则就找不到存进去的数据了。所以这里的random是伪随机函数。其次，随机数生成本身有一定计算开销。
方法对比总结表
| 方法 | 适用场景 | 优点 | 缺点 | 考试关注点 |
|---|---|---|---|---|
| 直接定址 | 关键字分布连续 | 无冲突，O(1)查找 | 空间浪费严重 | 识别适用条件 |
| 数字分析 | 关键字位数多，且位分布已知 | 针对性强，冲突少 | 依赖静态数据集，不通用 | 给定位数，要求抽取 |
| 平方取中 | 关键字位数中等，分布不详 | 散列均匀，关键字符号均参与 | 计算量稍大 | 计算平方并取指定位 |
| 折叠法 | 关键字位数很多 | 混合所有部分信息 | 有一定信息损失 | 分割、叠加、取模计算 |
| 除留余数 | 最通用 | 计算简单，效果好 | p的选择至关重要 | 必考！计算地址、填表、分析ASL |
| 随机数法 | 关键字不规则 | 散列效果好 | 计算慢，需确定函数 | 了解原理，较少直接计算 |
4. 四种冲突解决策略全解析与性能评估
冲突不可避免，所以必须有预案。这四种方法是解决冲突的经典策略，各有其应用场景和性能特征。
4.1 开放定址法（Open Addressing）
核心思想：一旦发生冲突，就按照某种探测序列，在哈希表中寻找下一个“开放”的（即空的）地址，直到找到为止。所有的数据都存放在表本身这个数组中。 通用探测公式：Hi = (H(key) + di) MOD m。其中，H(key)是初始哈希地址，m是表长，di是第i次探测的增量序列。i从0开始。
根据增量序列di的不同，分为以下三种主要方法：
4.1.1 线性探测法（Linear Probing）
增量序列di = 1, 2, 3, ... , m-1。即每次冲突后，顺序查看下一个单元是否为空。
实战与计算： 表长m=10，哈希函数H(key)=key MOD 7（注意p=7是质数）。 依次插入关键字序列：{8, 14, 19, 23, 30}。
- H(8)=1，地址1空，插入。
- H(14)=0，地址0空，插入。
- H(19)=5，地址5空，插入。
- H(23)=2，地址2空，插入。
- H(30)=2，冲突！开始线性探测：
- d1=1: (2+1) MOD 10 = 3，地址3空，插入。
此时哈希表为：[14, 8, 23, 30, -, 19, -, -, -, -] (地址0到9)
为什么要注意“堆积”？线性探测的缺点是容易产生“一次聚集”（Primary Clustering）或“堆积”。即连续被占用的地址单元形成一些区块。这会导致后续的关键字在探测时，需要跳过很长的已占用序列，大大增加查找时间。例如，如果接下来要插入关键字9，H(9)=2，会发现地址2、3都被占了，需要探测到地址4才空。
4.1.2 平方探测法（Quadratic Probing）
增量序列di = 1², -1², 2², -2², 3², -3², ...。即探测的步长是平方数，并且正负交替。
实战与计算： 接上例，插入30时冲突（H(30)=2）。
- i=1: d1=1²=1, (2+1) MOD 10 = 3，地址3空，插入成功。 如果地址3也冲突，则继续：
- i=2: d2=-1²=-1, (2-1) MOD 10 = 1，检查地址1。
- i=3: d3=2²=4, (2+4) MOD 10 = 6，检查地址6。
- ...
为什么它能缓解堆积？平方探测的步长是变化的，避免了线性探测那种“扎堆”的情况，能有效缓解“一次聚集”，称为“二次聚集”，但影响比一次聚集小。一个重要考点：平方探测法要求表长m必须是形如4k+3的质数，才能保证探测序列能够遍历所有表项。例如，m=7, 11, 19, 23等。
4.1.3 再哈希法（Double Hashing）
使用第二个哈希函数来计算增量：di = i * H2(key)。即每次探测的步长由另一个哈希函数决定。
实战与计算： 设H1(key)=key MOD 7, H2(key)=5 - (key MOD 5)。（注意H2不能为0） 插入30时冲突（H1(30)=2）。
- i=1: d1=1 * H2(30) = 1 * (5 - (30 MOD 5)) = 1 * (5-0)=5, (2+5) MOD 10 = 7，检查地址7。
- i=2: d2=2 * 5 =10, (2+10) MOD 10 = 2，回到原点，但通常i会继续增加，实际探测序列为2,7,(2),7...这里出现了循环，说明H2和表长m选择不当。好的H2应与m互质。
为什么它更优？再哈希法通过第二个哈希函数为不同的关键字生成不同的探测序列，极大地减少了“聚集”现象，是开放定址法中较好的方法。但计算开销稍大。
注意事项（开放定址法通病）：
- 删除操作不能直接删：如果直接删除某个单元，会截断探测路径，导致后续查找失败（因为查找时遇到空就认为不存在）。通常采用“标记删除”法，即给删除的单元打一个特殊标记（如DELETED），查找时视其为非空继续探测，插入时视其为空可复用。
- 装载因子：装载因子α = 表中已填入记录数 / 哈希表长度。开放定址法要求α必须小于1（通常建议α < 0.7~0.8），否则插入失败概率激增，查找效率也急剧下降。
4.2 链地址法（Chaining，又称拉链法）
这是实践中应用最广泛、最直观的方法。它的思想是：把哈希到同一地址的所有关键字都放在一个链表中。哈希表的每个单元不再存储数据本身，而是存储一个链表头指针（或引用）。
实战与计算： 表长m=5，H(key)=key MOD 5。 插入序列：{12, 22, 35, 8, 24}。
- H(12)=2，地址2链表：12 -> NULL
- H(22)=2，冲突，链地址法处理：将22插入地址2的链表头部（或尾部）。链表变为：22 -> 12 -> NULL
- H(35)=0，地址0链表：35 -> NULL
- H(8)=3，地址3链表：8 -> NULL
- H(24)=4，地址4链表：24 -> NULL
最终哈希表结构是一个数组+链表的结构。
为什么它如此受欢迎？
- 处理简单：冲突解决直观，就是链表插入。
- 无堆积问题：同义词（哈希地址相同的关键字）只在各自的链表上，不会影响其他地址的探测。
- 易于删除：直接在链表上删除节点即可。
- 可容纳更多数据：装载因子α可以大于1，因为链表可以动态增长。当然，α过大会导致单个链表过长，退化为顺序查找。
平均查找长度（ASL）计算： 这是考试大题！对于链地址法，查找成功的ASL，是查找每个关键字需要遍历链表节点数的平均值。 上例中，查找12需要遍历2个节点（22->12），查找22需要1个，查找35需要1个，查找8需要1个，查找24需要1个。 成功ASL = (1+1+1+1+2)/5 = 1.2。 查找失败的ASL，是指查找一个不存在的关键字时，需要遍历的链表节点数的平均值。通常假设要查找的关键字等概率地映射到每个地址。对于上例，地址0链表长度为1，查找失败需遍历1个节点（发现不是）；地址1链表长度为0，遍历0个；地址2链表长度为2，需遍历完2个；地址3长度1，遍历1个；地址4长度1，遍历1个。 失败ASL = (1 + 0 + 2 + 1 + 1) / 5 = 1.0。（注意：分母是表长m=5，代表可能映射到的地址数）
4.3 再哈希法（Rehashing）
这里的“再哈希法”与开放定址法中的“双哈希”同名但概念不同。它是指准备一组哈希函数{H1, H2, H3, ...}。当使用H1发生冲突时，换用H2计算地址，如果再冲突，换H3，以此类推。
为什么用得少？这种方法要求预先设计多个好的哈希函数，且每个函数计算不能太复杂。在实践中设计难度较大，不如链地址法或双哈希法（开放定址）通用，教材和考试中多作为概念了解。
4.4 建立公共溢出区法
思路很简单：将哈希表分为两部分：基本表和溢出表。所有冲突的记录，不再在基本表内解决，而是统一存放到另一个独立的存储区域——溢出表中。
工作流程：
- 根据哈希函数计算地址，若基本表该地址为空，则存入。
- 若冲突，则将该记录顺序存入溢出表。
- 查找时，先在基本表对应地址查找，若找不到，则到溢出表中进行顺序查找。
为什么它是一种选择？
- 优点：实现非常简单，逻辑清晰。基本表的插入和查找（无冲突时）速度极快。
- 缺点：溢出表成为了性能瓶颈。当冲突较多时，溢出表会变得很长，在溢出表上的查找退化为O(n)的顺序查找，整体性能下降。它适用于冲突发生较少的情况。
冲突解决方法对比总结表
| 方法 | 核心思想 | 优点 | 缺点 | 关键考点与ASL计算特点 |
|---|---|---|---|---|
| 开放定址法 | 在表内找下一个空位 | 所有数据存于一处，空间利用率高，缓存友好 | 删除麻烦（需标记），易聚集，α<1 | 线性探测：会堆积。计算ASL时，成功查找需考虑探测次数。平方探测：m需为4k+3质数。 |
| 链地址法 | 同义词组成链表 | 处理简单，无堆积，删除易，允许α>1 | 需要额外指针空间，缓存不友好 | 最常考ASL！成功ASL：求各关键字查找长度均值。失败ASL：求各地址链表长度均值（分母为m）。 |
| 再哈希法 | 换一个哈希函数 | 聚集少 | 需设计多个哈希函数 | 了解概念，较少直接计算。 |
| 公共溢出区 | 冲突记录全放另一个表 | 实现简单，基本表操作快 | 溢出表成为性能瓶颈 | 理解原理，能描述查找过程。 |
5. 期末实战：综合题型拆解与计算演练
光说不练假把式。下面我们用一个典型的期末/考研大题，把构造方法和冲突解决方法串起来。
题目：设哈希表表长m=13，哈希函数为 H(key) = key MOD 11。采用链地址法解决冲突。请画出依次插入关键字序列 { 16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77 } 后的哈希表，并计算查找成功和查找失败的平均查找长度（ASL）。
解题步骤：
确定参数：表长m=13，但哈希函数模数是p=11。这里要注意，表长和模数可以不同。地址范围是0到12（因为m=13），但哈希函数计算结果要对11取模，所以初始哈希地址范围是0到10。由于采用链地址法，即使H(key)算出来是0-10，我们依然有13个表项（0-12）来存放链表头，多出的位置（地址11,12）可能永远为空，但这不影响。
计算哈希地址并插入：
- H(16) = 16 MOD 11 = 5
- H(74) = 74 MOD 11 = 8
- H(60) = 60 MOD 11 = 5（冲突，链入地址5链表）
- H(43) = 43 MOD 11 = 10
- H(54) = 54 MOD 11 = 10（冲突，链入地址10链表）
- H(90) = 90 MOD 11 = 2
- H(46) = 46 MOD 11 = 2（冲突，链入地址2链表）
- H(31) = 31 MOD 11 = 9
- H(29) = 29 MOD 11 = 7
- H(88) = 88 MOD 11 = 0
- H(77) = 77 MOD 11 = 0（冲突，链入地址0链表）
画出哈希表（用数组+链表表示）：
地址0: 88 -> 77 -> NULL 地址1: NULL 地址2: 90 -> 46 -> NULL (通常按插入顺序，新插入的放表头，这里假设按题目顺序插入，90先，46后) 地址3: NULL 地址4: NULL 地址5: 16 -> 60 -> NULL 地址6: NULL 地址7: 29 -> NULL 地址8: 74 -> NULL 地址9: 31 -> NULL 地址10: 43 -> 54 -> NULL 地址11: NULL (表长13，多出的地址) 地址12: NULL计算查找成功的平均查找长度（ASL成功）： 需要统计查找每个关键字需要遍历的链表节点数（比较次数）。查找时，从链表头开始，一次比较算一次。
- 查找16：地址5，链表 16->60，第1个节点就是，比较1次。
- 查找74：地址8，链表只有74，比较1次。
- 查找60：地址5，链表 16->60，需先比较16（1次），再比较60（第2次），共2次。
- 查找43：地址10，链表 43->54，第1个节点就是，比较1次。
- 查找54：地址10，链表 43->54，先比较43（1次），再比较54（2次），共2次。
- 查找90：地址2，链表 90->46，第1个节点就是，比较1次。
- 查找46：地址2，链表 90->46，先比较90（1次），再比较46（2次），共2次。
- 查找31：地址9，比较1次。
- 查找29：地址7，比较1次。
- 查找88：地址0，链表 88->77，比较1次。
- 查找77：地址0，链表 88->77，先比较88（1次），再比较77（2次），共2次。
总比较次数 = 1(16)+1(74)+2(60)+1(43)+2(54)+1(90)+2(46)+1(31)+1(29)+1(88)+2(77) = 15次。 关键字总数n=11。ASL成功 = 15 / 11 ≈ 1.364。
计算查找失败的平均查找长度（ASL失败）： 查找失败时，假设待查关键字等概率地映射到哈希函数所能计算出的每一个地址上，即H(key)的值域。本题H(key)=key MOD 11，值域是0,1,2,...,10 共11个地址。注意，表长m=13，但地址11和12是哈希函数永远算不出来的，所以不考虑它们。 对于每个可能的哈希地址（0到10），我们计算“在这个地址对应的链表上，查找失败需要比较多少次”。查找失败意味着一直比较到链表末尾的NULL。
- 地址0：链表长度为2 (88->77->NULL)，需要比较3次（88，77，NULL）？不对。查找时，先与88比（1次），不匹配；再与77比（2次），不匹配；遇到NULL，停止。所以比较次数为2次（即链表长度）。
- 地址1：链表长度0，直接发现为空，比较0次。
- 地址2：链表长度2 (90->46->NULL)，比较2次。
- 地址3：长度0，比较0次。
- 地址4：长度0，比较0次。
- 地址5：长度2 (16->60->NULL)，比较2次。
- 地址6：长度0，比较0次。
- 地址7：长度1 (29->NULL)，比较1次。
- 地址8：长度1 (74->NULL)，比较1次。
- 地址9：长度1 (31->NULL)，比较1次。
- 地址10：长度2 (43->54->NULL)，比较2次。
总失败比较次数 = 2+0+2+0+0+2+0+1+1+1+2 = 11次。 可能的地址数 = 11。ASL失败 = 11 / 11 = 1.0。
踩坑提醒：计算ASL失败时，分母是哈希函数的值域大小（即模数p，本题是11），而不是表长m（本题是13），这是很多同学容易出错的地方！一定要理解，查找失败是基于“这个关键字如果存在，它应该落在哪个地址”来考虑的，它只可能落在H(key)能算出的那些地址上。
6. 高频考点与独家避坑技巧
根据多年刷题和教学经验，哈希表这章除了上述计算，还有一些容易混淆和出错的点。
6.1 装载因子α的理解与运用
装载因子α = 表中记录数n / 哈希表长度m。它是衡量哈希表满的程度，也是决定其性能的关键参数。
- 对于开放定址法：α必须小于1。通常，α < 0.7时，性能尚可；α > 0.8后，查找性能会非线性下降。考试中可能会让你根据预计存储的记录数n和设定的α，反推需要的表长m（m ≥ n / α）。
- 对于链地址法：α可以大于1，它表示每个链表的平均长度。α越大，平均链表越长，查找效率越低（趋向O(n)）。通常希望α控制在1~2以内。
考题变形：“若采用线性探测法，要求装载因子不超过0.7，现有100个记录，则哈希表长度至少应为多少？” 答案：m ≥ 100 / 0.7 ≈ 142.86，取至少143。同时，为了使用除留余数法，最好选择大于143的质数，例如149。
6.2 不同冲突解决方法下的删除操作
这是简答题和算法设计题的常客。
- 链地址法：删除最简单，找到节点后，在链表中删除即可。时间复杂度O(1)~O(α)。
- 开放定址法：不能直接物理删除，必须采用“标记删除”。在删除位置做一个特殊标记（如设为DELETED）。查找时，遇到DELETED标记应继续探测（因为后面可能还有同义词）。插入时，遇到DELETED标记可以将其覆盖（复用空间）。你需要能说清楚为什么不能直接置空。
6.3 平均查找长度（ASL）的深度辨析
ASL是衡量哈希表效率的核心指标，一定要会算，更要理解。
- ASL成功：查找表中已有记录的平均比较次数。计算方法是：对每个关键字，统计找到它需要比较的次数，求和后除以关键字总数n。
- ASL失败：查找表中不存在的记录的平均比较次数。计算方法是：对哈希函数值域内的每一个地址，统计在该地址对应的链表（或探测序列）上，一直查到“终止条件”（链表NULL或开放定址的空位）所需的比较次数，求和后除以哈希函数值域的大小（通常是模数p，或表长m，需根据方法判断）。
关键区别：失败ASL的分母不是n，也不是表长m（在链地址法中），而是可能映射到的地址总数。对于除留余数法H(key)=key MOD p，就是p；对于直接定址法，就是关键字取值范围的大小。这个概念务必厘清。
6.4 从考题到应用：如何选择构造与冲突解决方法？
考试中可能会出简答题：“比较开放定址法和链地址法的优缺点，并说明各自适用场景。” 你可以这样组织答案：
- 开放定址法：
- 优点：所有数据存储在连续数组中，存储效率高，缓存局部性好（CPU缓存命中率高），序列化方便。
- 缺点：有聚集现象，删除操作复杂（需标记），装载因子必须小于1，扩容成本高（需要rehash所有元素）。
- 适用场景：数据量相对固定或可预估，对缓存性能要求高，内存空间紧凑的场景。
- 链地址法：
- 优点：无聚集现象，处理冲突简单，删除操作容易，装载因子可以大于1，扩容相对灵活（可以单独对长链表进行拆分）。
- 缺点：需要额外的指针存储空间，节点内存不连续，缓存局部性差，小对象存储时空间开销比例大。
- 适用场景：数据量动态变化，频繁插入删除，内存相对充裕的场景。这也是大多数编程语言（如Java的HashMap，Python的dict）内置哈希表实现采用的方法（通常结合数组+链表/红黑树）。
最后，我个人在复习和实际编码中的体会是，哈希表这一章，理解远比死记硬背重要。一定要动手画图，把插入过程一步步画出来，计算ASL时把比较次数一个个数出来。考试时，无论题目怎么变，核心就是那6种构造方法和4种冲突解决方法的不同组合。把本文的例子和习题吃透，哈希表这部分的分，你基本就稳拿了。如果时间允许，最好能用你熟悉的编程语言（C、Java、Python都行）亲手实现一个简单的链地址法哈希表，从put、get到remove，实现一遍，理解会深刻十倍。