数据结构这块内容我一直觉得是Java工程师最容易跳过去的功课。平时写业务代码ArrayList拿来就addHashMap拿来就put等真正面对java面试题、蓝桥杯这类算法竞赛题或者线上接口突然变慢要定位性能瓶颈的时候根基不牢的人往往第一个卡住。我这些年带项目、面人、带新人反反复复绕回这些最基础的知识上索性沉淀了一套完整的Java核心数据结构笔记也就是你现在看到的这篇内容。这篇笔记不是什么教科书式的理论搬运而是从Java集合框架怎么用、底层怎么实现、实际项目里怎么选型、面试题怎么答四个维度展开数组、链表、栈、队列、哈希表、树、堆、图再到排序算法全部串起来讲。目标是让准备java面试题的人有的放矢让刷蓝桥杯的同学有模板可抄让日常写Spring Boot业务代码的工程师真正理解手里的集合工具。1. 为什么Java工程师必须吃透数据结构1.1 集合框架就是数据结构的包装壳很多人学Java基础背得最熟的往往是List有序、Set唯一、Map存键值对但面试一问HashMap为什么用红黑树ArrayList扩容为什么是1.5倍就答不上来了。问题出在把集合框架当成了API字典而不是数据结构教材。实际上Java集合框架就是一套面向对象封装好的数据结构库。ArrayList对应动态数组LinkedList对应双向链表ArrayDeque对应环形数组双端队列HashMap对应哈希表数组加链表或红黑树TreeMap对应红黑树PriorityQueue对应二叉堆。理解这一点你就不会把集合框架和数据结构当成两门课。这种封装对开发者的意义很大底层的扩容、碰撞、树化这些细节全部藏在源代码里你只需要调用add、put这些方法。可一旦出了问题——性能变慢、内存暴涨、并发数据错乱——你得能绕过封装看到底下的结构。这也是为什么大厂java面试题几乎都绕着集合框架的底层原理出。1.2 选错结构再好的算法也救不回来我见过太多实现没问题、性能一塌糊涂的代码。最典型的例子就是在ArrayList上做contains查询数据量一上来接口直接退化。这不是算法的问题是数据结构选型的失误。这里给一张我平时带新人时必讲的性能对照表操作ArrayListLinkedList随机访问 get(i)O(1)O(n)尾部 addO(1) 摊还O(1)头部 addFirstO(n)O(1)中部插入 add(i,e)O(n)O(n)遍历缓存友好缓存不友好很多人只知道LinkedList插入快却忽略了一点这个快只在头部插入时成立。中部插入两边都要先找位置复杂度都是O(n)。而且链表节点在内存里分散存放每次访问下一个节点都可能触发一次缓存未命中。我实测过100万元素尾部追加ArrayList清空重扩容也比LinkedList快不少所谓插入快在大量数据下经常是个错觉。结论是选数据结构时先看主操作是什么。高频随机访问选数组类高频只动两端选ArrayDeque需要频繁按key查询选HashMap需要有序加范围查询选TreeMap。顺序反了后面再优化都是徒劳。2. 数组与链表线性存储的两条路线2.1 ArrayList扩容的细节与假装很快的优化ArrayList的源码我建议每个Java工程师都亲手读一遍。它的底层就是一个Object数组创建空列表时用的是共享的DEFAULTCAPACITY_EMPTY_ELEMENTDATA第一次add才把容量撑到默认的10。核心扩容逻辑是这样的private Object[] grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5倍 if (newCapacity - minCapacity 0) { newCapacity minCapacity; } return Arrays.copyOf(elementData, newCapacity); }扩容倍数不是两倍而是1.5倍官方注释写得很清楚往2倍靠可能浪费大量内存往1.5倍靠能在扩容次数和空间利用率中间取平衡。扩容本身是System.arraycopy的native方法性能不差但频繁扩容会把O(1)的尾部add拖成O(n)摊还成本更高的操作。所以写代码时如果你能预判数据量直接给初始容量ListInteger list new ArrayList(100_000); int[] arr new int[100_000];这点在蓝桥杯这类算法题里尤其重要数组已知范围直接开满不要靠ArrayList反复扩容。另外还要注意一个高频报错数组只有10个元素你非要访问第11个原始数组会抛ArrayIndexOutOfBoundsExceptionArrayList的get方法则会抛IndexOutOfBoundsException。很多新人分不清这两者其实根因都是下标越界。ArrayList的get(i)本身是O(1)编译器或JIT会做边界检查消除不用太担心遍历性能真正要警惕的是边遍历边删除导致的java.util.ConcurrentModificationException后面第七节我会专门讲。2.2 LinkedList的节点设计与双端优势LinkedList的底层是内部类Node每个节点存三个东西当前元素、前驱引用、后继引用组成双向链表。private static class NodeE { E item; NodeE next; NodeE prev; }这个结构决定了它的优势场景很窄只在首尾增删是O(1)。Java 8之后的LinkedList额外实现了Deque接口所以可以当双端队列用。但要注意get(int index)的实现是二分式查找先判断index靠近头部还是尾部最坏还要遍历n/2个节点复杂度O(n)。我在实际项目里几乎不在大列表上用LinkedList。原因不光是缓存不友好还有一个容易被忽略的点每个节点都是一个独立对象100万个节点就是100多万个对象GC压力远高于连续数组。之前有个同事把百万级列表换成LinkedList做尾部追加结果内存占用翻了一倍还多换回ArrayList之后问题消失。如果你确实需要双端操作更好的选择是ArrayDeque底层是环形数组首尾增删O(1)内存也更紧凑。LinkedList的正确用途我认为更多是教学演示和需要实现Deque语义且无法预判容量的场景。2.3 一个小数据题判断字符串中的字母与数字很多蓝桥杯或Java基础题会撞到判断字符串中是否不是字母和数字这种需求看起来简单写起来容易踩坑。比如要求过滤掉输入里的非数字字符常见错法是先拿到字符再和a到z挨个比较那是O(26n)的写法没必要。正确姿势是用Character工具类public static boolean isAlphanumeric(String s) { if (s null || s.isEmpty()) { return false; } for (int i 0; i s.length(); i) { char c s.charAt(i); if (!Character.isLetterOrDigit(c)) { return false; } } return true; }charAt(i)对Java字符串是O(1)的随机访问Character.isLetterOrDigit内部用查表法判断字符类型一次就能定位。这个写法的好处是把字符串当作字符数组处理逻辑清晰也避免了正则表达式在简单规则下的性能损耗。小题目里藏着效率差异这也是为什么我会把这类细节写进数据结构笔记里。3. 栈与队列受限线性结构的场景与应用3.1 Stack已过时ArrayDeque才是正主提起栈很多人第一反应是java.util.Stack。但这个类继承自Vector所有方法都带synchronized锁属于遗留类官方注释都建议不要再用了。正确做法是用ArrayDeque充当栈DequeInteger stack new ArrayDeque(); stack.push(1); stack.push(2); int top stack.peek(); // 2不弹出 int x stack.pop(); // 2弹出ArrayDeque底层是一个环形数组head和tail两个指针在数组里转圈走逻辑上无限循环物理上扩容时整体搬移。所以它的push、pop、peek平均都是O(1)且没有同步开销。栈的经典场景我列一下括号匹配、表达式求值中缀转后缀、函数调用栈的模拟、DFS的显式写法、编辑器的撤销操作。蓝桥杯里有个高频题型叫迷宫/图的遍历很多用递归写的DFS在大数据量下爆栈改成栈visited数组的显式DFS就能稳定通过。我建议每个刷题的人掌握这种写法下面这个模板适用于绝大多数网格类题目Dequeint[] stack new ArrayDeque(); boolean[][] visited new boolean[m][n]; stack.push(new int[]{sx, sy}); visited[sx][sy] true; while (!stack.isEmpty()) { int[] cur stack.pop(); for (int[] dir : dirs) { int nx cur[0] dir[0]; int ny cur[1] dir[1]; if (nx 0 || nx m || ny 0 || ny n || visited[nx][ny]) { continue; } visited[nx][ny] true; stack.push(new int[]{nx, ny}); } }3.2 队列家族Queue接口、ArrayDeque与PriorityQueue队列的使用频率不亚于栈但要分清楚几个接口的语义。Queue接口定义了三组方法add/offer、remove/poll、element/peek区别在于队列已满或为空时的行为——add、remove、element在容量受限或为空时抛异常offer、poll、peek则返回false或null。操作组失败行为方法入队抛异常add(e)入队返回falseoffer(e)出队抛异常remove()出队返回nullpoll()查看队首抛异常element()查看队首返回nullpeek()实现类常见的就几个ArrayDeque非阻塞、不允许null、LinkedList也可以当队列用但不推荐、PriorityQueue按优先级出队、DelayQueue延迟出队。如果是消息队列、BFS这类普通场景直接ArrayDeque不要用LinkedList。BFS标准模板用队列实现以岛屿数量这类二维网格题为例每到一个可走的格子就入队出队时扩展四个方向。这套模板配合boolean[][]标记是蓝桥杯省赛的常客务必写到肌肉记忆里。3.3 定时任务框架里的优先队列思维聊到java定时任务框架很多人想到的是Spring的Scheduled或XXL-JOB但它们的底层调度模型里都会用按执行时间排序的最小堆来组织任务。这个最小堆在Java里就是PriorityQueue的变体比如DelayQueue内部就维护了一个优先队列每次取出的都是到期时间最早的任务。理解这个底层逻辑你就能解释一个常见现象同一个时刻注册了一堆定时任务调度器不是全部扫描一遍再执行而是每次O(log n)取出堆顶的最近到期任务。堆的插入和删除都是O(log n)比每次全量扫描的O(n)高效太多。如果你的项目需要自己实现一个简单的延迟任务队列优先级可以这样用PriorityQueueTask pq new PriorityQueue(Comparator.comparingLong(Task::getRunAt)); pq.offer(new Task(1000L, () - System.out.println(task))); while (true) { Task task pq.poll(); if (task null) break; long wait task.getRunAt() - System.currentTimeMillis(); if (wait 0) Thread.sleep(wait); task.getRunnable().run(); }这段代码串起了数据结构在真实框架里的价值数据结构的选型决定了调度系统的复杂度上限。这是面试里你用过哪些数据结构一类问题的进阶答法。4. 哈希表HashMap底层机制与高频面试题4.1 put流程里藏着三个精巧设计HashMap可以说是java面试题里占比最高的一类没有之一。它也是我建议每位工程师精读源码的第一个集合类。put一个键值对时走的路径是算hash定位桶下标处理冲突必要时树化最后判断要不要扩容。三个设计点非常关键第一个hash函数static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这里把hashCode的高16位异或到低16位是为了让散列均匀。因为HashMap定位桶用的是(n - 1) hash当数组长度n比较小时比如默认16起作用的基本只有低4位高位信息全部浪费了。异或之后高位变化也能影响低位冲突概率明显下降。第二个为什么容量必须是2的幂。因为只有n是2的幂hash % n才能等价于(n - 1) hash。位运算比取模快得多而且(n - 1)的低位全为1可以尽量散列均匀。如果你用new HashMap(20)构造函数会帮你把容量抬到最近的2的幂也就是32。第三个树化条件。当链表长度超过8且数组长度达到64时链表转红黑树如果数组长度不到64则先扩容。为什么阈值是8源码注释里给了泊松分布计算在负载因子0.75、hash分布理想的情况下一个桶里链表长度达到8的概率大约是一千万分之六属于几乎不可能出现的case。一旦真出现了基本可以断定hashCode设计得很糟糕或者被人为构造了碰撞。4.2 扩容、负载因子与数据一致性HashMap默认初始容量16负载因子0.75扩容阈值是capacity * loadFactor也就是12。当size超过阈值数组翻倍到32然后一个个重新计算位置。Java 8做了个很漂亮的优化扩容时不用重新算hash因为新下标要么是原来的位置要么是原位置旧容量。判断依据是看hash oldCap这一位是0还是1。0就留在原位1就挪到oldIndex oldCap。这个优化让扩容的常数显著变小也顺便解决了Java 7里扩容时链表成环的恶性bug。但注意这不等于HashMap线程安全。并发put时两个线程可能同时往同一个桶里写后写的覆盖先写的数据丢失迭代时其他线程修改结构还会抛ConcurrentModificationException。这就是面试里常问的HashMap为什么线程不安全、java怎么保证数据一致性的答案起点。要在并发场景用哈希表首选ConcurrentHashMap。Java 8之后的实现用CAS加synchronized锁桶头节点锁粒度比Java 7的分段锁更细。更重要的是它提供了原子方法比如check-then-act场景要写成ConcurrentHashMapString, Object cache new ConcurrentHashMap(); Object value cache.computeIfAbsent(key, k - loadFromDb(k));如果先containsKey再get再put三行代码之间就可能被其他线程插入数据导致覆盖。用computeIfAbsent一步到位能避免这类数据一致性问题。4.3 自定义Key的散列设计HashMap的散列依赖key的hashCode和equals。这两个方法必须遵守同一个约定equals相等的对象hashCode必须相等否则同一个key插入两次都落在不同桶里查不到数据。这条规则是面试题里的送分题也是实际开发里巨多的隐藏bug来源。更隐蔽的问题是用可变对象当key。比如你用一个User对象当key插入时根据其id算hash随后修改了id再get就找不到原来的值了——因为hashCode变了桶搬了家却没人把对象挪过去。所以自定义key时字段尽量不可变或者复写hashCode/equals时只用不可变字段。优先用String、Integer、Long这类不可变包装类型作为Map的key。别在放入Map之后修改会影响散列值的字段。这里再补一个跟多租户/行级权限沾边的实践很多Spring Boot MyBatis的项目里行级权限控制需要为每个用户缓存其可见的组织或数据范围很多人朴素地用MapLong, ListLong但权限查询频繁时list里的contains又成了O(n)。把可见范围改成MapLong, SetLong查询一下从O(n)变O(1)提速立竿见影。这类小结构换大性能的操作正是数据结构的价值所在。4.4 用Map在O(n)内组装树形结构说到树形结构很多人的第一反应是先写个递归逐层建树。但如果你手头是一批扁平数据每条数据带parentId用HashMap做一次遍历就能建好整棵树不用递归也不用O(n^2)。MapInteger, TreeNode index new HashMap(); ListTreeNode roots new ArrayList(); for (DeptDTO dto : list) { TreeNode node index.computeIfAbsent(dto.getId(), TreeNode::new); node.setLabel(dto.getName()); TreeNode parent index.computeIfAbsent(dto.getParentId(), TreeNode::new); parent.getChildren().add(node); if (dto.getParentId() null || dto.getParentId() 0) { roots.add(node); } }这段代码的核心是computeIfAbsent每个节点保证只会被new一次父节点和子节点通过map互相引用整棵树在一次遍历里挂完。时间复杂度从递归写法的O(n^2)降到O(n)。菜单权限树、部门树、多商户商城的组织树用这个方案都稳。5. 树与堆有序世界里的平衡之道5.1 二叉搜索树为什么需要自平衡二叉搜索树BST的定义很简单左子树所有节点小于根右子树所有节点大于根。查找一个值的过程就是沿着树往下走理想情况下高度是log n查找O(log n)。但BST有个致命弱点如果插入序列是有序的比如1、2、3、4、5树会退化成一条链表高度变成n所有操作退化成O(n)。红黑树就是解决这个问题的方案之一。它给每个节点染色通过几条性质把树的高度控制在大约2倍log n以内保证任何操作的路径长度差不多。性质简单记根黑、红节点不能有红孩子、从任意节点到叶子经过的黑节点数相同。这样最长路径也只是最短路径的两倍不会出现链表式的退化。Java里的TreeMap、TreeSet都是红黑树实现所以它们的put、get、remove是O(log n)。面试题HashMap和TreeMap怎么选的答案也因此清晰不需要有序就HashMap需要按键有序遍历、按范围查询就用TreeMap。5.2 TreeMap的区间查询能力TreeMap除了常规的get/put/remove还有几个很好用的区间方法floorKey(k)返回小于等于k的最大键ceilingKey(k)返回大于等于k的最小键lowerKey和higherKey对应严格版本。这些方法底层就是沿着红黑树找节点O(log n)。举一个实际场景你有一个价格区间配置比如满100减10、满200减30要给用户发放对应优惠券就可以把门槛存进TreeMap用floorKey找到用户订单金额对应的最大门槛再取出配置TreeMapInteger, String rules new TreeMap(); rules.put(100, 减10券); rules.put(200, 减30券); rules.put(500, 减80券); Map.EntryInteger, String rule rules.floorEntry(230); // 找到 200 - 减30券这类最近邻查询问题是TreeMap的看家本领也是HashMap无法直接替代的。刷题时如果遇到给一个数组求每个数左侧小于它的最大值之类的题目TreeMap往往能派上用场。5.3 PriorityQueue堆序不是有序很多人以为PriorityQueue用了一个能自动排序的队列取出来就是有序的。这是个常见误解。PriorityQueue底层是二叉堆用数组存储父节点下标i左右孩子在2i1和2i2它只保证堆顶是最小值默认最小堆并不保证全队列有序。你如果要按顺序取唯一正确的做法是循环pollPriorityQueueInteger pq new PriorityQueue(); pq.offer(5); pq.offer(1); pq.offer(3); while (!pq.isEmpty()) { System.out.println(pq.poll()); // 1 3 5 }直接把PQ的迭代器转成列表顺序可能是乱的这是一个非常容易在蓝桥杯或项目里踩的坑。PriorityQueue经典应用之一是求Top-K。求前K个最大元素用大小为K的最小堆堆顶永远是当前K个里最小的那个新元素如果比堆顶大就替换一趟下来堆里就是前K大。代码public ListInteger topK(int[] nums, int k) { PriorityQueueInteger heap new PriorityQueue(); for (int num : nums) { if (heap.size() k) { heap.offer(num); } else if (num heap.peek()) { heap.poll(); heap.offer(num); } } return new ArrayList(heap); }为什么用最小堆而不是最大堆因为你要淘汰的是当前最小的堆顶就是最小的O(1)就能决策。这是一种很典型的反直觉但正确的数据结构设计牢记这个思路。6. 图与排序蓝桥杯和面试的临场工具箱6.1 图的两种存储与BFS/DFS模板图的存储方式主要看顶点数和密度。邻接矩阵用一个二维布尔或整型数组存顶点间关系简单直观但空间是O(V^2)V到几千就受不了。邻接表用ListListInteger或ListInteger[]每个顶点存一份邻居列表空间O(VE)是刷题和工程里的默认选项。BFS模板很固定我把它变成肌肉记忆boolean[] visited new boolean[n]; DequeInteger queue new ArrayDeque(); queue.offer(start); visited[start] true; while (!queue.isEmpty()) { int cur queue.poll(); for (int next : adj[cur]) { if (!visited[next]) { visited[next] true; queue.offer(next); } } }关键细节是在一个节点入队的那一刻立即标记visited而不是出队时才标记。否则同一个节点可能被多个邻居同时入队产生重复和错误。这句话我在带新人时重复了不下十遍。DFS用递归简单用栈也可以避免爆栈。蓝桥杯的省赛题里DFS往往配合回溯解决排列组合、岛屿数量、连通块个数等问题。掌握两套模板再根据题目改改条件就行。6.2 常见排序算法的Java实现排序是java面试题和蓝桥杯的常客。冒泡排序是入门第一课代码最朴素我把它当作判断有没有理解交换的标准public void bubbleSort(int[] a) { int n a.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; swapped true; } } if (!swapped) { break; // 本轮没交换整体已有序 } } }快速排序是另一个常考手写题我更喜欢写这个既不容易越界又避免最坏情况的版本void quickSort(int[] a, int l, int r) { if (l r) return; int i l, j r, pivot a[l ((r - l) 1)]; while (i j) { while (a[i] pivot) i; while (a[j] pivot) j--; if (i j) { int t a[i]; a[i] a[j]; a[j] t; i; j--; } } quickSort(a, l, j); quickSort(a, i, r); }这里选中间值作为pivot避免了对近乎有序数组退化为O(n^2)的最坏情况。稳定性和是否原地也是面试常考冒泡、插入、归并稳定快排、堆排、选择不稳定。Arrays.sort内部对基本类型用双轴快排对对象类型用TimSort归并排序的改进这点知道即可不用手写。6.3 数字题里的溢出陷阱蓝桥杯的数字题目和日常开发里最容易被忽略的一件事是int溢出。两个200000相乘再赋给int结果是负数因为int只有32位溢出位被丢弃。有一年省赛题很多人就是这么翻的车。最简单的原则是可能乘积或累加超过20亿的场景一律用long。判断两个int相加是否溢出也有标准写法if (a Integer.MAX_VALUE - b) { // 溢出 } if (a Integer.MIN_VALUE - b) { // 下溢 }另外要注意Math.abs(Integer.MIN_VALUE)还是负数因为绝对值超界。这类细节在算法题上都是高频坑我把它们列进笔记就是提醒自己写算法题时先检查数据类型再写核心逻辑。7. 高频面试题速查与排坑实录7.1 面试题与解析对照表把Java核心数据结构相关的面试题整理成一张表平时复习效率高很多面试题核心答案HashMap容量为什么是2的幂(n-1)hash可替代取模且分布更均匀为什么重写equals必须重写hashCodeHashMap/HashSet按hashCode找桶equals判断桶内相等违反约定查不到HashSet如何保证元素不重复先比较hashCode再比较equals都相同视为重复ArrayList和LinkedList谁更适合插入头部插入LinkedList O(1)其余场景ArrayList通常更快缓存友好HashMap和Hashtable区别Hashtable加锁、不允许null键值已过时并发用ConcurrentHashMapTreeMap和HashMap怎么选需要按key有序或范围查询用TreeMap否则HashMapPriorityQueue取出的顺序只有poll才保证从小到大遍历无序红黑树比普通BST好在哪里自平衡高度O(log n)避免退化成链表每次面到Java集合这块把表中每一行展开讲两三分钟基本就能覆盖面试官的连环追问。最重要的是别背答案要能顺着源码讲出为什么。7.2 我踩过的三个经典坑第一个坑是用ArrayList做高频率contains查询。有一次线上活动热点商品ID列表几千个代码里每次请求都走list.contains(id)QPS一上来接口直接熔断。排查后把热点ID放到HashSet里查询从O(n)变成O(1)接口耗时从平均120ms降到8ms。这不是算法问题是用错数据结构的问题。第二个坑是用LinkedList做队列。我曾在读写两端都比较频繁的地方图省事直接new了一个LinkedList当FIFO用。数据量到80万的时候GC开销明显变大队列节点对象太多。换成ArrayDeque后内存和耗时都降下来了。教训是默认用ArrayList和ArrayDeque除非你有明确的、经过验证的理由选LinkedList。第三个坑是for循环里一边遍历一边remove。这段代码看着没问题运行时直接抛java.util.ConcurrentModificationExceptionfor (String s : list) { if (s.length() 3) { list.remove(s); // 错 } }正确做法是用Iterator的remove或者用removeIf一行解决list.removeIf(s - s.length() 3);removeIf底层是Iterator加写时检查既安全又简洁。7.3 用主操作反推最优结构最后分享一个我自己总结的决策方法拿到任何一个需要存数据的需求不要急着new集合先列主操作。主操作是按下标访问选数组或ArrayList。主操作是增删首尾选ArrayDeque。主操作是按key查值选HashMap。需要key有序遍历、求floor/ceiling选TreeMap。需要按优先级取最小或最大选PriorityQueue。需要去重加判存在选HashSet。需要缓存且并发读写选ConcurrentHashMap配合computeIfAbsent。把这个列表背下来几乎所有日常场景和面试题都不慌。数据结构不是八股它是你写每一行代码时都在做的隐式决策。把这些笔记吃透再看ArrayList、HashMap、LinkedList这些源码你会有一种原来它们的设计就是这么来的的通透感。我个人带新人时最后总会补充一句刷算法题初期先对着源码写集合用法中期尝试徒手实现一遍ArrayList和HashMap的put/get逻辑后期你会发现面试题里的为什么其实只是这些代码的注释和注释背后的取舍。这套Java核心数据结构笔记如果真的帮你在面试或蓝桥杯上多拿几分那我这几年的踩坑记录就没白折腾。