散列表 vs 二叉搜索树

概述

散列表（Hash Table）与二叉搜索树（Binary Search Tree, BST）是两种最常用的动态集合数据结构，它们各有优劣，适用于不同的应用场景。本页从多个维度对两者进行全面对比。

核心差异

特性	散列表	二叉搜索树
搜索	平均 $O (1)$ ，最坏 $O (n)$	平均 $O (l g n)$ ，最坏 $O (n)$ （退化为链表）
插入	平均 $O (1)$ ，最坏 $O (n)$	平均 $O (l g n)$ ，最坏 $O (n)$
删除	平均 $O (1)$ ，最坏 $O (n)$	平均 $O (l g n)$ ，最坏 $O (n)$
查找最小值	$O (n)$ （需要遍历所有桶）	$O (l g n)$ （沿左子树下降），最坏 $O (n)$
查找最大值	$O (n)$	$O (l g n)$ ，最坏 $O (n)$
前驱/后继	$O (n)$ （无序结构，需要遍历）	$O (l g n)$ （利用树的结构信息）
范围查询	$O (n)$ （需要扫描所有元素）	$O (k + l g n)$ （ $k$ 为结果集大小）
有序遍历	$O (n l g n)$ （需要先排序）	$O (n)$ （中序遍历直接得到有序序列）
最坏情况保证	无（依赖哈希函数质量）	平衡 BST（如红黑树）保证 $O (l g n)$
元素有序性	不保持	保持（中序遍历有序）
空间开销	可能浪费（负载因子 < 1 时有空桶）	每个节点存储左右子指针，开销固定
哈希函数依赖	强依赖（哈希函数质量决定性能）	不依赖
缓存友好性	较好（连续内存，开放寻址法）	较差（节点分散在堆上，指针追踪多）

性能对比总结

散列表在平均情况下更快：搜索、插入、删除均为 $O (1)$ ，是常数时间。
平衡 BST 在最坏情况下更可靠：红黑树保证所有操作 $O (l g n)$ ，散列表的最坏情况为 $O (n)$ 。
BST 天然支持有序操作：最小值、最大值、前驱、后继、范围查询、有序遍历都是 BST 的强项。

适用场景

选择散列表的场景

只需要精确查找：如字典、缓存、去重、计数器等场景，不需要有序性。
平均性能优先：能接受极小概率的最坏情况，追求平均 $O (1)$ 的极致性能。
键的分布均匀：哈希函数能将键均匀映射到桶中，避免大量冲突。
不需要范围查询：不需要”查找所有在 $[a, b]$ 之间的元素”这类操作。
内存充足：能接受一定的空间浪费来换取时间效率。

典型应用：

编程语言的字典/Map 实现（Python dict、Java HashMap、C++ unordered_map）
数据库索引中的哈希索引
缓存系统（Redis、Memcached）
符号表（编译器中的标识符管理）

选择二叉搜索树（特别是平衡 BST）的场景

需要有序操作：需要最小值、最大值、前驱、后继、范围查询、有序遍历。
需要最坏情况保证：不能接受 $O (n)$ 的最坏情况，要求所有操作都有 $O (l g n)$ 保证。
数据动态变化频繁：需要频繁的插入和删除，同时保持有序性。
需要区间操作：如区间树、线段树等高级数据结构的基础。

典型应用：

数据库索引中的 B/B+ 树（BST 的多路推广）
标准库中的有序容器（C++ std::map/std::set、Java TreeMap/TreeSet）
文本编辑器的行号管理
优先队列的某些实现

两者都不适用的场景

数据基本不变：如果数据集很少变化，使用有序数组 + 二分查找可能更高效（缓存友好，常数因子小）。
需要极低延迟：某些实时系统可能需要更可预测的数据结构。

参见

散列表 — 散列表的详细定义与实现
二叉搜索树 — 二叉搜索树的详细定义与操作
红黑树 — 一种自平衡 BST，提供最坏 $O (l g n)$ 保证
AVL树-vs-红黑树 — 两种平衡 BST 的对比