哈希表Hash table

将键映射到桶，使用冲突处理策略定位记录。

核心约束: 相等键必须产生相容的哈希值；冲突需进一步判等。
适用问题: 按键精确定位，去重、多索引和缓存。
边界与取舍: 不天然支持有序遍历；负载率、冲突与扩容影响延迟。

键先映射到桶，命中后仍需处理冲突并比较完整键。

常见操作#

n 为键数，C 为桶容量，α 为负载率，L 为键长；以下期望常数界假定哈希和相等比较为 $O(1)$ 。

操作	时间复杂度	条件与说明
按键查找	期望 $O(1)$ ；常见实现最坏 $O(n)$	哈希分布良好且负载率受控；树化桶等实现有不同最坏界。
插入 / 删除	期望摊还 $O(1)$	扩缩容使用适当策略；单次重建或严重冲突可达 $O(n)$ 。
扩容并重新分桶	$O(n)$	表容量与元素数同阶，单个键的哈希成本视作常数。
遍历所有条目	$O(n+C)$	例如需要扫描桶数组的实现；过低负载率会增加扫描空桶的成本。
计算字符串键哈希	$O(L)$	未缓存哈希时要读取键内容，不能忽略在所谓 $O(1)$ 查找之外。

时间与空间#

时间复杂度: 查找 / 更新通常期望摊还 $O(1)$
存储空间: $O(n+C)$

普通哈希表不提供有序遍历或范围查询；对抗输入与随机种子会影响冲突风险。

工程中的应用#

6 个案例 · 附源码

QEMU·TCG 翻译块v9.2.0

复用已翻译的机器代码块

QEMU TCG 用 QHT 保存 TranslationBlock 索引，帮助复用与当前客体执行状态一致的翻译结果。

附源码片段 · 缓存与复用

libvirt·Domain 对象管理v10.10.0

让名称和 UUID 指向同一虚拟机对象

libvirt 为 Domain 对象维护 UUID 与名称两个哈希索引，两个入口指向同一个对象。

附源码片段 · 索引与查找

vLLM·V1 / 前缀缓存v0.8.5 · V1

用块哈希复用 prompt 前缀

把上下文身份编码进块哈希，让重复请求共享已经计算的 KV cache。

哈希表分块与页映射

附源码片段 · 缓存与复用

Redis·Sorted Set7.2.0

排行榜为何同时需要跳表和哈希表

Redis 有序集合既要按成员查分数，也要按分数和名次遍历；较大集合通过两种索引服务这些访问方式。

跳表哈希表

附源码片段 · 索引与查找

Redis·Dictionary7.2.0

将哈希表迁移分散到多次操作

Redis 7.2.0 的字典扩缩容保留新旧两张哈希表，逐桶迁移，降低一次性搬迁全部条目的停顿。

哈希表渐进式 Rehash 渐进式工作

附源码片段 · 索引与查找

Git·xdiff 文本差异v2.46.0

代码 diff 在编辑长度与可读性间取舍

Git 文本差异默认采用 Myers 路径；选择 patience 时先利用双方唯一的公共行建立锚点，再处理锚点之间的差异。

Myers Diff Patience Diff 哈希表

附源码片段 · 检索与计算

基础原理参考资料

Java 21 · HashMap负载率、容量、基本操作的分布前提和迭代成本。

Open Data Structures · ChainedHashTable链式哈希的期望分析和重建。