1. 为什么我把Java中的数据结构列进新人必修清单先把标题这五个字拆开说。java中的数据结构在大多数人印象里是面试八股HashMap 底层是什么、ArrayList 和 LinkedList 怎么选、红黑树什么时候退化。但真正落到项目里它决定的是一个接口能扛住多少并发、一个报表任务跑完要不要加班等结果。我之前带过一个刚从培训班出来的新人他写最近七天登录用户去重时直接用了两层循环里套 ArrayList.contains数据量到几万就开始卡。换成一个 HashSet代码量减少一半耗时从秒级降到十几毫秒。这就是数据结构在 Java 里的意义它不是背给面试官听的而是每天写 CRUD 时都在用的基础工具。这篇文章适合三类人一是刚开始学 Java想知道集合框架和课本里的数据结构怎么对应起来的人二是在准备 Java 面试题或者复习数据结构和算法想要一份能直接落地的 Java 视角笔记的人三是报了蓝桥杯、或者正在啃数据结构408、王道这类资料希望用 Java 把抽象概念写出来的同学。我尽量少说空话给原理也给代码最后还会聊一些只有真正写业务才会遇到的坑。1.1 会用、懂原理、能选型是三个不同层次很多人在Scanner 一个 List阶段就把数据结构学完了这是误区。第一层是会用接口知道 put、get、add、poll 分别做什么第二层是懂原理ArrayList 为什么扩容是 1.5 倍HashMap 为什么默认容量是 16负载因子为什么是 0.75第三层是能选型面对订单按时间倒序分页千万用户标签去重TopK 排行榜这类真实问题能说出该用 Deque、HashSet、PriorityQueue 中的哪一个并且能解释代价。这篇文章的章节就是按这三个层次来排的从集合框架地图到底层实现再到实战选型和刷题路线。1.2 从一次候选人面试看数据结构的价值有一次我面一个三年经验的 Java 工程师问了个业务场景题短信网关要维护每个手机号最近 5 分钟的发送记录超过 5 分钟自动淘汰你会怎么存。他想了半天说用 List然后每 5 分钟全量扫一遍删除。这个答案在数据量小的时候也能跑但明显没有把时间维度上的淘汰这个需求映射到数据结构上。其实这就是一个典型的 Deque 或者环形缓冲问题每来一条记录从尾部入队检查头部时间戳是否超时超时就从头部弹出。同样是这道题懂数据结构的人还会主动提并发版本用 ConcurrentLinkedDeque 或者加锁的 ArrayDeque。所以说数据结构在 Java 里不是孤立知识点它是把复杂业务需求翻译成高效代码的桥梁。2. 集合框架里藏着一张数据结构地图List、Set、Queue、Map 逐个对应JDK 的集合框架其实把教科书里大部分经典结构都封装好了。如果你手边有一本《数据结构与算法分析》或者《大话数据结构》会发现数组对应 ArrayList、链表对应 LinkedList、栈和双端队列对应 ArrayDeque、堆对应 PriorityQueue、哈希表对应 HashMap/HashSet、平衡二叉搜索树对应 TreeMap/TreeSet。把这张地图认全后面看源码和刷题都会轻松很多。2.1 List 体系动态数组和双向链表的真实差距ArrayList 底层是一个 Object[]不传容量时默认初始容量为 10满了之后扩容到原来的 1.5 倍并拷贝数组。随机访问是 O(1)尾部追加均摊也是 O(1)但中间插入或者删除需要移动后续元素是 O(n)。LinkedList 底层是双向链表每个节点有 prev 和 next 两个指针还有一个专门的 first/last 引用。头尾插入删除是 O(1)按下标 get(i) 却是 O(n)因为它要从头或尾一个个往后数。这里有个反直觉的点很多人在中间插入的场景会选 LinkedList理由是链表插入不用移动元素。实测下来不一定。ArrayList 的 System.arraycopy 是底层 native 内存拷贝对 CPU 缓存非常友好除非你需要在一个很长的列表中间疯狂插入几十万次否则大多数时候 ArrayList 反而更快。我见过有人为了理论上的 O(1)把 LinkedList 用得到处都是结果 GC 压力变大、内存翻倍最后又改回 ArrayList。LinkedList 真正的舒适区是频繁在头部操作或者实现队列/双端结构不过队列现在有更好的 ArrayDeque 可以选。再顺带提一句 Vector 和 Stack。它们出现在 JDK 1.0方法加了 synchronized线程安全但性能差新代码基本不推荐。Stack 用 Vector 实现的同步栈日常要栈结构的话更推荐 ArrayDeque。2.2 Set 体系三种去重思路HashSet 底层就是 HashMap只用了 key 那一列value 是一个固定的虚值。它无序、去重、contains 平均 O(1)。LinkedHashSet 在 HashSet 基础上额外维护了一条双向链表记录插入顺序所以遍历顺序和插入顺序一致代价是每个元素多两个指针的内存。TreeSet 底层是红黑树元素按自然顺序或者你传入的 Comparator 排序增删查都是 O(log n)适合需要有序集合的场景比如取最小元素或者找出比某个值大的第一个元素。2.3 Queue 和 Deque队列、栈、双端操作一次说清Queue 是 FIFO 队列接口Deque 是双端队列接口。ArrayDeque 用循环数组实现头尾插入删除都是 O(1)不允许放 null可以当队列用 addLast/pollFirst也可以当栈用 push/pop实际性能比 Stack 好。LinkedList 虽然也实现了 Deque但它每个节点有额外指针内存占用高双端操作不如 ArrayDeque 快。PriorityQueue 是二叉堆底层是一个数组默认是最小堆offer/poll 的时间复杂度是 O(log n)适合做定时任务按时间戳排序、TopK 这类问题。2.4 Map 体系先记住四张核心表HashMap 是哈希表平均 O(1)。TreeMap 是红黑树支持按照 key 做范围查询。LinkedHashMap 在哈希表基础上维护插入顺序或者访问顺序访问顺序模式下可以轻松实现 LRU 缓存。ConcurrentHashMap 是并发安全版本后面单独讲。这四张表的底层结构分别是数组链表红黑树、红黑树、哈希表双向链表、数组链表红黑树配上 CAS 和 synchronized刚入门先记住这张表就够了接口实现类底层结构平均复杂度典型场景ListArrayList动态数组get O(1)尾插均摊 O(1)随机访问、存列表数据ListLinkedList双向链表首尾增删 O(1)get O(n)频繁头尾操作但可用ArrayDeque替代SetHashSet哈希表contains O(1)去重、判存在SetTreeSet红黑树O(log n)有序集合、范围操作QueueArrayDeque循环数组头尾操作 O(1)栈、队列、滑动窗口QueuePriorityQueue二叉堆offer/poll O(log n)优先队列、TopKMapHashMap数组链表红黑树get/put O(1)键值映射MapTreeMap红黑树O(log n)有序键、范围查询MapLinkedHashMap哈希表双向链表O(1)LRU、保持插入顺序3. HashMap、TreeMap、ConcurrentHashMap 的底层结构高频面试题的真正考点如果只让我给别人讲一件关于 Java 数据结构的事我会选 HashMap。因为它融合了数组、链表、哈希、树是理解 Java 数据结构的一把钥匙。3.1 HashMap 的 put 流程一次读懂下标计算、冲突、扩容先看下标怎么定。HashMap 不是直接用 hashCode而是先做一次扰动(h key.hashCode()) ^ (h 16)把高 16 位的信息也混到低位减少哈希碰撞。然后因为容量 n 总是 2 的幂所以用(n - 1) hash定位桶下标不用取模位运算更快。为什么容量必须是 2 的幂因为n - 1的二进制是全 1正好可以当掩码。put 的时候如果桶为空就直接放不为空就发生冲突JDK 8 之后新节点采用尾插法挂在链表尾部。当同一个桶里的链表长度大于等于 8并且数组长度达到 64链表会转成红黑树把查找从 O(n) 降到 O(log n)。为什么是 8源码注释里给了泊松分布的计算在负载因子 0.75 且哈希均匀的情况下一个桶里出现 8 个节点的概率已经小到约千万分之一选 8 是为了防止普通情况下链表够用了但哈希被恶意攻击时还能兜底。如果后续 resize 把树节点拆散了长度小于等于 6 又会退化成链表。中间留了 7 的缓冲避免频繁在树和链表之间跳来跳去。扩容发生在元素个数超过容量 * 0.75时容量翻倍所有节点重新计算桶位。因为新容量是原来的 2 倍节点要么留在原索引要么去原索引旧容量的位置JDK 8 直接利用这个特性拆链表效率很高。实际使用时候选容量要考虑到 0.75 的负载因子比如你预估要放 1000 个元素直接new HashMap(1000 / 0.75 1)就能把扩容次数降到最少。3.2 TreeMap 的红黑树和有序性TreeMap 的核心价值不是 O(log n) 的查找而是有序。它支持 floorKey、ceilingKey、subMap 这类范围查询这在做区间统计、日程表、版本区间判断时非常有用。比如要查某个时间戳落在哪条价格策略里把策略的生效时间作为 key 放进 TreeMap用 floorEntry 一次就能定位。红黑树是一种自平衡的二叉搜索树从根到叶子的最长路径不超过最短路径的两倍所以增删查都能维持在 O(log n)。这里要提醒一句TreeMap 的 key 要么实现了 Comparable要么你在构造时传入 Comparator否则 put 会抛 ClassCastException。它默认也不允许 key 为 null。3.3 ConcurrentHashMap并发读写下不用怕的哈希表单线程用 HashMap多线程只读也用 HashMap但只要有写并发HashMap 会出问题。JDK 7 的老问题包括多线程扩容时链表成环、数据丢失面试里常被问到的HashMap 死循环就是那个时期的产物。JDK 8 的 ConcurrentHashMap 放弃了分段锁改成对桶数组的每个桶单独加锁。插入时如果桶为空用 CAS 无锁插入桶不为空再 synchronized 锁住这个桶的头节点然后走链表或红黑树逻辑。读操作几乎不加锁因为 Node 的 key 和 hash 用 final 修饰value 和 next 用 volatile 修饰可见性有保证。size() 也不再是遍历整个表数一次而是维护 baseCount 加 CounterCell 数组来减少竞争。理解了这些再去看相关源码会顺畅很多面试题问ConcurrentHashMap 怎么保证线程安全也就能答出 CAS、synchronized、volatile 三个关键点了。4. 从图和数组、双端队列、排序这些热词看算法题的 Java 落地数据结构408图和数组、双端队列、冒泡排序java、蓝桥杯数字题目这些搜索热词说明很多人不是在学理论而是要在考试和竞赛里动手写代码。Java 写算法题的体验其实不错集合框架和库函数能省掉大量体力活关键是知道每个结构怎么落地。4.1 二叉树在 Java 里的标准写法与三种遍历刷题时树节点的定义一般是这样的类public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }前序遍历就是先访问当前节点再递归左子树、右子树。中序、后序只是换一下递归顺序。层序遍历要用队列每次把当前层的节点取出再孩子入队。这套模板在蓝桥杯和面试算法题里反复出现建议默写。递归的时候要注意返回条件和避免重复入队不然容易栈溢出或者死循环。4.2 图的邻接矩阵和邻接表以及 DFS/BFS 怎么选图的存法有两种主流。邻接矩阵用int[][]适合点少、边多的情况判断两点是否相连是 O(1)但空间 O(n^2)。邻接表用ListInteger[]或者Listint[]适合点多、边少的大部分竞赛题和真实业务比如社交关系、路由拓扑。带权图可以把邻接表每一项存成int[] {邻居, 权重}。DFS 适合找路径、判断连通、回溯BFS 适合找最短步数、层序遍历。DFS 在 Java 里可以递归也可以自己用 ArrayDeque 模拟栈。BFS 一定要用队列并且要在入队时标记 visited否则会重复访问同一个节点指数级膨胀。4.3 ArrayDeque 在算法题里的两种身份很多新手写栈用 Stack写队列用 LinkedList遇到双端队列再去找别的类。其实 ArrayDeque 一个就够用。当栈用push 入栈、pop 出栈、peek 看栈顶。当双端队列用addLast、pollFirst、addFirst、pollLast。最典型的是滑动窗口最大值这种题需要维护一个单调队列用 ArrayDeque 存下标头部放最大值候选每次新元素入队前先把队尾比它小的全部弹出。这类题在热词里对应双端队列在面试里出现的频率也很高。4.4 排序算法自己写和库函数调用要分开手写冒泡排序是很多入门教程第一课也是蓝桥杯和期末复习的常客public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } if (!swapped) break; } }加了 swapped 标志之后最好情况能优化到 O(n)。不过工程里一般不会自己写排序Arrays.sort 对基本类型数组用的是双轴快速排序平均 O(n log n)对对象数组用的是 TimSort它是稳定排序。为什么同样一个 sort 分两种实现因为基本类型不需要稳定性快排更快对象排序往往希望相等元素的相对顺序保持TimSort 更合适。这些细节在面试里如果主动提出来是很加分的点。5. 真实开发里的数据结构选型三个场景和一堆踩过的坑把集合框架和底层原理都过完之后最值钱的是知道在业务里怎么选型。这一章我按自己的经验给几个可以直接抄的答案。5.1 三个高频业务场景的推荐方案场景一某接口要统计最近 1 小时内访问量 Top10 的页面。最粗暴的做法是全部塞进 List 排序但每个请求都全排一遍很浪费。正确思路是用固定大小为 10 的 PriorityQueue 维护最小堆堆顶是当前第 10 名新元素如果比堆顶大就替换堆顶并重新堆化。时间复杂度从 O(n log n) 降到 O(n log 10)数据量大时差别巨大。场景二需要给用户展示最近浏览的 20 条商品记录新的顶掉旧的。用 ArrayDeque 当双端队列新记录从头部压入超过 20 就弹掉尾部。配合数据库或者 Redis 来做持久化内存里只留热点。场景三实现一个简单 LRU 缓存不让热点数据被淘汰。Java 里最轻量的写法是继承 LinkedHashMap覆写 removeEldestEntryclass LRUCache extends LinkedHashMapString, String { private final int capacity; LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryString, String eldest) { return size() capacity; } }第三个参数传 true 表示按访问顺序维护链表每次 get 会把节点移到尾部头部自然就是最久没被访问的数据。这个方案比手动维护双向链表简单得多也是面试里经常要默写的一道题。5.2 常见踩坑点迭代中修改、HashMap 扩容、null 与默认值第一个坑是 for-each 遍历时调用 remove抓到 ConcurrentModificationException。原因是集合内部维护了一个 modCount迭代器会校验它是否变化。正确的删除方式是 Iterator.remove() 或者 list.removeIf(...)。第二个坑是拿 HashMap 当并发容器。本地环境数据量小可能一直不报错一到生产流量上来就丢数据。多线程写入一定要换 ConcurrentHashMap。第三个坑是 Map 的 key 如果是一个可变对象改完对象字段后 hashCode 变了原来的 value 就永远找不到了。所以 key 要么用不可变对象要么重写 hashCode 时只用稳定字段。第四个坑是 PriorityQueue 的迭代器不保证有序只有 poll 才能按优先级出队很多人直接 for-each 打印发现顺序不对就开始怀疑 JDK。5.3 内存占用和 GC 视角的补充建议数组是一段连续内存访问快、对象头开销小链表每个节点都有至少两个引用的额外开销。Java 里对象本身有对象头链表的节点对象更多长链表还会让 GC 遍历引用链更慢。所以在能预估大小、又不频繁增删的列表场景下优先 ArrayList频繁在头部插入、但要控制内存时优先 ArrayDeque 而不是 LinkedList。批量插入前记得给 ArrayList 和 HashMap 设置初始容量这能减少扩容时的数组拷贝和重哈希在高并发接口里省下的时间很可观。6. 求职、考研、蓝桥杯三条路上的补充路线这篇聊到这里最后按目标人群给一条可执行的路线方便你按自己的方向继续深入。6.1 面向 Java 面试源码、八股、刷题三件套面试准备的关键不是背八股而是把八股变成对源码的理解。建议按顺序读 ArrayList、HashMap、ConcurrentHashMap、PriorityQueue 的源码过程中重点看扩容倍数、负载因子、红黑树阈值、null 策略这几个点。LeetCode 按专题刷数组、哈希表、链表、栈与队列、二叉树、图、堆每个专题先刷 10 道基础题再刷 5 道进阶题。遇到题先写暴力解再分析瓶颈再换数据结构优化这个思考过程本身就是面试官想看的。6.2 面向考研和 408用 Java 把理论题敲一遍王道和天勤的资料上有很多伪代码很多人觉得看了就是会了结果一写就废。建议每看完一章就用 Java 把核心操作实现一次链表反转、栈模拟队列、循环队列、二叉树的先中后序和层序、二叉排序树插入删除、图的邻接表构建、DFS/BFS、最小生成树和单源最短路径。复杂度推导还是要在纸上手写Java 代码是辅助理解不是替代理论。6.3 面向蓝桥杯和竞赛模板和输入输出的提速细节竞赛里数据结构本身不复杂复杂的是时间限制和输入输出。Scanner 在数据量大时很慢可以换 BufferedReader 加自写的 int 读取或者用 PrintWriter 输出。栈和队列直接用 ArrayDeque排序用 Arrays.sort堆用 PriorityQueue。常见模板比如并查集、树状数组、线段树、字典树建议提前整理成自己的代码库赛前多默写几遍比临场推导可靠得多。蓝桥杯的题目往往会把数据结构藏在题目背景里比如数字操作类题目很多就是栈和哈希表的组合第一步永远是先识别数据特征。我个人现在带项目还有一个习惯写任何集合操作之前先问自己一句这里的数据规模是多少读写比例是多少要不要保证有序。想出答案再动笔基本就不会写出只能用在小数据量上的代码了。数据结构这门课在大学里学分不低在 Java 世界里却是每天都要用的一日三餐。与其刷几十遍八股不如真正理解一遍源码然后在业务里挨个用起来你会发现那些曾经绕不过去的面试题突然就变成了常识。