GESP 七级 · GESP 202312 C++ 七级 第 10 题

对关键字序列 $\{44,\ 36,\ 23,\ 35,\ 52,\ 73,\ 90,\ 58\}$ 建立哈希表，哈希函数为 $h(k) = k \% 7$，执行下面的 Insert 函数，则等概率情况下的平均成功查找长度（即查找成功时的关键字比较次数的均值）为（ ）。

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
using namespace std;

typedef struct Node {
    int data;
    struct Node *next;
} Node;
Node* hTab[7];
int key[] = {44, 36, 23, 35, 52, 73, 90, 58, 0};
void Insert()
{
    int i, j;
    Node *x;

    for (i = 0; key[i]; i++) {
        j = key[i] % 7;
        x = new Node;
        x->data = key[i];
        x->next = hTab[j];
        hTab[j] = x;
    }

    return;
}

这道题考哈希表链地址法的平均查找长度。拿到题先算每个关键字的哈希地址，还原出各槽位链表长度，再按头插顺序累加比较次数，最后除以总数。

很多同学算出各槽位元素个数后，直接把这些个数相加当作总比较次数，这是把链地址法当成线性探测法或简单平均了，忽略了同一槽内多个元素查找时比较次数是累加的。还有人会误用ASL=总元素数/表长这个线性探测公式，或者数错2号槽有3个元素、3号槽有2个元素这些细节，导致总数偏差。

考点定位与概念拆解

哈希表是GESP七级数据结构模块的高频考点，尤其链地址法（拉链法）的冲突处理与平均查找长度（ASL）计算，是区分度最大的地方。这道题的核心不是让你写代码，而是让你读懂这段插入代码后，在脑子里还原出哈希表长什么样，然后算出在等概率情况下，查找成功需要比较多少次。

先说概念：哈希函数 $h(k)=k\%7$ 把8个关键字映射到0~6共7个槽位。链地址法的特点是：每个槽位是一个链表，新元素总是插在链表头部（头插法）。因此，同一槽位内，先插入的元素在链表尾部，后插入的在头部。查找时，必须从头到尾遍历，第一个元素比较1次，第二个2次，第三个3次……

命题视角：为什么这么考？

命题人特意给了C++代码，就是想看你是否真的理解“头插”带来的顺序变化。如果只是背公式，看到 $k\%7$ 直接算出各槽位元素个数，然后草率地用“总元素数/表长”或“总元素数/总槽位”来估算，就会掉进坑里。真正的难点在于：你得先算出每个关键字的哈希地址，再按插入顺序（44→36→23→35→52→73→90→58）逐个模拟链表增长，最后统计每个槽位内元素的比较次数之和。