当前位置：首页 > article >正文

7.5考研408数据结构散列表专题深度解析

article 2025/3/31 2:36:37

考研408数据结构散列表专题深度解析

一、散列表基本概念与定义

1.1 核心定义

散列表（Hash Table） 是一种通过散列函数将关键字映射到存储位置的数据结构，实现 $O (1)$ 时间复杂度的查找、插入和删除操作。其核心要素包括：

散列函数： $\text{散列地址}$ ，需满足：
- 确定性：相同关键字映射到相同地址
- 均匀性：尽可能减少冲突概率
冲突（Collision）：不同关键字映射到同一地址的现象
装填因子： $\alpha = \frac{n}{m}$ ，表示表中元素数 $n$ 与表长 $m$ 的比值，直接影响查找效率

1.2 基本结构

散列表由以下部分组成：

存储数组：存放数据元素
冲突解决机制：开放定址法/链地址法
辅助参数：装填因子阈值（通常 $\alpha \leq 0.75$ ）

二、散列函数设计

2.1 常见散列函数类型

方法	公式/原理	适用场景	易错点
直接定址法	$\cdot key + b$	关键字连续分布	未考虑空位浪费问题
除留余数法	$\mod p$	通用场景（ $p$ 取质数）	错误选择非质数导致聚集
平方取中法	取关键字平方的中间若干位	关键字长度不一致	中间位数选择不当
折叠法	分割关键字后叠加求和	长关键字（如身份证号）	折叠方向影响均匀性

易错点：

除留余数法中误选 $p=2^k$ ，导致低位分布不均匀
平方取中法未考虑关键字位数奇偶性导致中间位截取错误

三、冲突处理方法

3.1 开放定址法

核心思想：发生冲突时，按探测序列寻找下一个空闲地址
探测序列公式：
$H_i = (H(key) + d_i) \mod m \quad (i=0,1,2,\dots)$

3.1.1 线性探测法

$d_i = i$
特点：

简单易实现
二次聚集：易形成长连续占用区
模拟题：

表长 $m = 7$ ，散列函数 $\mod 7$ ，依次插入{7,15,21,8}，画出线性探测后的存储状态。
答案：

索引：0  1  2  3  4  5  6  
元素：   15 21 7  8

3.1.2 平方探测法

$d_i = \pm i^2$
特点：

避免聚集现象
要求表长 $m = 4 k + 3$ （质数）
难点：
可能无法探测到所有位置（需数学证明）

3.1.3 再散列法

使用第二个散列函数：
$H_i = (H_1(key) + i \cdot H_2(key)) \mod m$
适用场景：高冲突率场景

3.2 链地址法

原理：每个地址维护链表存储同义词
优势：

无聚集现象
允许装填因子 $\alpha >1$
实现代码：

typedef struct HashNode {
    int key;
    struct HashNode *next;
} HashNode;

typedef struct {
    int size;
    HashNode **table;
} HashTable;

void insert(HashTable *ht, int key) {
    int index = key % ht->size;
    HashNode *node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->next = ht->table[index];
    ht->table[index] = node;
}

易错点：

未初始化链表头指针导致段错误
删除节点时未正确处理前驱指针

四、关键考点与真题解析

4.1 平均查找长度（ASL）计算

4.1.1 成功查找ASL

公式：
$ASL_{成功} = \frac{1}{n} \sum_{i=1}^{n} C_i$
其中 $C_i$ 为第 $i$ 个元素的探测次数

真题（2010年408）：

关键字序列{7,8,30,11,18,9,14}，散列函数 $\times key) \mod 7$ ，表长 $m = 10$ ，线性探测处理冲突。求成功查找的ASL。
解析：

计算各元素地址：
- H(7)=21 mod7=0 → 位置0
- H(8)=24 mod7=3 → 位置3
- H(30)=90 mod7=6 → 位置6
- H(11)=33 mod7=5 → 位置5
- H(18)=54 mod7=5（冲突）→ 探测位置6（冲突）→位置7
- H(9)=27 mod7=6（冲突）→位置7（冲突）→位置8
- H(14)=42 mod7=0（冲突）→位置1
各元素探测次数：
{1,1,1,1,3,3,2}
ASL = (1+1+1+1+3+3+2)/7 = 12/7 ≈ 1.71

4.1.2 失败查找ASL

公式：
$ASL_{失败} = \frac{1}{m} \sum_{i=0}^{m-1} 探测次数直到空位$

模拟题：

对上述真题计算查找失败的ASL。
答案：

对每个地址i（0≤i≤6）：
- i=0: 探测0→1（空）→2次
- i=3: 探测3→4→5→6→7→8→9（空）→7次
- …（其他地址类似计算）
ASL失败 = (2+3+1+7+2+5+6)/7 ≈ 3.43

五、高频易错点总结

5.1 装填因子误区

错误认知：装填因子仅影响空间利用率
正确理解： $\alpha$ 直接影响冲突概率，当 $\alpha>0.75$ 时开放定址法效率急剧下降

5.2 探测序列错误

线性探测未循环到表首继续探测
平方探测未正确处理负数情况（ $d_i = i^2$ 和 $d_i = -i^2$ 交替）

5.3 删除操作处理

开放定址法中直接置空导致查找链断裂，需标记为"已删除"
链地址法删除节点时未更新前驱节点的next指针

六、综合应用题训练

6.1 真题再现（2018年408）

题目：
设散列表长 $m = 11$ ，散列函数 $\mod 11$ ，采用平方探测法处理冲突（ $d_i = \pm i^2$ ）。插入序列{16,74,60,43,54,90,46}，要求：

画出最终散列表
计算成功查找ASL
若删除46后插入76，画出新表

解析：

插入过程：
- 16 mod11=5 → 位置5
- 74 mod11=8 → 位置8
- 60 mod11=5（冲突）→5+1²=6 →位置6
- 43 mod11=10 →位置10
- 54 mod11=10（冲突）→10+1²=0 →位置0
- 90 mod11=2 →位置2
- 46 mod11=2（冲突）→2+1²=3 →位置3
ASL计算：
各元素探测次数{1,1,2,1,2,1,2} → ASL=10/7≈1.43
删除46后插入76：
- 删除46后位置3标记为"已删除"
- 76 mod11=10（冲突）→10+1²=0（冲突）→10-1²=9 →位置9

七、模拟题精选

7.1 基础题

题目1：
表长 $m = 7$ ，散列函数 $\mod 7$ ，线性探测处理冲突。插入序列{3,10,7,4,5}，求：

散列表最终状态
成功查找ASL
答案：
索引：0 1 2 3 4 5 6
元素：7 3 10 4 5
ASL=(1+1+2+1+3)/5=8/5=1.6

7.2 进阶题

题目2：
设计散列表存储学生学号（10位数字），要求：

选择适合的散列函数并说明理由
预估装填因子达到0.8时的性能变化
写出删除操作的伪代码
解析：
建议使用折叠法：将学号分为3段（如前4位、中间3位、后3位），求和后取模
当 $\alpha=0.8$ 时，开放定址法的ASL将呈指数上升，建议扩容或改用链地址法
删除伪代码：

void delete(HashTable *ht, int key) {
    int index = hash(key);
    HashNode *prev = NULL;
    HashNode *curr = ht->table[index];
    while (curr) {
        if (curr->key == key) {
            if (prev) prev->next = curr->next;
            else ht->table[index] = curr->next;
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}