跳转至

408 高频考点精讲:平均查找长度(Average Search Length)

模块归属:数据结构 · 查找
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:3 次(2016~2025 年:2018#9、2019#8、2023#9)
  • 历年总考查频次:5 次(含 2010#9、2014#9)
  • 出题形式:单项选择题为主;亦作为综合大题中算法效率分析的核心理论依据。
  • 命题特点:
  • 近年命题高度聚焦于散列表(Hash Table)的平均查找长度,考查重点逐步由“查找成功”转向更为复杂的“查找失败”。
  • 概念陷阱集中在“散列表查找失败的分母判定”(散列函数模数 \(p\)$ \text{和物理表长} $\(m\) 的本质区别)、“墓碑标记(Deleted)对探测链终止条件的干扰”以及“探测回绕机制”。
  • 各类经典查找结构(顺序查找、折半查找、分块查找、二叉排序树、散列表)的形式化数学推导及判定树映射是高频考查的基本功。
近十年考查年份分布:
2016  2017  2018   2019   2020   2021   2022   2023   2024   2025
 -     -     √      √      -      -      -      √      -      -
            (#9)   (#8)                         (#9)

二、 具体考察内容

1. 平均查找长度的形式化数学定义

在查找结构中,关键字的比较次数是衡量查找算法时间效率的核心指标。平均查找长度(Average Search Length, ASL) 定义为在查找过程中,一次查找所需进行的关键字比较次数的数学期望。

(1) 查找成功的平均查找长度(ASL(succ))

设含有 \(n\)$ \text{个记录的查找表中,查找第} $\(i\)$ \text{个记录的先验概率为} $\(P_i\)$ \text{,查找到该记录所需的关键字比较次数为} $\(C_i\),则查找成功的平均查找长度为: $\(\text{ASL}_{\text{succ}} = \sum_{i=1}^n P_i \cdot C_i\)$ 在等概率假设下,每个记录被查找的概率相等,即 \(P_i = \frac{1}{n}\)(\(1 \le i \le n\)),上式简化为: $\(\text{ASL}_{\text{succ}} = \frac{1}{n} \sum_{i=1}^n C_i\)$

(2) 查找失败的平均查找长度(ASL(fail))

若待查记录不在表中,查找过程最终以“确认失败”终止。设查找失败的情况可划分为 \(m\)$ \text{种互斥的等价类(或失败出口),待查关键字落入第} $\(j\)$ \text{种失败情况的概率为} $\(Q_j\)$ \text{,确认该情况失败所需的关键字比较次数为} $\(C_j'\),则查找失败的平均查找长度为: $\(\text{ASL}_{\text{fail}} = \sum_{j=1}^m Q_j \cdot C_j'\)$ 在等概率假设下,各个失败出口的概率均等(\(Q_j = \frac{1}{m}\)),则: $\(\text{ASL}_{\text{fail}} = \frac{1}{m} \sum_{j=1}^m C_j'\)$


2. 静态及动态查找结构的 ASL 严格推导

  • 无序线性表:
  • 查找成功:从前往后依次比较,第 \(i\)$ \text{个元素需比较} $\(i\) 次。 $\(\text{ASL}_{\text{succ}} = \frac{1}{n} \sum_{i=1}^n i = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2}\)$
  • 查找失败:必须遍历全部 \(n\)$ \text{个元素方能确认不存在,比较次数为} $\(n\)$ \text{次(若设哨兵,需比较} $\(n+1\) 次)。
  • 有序线性表(升序排列):
  • 引入判定树分析。\(n\)$ \text{个关键字将数轴分割为} $\(n+1\) 个查找失败区间。
  • 查找失败:若待查关键字小于第一个元素,只需比较 1 次;若介于第 \(i\)$ \text{个和第} $\(i+1\)$ \text{个元素之间,需比较} $\(i+1\)$ \text{次;若大于最大元素,需比较} $\(n\) 次。
  • 等概率假设下查找失败的 ASL: $\(\text{ASL}_{\text{fail}} = \frac{1}{n+1} \left( 1 + 2 + 3 + \dots + n + n \right) = \frac{1}{n+1} \left( \frac{n(n+1)}{2} + n \right) = \frac{n}{2} + \frac{n}{n+1}\)$
  • 判定树(Decision Tree)特性:
  • 折半查找的过程对应一棵二叉判定树。树中每个内部节点代表一次成功的查找,每个外部空叶节点(方形节点)代表一次失败的查找。
  • 含有 \(n\)$ \text{个内部节点的折半查找判定树,其外部节点数严格等于} $\(n+1\)。
  • 树的高度为 \(h = \lceil \log_2(n+1) \rceil\)。
  • 计算规则:
  • 查找成功:每个内部节点所需的比较次数等于该节点在判定树中的层数。 $\(\text{ASL}_{\text{succ}} = \frac{1}{n} \sum_{k=1}^h k \cdot N_k\)$ 其中 \(N_k\)$ \text{为判定树第} $\(k\)$ \text{层的内部节点数。当判定树为满二叉树时,} $\(\text{ASL}_{\text{succ}} \approx \log_2(n+1) - 1\)。
  • 查找失败:外部节点仅可能分布在第 \(h\)$ \text{层或第} $\(h+1\) 层。每个失败状态经历的关键字比较次数等于其双亲节点的层数。 $\(\text{ASL}_{\text{fail}} = \frac{1}{n+1} \sum_{j=1}^{n+1} \text{level}(\text{parent}(fail_j))\)$
  • 结构设定:
  • 将长度为 \(n\)$ \text{的表分为} $\(b\)$ \text{块,每块含} $\(s\)$ \text{个元素(} $\(n = b \cdot s\))。
  • 索引表按块的最大关键字有序组织,块内元素允许无序。
  • 查找过程分为两步:先在索引表中确定待查关键字所在块,再在对应块内顺序查找。
  • \(\text{ASL} = L_I + L_S\)(\(L_I\)$ \text{为索引查找长度,} $\(L_S\) 为块内查找长度)。
  • 平均查找长度推导:
  • 若索引表及块内均采用顺序查找: $\(\text{ASL}_{\text{succ}} = \frac{b+1}{2} + \frac{s+1}{2} = \frac{b + \frac{n}{b}}{2} + 1\)$ 根据均值不等式,当 \(b = \frac{n}{b} \implies b = s = \sqrt{n}\)$ \text{时,} $\(\text{ASL}_{\text{succ}}\) 取得理论极小值: $\(\text{ASL}_{\min} = \sqrt{n} + 1\)$
  • 若索引表采用折半查找,块内采用顺序查找: $\(\text{ASL}_{\text{succ}} \approx \lceil \log_2(b+1) \rceil + \frac{s+1}{2}\)$

(4) 二叉排序树(BST)及平衡二叉树(AVL)

  • 比较次数等于待查关键字所在节点的深度(根节点为第 1 层)。
  • 最优情况(平衡二叉树):\(\text{ASL} = O(\log_2 n)\)。
  • 最坏情况(单支树,输入序列已有序):退化为单链表,\(\text{ASL} = \frac{n+1}{2} = O(n)\)。

3. 散列表的 ASL 深度推导(408 核心重难点)

散列表(Hash Table)建立了关键字集合到地址集合的直接映射 \(H(key)\)。由于散列函数存在“多对一”的多义性,冲突处理机制决定了其实际平均查找长度。

(1) 冲突处理方法分类

  1. 开放定址法(Open Addressing): $\(H_i = (H(key) + d_i) \bmod m, \quad i = 1, 2, \dots, k\)$
  2. 线性探测法:\(d_i = 1, 2, 3, \dots, m-1\)。极易引发聚集(Clustering)现象,增大查找长度。
  3. 二次探测法(平方探测法):\(d_i = 1^2, -1^2, 2^2, -2^2, \dots, \pm k^2\)(\(k \le m/2\)$ \text{)。可有效消除一次聚集,但需要表长} $\(m\)$ \text{为} $\(4k+3\) 形式的素数以遍历半数存储空间。
  4. 双重散列法:\(d_i = i \times H_2(key)\)。探测步长由关键字决定。
  5. 拉链法(Chaining / 链地址法): 将所有同义词存储在同一个单链表中,散列表各单元仅存储各链表的头指针。

(2) 散列表查找成功的 ASL 计算

  • 计算规则: 对于表中已存在的每一个关键字 \(key_i\)$ \text{,从其初值地址} $\(H(key_i)\)$ \text{开始探测,记录直到成功匹配到该元素时经历的比较次数} $\(C_i\)。
  • 数学表达: $\(\text{ASL}_{\text{succ}} = \frac{1}{n} \sum_{i=1}^n C_i\)$ 注意:分母恒为散列表中实际存储的关键字总数 \(n\)。

(3) 散列表查找失败的 ASL 计算及分母本质

这是考研中最具区分度的考点,必须深入理解其底层原理: * 终止判定准则: 在开放定址法中,从初始散列地址出发,逐个探测后续位置。当探测到某个真正未被占用的空单元(Empty)时,即可断定待查关键字必定不在表中,查找失败终止。 * 分母确定依据(模数 \(p\)$ \text{和物理表长} $\(m\) 的本质区别): 设散列表物理长度为 \(m\),散列函数采用除留余数法: $\(H(key) = key \bmod p \quad (p \le m)\)$ * 在等概率查找假设下,待查关键字落入散列函数各输出取值的概率是均等的。 * 散列函数的值域空间为 \([0, p-1]\)$ \text{,共} $\(p\) 种可能。 * 待查关键字经过散列函数计算后,初始探测地址只能落在 \([0, p-1]\)$ \text{区间内,绝对不可能直接被散列映射到} $\([p, m-1]\)。 * 因此,查找失败的可能起点等价类只有 \(p\)$ \text{个,查找失败的平均查找长度分母严格为} $\(p\)$ \text{(散列函数的模数),绝非物理表长} $\(m\): $\(\text{ASL}_{\text{fail}} = \frac{1}{p} \sum_{k=0}^{p-1} C_k'\)$ 其中 \(C_k'\)$ \text{表示以散列地址} $\(k\)(\(0 \le k \le p-1\))作为探测起点,依照冲突处理策略探测到第一个真正空单元时所耗费的比较次数。

(4) 墓碑标记(Deleted)对查找失败的影响

开放定址法中,若物理删除某一关键字(将其直接置为空单元),会截断经过该单元的后续同义词探测链,导致本应存在的元素无法被查出。因此,必须采用墓碑标记(Tombstone / Deleted)进行逻辑删除: * 查找操作: 遇到墓碑标记时,不能停止探测,必须将其视为一次失配的比较,继续向下探测!直到探测到真正的空单元(Empty)时,才能确认查找失败。 * 插入操作: 遇到墓碑标记时,可将新关键字填入该单元,复用存储空间。

开放定址法单元状态及处理动作矩阵:
┌───────────────┬─────────────────────────┬─────────────────────────┐
│ 单元状态      │ 查找操作 (Search)       │ 插入操作 (Insert)       │
├───────────────┼─────────────────────────┼─────────────────────────┤
│ 存放有效键值  │ 比较匹配? 命中停/失配走 │ 继续探测下一单元        │
│ 墓碑标记(Del) │ 计1次比较, 继续向下探测 │ 记录首个可用位置并复用  │
│ 真正空单元    │ 计1次比较, 判定失败终止 │ 写入新关键字, 插入终止  │
└───────────────┴─────────────────────────┴─────────────────────────┘

(5) 装填因子(Load Factor)对 ASL 的决定性影响

散列表的装填因子定义为: $$ \text{\alpha = \frac{\text{表中记录数 } n}{\text{散列表物理长度 } m}} $$ 散列表的平均查找长度不直接依赖于 \(n\)$ \text{或} $\(m\)$ \text{单独的数值,而是装填因子} $\(\alpha\) 的函数: * 线性探测法: $\(\text{ASL}_{\text{succ}} \approx \frac{1}{2}\left( 1 + \frac{1}{1 - \alpha} \right), \quad \text{ASL}_{\text{fail}} \approx \frac{1}{2}\left( 1 + \frac{1}{(1 - \alpha)^2} \right)\)$ * 拉链法: $\(\text{ASL}_{\text{succ}} \approx 1 + \frac{\alpha}{2}, \quad \text{ASL}_{\text{fail}} \approx \alpha + e^{-\alpha}\)$ 当 \(\alpha\) 增大时,冲突概率急剧增加,ASL 显著上升。


三、 近十年真题精讲(2016~2025)


【真题 1】2023 年 408 第 9 题 · 开放定址逻辑删除及失败 ASL

题目
现有长度为 5,初始为空的散列表 HT,散列函数 \(H(k) = (k + 4) \bmod 5\),用线性探测再散列法解决冲突。若将关键字序列 2022, 12, 25 依次插入 HT 中,然后删除关键字 25,则 HT 中查找失败的平均查找长度( )。
A. 1          B. 1.6          C. 1.8          D. 2.2

【解析】

  1. 关键字依次插入推导:
  2. 散列表容量 \(m = 5\)$ \text{,地址范围为} $\(0 \sim 4\)。
  3. 插入 2022: $\(H(2022) = (2022 + 4) \bmod 5 = 2026 \bmod 5 = 1\)$ HT[1] 为空,放入 HT[1],比较 1 次。
  4. 插入 12: $\(H(12) = (12 + 4) \bmod 5 = 16 \bmod 5 = 1\)$ HT[1] 已被占用,发生冲突;采用线性探测:\((1 + 1) \bmod 5 = 2\)。HT[2] 为空,放入 HT[2],比较 2 次。
  5. 插入 25: $\(H(25) = (25 + 4) \bmod 5 = 29 \bmod 5 = 4\)$ HT[4] 为空,放入 HT[4],比较 1 次。

  6. 删除关键字 25 的状态变迁: 在开放定址散列表中,删除元素不得直接物理置空,否则会导致冲突探测链断裂。因此必须在 HT[4] 设置墓碑删除标记(Deleted)。此时散列表的物理状态如下:

地址(HT): [0]        [1]       [2]       [3]        [4]
存储内容:  Empty     2022       12      Empty     [Deleted]
  1. 各起始散列地址查找失败的探测过程分析: 散列函数值域为 \(0 \sim 4\)$ \text{,待查关键字初始映射到各个地址的概率均等(各为} $\(\frac{1}{5}\))。依据规则,探测直到遇到真正空单元(Empty)才能断定查找失败;遇到 Deleted 标记必须计入比较次数并继续探测:
  2. 起始地址 0: 探测 HT[0],直接遇到 Empty,判定失败。比较次数 = 1。
  3. 起始地址 1: 探测 HT[1](有 2022,不匹配) \(\to\)$ \text{探测 HT[2](有 12,不匹配)} $\(\to\) 探测 HT[3](遇到 Empty,失败终止)。比较次数 = 3。
  4. 起始地址 2: 探测 HT[2](有 12,不匹配) \(\to\) 探测 HT[3](遇到 Empty,失败终止)。比较次数 = 2。
  5. 起始地址 3: 探测 HT[3],直接遇到 Empty,判定失败。比较次数 = 1。
  6. 起始地址 4: 探测 HT[4](遇到 Deleted 墓碑,算 1 次比较,不能停) \(\to\) 探测 HT[(4+1)%5] = HT[0](遇到 Empty,失败终止)。比较次数 = 2。

  7. 计算查找失败平均查找长度: $\(\text{ASL}_{\text{fail}} = \frac{\sum_{k=0}^4 C_k'}{5} = \frac{1 + 3 + 2 + 1 + 2}{5} = \frac{9}{5} = 1.8\)$

正确答案:C


【真题 2】2019 年 408 第 8 题 · 模数及表长分离的失败 ASL

题目
现有长度为 11 且初始为空的散列表 HT,散列函数是 \(H(key) = key \bmod 7\),采用线性探测再散列法解决冲突。将关键字序列 87, 40, 30, 6, 11, 22, 98, 20 依次插入到 HT 后,HT 查找失败的平均查找长度是( )。
A. 4          B. 5.25          C. 6          D. 6.29

【解析】

  1. 关键字依次插入及冲突探测: 散列表长度 \(m = 11\)$ \text{(存储下标} $\(0 \sim 10\)$ \text{),散列函数模数} $\(p = 7\)。
  2. \(87 \bmod 7 = 3 \implies \text{HT}[3] = 87\)
  3. \(40 \bmod 7 = 5 \implies \text{HT}[5] = 40\)
  4. \(30 \bmod 7 = 2 \implies \text{HT}[2] = 30\)
  5. \(6 \bmod 7 = 6 \implies \text{HT}[6] = 6\)
  6. \(11 \bmod 7 = 4 \implies \text{HT}[4] = 11\)
  7. \(22 \bmod 7 = 1 \implies \text{HT}[1] = 22\)
  8. \(98 \bmod 7 = 0 \implies \text{HT}[0] = 98\)
  9. \(20 \bmod 7 = 6\): HT[6] 已被 6 占用,线性探测 \((6+1) \bmod 11 = 7\)$ \text{;HT[7] 为空,写入} $\(\text{HT}[7] = 20\)。

  10. 散列表最终物理分布:

    下标:  0    1    2    3    4    5    6    7     8      9     10
    元素: 98   22   30   87   11   40    6   20   Empty  Empty  Empty
    
    可知:\(\text{HT}[0 \sim 7]\)$ \text{全部填满有效关键字,首个真正空单元为} $\(\text{HT}[8]\)。

  11. 查找失败分母及探测路径推导:

  12. 分母确定:散列函数为 \(key \bmod 7\)$ \text{,可能的初始散列地址仅有} $\(0, 1, 2, 3, 4, 5, 6\)$ \text{共 7 个(地址} $\(7 \sim 10\) 绝不可能由除留余数法初次散列产生)。因此分母必为 7。
  13. 各散列地址探测至首个空单元(HT[8])的比较次数:

    • 起始地址 0:探测 0, 1, 2, 3, 4, 5, 6, 7, 8,共比较 9 次。
    • 起始地址 1:探测 1, 2, 3, 4, 5, 6, 7, 8,共比较 8 次。
    • 起始地址 2:探测 2, 3, 4, 5, 6, 7, 8,共比较 7 次。
    • 起始地址 3:探测 3, 4, 5, 6, 7, 8,共比较 6 次。
    • 起始地址 4:探测 4, 5, 6, 7, 8,共比较 5 次。
    • 起始地址 5:探测 5, 6, 7, 8,共比较 4 次。
    • 起始地址 6:探测 6, 7, 8,共比较 3 次。
  14. 查找失败平均查找长度计算: $\(\text{ASL}_{\text{fail}} = \frac{9 + 8 + 7 + 6 + 5 + 4 + 3}{7} = \frac{42}{7} = 6\)$

易错干扰项辨析: 若误将散列表长度 11 作为分母,错误计算为 \(\frac{42}{11} \approx 3.82\)$ \text{或包含} $\(7 \sim 10\)$ \text{算出的} $\(\frac{42+1+1+1+1}{11} = \frac{46}{11} \approx 4.18\),或者选项 B 的 5.25(若将分母误算为 8),均会落入命题陷阱。

正确答案:C


【真题 3】2018 年 408 第 9 题 · 开放定址查找成功 ASL

题目
现有长度为 7、初始为空的散列表 HT,散列函数 \(H(k) = k \bmod 7\),用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到 HT 后,查找成功的平均查找长度是( )。
A. 1.5          B. 1.6          C. 2          D. 3

【解析】

  1. 关键字插入过程及成功比较次数:
  2. 插入 22: \(H(22) = 22 \bmod 7 = 1\)。 HT[1] 为空,直接存入 HT[1]。 查找 22 时,直接在 HT[1] 命中,比较次数 \(C_1 = 1\)。
  3. 插入 43: \(H(43) = 43 \bmod 7 = 1\)。 HT[1] 已被占用(冲突);线性探测 \((1 + 1) \bmod 7 = 2\)。HT[2] 为空,存入 HT[2]。 查找 43 时,先查 HT[1](未命中),再查 HT[2](命中),比较次数 \(C_2 = 2\)。
  4. 插入 15: \(H(15) = 15 \bmod 7 = 1\)。 HT[1] 已被 22 占用(第 1 次探测); 线性探测到 HT[2],已被 43 占用(第 2 次探测); 线性探测到 \((2 + 1) \bmod 7 = 3\),HT[3] 为空,存入 HT[3](第 3 次探测)。 查找 15 时,依次比较 HT[1], HT[2], HT[3],命中,比较次数 \(C_3 = 3\)。

  5. 散列表物理存储状态:

    地址(HT): [0]    [1]    [2]    [3]    [4]    [5]    [6]
    存储内容:  空     22     43     15     空     空     空
    比较次数:          1      2      3
    

  6. 计算查找成功的平均查找长度: 查找成功的分母为关键字个数 \(n = 3\): $\(\text{ASL}_{\text{succ}} = \frac{1 + 2 + 3}{3} = \frac{6}{3} = 2\)$

正确答案:C


四、 核心解题套路与易错陷阱

1. 散列表 ASL 成功及失败的分母防混淆基石

下表给出了严格的数学对照:

┌──────────────┬──────────────────────────┬──────────────────────────────────────────┐
│ 指标类型     │ 分母取值                 │ 本质数学意义                             │
├──────────────┼──────────────────────────┼──────────────────────────────────────────┤
│ ASL (成功)   │ 关键字总个数 n           │ 对表中已存在的每一个元素等概率查找       │
├──────────────┼──────────────────────────┼──────────────────────────────────────────┤
│ ASL (失败)   │ 散列函数模数 p (非表长 m)│ 待查键值等概率映射至散列函数的值域空间   │
└──────────────┴──────────────────────────┴──────────────────────────────────────────┘

核心口诀:
算成功,分母数元素;算失败,分母看模数!


2. 开放定址法探测链的边界及回绕陷阱

在计算线性探测时,必须严格区分“模数 \(p\)$ \text{”和“表长} $\(m\)”的作用阶段: 1. 初始散列位置:由散列函数 \(H(key) = key \bmod p\)$ \text{决定,取值范围在} $\([0, p-1]\)。 2. 冲突探测与回绕:探测公式为 \(H_i = (H(key) + i) \bmod m\)$ \text{。此处的回绕是模表长} $\(m\)$ \text{,绝不能模} $\(p\)$ \text{!因为物理散列表的有效索引空间是} $\(0 \sim m-1\)。


3. 墓碑标记的三大规则辨析

针对带有逻辑删除标记(Deleted / Tombstone)的散列表,解题时应牢记以下准则: 1. 查找操作(包括成功及失败):遇到墓碑标记必须计入 1 次比较,并且严禁停止探测,必须沿着探测链继续向下寻找。 2. 失败终点判定:只有探测到真正的空白单元(Empty),且待查键值未在路径中出现,方可判定查找失败。 3. 墓碑标记对失败 ASL 的直接影响:墓碑标记相当于拉长了探测链,使得跨越该墓碑的查找探测步数增加,从而使查找失败的 ASL 严格增大。


4. 拉链法(链地址法)ASL 的比较次数判定

在链地址法中,处理同义词冲突由各单链表承载: * 查找成功:节点在单链表中的位置决定了比较次数。表头第一个节点需比较 1 次,第 \(k\)$ \text{个节点需比较} $\(k\) 次。 $$ \text{ASL}_{\text{succ}} = \frac{1}{n} \sum (\text{各关键字在链表中的位序}) $$ * 查找失败:在 408 统考体系中,查找失败通常定义为“与单链表中的有效关键字进行比较”。若散列到的链表为空,关键字比较次数为 0;若散列到的链表非空,则需遍历完该链表的所有有效节点,比较次数等于该链表包含的节点个数。分母同样为散列函数模数 \(p\)。


五、 考点速记清单

  1. 基本概念:ASL 是查找算法关键字比较次数的数学期望,衡量算法时间复杂度。
  2. 顺序查找:无序表成功 \(\text{ASL} = \frac{n+1}{2}\)$ \text{;有序表失败} $\(\text{ASL} = \frac{n}{2} + \frac{n}{n+1}\)。
  3. 折半查找:判定树节点数 \(n\)$ \text{,失败外部节点数} $\(n+1\)$ \text{,树高} $\(\lceil \log_2(n+1) \rceil\);成功看各内部节点层数,失败看外部节点双亲层数。
  4. 分块查找:顺序块查找最优分块数为 \(b = s = \sqrt{n}\)$ \text{,对应} $\(\text{ASL}_{\min} = \sqrt{n} + 1\)。
  5. 散列成功 ASL:分子为各关键字从初始地址探测到自身实际位置的比较次数总和,分母为关键字总数 \(n\)。
  6. 散列失败 ASL:分子为从各散列函数初值(\(0 \sim p-1\)$ \text{)探测到首个真正空单元(Empty)的比较次数总和,分母严格为散列函数模数} $\(p\)。
  7. 墓碑标记:遇到 Deleted 标记必须计入比较次数,不可停步,直至遇到真正空单元才算失败终止。