散列表

概述

散列表（Hash Table） 是一种通过散列函数 $h(k)$ 将关键字映射到数组槽位来实现字典操作的通用数据结构。它以 $O(1)$ 的期望时间完成搜索、插入和删除，是实际应用中最常用的字典实现之一。与 直接寻址表 不同，散列表使用远小于全域 $|U|$ 的存储空间 $m$，通过散列函数将关键字压缩映射，代价是需要处理冲突（collision）问题。

定义

散列表

散列表是一种基于数组的数据结构，它使用一个散列函数 $h:U\to \{0,1,\dots ,m-1\}$ 将全域 $U$ 中的关键字 $k$ 映射到大小为 $m$ 的数组 $T[\mathrm{0..}m-1]$ 的某个槽位（slot）上。当两个不同的关键字被映射到同一个槽位时，称为冲突（collision）。

核心思想

散列表的核心思想是：用少量的空间 + 散列函数，将大域映射到小表。

• 直接寻址：关键字 $k$ $\to$ 槽位 $k$（需要 $O(|U|)$ 空间）
• 散列：关键字 $k$ $\to$ 槽位 $h(k)$（只需要 $O(m)$ 空间，$m\ll |U|$）

伪代码

搜索：

HASH-SEARCH(T, k)
    return LIST-SEARCH(T[h(k)], k)   // 链地址法

插入：

HASH-INSERT(T, x)
    LIST-INSERT(T[h(x.key)], x)      // 将 x 插入到 T[h(x.key)] 对应的链表头部

删除：

HASH-DELETE(T, x)
    LIST-DELETE(T[h(x.key)], x)      // 从 T[h(x.key)] 对应的链表中删除 x

核心性质

装载因子

装载因子

散列表的装载因子（load factor）定义为： $\alpha =\frac{n}{m}$ 其中 $n$ 是当前存储的元素数量，$m$ 是散列表的槽数（表的大小）。装载因子衡量了散列表的”满”程度。

• 当 $\alpha =0$ 时，表为空；当 $\alpha =1$ 时，平均每个槽位有一个元素。
• 装载因子直接影响散列表的性能：$\alpha$ 越大，冲突概率越高，操作时间越长。
• 对于 链地址法，$\alpha$ 可以大于 1；对于 开放寻址法，必须保证 $\alpha <1$。

时间复杂度

散列表的操作时间是期望 $O(1)$，而非最坏情况 $O(1)$。

操作	期望时间	最坏时间	说明
搜索	$O(1)$	$O(n)$	最坏情况所有元素冲突到同一槽位
插入	$O(1)$	$O(n)$	同上
删除	$O(1)$	$O(n)$	同上

冲突问题

冲突

当两个关键字 $k_1\ne k_2$ 满足 $h(k_1)=h(k_2)$ 时，称为发生了冲突（collision）。

由于 $|U|>m$，根据鸽巢原理，冲突不可避免。处理冲突的两种主要方法：

1. 链地址法（Chaining）：每个槽位维护一个链表，冲突的元素串在同一链表中
2. 开放寻址法（Open Addressing）：所有元素都存放在表内，冲突时按探测序列寻找下一个空槽

散列函数的要求

一个好的散列函数应满足：

• 确定性：同一关键字始终映射到同一槽位
• 均匀性：将关键字尽可能均匀地分散到各槽位
• 高效性：计算 $h(k)$ 的时间为 $O(1)$

详见 散列函数。

章节扩展

散列表 vs. 直接寻址表

特性	直接寻址表	散列表
映射方式	$k\to k$（直接）	$k\to h(k)$（间接）
空间	$O(\Vert U\Vert )$	$O(m)$，$m$ 可远小于 $\Vert U\Vert$
最坏时间	$O(1)$	$O(n)$
期望时间	$O(1)$	$O(1)$
冲突	无	有（需专门处理）

散列表 vs. 平衡搜索树

特性	散列表	平衡搜索树（如红黑树）
搜索（期望）	$O(1)$	$O(\lg n)$
搜索（最坏）	$O(n)$	$O(\lg n)$
有序遍历	不支持	支持
适用场景	无序字典、快速查找	需要范围查询/有序操作

参见

• 直接寻址表 —— 散列表的前身，用直接映射实现字典
• 散列函数 —— 散列表的核心组件，决定映射质量
• 链地址法 —— 冲突处理方法之一，用链表存储冲突元素
• 开放寻址法 —— 冲突处理方法之二，在表内探测空槽