一、起源:选型失误的代价
1.1 同一份需求下的多种可行解
给定一组数据与一组操作,"实现它"通常有多种答案。表示一个键值集合可以用数组、链表、散列表、平衡树、跳表;维护一组待处理任务可以用队列、堆、时间轮;判断一个元素是否出现过可以用哈希集合、位图、布隆过滤器。这些结构都能通过功能测试,区别只在代价随规模增长的方式、内存占用的量级,以及后续扩展的余地。
这种"都能用"的表象带来一个具体的困难:选择发生在写代码之前,而后果发生在数据量增长之后。功能正确性由测试覆盖,代价是否合适在测试阶段通常不体现——测试数据往往只有几十上百条,此时几乎所有实现都在同一量级内,差异被常数因子与调用开销掩盖。相关分析见 复杂度与算法分析 中量级与增长一节。
1.2 三种失误形态
选型失误在工程中表现为三类可观测的后果,它们的发现时间与修复成本依次上升。
性能不足。 单次请求耗时随数据量呈平方增长,或局部操作把整体的量级抬高一阶。典型形态是把线性查找放进循环(contains、indexOf 出现在遍历体内)、对同一集合反复排序、用链表或列表做高频按值检索。这类问题有明确的量级特征:数据量翻倍而耗时变为四倍,指向嵌套遍历或循环内的线性调用。
内存浪费。 时间上可接受,但内存占用远超必要量级。同一个"是否存在"的判断,用哈希集合存放一亿个整数需要数 GB 级别的堆内存,用位图只需百 MB 量级;同一个百万级的键值映射,用通用散列表与用基本类型特化的开放寻址实现,占用可能相差两倍以上。内存浪费的后果不止于资源成本:对象数量增加会抬高分配与回收压力,堆占用逼近容器限额时以进程被终止的形式失败,而应用中可能没有任何异常抛出。
后期重构成本。 前两类问题至少发生在系统边界之内。第三类发生在结构被外部使用时:一个以 List 暴露返回值的接口,调用方按返回值位置建立了业务逻辑;一个把"任务顺序"隐含在数组下标中的实现,被下游按数组语义依赖。当内部结构必须替换时,改动范围从实现类扩散到所有调用点、序列化格式与测试用例。这类代价通常远高于当初多花在选择上的时间。
三种形态的共同点是:代价不在写下的那一段代码里,而在数据增长、并发接入或结构被替换的时刻出现。
1.3 "熟悉哪个用哪个"的偏差
多数选型并非经过比较后的决策,而是沿用了上一次的写法。这一偏差有稳定的表现形态。
- 把列表当作集合使用。 为了让元素不重复而引入一个
List,每次插入前调用contains判断。单次判断是 O(n),n 次插入累计 O(n²)。作者的注意力集中在"去重"这一语义上,而语义同样可以由哈希集合提供,代价是期望 O(1)。 - 把散列表当作有序结构使用。 需要按时间或数值顺序输出时,先遍历散列表取出所有键再排序。若这一操作在每次请求中执行,排序的 O(n log n) 会叠加在请求路径上,而有序映射本身可以边插入边维持顺序。
- 默认使用内置列表中"最通用的那个"。 语言内置的
List默认实现是动态数组,它能覆盖多数场景,但在两端频繁操作、按优先级出队、需要区间查询这几类模式下,专用结构的代价明显更低。 - 把数据结构的选择与算法的选择分开考虑。 事实上两者互相约束:Top K 问题用堆是 O(n log k),全量排序后取前 k 是 O(n log n),快速选择是平均 O(n);同一需求下结构决定了可达的量级。
- 沿用上游传递过来的结构。 上游因为自身需要选择了链表或不可变列表,下游在此之上做随机访问或高频修改,代价被放大却难以追溯到源头。
偏差的根源在于选型依据来自经验记忆而非当前问题的操作特征。纠正方式是把问题拆成"需要哪些操作、各自频率如何、规模多大"三个可直接回答的问题,再据此反查结构,而不是先想到某个类型名。
1.4 复杂度之外的现实因素
即使量级分析给出明确结论,实际选择仍受若干非渐近因素影响。忽略它们会造成"量级更优的实现反而更慢"的结果。
| 因素 | 机制 | 对选型的影响 |
|---|---|---|
| 常数因子 | 同一量级下指令数、函数调用、装箱与边界检查的差异可达数倍 | 规模在数百以内时量级排序常被常数排序覆盖 |
| 缓存局部性 | 顺序访问与随机访问的访存延迟相差一到两个数量级 | 同为 O(n) 的遍历,数组与链表实测差近一个数量级 |
| 并发实现代价 | 加锁、CAS 重试、内存屏障带来的额外开销与不保证 | 单线程最优的结构在高并发下未必最优,需要按访问模式重选 |
| 内存开销 | 每元素的节点头、指针与对齐填充 | 元素数很大时,结构开销可能超过数据本身 |
| 可维护性 | 自定义结构的代码量、调试成本与出错面 | 量级相同时应选择能被团队正确使用与修改的实现 |
| 生态与运维 | 序列化格式、监控指标、跨语言兼容、已有工具链支持 | 自研结构在这些方面通常弱于标准实现 |
这些因素的完整分析见 复杂度与算法分析 中理论与实测的差异一节,数组与链表的对照见 数组与链表 中"为什么复杂度相同而实测差异明显"一节。它们的共同结论是:复杂度负责筛选与排除,最终取舍需要结合目标规模实测。
二、原理
2.1 判断维度
选型可以按固定的维度顺序推进,前一项的结论会收窄后一项的可选范围。
| 维度 | 需要回答的问题 | 对结构的约束 |
|---|---|---|
| 操作种类 | 需要增、删、改、查中的哪几项;是否需要按序遍历、区间查询、按排名访问、取最值 | 决定结构类别,是最先确定的一项 |
| 操作频率 | 读与写的比例;热点操作是哪一个 | 决定在读写代价之间的倾斜方向 |
| 数据规模与增长 | 当前规模、预期峰值、是否可能增长数个数量级 | 决定复杂度差异是否已经显现 |
| 内存约束 | 可用堆上限、容器限额、是否要求常驻内存 | 决定能否使用节点式结构或需要紧凑表示 |
| 持久化 | 数据是否需要落盘、重启后是否必须保留、能否重建 | 决定是否需要外部存储结构或索引 |
| 并发模式 | 单线程、读多写少、写多读少、并发写;是否需要阻塞语义 | 决定是自建同步、使用并发容器还是不可变结构 |
| 有序性 | 是否需要按键排序输出、范围查询、前驱后继 | 在散列与有序结构之间作二选一 |
| 稳定性与去重 | 相等元素是否要保持到达顺序;是否需要去重与计数 | 排除不稳定的结构或要求附加次序键 |
操作种类与频率。 单纯列出需要的操作不足以决策,频率分布才是关键。查找为主、写入极少时,散列表与平衡树的差异被放大到常数因子层面,可以直接按内存与实现复杂度取舍;查找与写入各占一半且需要有序时,平衡树或跳表是唯一同时满足两端的选项。对"写多读少"还需要进一步确认写的位置:集中在两端、分散在中间但位置由遍历过程给出、还是按下标定位,三者的结论完全不同。
数据规模与增长预期。 量级差异只在规模足够大时显现。以每秒约 10⁸ 次基本操作为参照,平方级在 10⁴ 规模已接近一秒,而线性对数级在 10⁷ 规模仍是数秒量级。同一份代码在千级与千万级数据上会给出相反的选型结论,因此需要按预期峰值而非当前值判断。规模会增长的判断尤其重要:当前可接受的实现可能在翻倍后不可接受,而此时的替换成本远高于初期。
有序性与稳定性。 需要有序输出时,散列结构需要额外一次排序,而排序结果无法增量维护;有序结构则以每次操作 O(log n) 的代价持续维持顺序。需要保持相等元素的到达顺序时,排序算法必须稳定(见 排序与查找),堆这类结构还需要在比较器中引入额外的次序键。
去重与计数。 语义上"只保留一个副本"与"统计每个值出现次数"分别对应集合与计数映射,两者都可以用散列表实现,也都可以在位图或 HyperLogLog 上得到更省内存的近似版本。判断依据是是否允许误差以及值域的形态,见 位图与布隆过滤器。
复杂度与实测的差异。 上述维度给出的都是量级层面的约束。依据分析可以直接排除在目标规模下不可行的候选,但在量级相同或接近的候选中,必须依靠实测确定顺序。这一分工见 复杂度与算法分析 中理论与实测的差异一节。
2.2 按操作特征反查结构
把访问模式翻译成操作特征后,可以逐项反查候选结构。下表给出每一类操作特征的候选与取舍依据。
| 操作特征 | 候选结构 | 取舍依据 |
|---|---|---|
| 频繁随机访问(按下标读写为主) | 数组、动态数组 | 地址算术一次定位;代价是中间插入删除需搬移后续元素 |
| 频繁头尾插入删除 | 双端队列、环形数组、双向链表 | 两端均摊 O(1);环形数组无节点开销,链表无扩容毛刺 |
| 频繁中间插入删除 | 平衡树、跳表、块状链表 | O(log n) 或 O(√n),优于数组的 O(n);代价是实现复杂、缓存局部性差 |
| 按值查找(无索引键) | 哈希集合、位图、排序后二分 | 期望 O(1) 需要键可散列;位图要求值域为有限整数区间 |
| 按键查找(等值) | 散列表、平衡树、跳表 | 散列表常数更小;平衡树与跳表同时提供顺序能力 |
| 范围查询(按键区间) | 平衡树、跳表、B+ 树、有序数组 | 有序结构天然支持;散列表需要全量扫描 |
| 按序输出(全量有序遍历) | 平衡树、跳表、排序后的数组 | 有序结构可持续维护;排序后数组适合静态数据 |
| 取最值(反复取极值) | 二叉堆、优先队列 | 取堆顶 O(1)、插入 O(log n),比有序结构更省;但不支持任意查找 |
| 按排名访问 | 跳表(维护跨距)、顺序统计树 | 排名可随查找路径累加;平衡树需额外维护子树规模 |
| 去重与计数 | 哈希集合与计数映射、位图 | 精确去重需哈希;允许误差且值域大时可用近似结构 |
| 区间聚合(区间和、区间最值、区间计数) | 前缀和、差分数组、树状数组、线段树、稀疏表 | 按"是否可更新""运算是否可逆"逐层排除 |
| 连通性判定(动态合并集合) | 并查集 | 摊还近常数时间;只支持合并、不支持分裂 |
| 前缀匹配与字典查询 | 字典树、压缩字典树、有序词典加二分 | 共享前缀换取查询能力;代价是节点开销 |
| 近似判断存在性 | 布隆过滤器、Cuckoo Filter | 空间远小于精确集合;只有假阳性,无假阴性 |
| 有序且要求并发访问 | 跳表(如 ConcurrentSkipListMap) | 更新局部化使无锁实现可行;并发平衡树实现困难 |
各项的原理与实现要点分别见 数组与链表、栈与队列、跳表、散列表、位图与布隆过滤器、二叉树与二叉搜索树、平衡树:AVL 与红黑树、B 树与 B+ 树、堆与优先队列、字典树与字符串索引、线段树与并查集、图的表示与遍历。
几点需要在反查时补充的约束:
- "按键查找"与"按范围查询"往往同时出现。 若同一份数据既要等值定位又要范围扫描,散列表无法承担后者,此时平衡树或跳表是唯一能同时满足两者的内存结构;若等值查找占绝对主导、范围查询只是偶尔的运维需求,可以用散列表加一次排序的离线方案替代。
- "频繁中间插入"的结论依赖插入位置是否已知。 位置由排序键决定时用平衡树;位置由下标给出且需要按序访问时,块状结构或跳表更合适;位置由遍历过程给出(如迭代器删除当前元素)时链表反而最省,见 数组与链表 中链表查找 O(n) 的本质一节。
- "区间聚合"的选型有固定顺序。 数据不被修改时优先前缀和或稀疏表;只有区间更新而无区间查询时用差分数组;点更新加区间和优先树状数组;运算不可逆或合并信息复杂时用线段树。完整顺序见 线段树与并查集 中对比与选型一节。
- "取最值"与"有序输出"不可互相替代。 堆只保证堆顶为极值,其余元素没有顺序承诺,迭代优先队列得到的顺序通常不是出队顺序;需要完整有序序列时,要么连续出队,要么改用有序结构。
- 连通性判定的两条路线。 关系只增不减时并查集最优;关系可能变化、或需要路径本身时,必须退回图的遍历,见 图的表示与遍历。
2.3 复杂度之外的决策因素
2.3.1 实际规模下常数因子的影响
量级结论只在规模足够大时成立,原因在于渐近分析丢弃了常数与低阶项。以每秒约 10⁸ 次基本操作为参照:
n = 20 插入排序(O(n^2)) 约 400 次操作 可忽略
归并排序(O(n log n)) 约 90 次操作 + 递归开销 实际更慢
n = 10^6 插入排序 约 5×10^11 次 不可行
归并排序 约 2×10^7 次 可接受
多数语言标准库的排序实现在小区间(常见阈值为 7 至 16 个元素)切换为插入排序,正是这一判断的落地。选型的含义是:目标规模在数十以内时,应优先选择实现简单、分配更少的结构,而不是按量级排名选择;目标规模上万后,才需要检查是否存在隐藏的量级问题。
2.3.2 缓存局部性与内存层次
同一量级的两种实现在实测中的差距,多数来自访存模式。数组元素连续存放,一次缓存行可覆盖多个元素,顺序扫描的平均访存次数远小于元素个数,硬件预取器可以识别递进地址流;链表节点由分配器决定物理位置,遍历时每次读取下一个地址都依赖当前节点内容,无法预取。两者同为 O(n) 的遍历,实测可以相差近一个数量级。
这一因素在选型上有两个直接含义:
- 遍历为主的负载优先选择连续存储,即使量级分析给出相同结论。
- 结构的内存布局属于选型的一部分。同一个抽象数据类型可以有紧凑与松散两种实现,差异不体现在复杂度记号上,却体现在实测与内存占用上。详细机制见 数组与链表 中内存与缓存一节。
2.3.3 扩容与再平衡的代价
动态结构与固定结构的一个关键差别是:前者通过偶发的高代价操作换取常规操作的常数时间。这类代价有三种形态。
| 形态 | 触发条件 | 单次代价 | 摊还代价 | 工程影响 |
|---|---|---|---|---|
| 动态数组扩容 | 元素数等于容量 | O(n) 复制,内存峰值约 2.5 倍 | 追加摊还 O(1) | 延迟毛刺、扩容瞬间内存翻倍 |
| 散列表扩容 | 元素数 / 容量超过负载因子 | O(n) 重散列,内存峰值翻倍 | 插入摊还 O(1) | 批量写入时的延迟毛刺,键的重新分布 |
| 平衡树再平衡 | 插入删除破坏平衡条件 | O(log n) 旋转与着色 | 计入单次操作 | 常数比散列表高,但无规模突变 |
| 跳表层数增长 | 随机层数超过当前最大层 | 常数次指针更新 | 计入单次操作 | 无集中代价 |
| 渐进式 rehash | 大容量扩容耗时过长 | 分摊到后续每次读写 | 单次代价小 | 迁移期需要双表路由 |
判定依据是摊还结论不约束单次延迟。吞吐为主的批处理只关心摊还值;延迟敏感的服务关心最坏情况,此时应通过预设容量、分批构建、把扩容移出请求路径来消除毛刺。散列表的渐进式 rehash 是同一问题的另一种解法,其桶分批迁移与迁移期读写路由见 散列表 中渐进式 rehash 一节。动态数组的扩容倍数选择、内存峰值推导与缩容滞后阈值见 数组与链表 中扩容策略与倍数选择一节。
2.3.4 内存开销的量化方式
按"每元素结构开销 × 元素数"估算,而不是按元素本身大小估算。单元素开销由三部分构成:
单元素开销 = 数据本身 + 结构附加字段 + 对齐填充
↑ ↑ ↑
基本类型宽度 指针、哈希值、 平台按 8 字节对齐
颜色位、规模字段 造成的补零
对象式实现的每一层都会引入额外开销:容器对象有对象头,节点对象有各自的对象头,引用在 64 位 JVM 开启压缩指针时占 4 字节、关闭时占 8 字节。估算方法与本仓库采用的 JVM 口径见 数组与链表 中节点开销一节,对象头构成与指针压缩的开关条件见 JVM 内存结构与垃圾回收。
2.3.5 并发安全实现的代价
并发场景下的选型不只是"给单线程结构加锁"。可选方案与代价如下。
| 方案 | 实现要点 | 代价 |
|---|---|---|
| 外部加锁 | 调用方在临界区内完成复合操作 | 锁粒度由调用方决定;不保证单个操作的原子性由容器提供 |
| 容器内置同步 | 方法级同步或内部锁 | 全表锁,读写串行;读多写少场景浪费并发度 |
| 并发容器 | 分段锁、CAS、写时复制 | 语义有边界:复合操作仍需原子方法,size() 可能是近似值 |
| 写时复制 | 写加锁并整体复制后发布新引用 | 读完全无锁;单次写 O(n)、内存峰值翻倍,只适合读远多于写的场景 |
| 不可变结构 | 修改产生新版本,旧版本共享大部分节点 | 读无同步;写产生新对象,需要评估分配量与 GC 压力 |
| 线程私有 | 每个线程持有独立结构,定期合并 | 无同步开销;合并时机与内存占用需要额外设计 |
其中有三点容易误判:
- 可见性与原子性是两件事。 把引用声明为
volatile只能保证可见性,不能修复"读—改—写"三步复合操作的竞态。 - 并发容器的单方法原子性不等于复合操作原子性。 先判断再写入的模式必须改用容器提供的原子方法。
size()的语义在不同实现中不同。 链表式并发队列通常只能给出近似值,不能作为控制条件使用。
相关机制见 Java 并发编程 中线程安全与 AQS 部分,各类集合的并发边界见 Java 集合框架实现原理。
2.4 内存与规模估算
2.4.1 单元素开销的组成
以 64 位 JVM 开启压缩指针为例(对象头 12 字节、引用 4 字节、按 8 字节对齐),常见结构的每元素开销:
| 结构 | 每元素容器结构开销 | 说明 |
|---|---|---|
int[] | 4 字节 | 无附加字段 |
| 引用数组 | 4 字节 | 不含被引用对象 |
| 位图 | 0.125 字节(1 位) | 一个二值状态占一位 |
| 单链表节点 | 24 字节 | 对象头 + 数据引用 + next,对齐后 |
| 双向链表节点 | 24 字节 | 多出的 prev 在本口径下被对齐填充吸收 |
| 散列表节点 | 32 字节 | 对象头 12 + 哈希值 4 + 键引用 4 + 值引用 4 + next 4,对齐后 32 |
| 红黑树节点 | 40 字节 | 对象头 + 5 个引用 + 颜色位,对齐后 |
表中的数值只统计容器结构本身,不含键与值对象。键为字符串或包装类型时,键对象的开销往往超过结构开销,这一点在所有以对象为键的结构中一致。
2.4.2 千万级数据的内存核算示例
以一千万元素的键值映射为例,键为整数、值为长整数。通用实现(HashMap<Integer, Long>)的构成:
数据结构选择:HashMap<Integer, Long>,元素数 10^7,负载因子 0.75
表数组:容量取 2^24 = 16,777,216(约 10^7 / 0.75 向上取到 2 的幂)
16,777,216 × 4 字节(压缩指针下的引用) ≈ 64 MB
节点: 每个 Node 32 字节
10^7 × 32 ≈ 320 MB
键: 超出 -128 至 127 缓存范围的 Integer 各自独立分配
10^7 × 16 字节(对象头 12 + int 4) ≈ 160 MB
值: 10^7 × 24 字节(对象头 12 + long 8,对齐后 24)≈ 240 MB
合计 ≈ 784 MB
同样的语义用两种替代实现:
替代一:两个并行的基本类型数组(键 long[] + 值 long[],按插入顺序存,查找时线性扫描)
10^7 × 8 × 2 = 160 MB
代价:按值查找为 O(n),只适合配合外层索引使用
替代二:基本类型特化的开放寻址映射(键值各 8 字节 + 1 字节状态,容量 2^24)
16,777,216 × 17 字节 ≈ 272 MB
代价:需要引入第三方实现或自行开发,缺少通用集合的接口生态
三点结论:
- 通用散列表的开销主要由对象化造成。 节点对象、包装类型的键与值各自携带对象头,三者合计远大于数据本身。消除对象化是数量级层面的优化,而非常数调优。
- 容量取整到 2 的幂会放大表数组占用。 负载因子 0.75 意味着表数组常有多余槽位,元素数刚越过阈值时浪费最明显。
- 估算应覆盖全链路而不仅是容器。 序列化缓冲区、副本、缓存以及扩容瞬间的中间态都会叠加占用,容器本身只是其中一项。
2.4.3 内存受限时的替代方案
| 约束 | 替代方案 | 代价 |
|---|---|---|
| 只判断存在性,允许假阳性 | 布隆过滤器 | 无法删除单个元素、无法枚举、存在误判率 |
| 布尔状态数量极大 | 位图 | 值域必须是有限整数区间;稀疏时改用分块位图 |
| 允许近似计数 | HyperLogLog 等基数估算结构 | 相对误差与内存成反比,无法给出精确值 |
| 元素为小整数且值域集中 | 定长数组直接寻址 | 值域过大时空间浪费,需要先做映射或压缩 |
| 单机内存不足 | 分块处理、外部排序、落盘索引 | 引入 IO 代价,结构从内存结构变为磁盘结构 |
| 访问具有局部性 | 分层缓存与热点常驻 | 需要设计淘汰策略与一致性维护 |
近似结构的误判率、位数组长度与散列个数的换算、以及稀疏位图的分块容器思路见 位图与布隆过滤器。数据超出内存后由内存结构转为磁盘结构的原则见 B 树与 B+ 树。
2.5 语言内置结构的理解
2.5.1 常见容器背后的实现
语言内置的容器名称描述的是接口,不是实现。选型时需要把"名称"翻译为"底层结构 + 复杂度 + 实际特性"。
| 常见容器 | 底层实现 | 关键操作复杂度 | 实际特性与陷阱 |
|---|---|---|---|
动态数组(ArrayList、list、vector、slice) | 连续数组 + 容量字段 | 按下标读写 O(1),尾部追加摊还 O(1),中间插入删除 O(n) | 扩容有单次 O(n) 与内存峰值;按值查找为 O(n) |
链表(LinkedList、list、std::list) | 双向链表 | 已知节点处插入删除 O(1),按下标访问 O(n) | 作为列表使用时按下标访问退化;节点开销大、缓存局部性差 |
双端队列(ArrayDeque、std::deque) | 环形数组或分块数组 | 两端操作摊还 O(1),随机访问 O(1) 或 O(n) | 多数实现不允许插入 null;部分实现不支持按下标访问 |
散列表(HashMap、dict、unordered_map) | 数组 + 链表 / 开放寻址,冲突严重时树化 | 增删查期望 O(1),最坏 O(n) | 无序;扩容有毛刺;键必须正确实现相等与散列契约 |
有序映射(TreeMap、std::map) | 红黑树 | 增删查与范围查询 O(log n) | 每个元素一个节点对象;常数高于散列表 |
跳表映射(ConcurrentSkipListMap) | 多级索引链表 | 期望 O(log n),最坏 O(n) | 并发友好;最坏情况不是确定性上界 |
优先队列(PriorityQueue、heapq) | 二叉堆 | 取堆顶 O(1),插入与出队 O(log n) | 不保证有序遍历;任意查找 O(n);相等优先级顺序不确定 |
哈希集合(HashSet、set) | 底层复用散列表 | 期望 O(1) | 语义与底层映射一致,同样无序 |
2.5.2 确认实现的方式
内置结构的实现属于具体实现的细节,语言规范通常不作保证。确认方式按可靠性递增排列:
- 读接口文档的复杂度说明。 标准库文档通常会标注"摊还 O(1)""O(log n)"这类结论,并说明前提。这是最低成本的入口。
- 读源码或实现注释。 扩容倍数、树化阈值、负载因子的默认值都属于实现细节,直接决定内存占用与毛刺形态。
- 在目标规模下实测。 两个实现的量级相同时,文档无法给出取舍结论,只能实测。
需要特别说明的是:不应把实现细节写进代码的假设里。依赖"某容器扩容倍数为 1.5 倍"或"元素数达到 8 时转为红黑树"这类数值的代码会在版本升级后失效。可以依赖的是接口承诺的复杂度语义与可见的行为边界。Java 侧各集合的扩容机制、树化阈值、迭代器与视图语义的完整说明见 Java 集合框架实现原理。
2.6 持久化与分布式视角
2.6.1 需要落盘时的结构选择
数据需要落盘后,代价模型从"比较次数"变为"页访问次数",因为一次随机 IO 的代价与一次内存访问相差数个数量级。结构选择随之改变。
| 结构 | 写路径 | 读路径 | 适用负载 |
|---|---|---|---|
| B+ 树 | 原地更新页,写日志保证持久性 | 沿树定位到页,页内二分 | 读多写少、需要范围查询与低延迟点查 |
| LSM 树 | 写内存表,批量落盘为有序文件,后台分层合并 | 从新到旧逐层查找,用布隆过滤器减少无效查找 | 写多读少、追加型写入 |
| 追加日志 | 顺序追加,定期做检查点或压缩 | 正向扫描或按偏移定位 | 顺序写入的提交记录、变更流 |
三者的取舍与 B+ 树在关系数据库、文件系统、键值存储中的落地形态见 B 树与 B+ 树 中键值存储的索引层一节;这些结构在真实系统中的落地要点与观测指标(缓存淘汰、队列缓冲、存储索引、定时结构与近似结构)见 工程中的数据结构。需要指出的是:LSM 树的读路径依赖布隆过滤器减少无效查找,这正是近似结构在持久化场景中的典型位置,其参数换算见 位图与布隆过滤器。
2.6.2 需要跨节点时的分片与路由
单机结构无法容纳数据或无法承载吞吐时,问题从"选择哪个结构"变为"如何把键映射到节点"。映射方式决定了扩容时的影响范围。
| 方案 | 节点变化时的影响 | 代价 |
|---|---|---|
| 取模分片 | 约 (N−1)/N 的键需要迁移 | 实现最简单,扩容接近全量搬迁 |
| 一致性哈希 | 仅影响环上相邻区间 | 需要维护哈希环与虚拟节点以缓解倾斜 |
| 固定哈希槽 | 只需迁移槽,无需重算键到节点的映射 | 需要额外的槽分配元数据与迁移流程 |
普通取模在节点数变化时导致缓存命中率断崖下降,是一类高频故障;虚拟节点解决小规模下的分布倾斜;哈希槽把映射关系与物理节点解耦,使扩容变成"迁移槽"这一可控操作。三者的原理与对照见 散列表 中一致性哈希与分片一节。
2.6.3 分布式场景下的唯一标识与有序键
分片之后,标识的生成与排序不再由单机自增序列保证,需要引入额外的方案。判断依据是三项:是否要求趋势递增、是否要求全局唯一且无协调、以及标识长度对索引扇出的影响。
| 方案 | 有序性 | 依赖 | 主要代价 |
|---|---|---|---|
| 数据库自增步长 | 趋势递增 | 数据库 | 扩展受实例数限制,合并扩容需要调整步长 |
| 号段模式 | 趋势递增 | 集中式存储 | 需要处理号段耗尽与故障转移 |
| 雪花算法 | 趋势递增(按时间) | 时钟、机器标识 | 时钟回拨需要专门处理 |
| UUID | 无序 | 无 | 随机主键导致插入位置分散、页填充率下降 |
其中最后一项与索引结构直接相关:随机主键使 B+ 树的插入散布在整棵树中,触发页分裂与随机写,同时降低页填充率、放大索引体积。使用随机标识符时应评估其有序性,或压缩为定长二进制列以减小对扇出的影响。两种方案的完整对照、时钟回拨的处理方式与分片键的选择要求见 分库分表与全局唯一 ID。
2.7 演进与替换
2.7.1 从简单结构起步
选型的目标不是一开始就找到最优结构,而是避免在错误的方向上投入。可行的推进顺序:
- 用最简单的结构实现正确语义。 首选语言内置的动态数组、哈希映射与堆,它们经过充分验证且不引入自研代码的缺陷面。
- 确定规模与访问模式。 记录当前规模、增长速度与读写比例。这一步的产出是后续判断的依据,而不是猜测。
- 在目标规模下测量。 依据实测而非直觉决定是否需要替换。测量方法见本章 3.4 节。
- 按测量结果替换。 替换的触发条件应当是具体的:单次请求耗时超阈值、内存占用逼近限额、扩容毛刺落在请求路径上。
需要替换的典型信号:
- 耗时随数据量呈平方增长,说明存在嵌套遍历或循环内的线性调用。
- 内存占用与数据量不成比例,说明结构开销主导而非数据主导。
- 延迟分布出现长尾,且长尾与扩容、再平衡的时机吻合。
- 出现自研结构才能满足的语义(区间查询、按排名访问、前缀匹配)。
2.7.2 替换的兼容与迁移代价
替换的代价由结构的暴露程度决定。按代价递增:
| 暴露方式 | 迁移代价 | 规避方式 |
|---|---|---|
| 结构完全封装在单个方法内 | 只改实现与单元测试 | 无需特别处理 |
| 作为接口返回值暴露 | 调用方可能依赖下标、顺序或去重语义 | 返回抽象类型或不可变视图 |
| 参与序列化 | 格式变化影响存量数据与跨版本兼容 | 格式版本号、双读或迁移脚本 |
| 作为跨进程协议的一部分 | 需要上下游同步升级 | 协议层做结构无关的抽象 |
| 隐含在外部存储的物理布局中 | 需要数据迁移与双写 | 用逻辑映射隔离物理布局 |
其中序列化一项最容易被低估:把内部结构直接作为序列化对象,等于把实现细节固化为协议。可替换的写法是显式定义传输结构(数组或键值对),在边界处做一次转换。
2.7.3 用抽象接口隔离实现
隔离手段是抽象数据类型:定义操作集合与语义,隐藏存储与实现。调用方只依赖接口,替换实现不改变调用方代码。这一思想与"接口收窄换取实现自由"的关系见 抽象数据类型(ADT)。
// 面向接口编程:调用方只依赖操作语义
public interface RecentItems<K> {
void touch(K key); // 记录一次访问
List<K> mostRecent(int n); // 取出最近的 n 个键,按最近程度排序
}
// 实现一:哈希表 + 双端队列,适合读多写少、n 较小
// 实现二:哈希表 + 跳表,适合需要按时间区间查询的场景
// 调用方代码不因实现切换而改变
两点边界需要明确:
- 接口隔离的是实现,不是代价。 同一接口下不同实现的复杂度可能相差一个量级,接口文档应标注各项操作的时间与空间代价,否则调用方无法据此设计。
- 接口粒度决定替换成本。 过细的接口(暴露下标、节点、迭代顺序)会把实现细节泄漏出去;过粗的接口(只有一个"处理全部数据"的方法)会让实现无法利用调用方的访问模式先验。粒度应与调用方的实际需求对齐。
三、实现
3.1 决策表
下表以操作特征与数据规模为输入,给出结构与实现的推荐。表中的复杂度为量级结论,实际取舍需结合 2.3 节的因素实测。
| 操作特征 | 数据规模 | 推荐结构 | 可用实现 | 关键复杂度 | 注意点 |
|---|---|---|---|---|---|
| 按下标随机读写 | 任意 | 动态数组 | ArrayList、list、vector | 读写 O(1),中间改 O(n) | 已知规模时预设容量;批量追加前一次性扩容 |
| 尾部追加、批量构建 | 中至大 | 动态数组 | 同上 | 追加摊还 O(1) | 单次扩容为 O(n),内存峰值约 2.5 倍 |
| 两端增删 | 任意 | 环形数组双端队列 | ArrayDeque、std::deque | 两端摊还 O(1) | 一般不允许 null;部分实现不支持随机访问 |
| 顺序访问中删除当前元素 | 中至大 | 链表(经迭代器) | LinkedList、std::list | 删除 O(1) | 定位代价依赖迭代器推进方式 |
| 频繁中间插入(按键序) | 中至大 | 平衡树、跳表 | TreeMap、ConcurrentSkipListMap | 单次 O(log n) | 跳表的并发友好性更好、最坏界更弱 |
| 等值查找为主 | 任意 | 散列表 | HashMap、dict、unordered_map | 期望 O(1),最坏 O(n) | 键需正确实现相等与散列契约;预设容量 |
| 等值查找 + 有序遍历 | 中至大 | 平衡树、跳表 | TreeMap、ConcurrentSkipListMap | 单次 O(log n) | 需要比较器满足全序;比较成本可能主导耗时 |
| 范围查询 | 中至大 | 平衡树、跳表、B+ 树 | 同上 | O(log n + M),M 为结果数 | 推进过程必须沿序前进,不可逐次重新查找 |
| 按排名访问 | 中至大 | 跳表(维护跨距) | ConcurrentSkipListMap 不直接暴露 | O(log n) | 需要额外维护规模或跨距字段 |
| 反复取最值 | 中至大 | 二叉堆 | PriorityQueue、heapq | 取顶 O(1),插入出队 O(log n) | 不支持任意查找与有序遍历 |
| Top K(流式) | 大 | 大小为 K 的堆 | PriorityQueue | O(n log k) | K 接近 n 时优势消失,需要重新评估 |
| 前缀匹配、字典查询 | 中至大 | 字典树及变体 | 自研、双数组字典树 | 与键长相关 | 节点开销大,需要选择子节点表示方式 |
| 去重(精确) | 中至大 | 哈希集合 | HashSet、set | 期望 O(1) | 元素数极多时内存成为约束 |
| 去重(近似,允许假阳性) | 极大 | 布隆过滤器 | 自研、Redis 模块 | 插入与查询常数时间 | 无法删除与枚举,需要按误判率计算位数组长度 |
| 布尔状态、整数集合 | 极大且值域有限 | 位图 | 位运算自研、分块位图 | 位操作常数时间 | 值域大且稀疏时需要分块或压缩 |
| 区间和(可更新) | 中至大 | 树状数组 | 自研 | 更新查询 O(log n) | 要求运算可逆;不可逆时改用线段树 |
| 区间聚合(可更新,信息复杂) | 中至大 | 线段树 | 自研 | 更新查询 O(log n) | 需要处理懒标记下推与空间上限 |
| 区间聚合(静态) | 中至大 | 前缀和、稀疏表 | 自研 | 查询 O(1) | 不支持更新;稀疏表预处理 O(n log n) |
| 动态集合合并与连通性 | 中至大 | 并查集 | 自研 | 摊还 O(α(n)) | 只支持合并;需要分裂时改用其他结构 |
| 图的遍历与可达性 | 中至大 | 邻接表 + 队列或栈 | 自研 | O(V+E) | 稀疏图用邻接表,稠密图可用邻接矩阵 |
| 带权最短路 | 中至大 | 优先队列 + 邻接表 | 自研 | Dijkstra 为 O((V+E) log V) | 非负边权;负权需要换算法 |
| 并发有序访问 | 中至大 | 跳表 | ConcurrentSkipListMap | 期望 O(log n) | 复合操作仍需原子方法 |
| 读多写少的共享快照 | 中至大 | 写时复制结构 | 语言内置或自研 | 读 O(1),写 O(n) | 单次写代价高,只适合写极少场景 |
3.2 场景对照
下表按典型业务场景给出推荐结构、复杂度与注意点。表中同时给出该场景对应的专题文档位置。
| 场景 | 推荐结构 | 复杂度 | 注意点 | 对应文档 |
|---|---|---|---|---|
| 排行榜(按分值排序、按排名取区间) | 跳表,或跳表 + 散列表组合 | 插入与查询 O(log n),范围查询 O(log n + M) | 需要按排名访问时维护跨距字段;深分页的偏移量随规模变慢 | 跳表 |
| 延迟队列(按到期时间出队) | 二叉堆(按到期时间的小顶堆),大规模分散到期时用时间轮 | 堆:入队出队 O(log n);时间轮:入队 O(1) | 时间轮精度受 tick 限制,长延时需要多层;堆的精度不受限 | 栈与队列、堆与优先队列 |
| 最近访问缓存(LRU) | 散列表 + 双向链表,或语言内置的顺序映射 | 读写期望 O(1) | 需要同时保证按访问时间顺序淘汰与常数级定位;并发场景需处理命中时的结构修改 | 散列表、Java 集合框架实现原理 |
| 去重(精确) | 哈希集合;元素为小整数且值域集中时用位图 | 期望 O(1) / 位操作常数时间 | 元素数极大时内存是主要约束;位图要求值域有限 | 位图与布隆过滤器 |
| 去重(大规模、允许假阳性) | 布隆过滤器,必要时加持久化精确集合兜底 | 常数时间 | 只能判断"可能存在";假阳性需要下游精确校验 | 位图与布隆过滤器 |
| 频次统计与 Top K | 散列计数映射 + 大小为 K 的堆;需要完整排序时先聚合再排序 | 统计 O(n),Top K 为 O(n log k) | 全量排序取前 K 是常见误用;K 接近 n 时堆方案优势消失 | 堆与优先队列、排序与查找 |
| 区间统计(区间和、区间最值、区间计数) | 静态用前缀和或稀疏表;可更新用树状数组;运算不可逆或信息复杂用线段树 | 静态查询 O(1);可更新结构 O(log n) | 必须先确认数据是否被修改、运算是否可逆 | 线段树与并查集 |
| 依赖排序与任务编排 | 有向图 + 邻接表 + 入度队列(Kahn 算法) | O(V+E) | 需要检测环以识别不可执行的任务;入队去重依赖访问标记 | 图的表示与遍历 |
| 前缀搜索与自动补全 | 字典树及压缩变体,热词子集常驻内存 | 与键长相关 | 节点开销大,需要在子节点表示方式与空间之间权衡 | 字典树与字符串索引 |
| 消息去重与幂等 | 短窗口用布隆过滤器,长窗口用持久化去重表或有序时间范围清理 | 常数时间 / 按键 O(log n) | 需要明确去重窗口长度;窗口过长会导致存储无限增长 | 位图与布隆过滤器、消息可靠性 |
| 网络与拓扑的最短路、集群互联 | 优先队列 + 邻接表;最小生成树用排序 + 并查集 | Dijkstra 为 O((V+E) log V),Kruskal 为 O(E log E) | 边权为负时不能使用 Dijkstra;稠密图与稀疏图选择不同实现 | 最短路径与最小生成树 |
| 动态连通性(账号归并、集群连通判定) | 并查集 | 摊还 O(α(n)) | 只支持合并;需要删除边时改用其他结构或离线倒序处理 | 线段树与并查集 |
3.3 误用与替代
下表列出高频误用、其量级后果与替代方案。判定方式是看数据量翻倍后耗时是否变为四倍(平方特征)或内存占用是否与元素数不成比例。
| 误用 | 量级后果 | 替代方案 | 替代的代价 |
|---|---|---|---|
用列表做频繁按值查找(循环中 contains) | O(n²) | 改用哈希集合或先排序后二分 | 需要额外 O(n) 空间;哈希要求键实现相等契约 |
| 用有序数组做频繁插入 | 每次插入 O(n),累计 O(n²) | 平衡树、跳表或块状结构 | 单次操作从 O(n) 降到 O(log n),常数上升、缓存局部性下降 |
| 用散列表做范围查询 | 每次查询需全量扫描 O(n) | 平衡树或跳表 | 单次等值查找从期望 O(1) 降到 O(log n) |
| 用链表做随机访问 | 每次访问 O(n) | 动态数组 | 中间插入删除代价上升;需要评估插入位置是否已知 |
| 用全量排序取 Top K | O(n log n) | 大小为 K 的堆或快速选择 | 堆方案要求 K 远小于 n;快速选择需要可随机访问的数据 |
| 用嵌套遍历代替索引(两两比较去重) | O(n²) | 先用哈希集合去重再输出 | 需要 O(n) 额外空间;哈希退化时需要兜底 |
用字符串拼接代替缓冲(循环中 +=) | O(n²) | 使用可变缓冲(StringBuilder 等) | 需要显式管理缓冲生命周期;并发场景需线程私有缓冲 |
| 用大对象作为散列表键 | 单次操作常数高、内存放大 | 用稳定且短的标识作键,或预计算并缓存散列值 | 需要维护标识与对象的映射,并保证标识稳定 |
| 用哈希集合存海量布尔状态或小整数 | 内存放大数十倍 | 位图 | 值域必须是有限整数区间;稀疏时需分块或压缩 |
| 用通用散列表存海量数值键值对 | 对象化开销主导内存占用 | 基本类型特化的开放寻址实现 | 需要引入第三方实现或自研,缺少通用集合的接口生态 |
| 在循环内排序或重建集合 | 量级升一阶 | 把排序与集合构建提到循环外并复用 | 需要确认数据在循环期间不变 |
| 用堆做"取某个元素是否存在"的判断 | 每次 O(n) | 哈希集合或平衡树 | 失去 O(1) 取最值的能力;需要评估两者是否同时需要 |
几处需要补充的说明:
- "改用哈希集合"的前提是键的相等与散列契约正确。 键对象未同时重写
equals与hashCode,或键的字段在放入后被修改,都会造成元素失联。这类缺陷表现为"刚放进去就查不到",与结构选择无关。相关契约与碰撞攻击的讨论见 散列表。 - "用堆替代全量排序"的有效范围有限。 K 与 n 接近时,堆的 O(n log k) 与排序的 O(n log n) 差别很小;流式数据无法回退时,堆是少数可行选择。三者的对照见 堆与优先队列。
- "用位图替代哈希集合"要求值域可控。 值域为稀疏的大整数时,定长位图的空间与最大取值成正比,反而可能超过哈希集合,此时应改用分块位图或保留哈希方案。
- 替代的净收益需要实测确认。 表中给出的是量级结论;目标规模落在交叉点附近时,常数因子可能改变排序结果。
3.4 验证方法
3.4.1 基准与压测的分工
| 方法 | 观测对象 | 回答的问题 | 结论边界 |
|---|---|---|---|
| 复杂度分析 | 增长量级 | 规模增长后哪一方占优 | 量级层面的趋势,不含常数 |
| 微基准 | 方法或代码路径 | 同一量级下哪种实现局部成本更低 | 该版本、该规模、该数据分布下的相对关系 |
| 系统压测 | 完整服务与主机资源 | 能承载多少、延迟分位是多少 | 该环境与配置下的容量边界 |
| 线上观测 | 真实流量 | 变更后实际表现是否改善 | 当前数据分布下的实际结果 |
微基准的设计要点(预热与测量轮次分离、结果消费、分叉隔离、参数化展开规模、结果判读)见 JMH 微基准测试;压测的环境确认、基线归档、回归阈值与容量换算见 linux: 压测与性能基线。两者的干扰控制原则一致:固定条件、明确预热、一次只改一个变量、多轮取稳态值。
需要避免的一类错误是用微基准的结论推导容量结论。微基准测的是单次调用耗时,容量由并发度、资源竞争与外部依赖共同决定,两者的口径不可互换。
3.4.2 以真实规模与分布测试
结构对比基准需要覆盖的维度:
- 规模。至少取三个数量级(如 10³、10⁵、10⁷),观察耗时随规模变化的曲线形态,而不是比较单点数值。曲线形态才能区分"常数差异"与"量级差异"。
- 数据分布。至少包含随机与最坏两类输入。哈希函数对特定键集合退化和有序输入导致平衡树左右失衡,都只在特定分布下出现;跳表与哈希表对输入分布的敏感度则不同。
- 操作混合比例。分别测量纯读、读写各半、含删除的更新流;只测单一操作会掩盖更新代价。
- 键的类型与比较成本。整数键与字符串键分别测量。比较器内部做字符串解析或正则匹配时,单次操作开销由比较器主导而非结构主导。
- 结果消费。使用黑洞消费返回值,避免计算被即时编译整体消除。
3.4.3 内存占用的测量方法
时间之外必须同时记录内存。常用手段与适用场景:
| 手段 | 观测对象 | 适用场景 | 局限 |
|---|---|---|---|
| 单次操作的分配量(如 JMH 的分配量指标) | 结构本身与临时对象 | 微基准层面比较两种实现 | 不含长期驻留与碎片 |
| 类直方图 | 各类实例数与占用 | 快速判断是否有异常数量的容器或数组 | 只反映瞬时快照 |
| 堆转储按保留大小排序 | 对象及其引用链 | 定位持有者字段与业务代码位置 | 有停顿与磁盘开销,不适合频繁执行 |
| GC 日志统计 | 回收频率、晋升量与停顿 | 观察长期运行的分配压力 | 需要开启对应参数并长期采集 |
| 进程 RSS 与容器限额 | 主机侧实际占用 | 判断是否逼近容器内存上限 | 包含堆外与内核态缓存,口径与堆不同 |
堆内占用与主机内存口径的对应关系、页的映射方式与容器内存判定的关系见 JVM 内存结构与垃圾回收。
3.4.4 灰度与替换过程中的观察指标
结构替换属于影响面较广的变更,观察指标应覆盖功能与资源两侧:
| 指标类别 | 具体指标 | 预期信号 |
|---|---|---|
| 延迟 | 平均值与 P99、P999 分位 | 替换后 P99 应下降;若仅平均值下降而长尾未变,说明瓶颈不在该结构 |
| 资源 | 堆占用、GC 频率与停顿、进程 RSS | 内存型替换应体现为占用下降或增长速度变缓 |
| 吞吐 | 单位时间处理量、队列长度 | 削峰类替换(有界队列等)应体现为积压可控 |
| 正确性 | 结果一致性校验、去重结果的差集统计 | 近似结构替换为精确结构或反向替换时,必须统计差异 |
| 稳定性 | 错误率、超时、重试次数 | 毛刺消除后应体现为超时次数下降 |
替换过程中的两个必要保护措施:保留可回退路径(开关或双实现并存的短期形态),以及在灰度阶段同时统计新旧两路的结果差异,而不是只比较耗时。
3.5 评审清单
3.5.1 设计评审中的结构相关提问
按五个方向逐项确认。任一方向无法给出明确答案时,选型结论都不算成立。
规模与增长
- 当前数据量、单机上限与预期峰值分别是多少;数据量是否会随业务增长跨越数量级。
- 单条请求路径上会处理多少个元素;是否存在随租户或随数据增长而线性扩大的循环。
- 是否有超大数据量的单点操作(一次性加载全量、一次性排序全量),能否改为分批或流式。
操作频率与模式
- 读写比例是多少;热点操作是哪一项。
- 是否需要有序输出、范围查询、按排名访问;这些需求是否会被后续功能引入。
- 是否存在"按下标访问"与"按键访问"混合的模式;混合时选择的结构能否同时满足。
内存预算
- 每元素的容器结构开销估算值是多少;规模乘以该值后的总占用是多少。
- 是否留有扩容的峰值余量(动态数组与散列表的扩容瞬间占用可达稳态的数倍)。
- 数据量超出内存时的降级路径是什么。
并发
- 结构会被多少个线程访问;访问模式是读多写少、写多读少还是并发写。
- 复合操作(判断后写入、读取后修改)是否需要由容器提供原子性。
- 是否存在先发布后初始化的安全发布问题;迭代期间的修改如何处理。
失败与恢复
- 结构所在进程重启后数据是否需要保留;不需要保留时,重建的耗时是否可接受。
- 结构损坏或数据超限时的行为是否有定义(拒绝写入、淘汰、降级)。
- 是否有容量上限与淘汰策略;无界增长的结构是否被明确识别并说明理由。
3.5.2 代码评审中的结构误用检查项
容器选择与访问模式
- 容器选择是否与访问模式匹配:按位置访问用数组、按键访问用散列、需要顺序用有序结构、需要最值用堆。
- 是否存在把列表当集合使用(用
contains做去重)的写法。 - 是否存在对链表的按下标访问,形成隐式的平方级遍历。
- 数据量大时是否预设容量,以消除扩容的时间开销与内存峰值。
- 是否在循环内排序、去重、建立集合或索引;这些操作能否提到循环外。
- 是否存在只使用一次的中间集合,能否直接消费数据源。
结构语义
- 键对象的相等与散列契约是否一致且稳定;键的字段是否在放入后被修改。
- 有序结构的比较器是否满足全序;是否存在不可比较的元素。
- 堆的比较器在优先级相等时是否稳定;是否会出现遍历顺序被误当作出队顺序的用法。
- 是否需要按下标删除元素的正向循环(会跳过一个元素),是否应改为倒序或使用迭代器删除。
- 删除引用型元素后是否清理了容器内的引用,避免对象无法回收。
并发与可见性
- 共享结构是否使用了并发安全的实现,还是自行加锁暴露了内部结构。
- 复合操作是否已合并为原子操作;
size()是否被用作控制条件。 - 是否依赖"看起来能跑"的可见性假设,而不是语言内存模型提供的保证。
资源与边界
- 是否存在无上限增长的容器;是否有容量上限与淘汰策略。
- 递归或迭代的深度是否与数据规模相关;最坏深度是否被评估过。
- 是否存在与输入规模同阶的多份数据副本。
- 结构是否被直接放入序列化协议,从而把实现细节固化为兼容接口。
静态分析工具对上述部分检查项(空指针、资源未关闭、并发误用、过长方法与重复代码)可以自动识别,但涉及语义与访问模式的判断仍依赖人工评审。工具能力边界、规则分级与质量门禁的位置见 Java 代码质量与静态分析。
3.6 常见问题与排查
3.6.1 如何确认是结构选择问题
性能问题的第一判断是瓶颈类别,而不是直接替换结构。固定顺序如下。
- 确认时间花在哪里。 用采样剖析或事件记录确定热点方法,而不是按代码阅读推测。工具选择与开销边界见 Java 应用诊断与部署调优。
- 确认规模与耗时的关系形态。 线性、线性对数、还是平方级以上。数据量翻倍而耗时变为四倍,指向嵌套遍历或循环内的线性调用,属于结构选择问题;耗时与数据量近似线性而与外部调用次数相关,则更可能是 IO 或下游依赖问题。
- 确认内存与时间的对应关系。 时间正常但内存单调上涨,通常指向无界容器、未清理的引用或缓存缺少淘汰;两者的趋势不一致时必须解释差异来源。
- 确认是否由结构引起,而非由使用方式引起。 同一结构在正确用法下可能是 O(1) 或 O(log n),在错误用法下退化为 O(n)。判断依据是是否存在循环内的线性调用、重复的集合构造、对同一数据的多次遍历。
- 确认并发是否为诱因。 单线程复现成功说明与并发无关;仅在并发下出现时,需要检查锁竞争、CAS 重试、伪共享与容器可见性。
只有在确认"热点在结构的操作上,且使用方式正确"之后,替换结构才是正确的动作。
3.6.2 扩容毛刺与内存增长
扩容毛刺。 表现是延迟分布出现间隔性的长尾,长尾与写入量累积到容量阈值的时刻吻合;GC 日志中可见对应的分配尖峰。确认方式是记录容器元素数与延迟的对应关系,观察长尾是否出现在元素数接近容量的时刻。处置方向:
- 已知规模时预设容量;无法精确估计时在批量写入前一次性扩容到足够容量。
- 把大批量构建移出请求路径,或改为分批处理。
- 延迟敏感路径上改用无集中扩容代价的结构(链表、跳表)。
- 无法消除时评估是否可接受,而不是默认忽略。
内存增长。 表现是堆占用随运行时间单调上升。结构相关的成因有三类:
| 成因 | 特征 | 处置方向 |
|---|---|---|
| 无界容器 | 元素数持续增长 | 设置容量上限与淘汰策略;有界队列提供背压 |
| 引用未清理(出队后槽位仍持有引用、删除元素后未置空) | 占用不随删除下降,且与容器容量同阶 | 出队或删除时显式清空引用 |
| 结构开销放大(节点对象、包装类型、表数组取整) | 占用与数据量成固定倍数关系 | 改用紧凑表示或基本类型特化实现 |
堆转储按保留大小排序是区分三者的直接手段;类直方图可快速判断是否有异常数量的容器实例。
3.6.3 结构在并发下的正确性
结构本身不包含并发语义,多线程共享时以下四类问题最常出现。
| 现象 | 成因 | 处置方向 |
|---|---|---|
| 元素丢失或计数不一致 | "读—改—写"复合操作存在竞态;可见性不足 | 使用容器提供的原子方法,或把复合操作纳入同一临界区 |
| 迭代时抛并发修改异常 | 迭代期间发生结构性修改 | 使用迭代器的删除方法;或改为快照式遍历 |
| 结构内部不一致(链表成环、数组与计数不符) | 无保护的结构修改被并发执行 | 换用并发容器;不要给非线程安全结构加局部锁后继续暴露内部引用 |
| 观察到的对象处于部分构造状态 | 未安全发布;字段非 final 且未通过同步或 volatile 发布 | 按安全发布规则处理,见 Java 并发编程 |
这里的通用原则是:可见性与原子性是两个独立问题,加锁与 volatile 各自只能解决其中之一。 并发有序访问应优先选择天然并发友好的跳表,而不是给平衡树加锁。
3.6.4 序列化与持久化带来的额外开销
结构被序列化或持久化时,代价模型增加三项。
- 序列化体量与结构强相关。 节点式结构的序列化往往包含指针信息或需要重建关系;同一份数据用数组表示通常比用链表表示更紧凑。把内部结构直接序列化,还会把实现细节固化为跨版本兼容约束。
- 反序列化重建的代价。 重建有序结构需要逐元素插入,代价为 O(n log n);重建过程的内存峰值高于稳态占用。替代做法是存储有序的键值序列,加载时批量建堆或直接以有序数组形式使用。
- 跨版本兼容。 结构变更需要处理存量数据的读取。可行手段是格式版本号、双读(同时支持新旧格式)与迁移脚本。相关机制见 Java 序列化。
持久化场景还引入了崩溃恢复的正确性问题:写入顺序、校验与重复写入的处理决定了恢复后结构是否自洽。这部分属于持久化结构自身的语义,其页管理与日志机制见 B 树与 B+ 树。
四、总结
定位。 选型是把操作特征翻译为结构的过程,判断依据来自三个可直接回答的问题:需要哪些操作、各自频率如何、规模多大。它发生在写代码之前,后果出现在数据增长之后,因此代价的发现时间与修复成本通常不对称。选型的目标不是一次选中最优结构,而是避免在错误的方向上投入,并保留替换的余地。
判断维度。 操作种类与频率决定结构类别;规模与增长预期决定量级差异是否已经显现;内存与持久化约束决定能否使用节点式结构;并发模式决定同步方案;有序性与去重计数需求在散列与有序结构之间作出二选一;稳定性要求可能迫使引入额外的次序键。这些维度的结论互相约束,需要按顺序推进。
按操作反查。 随机访问选连续存储;两端操作选环形数组或链表;中间插入选有序结构或块状结构;等值查找选散列表;范围查询与有序输出选平衡树、跳表或 B+ 树;取最值选堆;区间聚合按"是否可更新、运算是否可逆"在前缀和、差分数组、树状数组与线段树之间递进;连通性判定选并查集;前缀匹配选字典树;近似存在性判断选布隆过滤器;并发有序访问选跳表。
复杂度之外的因素。 常数因子在小规模时主导;缓存局部性使同为 O(n) 的遍历相差近一个数量级;扩容与再平衡带来摊还代价与单次毛刺的分离;内存开销由数据、结构字段与对齐填充三部分构成,需要按规模核算而不是按元素大小估算;并发方案之间存在语义与代价的双重差异,不能简化为"加锁即可"。
内存核算。 千万级键值映射的核算表明,通用散列表的占用主要由对象化造成——节点对象、包装类型键与值各自携带对象头,合计远大于数据本身。内存受限时的替代方向是按值域与精度要求放宽语义:位图、近似计数结构、分块处理、落盘索引;每一项都以能力或精度换取空间。
内置结构。 容器名称描述接口而非实现。动态数组、散列映射、红黑树映射、跳表映射、堆、双端队列各自对应固定的底层结构与复杂度,确认方式依次为读文档的复杂度声明、读源码的实现细节、以及目标规模下的实测。实现细节不应写入代码假设,绑定实现数值的代码会在版本升级后失效。
持久化与分布式。 落盘后代价模型从比较次数变为页访问次数,写多读少选 LSM、读多写少与范围查询选 B+ 树、追加型写入选日志。跨节点时映射方式决定扩容的搬迁范围,一致性哈希与哈希槽把节点变化的影响局部化。全局标识的有序性直接影响索引的插入模式与页填充率。
演进。 从语言内置的简单结构起步,按实测替换;替换代价由结构的暴露程度决定,序列化与协议层的暴露最容易被低估;抽象接口隔离实现,但接口隔离的是实现而代价,接口文档需要标注各项操作的复杂度。
验证与评审。 复杂度分析负责筛选,微基准负责方法级取舍,压测负责容量边界,线上观测负责验证实际收益,四者口径不可互换。测量必须覆盖规模、分布与操作混合比例,并同时记录时间与内存。评审清单覆盖规模与增长、操作频率、内存预算、并发与失败恢复五个方向;代码评审重点检查容器选择与访问模式的匹配、结构语义的正确性与资源边界的处理。
选型的核心不是记住结构之间的优劣排序,而是建立从操作特征到结构的映射,并明确该映射的成立条件。结构没有绝对的最优,只有与访问模式、数据规模与资源约束相匹配的实现;匹配关系一旦变化,结论也随之改变。