一、起源:选型失误的代价

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+ 树、堆与优先队列、字典树与字符串索引、线段树与并查集、图的表示与遍历。

几点需要在反查时补充的约束:

  1. "按键查找"与"按范围查询"往往同时出现。 若同一份数据既要等值定位又要范围扫描,散列表无法承担后者,此时平衡树或跳表是唯一能同时满足两者的内存结构;若等值查找占绝对主导、范围查询只是偶尔的运维需求,可以用散列表加一次排序的离线方案替代。
  2. "频繁中间插入"的结论依赖插入位置是否已知。 位置由排序键决定时用平衡树;位置由下标给出且需要按序访问时,块状结构或跳表更合适;位置由遍历过程给出(如迭代器删除当前元素)时链表反而最省,见 数组与链表 中链表查找 O(n) 的本质一节。
  3. "区间聚合"的选型有固定顺序。 数据不被修改时优先前缀和或稀疏表;只有区间更新而无区间查询时用差分数组;点更新加区间和优先树状数组;运算不可逆或合并信息复杂时用线段树。完整顺序见 线段树与并查集 中对比与选型一节。
  4. "取最值"与"有序输出"不可互相替代。 堆只保证堆顶为极值,其余元素没有顺序承诺,迭代优先队列得到的顺序通常不是出队顺序;需要完整有序序列时,要么连续出队,要么改用有序结构。
  5. 连通性判定的两条路线。 关系只增不减时并查集最优;关系可能变化、或需要路径本身时,必须退回图的遍历,见 图的表示与遍历。

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 压力
线程私有 每个线程持有独立结构,定期合并 无同步开销;合并时机与内存占用需要额外设计

其中有三点容易误判:

  1. 可见性与原子性是两件事。 把引用声明为 volatile 只能保证可见性,不能修复"读—改—写"三步复合操作的竞态。
  2. 并发容器的单方法原子性不等于复合操作原子性。 先判断再写入的模式必须改用容器提供的原子方法。
  3. 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
        代价:需要引入第三方实现或自行开发,缺少通用集合的接口生态

三点结论:

  1. 通用散列表的开销主要由对象化造成。 节点对象、包装类型的键与值各自携带对象头,三者合计远大于数据本身。消除对象化是数量级层面的优化,而非常数调优。
  2. 容量取整到 2 的幂会放大表数组占用。 负载因子 0.75 意味着表数组常有多余槽位,元素数刚越过阈值时浪费最明显。
  3. 估算应覆盖全链路而不仅是容器。 序列化缓冲区、副本、缓存以及扩容瞬间的中间态都会叠加占用,容器本身只是其中一项。

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 确认实现的方式

内置结构的实现属于具体实现的细节,语言规范通常不作保证。确认方式按可靠性递增排列:

  1. 读接口文档的复杂度说明。 标准库文档通常会标注"摊还 O(1)""O(log n)"这类结论,并说明前提。这是最低成本的入口。
  2. 读源码或实现注释。 扩容倍数、树化阈值、负载因子的默认值都属于实现细节,直接决定内存占用与毛刺形态。
  3. 在目标规模下实测。 两个实现的量级相同时,文档无法给出取舍结论,只能实测。

需要特别说明的是:不应把实现细节写进代码的假设里。依赖"某容器扩容倍数为 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 从简单结构起步

选型的目标不是一开始就找到最优结构,而是避免在错误的方向上投入。可行的推进顺序:

  1. 用最简单的结构实现正确语义。 首选语言内置的动态数组、哈希映射与堆,它们经过充分验证且不引入自研代码的缺陷面。
  2. 确定规模与访问模式。 记录当前规模、增长速度与读写比例。这一步的产出是后续判断的依据,而不是猜测。
  3. 在目标规模下测量。 依据实测而非直觉决定是否需要替换。测量方法见本章 3.4 节。
  4. 按测量结果替换。 替换的触发条件应当是具体的:单次请求耗时超阈值、内存占用逼近限额、扩容毛刺落在请求路径上。

需要替换的典型信号:

  • 耗时随数据量呈平方增长,说明存在嵌套遍历或循环内的线性调用。
  • 内存占用与数据量不成比例,说明结构开销主导而非数据主导。
  • 延迟分布出现长尾,且长尾与扩容、再平衡的时机吻合。
  • 出现自研结构才能满足的语义(区间查询、按排名访问、前缀匹配)。

2.7.2 替换的兼容与迁移代价

替换的代价由结构的暴露程度决定。按代价递增:

暴露方式 迁移代价 规避方式
结构完全封装在单个方法内 只改实现与单元测试 无需特别处理
作为接口返回值暴露 调用方可能依赖下标、顺序或去重语义 返回抽象类型或不可变视图
参与序列化 格式变化影响存量数据与跨版本兼容 格式版本号、双读或迁移脚本
作为跨进程协议的一部分 需要上下游同步升级 协议层做结构无关的抽象
隐含在外部存储的物理布局中 需要数据迁移与双写 用逻辑映射隔离物理布局

其中序列化一项最容易被低估:把内部结构直接作为序列化对象,等于把实现细节固化为协议。可替换的写法是显式定义传输结构(数组或键值对),在边界处做一次转换。

2.7.3 用抽象接口隔离实现

隔离手段是抽象数据类型:定义操作集合与语义,隐藏存储与实现。调用方只依赖接口,替换实现不改变调用方代码。这一思想与"接口收窄换取实现自由"的关系见 抽象数据类型(ADT)。

// 面向接口编程:调用方只依赖操作语义
public interface RecentItems<K> {
    void touch(K key);            // 记录一次访问
    List<K> mostRecent(int n);    // 取出最近的 n 个键,按最近程度排序
}

// 实现一:哈希表 + 双端队列,适合读多写少、n 较小
// 实现二:哈希表 + 跳表,适合需要按时间区间查询的场景
// 调用方代码不因实现切换而改变

两点边界需要明确:

  1. 接口隔离的是实现,不是代价。 同一接口下不同实现的复杂度可能相差一个量级,接口文档应标注各项操作的时间与空间代价,否则调用方无法据此设计。
  2. 接口粒度决定替换成本。 过细的接口(暴露下标、节点、迭代顺序)会把实现细节泄漏出去;过粗的接口(只有一个"处理全部数据"的方法)会让实现无法利用调用方的访问模式先验。粒度应与调用方的实际需求对齐。

三、实现

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) 取最值的能力;需要评估两者是否同时需要

几处需要补充的说明:

  1. "改用哈希集合"的前提是键的相等与散列契约正确。 键对象未同时重写 equals 与 hashCode,或键的字段在放入后被修改,都会造成元素失联。这类缺陷表现为"刚放进去就查不到",与结构选择无关。相关契约与碰撞攻击的讨论见 散列表。
  2. "用堆替代全量排序"的有效范围有限。 K 与 n 接近时,堆的 O(n log k) 与排序的 O(n log n) 差别很小;流式数据无法回退时,堆是少数可行选择。三者的对照见 堆与优先队列。
  3. "用位图替代哈希集合"要求值域可控。 值域为稀疏的大整数时,定长位图的空间与最大取值成正比,反而可能超过哈希集合,此时应改用分块位图或保留哈希方案。
  4. 替代的净收益需要实测确认。 表中给出的是量级结论;目标规模落在交叉点附近时,常数因子可能改变排序结果。

3.4 验证方法

3.4.1 基准与压测的分工

方法 观测对象 回答的问题 结论边界
复杂度分析 增长量级 规模增长后哪一方占优 量级层面的趋势,不含常数
微基准 方法或代码路径 同一量级下哪种实现局部成本更低 该版本、该规模、该数据分布下的相对关系
系统压测 完整服务与主机资源 能承载多少、延迟分位是多少 该环境与配置下的容量边界
线上观测 真实流量 变更后实际表现是否改善 当前数据分布下的实际结果

微基准的设计要点(预热与测量轮次分离、结果消费、分叉隔离、参数化展开规模、结果判读)见 JMH 微基准测试;压测的环境确认、基线归档、回归阈值与容量换算见 linux: 压测与性能基线。两者的干扰控制原则一致:固定条件、明确预热、一次只改一个变量、多轮取稳态值。

需要避免的一类错误是用微基准的结论推导容量结论。微基准测的是单次调用耗时,容量由并发度、资源竞争与外部依赖共同决定,两者的口径不可互换。

3.4.2 以真实规模与分布测试

结构对比基准需要覆盖的维度:

  1. 规模。至少取三个数量级(如 10³、10⁵、10⁷),观察耗时随规模变化的曲线形态,而不是比较单点数值。曲线形态才能区分"常数差异"与"量级差异"。
  2. 数据分布。至少包含随机与最坏两类输入。哈希函数对特定键集合退化和有序输入导致平衡树左右失衡,都只在特定分布下出现;跳表与哈希表对输入分布的敏感度则不同。
  3. 操作混合比例。分别测量纯读、读写各半、含删除的更新流;只测单一操作会掩盖更新代价。
  4. 键的类型与比较成本。整数键与字符串键分别测量。比较器内部做字符串解析或正则匹配时,单次操作开销由比较器主导而非结构主导。
  5. 结果消费。使用黑洞消费返回值,避免计算被即时编译整体消除。

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 如何确认是结构选择问题

性能问题的第一判断是瓶颈类别,而不是直接替换结构。固定顺序如下。

  1. 确认时间花在哪里。 用采样剖析或事件记录确定热点方法,而不是按代码阅读推测。工具选择与开销边界见 Java 应用诊断与部署调优。
  2. 确认规模与耗时的关系形态。 线性、线性对数、还是平方级以上。数据量翻倍而耗时变为四倍,指向嵌套遍历或循环内的线性调用,属于结构选择问题;耗时与数据量近似线性而与外部调用次数相关,则更可能是 IO 或下游依赖问题。
  3. 确认内存与时间的对应关系。 时间正常但内存单调上涨,通常指向无界容器、未清理的引用或缓存缺少淘汰;两者的趋势不一致时必须解释差异来源。
  4. 确认是否由结构引起,而非由使用方式引起。 同一结构在正确用法下可能是 O(1) 或 O(log n),在错误用法下退化为 O(n)。判断依据是是否存在循环内的线性调用、重复的集合构造、对同一数据的多次遍历。
  5. 确认并发是否为诱因。 单线程复现成功说明与并发无关;仅在并发下出现时,需要检查锁竞争、CAS 重试、伪共享与容器可见性。

只有在确认"热点在结构的操作上,且使用方式正确"之后,替换结构才是正确的动作。

3.6.2 扩容毛刺与内存增长

扩容毛刺。 表现是延迟分布出现间隔性的长尾,长尾与写入量累积到容量阈值的时刻吻合;GC 日志中可见对应的分配尖峰。确认方式是记录容器元素数与延迟的对应关系,观察长尾是否出现在元素数接近容量的时刻。处置方向:

  • 已知规模时预设容量;无法精确估计时在批量写入前一次性扩容到足够容量。
  • 把大批量构建移出请求路径,或改为分批处理。
  • 延迟敏感路径上改用无集中扩容代价的结构(链表、跳表)。
  • 无法消除时评估是否可接受,而不是默认忽略。

内存增长。 表现是堆占用随运行时间单调上升。结构相关的成因有三类:

成因 特征 处置方向
无界容器 元素数持续增长 设置容量上限与淘汰策略;有界队列提供背压
引用未清理(出队后槽位仍持有引用、删除元素后未置空) 占用不随删除下降,且与容器容量同阶 出队或删除时显式清空引用
结构开销放大(节点对象、包装类型、表数组取整) 占用与数据量成固定倍数关系 改用紧凑表示或基本类型特化实现

堆转储按保留大小排序是区分三者的直接手段;类直方图可快速判断是否有异常数量的容器实例。

3.6.3 结构在并发下的正确性

结构本身不包含并发语义,多线程共享时以下四类问题最常出现。

现象 成因 处置方向
元素丢失或计数不一致 "读—改—写"复合操作存在竞态;可见性不足 使用容器提供的原子方法,或把复合操作纳入同一临界区
迭代时抛并发修改异常 迭代期间发生结构性修改 使用迭代器的删除方法;或改为快照式遍历
结构内部不一致(链表成环、数组与计数不符) 无保护的结构修改被并发执行 换用并发容器;不要给非线程安全结构加局部锁后继续暴露内部引用
观察到的对象处于部分构造状态 未安全发布;字段非 final 且未通过同步或 volatile 发布 按安全发布规则处理,见 Java 并发编程

这里的通用原则是:可见性与原子性是两个独立问题,加锁与 volatile 各自只能解决其中之一。 并发有序访问应优先选择天然并发友好的跳表,而不是给平衡树加锁。

3.6.4 序列化与持久化带来的额外开销

结构被序列化或持久化时,代价模型增加三项。

  1. 序列化体量与结构强相关。 节点式结构的序列化往往包含指针信息或需要重建关系;同一份数据用数组表示通常比用链表表示更紧凑。把内部结构直接序列化,还会把实现细节固化为跨版本兼容约束。
  2. 反序列化重建的代价。 重建有序结构需要逐元素插入,代价为 O(n log n);重建过程的内存峰值高于稳态占用。替代做法是存储有序的键值序列,加载时批量建堆或直接以有序数组形式使用。
  3. 跨版本兼容。 结构变更需要处理存量数据的读取。可行手段是格式版本号、双读(同时支持新旧格式)与迁移脚本。相关机制见 Java 序列化。

持久化场景还引入了崩溃恢复的正确性问题:写入顺序、校验与重复写入的处理决定了恢复后结构是否自洽。这部分属于持久化结构自身的语义,其页管理与日志机制见 B 树与 B+ 树。


四、总结

定位。 选型是把操作特征翻译为结构的过程,判断依据来自三个可直接回答的问题:需要哪些操作、各自频率如何、规模多大。它发生在写代码之前,后果出现在数据增长之后,因此代价的发现时间与修复成本通常不对称。选型的目标不是一次选中最优结构,而是避免在错误的方向上投入,并保留替换的余地。

判断维度。 操作种类与频率决定结构类别;规模与增长预期决定量级差异是否已经显现;内存与持久化约束决定能否使用节点式结构;并发模式决定同步方案;有序性与去重计数需求在散列与有序结构之间作出二选一;稳定性要求可能迫使引入额外的次序键。这些维度的结论互相约束,需要按顺序推进。

按操作反查。 随机访问选连续存储;两端操作选环形数组或链表;中间插入选有序结构或块状结构;等值查找选散列表;范围查询与有序输出选平衡树、跳表或 B+ 树;取最值选堆;区间聚合按"是否可更新、运算是否可逆"在前缀和、差分数组、树状数组与线段树之间递进;连通性判定选并查集;前缀匹配选字典树;近似存在性判断选布隆过滤器;并发有序访问选跳表。

复杂度之外的因素。 常数因子在小规模时主导;缓存局部性使同为 O(n) 的遍历相差近一个数量级;扩容与再平衡带来摊还代价与单次毛刺的分离;内存开销由数据、结构字段与对齐填充三部分构成,需要按规模核算而不是按元素大小估算;并发方案之间存在语义与代价的双重差异,不能简化为"加锁即可"。

内存核算。 千万级键值映射的核算表明,通用散列表的占用主要由对象化造成——节点对象、包装类型键与值各自携带对象头,合计远大于数据本身。内存受限时的替代方向是按值域与精度要求放宽语义:位图、近似计数结构、分块处理、落盘索引;每一项都以能力或精度换取空间。

内置结构。 容器名称描述接口而非实现。动态数组、散列映射、红黑树映射、跳表映射、堆、双端队列各自对应固定的底层结构与复杂度,确认方式依次为读文档的复杂度声明、读源码的实现细节、以及目标规模下的实测。实现细节不应写入代码假设,绑定实现数值的代码会在版本升级后失效。

持久化与分布式。 落盘后代价模型从比较次数变为页访问次数,写多读少选 LSM、读多写少与范围查询选 B+ 树、追加型写入选日志。跨节点时映射方式决定扩容的搬迁范围,一致性哈希与哈希槽把节点变化的影响局部化。全局标识的有序性直接影响索引的插入模式与页填充率。

演进。 从语言内置的简单结构起步,按实测替换;替换代价由结构的暴露程度决定,序列化与协议层的暴露最容易被低估;抽象接口隔离实现,但接口隔离的是实现而代价,接口文档需要标注各项操作的复杂度。

验证与评审。 复杂度分析负责筛选,微基准负责方法级取舍,压测负责容量边界,线上观测负责验证实际收益,四者口径不可互换。测量必须覆盖规模、分布与操作混合比例,并同时记录时间与内存。评审清单覆盖规模与增长、操作频率、内存预算、并发与失败恢复五个方向;代码评审重点检查容器选择与访问模式的匹配、结构语义的正确性与资源边界的处理。

选型的核心不是记住结构之间的优劣排序,而是建立从操作特征到结构的映射,并明确该映射的成立条件。结构没有绝对的最优,只有与访问模式、数据规模与资源约束相匹配的实现;匹配关系一旦变化,结论也随之改变。