线性与散列数据结构总览

这部分知识我前后看过不止一次。刚接触“线性与散列数据结构总览”时，数组、链表、栈、队列和哈希表是我最早学的一批结构，也最容易因为熟悉 API 而误以为自己已经理解。等我回头从问题本身出发，而不是从模板出发，很多原来零散的规则才慢慢连在一起。下面按我自己的理解过程展开。

数组、链表、队列、栈和哈希表解决的其实是同一个问题：怎样组织一组元素，才能让最重要的操作足够快。区别不在于谁更“高级”，而在于它们为不同操作支付了不同成本。

先建立一张选择地图

结构	最擅长的操作	典型复杂度	主要代价
数组	按下标随机访问	`O(1)`	中间插入、删除需要搬移
链表	已知节点后的插入、删除	`O(1)`	定位第 k 个元素需要遍历
队列	按到达顺序处理任务	入队、出队 `O(1)`	只能从约定的一端访问
栈	保存最近状态、逆序处理	压栈、出栈 `O(1)`	只能直接访问栈顶
哈希表	根据键快速查找	平均 `O(1)`	需要处理碰撞、扩容和哈希质量

复杂度只是第一层。真实工程中还要考虑缓存局部性、对象开销、扩容峰值、并发控制和访问模式。比如链表“插入是 O(1)”这句话有一个常被省略的前提：你已经拿到了插入位置的节点。如果为了找到它先遍历一次，总成本仍然是 O(n)。

五种结构之间的关系

数组把元素放在连续区域，索引可以直接换算为地址，因此随机访问快。链表不要求节点连续，用指针换取灵活连接。队列和栈不是某种固定的底层存储，而是对访问顺序的约束：它们既可以用数组实现，也可以用链表实现。

哈希表则把“键”经过哈希函数映射到数组槽位。它的快速查找来自数组，碰撞处理又经常借助链表、红黑树或开放寻址。所以理解数组和链表之后，再学习哈希表会自然很多。

数组、链表、队列、栈和哈希表选择关系图

图：先根据访问需求选择结构，再评估内存、并发和扩容代价

不要只背“大 O”

同为 O(1)，数组读取通常比链表节点访问更快，因为连续内存更有利于 CPU 缓存。同为 O(n)，顺序扫描数组也可能比频繁跳转指针的链表更高效。大 O 描述增长趋势，不代表具体耗时相同。

还要区分四种口径：

最坏复杂度：输入最不利时的上界。
平均复杂度：对输入分布作合理假设后的期望。
摊销复杂度：把偶尔发生的昂贵操作分摊到多次操作上。
空间复杂度：除元素本身外还需要多少额外空间。

ArrayList 扩容单次要复制 O(n) 个元素，但连续追加的摊销成本仍是 O(1)；HashMap 平均查找是 O(1)，但极端碰撞下并不是绝对常数时间。

从需求反推数据结构

选择结构时，可以按下面五步判断：

确定主键：调用方是拿整数下标、业务键，还是只关心处理顺序？
统计操作比例：读取、追加、中间插入、删除和遍历各占多少？
确认顺序要求：是否需要插入顺序、排序顺序或优先级顺序？
估算数据规模：几十条、几十万条和持续增长的数据，成本完全不同。
补充非功能约束：并发、内存上限、延迟尾部、持久化和故障恢复是否重要？

例如“根据用户 ID 获取资料，同时按最近访问顺序淘汰”，单一结构无法同时满足。哈希表负责 O(1) 定位，双向链表负责顺序调整，组合后才是 LRU。很多工程结构都不是发明了新节点，而是把基础结构按访问模式组合。

Java 集合与底层结构对应

业务意图	常用 Java 类型	底层思想
按索引读、尾部追加	`ArrayList`	动态数组
双端入队出队	`ArrayDeque`	环形动态数组
按键查找	`HashMap`	哈希桶 + 碰撞处理
保持插入/访问顺序	`LinkedHashMap`	哈希表 + 双向链表
按键有序	`TreeMap`	红黑树
按优先级取元素	`PriorityQueue`	二叉堆
并发键值访问	`ConcurrentHashMap`	分桶并发控制

接口类型也很重要。参数只需要遍历时声明为 Collection 或 Iterable，只需要队列语义时声明为 Queue，能减少调用方对具体实现的依赖。

复杂度分析的常见陷阱

忽略隐藏的定位成本

“链表插入 O(1)”必须说明插入位置是否已经拿到；“数组删除 O(n)”也要看是否允许与末尾交换、是否要求保持顺序。

忽略摊销峰值

动态数组和哈希表的日常操作很快，但扩容会复制或重排大量元素。平均吞吐可能很好，单次尾延迟却会抖动。对低延迟系统，应预分配容量或分批迁移。

忽略内存常数

链表每个节点包含对象头和引用，哈希表为低碰撞保留空桶，装箱集合又为基本类型创建对象。数据量达到千万级后，常数项会从细节变成容量问题。

忽略并发语义

单线程 O(1) 不代表并发下仍然便宜。锁竞争、内存可见性、扩容协作和迭代一致性都可能成为主成本。线程安全应该通过成熟容器和清晰所有权解决，而不是给每个方法随手加 synchronized。

一组贯穿本章的实践题

实现动态数组并记录每次扩容发生时的 size 与 capacity。
实现双向链表，随机执行插入删除后验证前后指针对称。
用环形数组实现固定容量队列，并覆盖索引回绕。
分别用栈和队列实现 DFS、BFS，观察访问顺序差异。
实现拉链哈希表，构造相同 hashCode 的键测试碰撞。
用 JMH 比较 ArrayList 与 LinkedList 的顺序遍历和按索引访问。

实践的验收标准不只是结果正确，还包括边界不变量、复杂度符合预期、异常语义明确，以及测试能主动构造最坏情况。

本章自测

为什么 ArrayList 尾部追加通常是 O(1)，却偶尔会变成 O(n)？
LinkedList 在什么前提下删除节点才是 O(1)？
为什么 Java 中实现栈通常优先选择 ArrayDeque，而不是旧的 Stack？
哈希碰撞为什么无法完全消除？
如果需要保持插入顺序并按键查询，你会怎样组合结构？