散列表

概述

散列表（Hash Table）是一种基于哈希函数将键映射到数组位置的数据结构，支持平均 $O(1)$ 的查找、插入和删除操作。其核心挑战在于冲突处理——当两个不同的键被映射到同一位置时，需要通过链表法或开放寻址法解决。散列表是符号表、数据库索引和缓存的核心实现。

定义

散列表（Hash Table）

散列表使用哈希函数 $h:U\to \{0,1,\dots ,m-1\}$ 将来自全域 $U$ 的键映射到大小为 $m$ 的数组（桶）中。

两个关键参数：

• 装载因子（load factor）：$\alpha =n/m$，其中 $n$ 为已存储元素数
• 哈希函数：将键均匀映射到桶中，理想情况下每个键等概率映射到每个位置

冲突解决方法

链表法（Chaining）：每个桶维护一个链表，冲突的元素追加到链表中。

开放寻址法（Open Addressing）：冲突时按某种探查序列寻找下一个空桶。常见探查策略：

• 线性探查：$h(k,i)=(h^{\prime }(k)+i)\mathrm{mod}m$
• 二次探查：$h(k,i)=(h^{\prime }(k)+c_{1}i+c_2{i}^2)\mathrm{mod}m$
• 双重散列：$h(k,i)=(h_1(k)+i\cdot h_2(k))\mathrm{mod}m$

核心性质

性质	描述	备注
平均查找	$O(1)$（简单均匀散列假设下）	取决于装载因子 $\alpha$
最坏查找	$O(n)$	所有键映射到同一桶
插入/删除	平均 $O(1)$	删除在开放寻址法中较复杂
装载因子	$\alpha =n/m$	$\alpha$ 越大，冲突越多
空间效率	链表法可 $\alpha >1$，开放寻址法需 $\alpha <1$	需要权衡空间和时间

性能分析（简单均匀散列假设）

在简单均匀散列假设下（每个键等概率映射到每个位置，且独立）：

操作	链表法	开放寻址法
不成功搜索	$\Theta (1+\alpha )$	$\Theta (1/(1-\alpha ))$
成功搜索	$\Theta (1+\alpha /2)$	$\Theta (1/\alpha \cdot \ln (1/(1-\alpha )))$

应用场景

• 符号表：编译器中的变量名查找
• 数据库索引：快速定位数据记录
• 缓存实现：LRU 缓存等
• 去重：快速判断元素是否已出现
• 字典/Map：编程语言中的关联数组（Python dict, Java HashMap）

参见

• 概率分析 — 散列表性能的概率分析
• 摊还分析 — 动态散列表扩容的摊还分析
• 在线算法 — 缓存淘汰策略（LRU 等）