"背了那么多算法，真写业务时一个也用不上"——这句话的真相不是算法没用，而是选型的输入搞错了。多数人从"我会哪些结构"出发去找问题，正确的方向是从约束出发推导结构：数据量在哪个量级、读写比多少、要不要顺序、内存给多少、有没有并发。

这篇不谈某个结构的实现，只谈判断：给定一组约束，怎么排除掉不合适的结构，以及换错结构之后要付多少账。

---

1. 约束清单：先写下来，再选

选型的第一个动作不是打开 IDE，是写一张约束卡；没有它，讨论会退化成"我觉得链表更好"。

约束	它决定什么	常见取值
数据量量级	常数因子是否重要、能否全量驻留	1e3 / 1e6 / 1e8
操作分布	成本落在哪一侧	读 95% / 写 95% / 均衡
顺序要求	是否需要有序容器或额外排序	无 / 局部有序 / 全局有序
内存上限	能否承受指针开销与冗余索引	单机 8G / 堆内 2G
并发模型	是否需要锁、分片或无锁	单写多读 / 多写
生命周期	是否需持久化与淘汰	请求级 / 小时级 / 永久

约束卡：订单明细检索
规模  单日 ~1e6 行 × 90 天 → 1e8
操作  写入 95%，点查 4%，范围统计 1%
顺序  无全局有序要求
内存  单机 8G，不全量驻留
并发  多写少读
结论  排除内存哈希、有序数组 → 候选 LSM KV / 分片哈希+二级索引

约束卡可以被推翻：数据量翻十倍，卡上的"1e8"变了，结论就要重算，而不是等线上慢了再猜。

2. 读写比决定一半的结构选择

"读多写少"与"写多读少"是两套成本模型：前者可以接受写入时多维护索引、把查询压到一次寻址；后者任何"写时维护"都是吞吐税。

形态	结构倾向	主要成本	反模式
读多写少	索引、缓存、预计算、倒排	写入放大、一致性维护	每次读都全表扫
写多读少	追加日志、LSM、批量落盘	查询要合并多层、读放大	每写一条就更新全局有序结构
读写均衡	平衡树、跳表、B+ 树	两头都不极致	用两套结构各管一半

// 写多读少：攒批 + 追加，别在写路径上排序
List<Row> buffer = new ArrayList<>(BATCH);
void onWrite(Row row) {
    buffer.add(row);
    if (buffer.size() >= BATCH) { flushSorted(buffer); buffer.clear(); }
}
// 读多写少：写入时建好查询路径，读取只做一次寻址

关键判断是成本放在哪一侧："写入时排序"和"查询时排序"是两种系统，不是两种写法。

3. 有序与无序：贵的不是查询，是维护

"要不要顺序"最容易被忽略：有序换来范围查询，代价是每次写入都要定位并调整结构。

结构	点查	范围查	插入	删除	额外空间
哈希表	O(1) 均摊	不支持（需全扫）	O(1) 均摊	O(1) 均摊	桶 + 负载因子冗余
有序数组	O(log n)	O(log n + k)	O(n) 搬移	O(n) 搬移	无指针开销，紧凑
平衡树	O(log n)	O(log n + k)	O(log n) 旋转	O(log n)	每节点 2–3 指针
跳表	O(log n) 期望	O(log n + k)	O(log n) 期望	O(log n) 期望	多层指针，概率结构
B+ 树	O(log n)	O(log n + k)	页分裂	页合并	按页组织，适合外存

// 反例：哈希做范围查询，只能全量遍历再过滤
map.values().stream().filter(v -> v.ts >= from && v.ts < to).toList();
// 正例：结构支持区间，代价前移到写入
byTs.subMap(from, true, to, false).values();

区间能力是结构给的，不是写法给的。选了哈希就提前放弃了范围能力，后面用流式过滤补，是把 O(k) 变成 O(n)。

4. 四类问题的结构映射

业务里的结构问题高度重复，先归类再选，比逐个试要快。

问题	首选结构	关键参数	典型失效点
去重	哈希集合 / 位图 / 布隆过滤器	基数上限、误判容忍度	基数超预期后位图爆内存
计数	哈希计数 / 分桶计数 / Count-Min	键空间大小、是否需要精确	长尾键把内存吃满
Top-K	大小为 K 的堆 / 分片堆合并	K 的量级、是否要求稳定排序	K 很大时堆退化成全排序
滑动窗口	双端队列 + 单调性	窗口长度、是否可丢弃	窗口内需要随机访问
存在性判断	布隆过滤器 / Cuckoo	误判率、删除需求	需要删除却选了标准布隆

// Top-K：小顶堆，堆顶是当前第 K 名，新元素只和堆顶比较
PriorityQueue<Item> heap = new PriorityQueue<>(K, Comparator.comparingLong(Item::score));
for (Item it : stream) {
    if (heap.size() < K) heap.offer(it);
    else if (it.score > heap.peek().score) { heap.poll(); heap.offer(it); }
}

布隆过滤器容量估算（按目标误判率 p、元素数 n）
m = -n * ln(p) / (ln2)^2     位数组长度
k = m / n * ln2              哈希函数个数
例：n=1e6, p=0.01 → m≈9.6e6 bit（约 1.2MB），k≈7

这里的"约"是公式推导值，实际内存还要乘上对齐与分片开销，按所用库的版本文档核对。

5. 常数因子与缓存局部性：O(1) 不一定更快

复杂度只描述增长趋势，不描述单步成本：链表的 O(1) 插入是一次随机访问，数组的 O(log n) 查找可能整段命中缓存，小规模下后者常更快。

访问模式	单步成本构成	什么时候 O(log n) 会赢
数组/连续内存	一次 cache line 命中，硬件预取有效	n 小、数据紧凑
链表/指针跳转	每步一次潜在 cache miss	几乎不赢，除非插入极频繁且已持引用
哈希表	计算哈希 + 探测，可能 miss	负载因子高、键对象大时退化
树	log n 次指针跳转	数据量中等且节点紧凑（如 B 树扇出大）

@BenchmarkMode(Mode.AverageTime)
@State(Scope.Thread)
public class LookupBench {
    @Benchmark public Row hashLookup() { return hashMap.get(key); }
    @Benchmark public Row treeLookup() { return treeMap.get(key); }
}

基准结论必须带规模：n=100 与 n=1e6 的排序可能相反，把"我测过"当普适结论是常见的伪证据。

6. 最坏情况：哈希退化与近似结构的误差

哈希的 O(1) 是均摊不是保证：冲突集中时退化成遍历，最坏 O(n)。

触发条件	表现	缓解方式
键的哈希函数质量差	大量键落同一桶	换哈希、加扰动、随机种子
恶意构造的同哈希键	单次请求即可打满 CPU	限制单桶长度、树化、限流
负载因子过高	探测链变长，均摊失效	扩容阈值前扩容
键对象可变	写入后哈希值改变，查不到	键必须不可变

// JDK 的 HashMap 在单桶过长时会树化；阈值按 JDK 版本核对
// 但树化只治"桶内退化"，治不了"哈希函数被完全预测"

近似结构同理：布隆把"是否存在"换成"可能存在"，HLL 把基数换成估计。误差可交易，但要提前写下误判率、误差上限、超限降级。

近似结构	换来什么	付出什么	不能用在
布隆过滤器	内存降一到两个数量级	假阳性、不支持删除	必须精确判定存在性
HyperLogLog	常量级内存估基数	相对误差、不可列举	需要精确计数或取元素
Count-Min Sketch	固定内存估频次	只高估不低估	需要精确 Top-K 排序

7. 并发结构：锁、无锁、分片

并发选择取决于争用强度，不是功能。

方式	适用并发度	代价	备注
全局锁	低，临界区短	串行化	最容易写对，先用它跑通
读写锁	读多写少	写饥饿风险、读锁开销	读临界区短时未必划算
分段/分片	中高，键可分区	跨分片聚合变复杂	分片数不是越多越好
无锁/CAS	高，冲突低	ABA、内存序、调试难	profile 证明锁是瓶颈后再用

// 分片：把争用摊到 N 个桶，代价是聚合要跨桶
final class ShardedCounter {
    private final AtomicLong[] cells = new AtomicLong[64];
    void inc(long key) { cells[(int) (key & 63)].incrementAndGet(); }
    long sum() { long s = 0; for (AtomicLong c : cells) s += c.get(); return s; }
}

8. 验证：怎么知道选对了

信号	采集	判定
吞吐随并发	梯度压测	提前饱和 → 全局争用
耗时分布	直方图而非均值	P99 远高于 P50 → 退化或 GC
内存增长	堆直方图、GC 日志	超线性 → 指针冗余
热点方法	CPU/分配 profile	不在预期结构 → 选型不符

9. 排错：五种"像是选型错了"的表现

现象	更可能的真实原因	处理
插入越来越慢	扩容/重哈希/页分裂的均摊成本	预分配容量或改批量
查询偶发几秒	单桶退化、序列化、GC 停顿	先看 P99 与 GC 日志
内存涨得比数据快	对象头与指针开销	换紧凑表示
并发吞吐不涨	全局锁或伪共享	分片、padding，先确认
换了结构没变快	瓶颈在 IO 或下游	回到端到端拆解

10. 边界：这些情况不要自研结构

场景	结论	理由
千级数据以内	标准库最笨的写法	常数因子与可读性优先
操作单一（只追加）	数组/切片	引入树只增加维护面
标准库已高度优化	直接用	追平工程优化成本极高
需持久化与崩溃恢复	现成存储引擎	事务与恢复不是算法问题
团队无人能维护	换简单方案	维护成本两年后结算

工程纪律只有一句：先用最笨的写法跑通，再用 profile 证明它不够快，然后才换。

换结构的成本不止改代码：序列化格式、缓存键、监控指标都会跟着变。把"未来换掉的代价"算进去，接口边界比结构更值得先设计。

自测

1. 拿到一个新需求，你会先写哪五项约束？其中哪一项最容易被漏掉？
2. "读多写少"为什么会把成本推到写入侧？举一个你项目里的例子。
3. 用哈希表做范围查询，复杂度从多少变成了多少？
4. 什么情况下 O(log n) 的结构会比 O(1) 的哈希更快？为什么？
5. 布隆过滤器的误判率是"配置"还是"结果"？容量算错时先坏在哪？
6. 什么时候应该拒绝自研结构，改用标准库或现成存储引擎？