Theory · Data Structure · Hash Table
平均 O(1) 的艺术：哈希函数 · 冲突解决 · 负载因子与渐进 rehash · 一致性哈希 —— 从内存结构到分布式分片
key → 下标的一步映射：均匀、确定、雪崩；坏函数全碰撞退化 O(n)
拉链 vs 开放寻址、tombstone、负载因子——渐进 rehash 把大搬家摊薄
一致性哈希管分布式分片，布隆过滤器管近似集合——同一个思想的不同尺度
Why It Matters
号码不在表里时要比完全部 100 万条，在表里平均也要比 50 万条。每次查询都这样，用户会明显感到卡。
每次只要 约 20 次比较（log₂10⁶ ≈ 20）。代价是插入新号码要维持有序——挪数据 O(n)，或者上一棵平衡树。
如果有一个公式，把号码直接变成"第几号抽屉"，那查询就是算一次 + 看一眼——1 次操作，和总共有多少条完全无关。这就是哈希表：把"查找"变成"计算"。
去重、计数、缓存索引、路由表、编译器符号表、数据库 join 全都要退回 O(n) 或 O(log n)。所有语言把它做成内置类型（Go map / Java HashMap / Python dict），正是因为它是"按 key 取值"这个最常见动作的最优解。
| 做法 | 100 万条里查一次 | 额外代价 |
|---|---|---|
| 逐条比较 | 最坏 100 万次 | 无 |
| 排序 + 二分 | 约 20 次 | 插入要维持有序 |
| 平衡树 | 约 20 次 | 指针开销、比较开销 |
| 哈希表 | 约 1 次（平均） | 多占内存 + 丢失顺序 |
Prerequisites & Glossary
| 术语 | 一句话理解（细节后面展开） |
|---|---|
| 键值对 key-value | 用 key（号码）去取 value（姓名）；哈希表存的就是一堆键值对 |
| 哈希函数 hash | 把任意 key 揉成一个整数的函数；同一个 key 每次揉出的数必须相同 |
| 桶 bucket / 槽 slot | 存放键值对的"抽屉"，编号 0..n−1；桶数组就是那排抽屉 |
| 取模 % | 把很大的哈希值压进 0..n−1：h % n；n 是 2 的幂时等价于位与 h & (n−1) |
| 冲突 collision | 两个不同的 key 算出同一个桶号——不可避免，只能处理 |
| 鸽巢原理 | 10 只鸽子放进 9 个笼子，必有一笼装两只；key 无限、桶有限，所以必冲突 |
| 负载因子 α | 已存元素数 ÷ 桶数，衡量"抽屉挤不挤"，超过阈值就扩容 |
| 拉链法 chaining | 撞了就在这个桶后面挂一条链，同桶的都串起来 |
| 开放寻址 probing | 撞了就换下一个空桶放，不用链；探测 probe = 依次试探的过程 |
| rehash 重哈希 | 桶数变了，下标依赖桶数，所以已有元素必须全部重新算位置并搬迁 |
数组与链表 → 哈希表由这两样材料拼成（桶数组 + 冲突链）
复杂度分析 → "平均 O(1) 而最坏 O(n)"这句话到底在说什么
哈希表 = 一排编号的抽屉 + 一个把钥匙算成抽屉号的公式。
存：算出号，放进去。取：算出号，看一眼。
不同钥匙可能算出同一个抽屉号。于是各家实现的全部差异，只是在回答两个问题：
· 撞了怎么办？→ 挂链（拉链法）还是换个空抽屉（开放寻址）；
· 抽屉不够了怎么办？→ 什么时候扩容（负载因子）、怎么搬（一次搬完还是边用边搬）。
Hashing Idea · CLRS ch11
把开场那个"能不能算出它在哪"的想法正式化：下标 = hash(key) 压缩到桶数范围内，一次计算直达抽屉。
数组逐个比较 O(n)；平衡树按序比较 O(log n)。哈希表直接算出位置：index = hash(key) → 寻址 O(1)——把"查找"变成"计算"。
① 确定性：同 key 同值；② 均匀性：输出均匀铺满下标空间，冲突少；③ 雪崩效应：输入差 1 bit，输出约一半 bit 翻转——常见实现 FNV-1a、MurmurHash、xxHash。
① 额外内存（负载因子 < 1）；② 冲突不可避免（鸽巢原理：key 无限、桶有限）；③ 无序语义丢失——有序需求请回树/跳表。
| 结构 | 查找 | 有序? |
|---|---|---|
| 无序数组 | O(n) | — |
| 有序数组+二分 | O(log n) | ✓（但插入 O(n)） |
| 平衡 BST | O(log n) | ✓ 范围查询 |
| 哈希表 | O(1) 平均 | ✗ |
Key To Index In One Step
Separate Chaining
Open Addressing · Probing
没有链表，一切都在数组里。线性探测：(i+1) % n；平方探测：i+1², i+2², i+4²…；双重哈希：i + k·hash₂(key)。
连续占用的块会"越滚越大"（primary clustering）——碰撞越多、探测链越长、更容易再碰撞，恶性循环。平方探测缓解；双重哈希让探测序列与 key 相关，最均匀。
直接置空会切断探测链——排在其后的同位元素再也找不到。所以放"已删除"标记：查找时跳过、插入时可复用；墓碑多了拉低效率，定期 rehash 清理。
Python dict、C++ robin_hood/flat_hash_map 家族、Go 1.24 Swiss Table（组探测）、CPU 高频场景——缓存友好是开放寻址的最大理由：数据连续、无指针追踪。
| 维度 | 拉链法 | 开放寻址 |
|---|---|---|
| 删除 | 容易（摘节点） | tombstone 墓碑 |
| 负载因子 | 可 > 1（链变长） | 必须 < 1，接近 1 性能悬崖 |
| 缓存 | 差（指针追踪） | 好（连续内存） |
| 最坏查找 | O(n)（树化后 O(log n)） | O(n) |
| 代表 | Java HashMap、Go 经典 map、Redis dict | Python dict、Swiss Table、flat_hash_map |
Load Factor · Resize
α 越大越省内存但冲突越多。拉链法平均查找 ≈ 1 + α/2；开放寻址在 α → 1 时探测长度爆炸。每个实现都设了扩容阈值。
Java HashMap 0.75（默认 16 桶，超 12 个扩容 2 倍）；Redis dict 平时 1.0（有 BGSAVE 时提到 5.0，防写时复制期间扩容）；Go 经典 map 6.5/8 ≈ 81%（因为以桶为单位，不精确数元素）；Python dict 2/3。
桶数翻倍 → 所有元素重新计算下标（必须重哈希：下标依赖容量）。搬迁本身 O(n)——怎么消除这根延迟尖刺？下一页：渐进式 rehash。
大量删除后α 过低浪费内存，Redis 有收缩机制（dict_force_resize_ratio）；Go 经典 map 只缩溢出桶不缩表（整理 swiss 会重排）。
| 实现 | 阈值 α | 扩容策略 |
|---|---|---|
| Java HashMap | 0.75 | 2×，全量 rehash |
| Redis dict | 1.0 / 5.0¹ | ≥ 第一个 2ⁿ，渐进搬迁 |
| Go 经典 map | 6.5/8 ≈ 81% | 2× 或等量（溢出桶多时），渐进 |
| Go 1.24 Swiss | ≈ 87.5% | 增长余量耗尽 → 翻倍/目录分裂 |
| Python dict | 2/3 | used×3（大表 ×2）全量 |
¹ BGSAVE fork 期间写时复制代价高，阈值放宽到 5.0 减少扩容。
Incremental Rehash · Redis Dict
Go Map · Classic To Swiss
桶数组 + 每桶 8 槽 + 溢出桶链（拉链法变体）；低 B 位选桶、桶顶 8 字节 tophash 快速比对；负载 6.5、渐进扩容（翻倍/等量整理）。
开放寻址思想：8 槽为一组，组头 control word 存 tophash——SIMD 一次比较 8 个槽；探测以组为单位；目录分层支持就地分裂扩容。
遍历无序（起点随机）、并发读写 fatal（不可 recover）、key 不可比较会 panic、float NaN 作 key 永远查不到自己——两代行为完全一致，换的是内部布局。
官方博客基准：读 +60%、写 +30% 级别——本质来自缓存局部性 + SIMD 并行比对，不是玄学。
| 维度 | 经典（≤1.23） | Swiss（1.24+） |
|---|---|---|
| 存储 | bmap 桶 + 溢出桶链 | Group（8 槽 + control word） |
| 定位 | 低 B 位选桶 | 高位选目录 + 组内 SIMD 匹配 |
| 冲突解决 | 拉链（溢出桶） | 开放寻址（组间三角探测） |
| 扩容 | 渐进 evacuate | 渐进 + 目录分裂 |
| 满载率 | ≈ 81% | ≈ 87.5% |
Where Hashing Lives
Go map、Java HashMap、Python dict——去重集合、计数器、缓存索引、两数之和式的反查表
Redis 整库就是一个大 dict（渐进 rehash）；Memcached；数据库的哈希索引、join 的 hash join
分库分表取模路由、一致性哈希环、布隆过滤器挡穿透——把"哈希定位"从内存搬到分布式
两数之和（LC 1）：边遍历边把"值→下标"存入 map，对每个 x 查 target−x 是否已存在——把 O(n²) 双扫变 O(n)。"需要回头找历史元素"= 上哈希。
字母异位词分组（LC 49）：key 用排序后的串或 26 位计数串；有效字母异位词（LC 242）：26 长度数组就是小哈希表。
Cache-Aside 的读路径就是"本地 map → Redis → DB"三级查找；缓存穿透的布隆过滤、热点 key 的一致性哈希分片，全是本 deck 结构的工程化。
普通 hash % N 在 N 变化时几乎全部重映射——一致性哈希把 key 和节点都放到环上，增减节点只迁移相邻弧段。下一页图解。
Consistent Hashing · Ketama
Across Languages
| 语言 | 实现 | 冲突方案 | 负载/扩容 | 特色细节 |
|---|---|---|---|---|
| Go | map（经典 → 1.24 Swiss） | 溢出桶链 → 组探测 | 6.5 → 87.5% | 渐进扩容；遍历起点随机；并发 fatal |
| Java | HashMap / ConcurrentHashMap | 拉链 + 红黑树化 | 0.75 / 2× | 扰动 h^(h>>>16)；链长 8 且表长 ≥64 树化 |
| C++ | unordered_map | 拉链 | max_load 1.0 | rehash() 可手动预分配；迭代器 rehash 失效 |
| Python | dict / set | 开放寻址（扰动 5i+1+perturb） | 2/3 | 3.7+ 保插入序；key 必须 hashable（不可变） |
LeetCode Shortlist
| 用法 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 反查（值→下标） | 1 两数之和 E · 167 两数之和 II M · 454 四数相加 II M | 边遍历边存，查"目标差值"在不在 |
| 计数 / 分组 | 242 有效字母异位词 E · 49 字母异位词分组 M · 560 和为 K 的子数组 M | 49 的 key 设计是灵魂；560 = 前缀和 + 计数 |
| 去重 / 存在 | 217 存在重复元素 E · 128 最长连续序列 M · 349 交集 E | 128 只查 n−1/n+1 在不在，O(n) |
| 结构组合 | 146 LRU 缓存 M · 380 O(1) 插入删除随机 M · 981 基于时间的键值存储 M | 146 = 哈希 + 双链表（必手撕） |
Cheat Sheet
| 查 / 插 / 删 | 平均 O(1)，最坏 O(n)（全部撞进一个桶） |
| 平均 O(1) 的三个前提 | 哈希函数够均匀 + 负载因子受控 + key 的哈希/比较本身是 O(1) |
| 拉链法平均查找 | ≈ 1 + α/2（α 就是平均链长） |
| 不提供的能力 | 范围查询、排序、前驱后继 → 找 平衡树 / 跳表；只要"近似存在性"→ 布隆过滤器 |
| 维度 | 拉链法 | 开放寻址 |
|---|---|---|
| 删除 | 摘链节点，简单 | 必须留墓碑，否则断探测链 |
| 负载因子 | 可以 > 1 | 必须 < 1，接近 1 有性能悬崖 |
| 缓存局部性 | 差（指针追踪） | 好（连续内存 + SIMD） |
| 代表 | Java HashMap、Redis dict | Python dict、Go 1.24 Swiss |
| 扩容阈值 α | Java 0.75 · Redis 1.0（BGSAVE 时 5.0）· Go 经典 6.5/8≈81% · Swiss ≈87.5% · Python 2/3 |
| 为什么必须 rehash | 下标由桶数决定，桶数变了位置就全变 |
| 一次搬完 | Java / Python：实现简单，代价是单次操作 O(n) 延迟尖刺 |
| 渐进搬迁 | Redis dict / Go map：新旧表共存，每次操作顺手搬一点；查要查两张表，新写只进新表 |
| 节点数会变的分布式 | 用一致性哈希（+虚拟节点），只迁移相邻弧段 ≈ K/N |
| "要回头找历史元素" | 上哈希做反查表（两数之和、560 前缀和计数） |
| "分组 / 判重 / 计数" | 上哈希，重点在key 怎么设计（排序串、计数串） |
| 坑 · 遍历顺序 | Go map 遍历随机，不可依赖；Python 3.7+ 保插入序是实现附赠 |
| 坑 · 并发 | Go map 并发读写直接 fatal（不可 recover），要 sync.Map 或加锁 |
| 坑 · key 的要求 | 必须可哈希 / 可比较且不可变；NaN 作 key 永远查不到自己 |
Interview QA · Part 1
先盖住答案自己答一遍，再展开对照——想不起来比看得顺眼记得牢；答不出的翻回上一页速查表。
平均 O(1) 依赖散列均匀 + 负载受控；最坏全碰撞退化为链表扫描 O(n)。工程三保险：好哈希函数、负载因子阈值、树化（Java）。
确定性、输出均匀、雪崩（1 bit 输入差 → 约半数输出位翻转）。工程常用 FNV-1a / MurmurHash / xxHash；防碰撞攻击用带随机种子的 SipHash。
拉链：删除简单、负载可超 1，代价是指针追踪与分配开销。开放寻址：连续内存缓存友好，代价是删除要墓碑、负载必须 <1。现代趋势（Swiss/flat_hash_map）偏开放寻址。
冲突的元素在数组里连成块，块越大越容易再被砸中，越滚越大。平方探测让探测步长平方化（缓解但不根治）；双重哈希的步长与 key 相关，分布最均匀。
查找沿探测链走，遇到空格才算"不存在"。直接置空会切断链——后面的同位元素永远找不到。墓碑="此位可复用但链还通"；多了降低效率，定期重建。
泊松模型下 α=0.75 时链长超过 8 的概率 ≈ 0.00000006——冲突极少且空间利用率 75%，是时间/空间的经验平衡点；树化阈值 8 正是同一条泊松曲线的反向应用。
扩容搬迁 O(n) 会造成单次操作延迟尖刺，服务长尾 P99 恶化。渐进式把搬迁摊到每次操作里（Redis rehashidx / Go evacuate / Swiss 分裂），总代价不变但单次有界——均摊思想（复杂度 deck）。
链长 8 在正常哈希下是极小概率事件，出现了多半说明哈希差或表太小——表长 <64 时优先扩容摊薄，别急着树化（树节点 2 倍内存）。退化阈值 6 留缓冲防在 8 附近抖动。
Interview QA · Part 2
同样先自答再对照。这一页的题要"结论 + 一句机制/边界"才完整——只答结论会被继续追问。
不可变 → hashCode 可缓存（Java 首次计算后存字段）、对象内容永不漂移。若用可变对象做 key，入表后改字段会"定位失联"——永远删不掉。
攻击者预计算一堆互相碰撞的 key 投给服务端，哈希表退化成 O(n²)。防御：哈希加随机种子（Python 默认 SipHash、Go runtime 每进程随机种子），让攻击无法离线预计算。
哈希本身无序。LinkedHashMap 用附加链表保插入/访问序（还够做 LRU）；TreeMap 红黑树按 key 排序；Redis 有序集合用跳表。都是"另一套结构补序"，不是哈希表变有序。
runtime 检测到并发写直接 throw → fatal error，绕过 recover（检测靠标志位、代价极小，加锁串行化会牺牲太多性能）。要并发安全：mutex 包一层、分片锁，或 sync.Map（读多写少）。详见 map deck。
哈希管"key → 节点"定位 O(1)，双链表管"摘下 + 头插"O(1)。单结构都不行：纯链表定位 O(n)，纯哈希没有序语义。这就是结构组合的力量（LC 146 必手撕，完整推导与手撕见 LRU 缓存 deck）。
哈希反查 O(n) 且保留下标；排序+双指针也 O(n log n)+O(n) 但打乱下标要额外记原位。本质是问题要求（返回下标）决定结构选择——先问输出再选数据结构。
物理节点少时在环上分布不均，某节点可能分到一半数据。每个物理节点映射 100~200 个虚拟节点打散到环上，负载趋近均值；节点增减时各节点分摊的迁移量也更平滑。
Related & References
数组与链表 →（拉链法的载体）
平衡树 →（树化后的红黑树 / 有序替代）
布隆过滤器 →（近似成员查询，防穿透）
跳表 →（有序场景的哈希替代品）
LRU 缓存 →（哈希 + 双链表的组合验收题）
Go map 底层 →（hmap/bmap 与 Swiss Table 源码级）
Redis 数据结构 →（dict 渐进 rehash 字段级）
复杂度分析 →（平均 vs 均摊、渐进搬迁）
缓存模式 →（哈希定位思想的工程化）
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch11 · Hash Tables | 拉链/开放寻址、负载因子与全域哈希的形式化分析 |
| src/runtime/map.go · internal/runtime/maps | Go 两代实现（6.5 负载 / 87.5% 容量比），对照本仓库 map deck |
| redis src/dict.c | 渐进 rehash、rehashidx、扩缩容阈值，对照本仓库 Redis deck |
| OpenJDK java.util.HashMap | 0.75 阈值、扰动函数、treeifyBin 双条件与泊松注释 |
| Karger et al. · Consistent Hashing and Random Trees (1997) | 一致性哈希原始论文 |